23 移动应用开发

简答题 5x8：

  1. 四大组件
  2. Activity 生命周期
  3. handler
  4. activity 启动方式显式/隐式
  5. Android 存储方式：ContentProvider SharedPreferce

代码补全：

  1. 最基础的 Activity
  2. handler 处理信息流程
  3. 根据 xml 文件画图: ConstraintLayout 布局 梅花布局

代码题：

  1. 登录界面
  2. 打印质数界面

23 人工智能基础

不全，考完都给忘了

  1. 20 分选择题
  2. A* AO*区别
  3. dfs bfs 在 open 表排序时的区别
  4. 根据博弈树极大极小过程写出各节点值
  5. 语义网络 篮球赛+每个人都喜欢奥里给
  6. 证据推理作业题
  7. cf
  8. 好像没有贝叶斯
  9. 谓词表示
  10. 子句集+证明逻辑结论
  11. 决策树根据 ida 选根节点
  12. 祖传八数码

23 计算机取证

  1. 刑法
  2. 职业道德
  3. FAT 引导扇区
  4. FAT 目录项
  5. 邮件头
  6. 浏览器取证
  7. MFT
  8. 内存取证 局限 风险 攻击

22 密码学

考的很简单，目测比 19 级简单的多，更偏向于 18 级的题目难度。而且没有考第二章信息熵和第八章数字签名的内容。

简答题 30 分

  1. 画 Feistel 网络结构
  2. md5 填充
  3. 求密钥空间
  4. 数游程个数
  5. AES 子密钥总比特数 密钥生成方法
  6. DES s 盒代换

分析题 30 分

  1. 仿射密码解密
  2. GF 域乘法 0xC1*0x02
  3. RSA 求 d 解密求明文

论述题 20 分

  1. DES 证明题 画 CBC 解密结构图
  2. lfsr 给生成多项式 求 f 画寄存器 求输出序列、周期

综合题 20 分

给了 Elgamal 算法的加解密公式。

  1. 公钥、私钥分别是什么
  2. 正确性验证
  3. 加解密计算

22 网络攻防

选择 15

课后题原题

简答题 25

  1. 安全策略 意义
  2. 安全服务
  3. 黑客攻击流程
  4. 反射 xss
  5. FIN 扫描

论述题 30

  1. TCP 劫持 防御
  2. 挑战响应机制
  3. 缓冲区 溢出 防御

代码分析 20

<?php
    $username = $_GET['username'];
    echo $username;
    mysqli_query("select * from user where username = '$username'")
  1. 存在漏洞 原理
  2. 防御

22 算法设计与分析

总的来说，感觉这次比较简单，应该是疫情上网课的原因，算的数据也比较小，虽然最后延长了 15 分钟，但好好复习应该都可以做完

综合题 40

矩阵连乘 10

5x5 矩阵，挺好算的

  1. 求 m[1][5]
  2. 最少乘法次数
  3. 最优解

流水作业调度变形 10

只是把作业换成切菜和炒菜了

  1. 安排顺序
  2. 时间

dj 最短路径 10

没什么好说的，就是给了个图，求到各点的最短路径

最小生成树 10

6 节点 10 个边

  1. kruskal 求最小生成树

  2. 比较 prim 算法和 krusal 哪个更适合

第二问就是比较时间复杂度，一个是 O(nm)另一个是 O(mlog(m))比大小就行

算法分析

时间复杂度 15

  1. 求时间复杂度
  2. 比较二分、归并、上面算法的上界

也是比较好算，第二问别记错就行 log(n) nlog(n) $n^2$

01 背包变形 15

p=[48 49 40 45]
v=[8 7 10 9]
m=100
  1. 回溯法
  2. 优先级队列分支限界

算法设计

称重 15

255 个鹅蛋，1 个鸭蛋，混一块，给个天平，设计算法称出鸭蛋

  1. 实际不高于 log(n)复杂度算法
  2. 100 个蛋，最多称多少次，找到鸭蛋
  3. 设计一个更快的算法

和课件称金块的很像，第一问二分放天平两边，第二问 6 个，第三问三分四分

积木堆 15

n 堆积木，每次合并 2 堆，合并(n-1)次，求最小合并代价。代价：合并的两个积木堆积木数量和

  1. 设计算法
  2. 给一组数据，求合并策略
  3. 只能合并挨着的两堆，设计 dp 算法，求最小代价

一二问贪心，贪心策略：每次合并，最少的两堆优先

第二问，类似哈夫曼树的求解过程

第三问区间 dp，就是石子合并

设有 N 堆沙子排成一排，其编号为 1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将 N 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 4 堆沙子分别为 1 3 5 2 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2 又合并 1，2 堆，代价为 9，得到 9 2，再合并得到 11，总代价为 4+9+11=24，如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

// 状态转移方程
// dp[i][j]表示[i,j]区间合并最小代价
// dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1])
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],s[N],dp[N][N];
int main(){
    int n,t;
    cin>>n;
    for(int i=1;i<=n;i++){ // 1开始
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=0x3fffffff; //初始化
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    system("pause");
    return 0;
}

22 算法设计实验

一共 5 道题，都是原题，2 道英文题是算法课的作业题，以为不会考，结果考了，勉强做了 4 个，最后一个忘了转移方程了，想写个暴力的解法，结果没写完。整体就是 dp+贪心+dp+模拟+hash，还是很简单的。

最长公共子序列

两个签到题之一

题目描述

一个字符串 A 的子串被定义成从 A 中顺次选出若干个字符构成的串。如 A=“cdaad” ,顺次选 1，3，5 个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。

输入

第一行两个字符串用空格分开。两个串的长度均小于 2000 。

输出

最长子串的长度。

样例输入

abccd aecd

样例输出

3

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
char a[N],b[N];
int dp[N][N];
int main(){
    cin>>a+1>>b+1;
    int l1=strlen(a+1);
    int l2=strlen(b+1);
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[l1][l2];
    return 0;
}

跳跃游戏 2

另一个签到题，简单的贪心，这两题做了就能及格了

题目描述

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标，并且使用最少的跳跃次数。例如：A = [2,3,1,1,4]，到达最后一个下标的最少跳跃次数为 2。（先跳跃 11 步，从下标 0 到 1，然后跳跃 3 步，到达最后一个下标。一共两次）

输入

第一行输入一个正整数 n(1≤n≤100)，接下来的一行，输入 n 个整数，表示数组 A。

输出

最后输出最少的跳跃次数。

样例输入

5
3 1 1 1 1

样例输出

2

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0,m=0,end=0;
    for(int i=0;i<n-1;i++){
        if(m>=i){
            m=max(m,i+a[i]);
            if(i==end){
                end=m;
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

Rock-Paper-Scissors Tournament

一个模拟的英文题，看着比较唬人，其实就是剪刀石头布

题目描述

Rock-Paper-Scissors is game for two players, A and B, who each choose, independently of the other, one of rock, paper, or scissors. A player chosing paper wins over a player chosing rock; a player chosing scissors wins over a player chosing paper; a player chosing rock wins over a player chosing scissors. A player chosing the same thing as the other player neither wins nor loses.
A tournament has been organized in which each of n players plays k rock-scissors-paper games with each of the other players - kn(n-1)/2 games in total. Your job is to compute the win average for each player, defined as w / (w + l) where w is the number of games won, and l is the number of games lost, by the player.

输入

Input consists of several test cases. The first line of input for each case contains 1 <= n <= 100 1 <= k <= 100 as defined above. For each game, a line follows containing p1, m1, p2, m2. 1 <= p1 <= n and 1 <= p2 <= n are distinct integers identifying two players; m1 and m2 are their respective moves (“rock”, “scissors”, or “paper”). A line containing 0 follows the last test case.

输出

Output one line each for player 1, player 2, and so on, through player n, giving the player’s win average rounded to three decimal places. If the win average is undefined, output “-“. Output an empty line between cases.

样例输入

2 4
1 rock 2 paper
1 scissors 2 paper
1 rock 2 rock
2 rock 1 scissors
2 1
1 rock 2 paper
0

样例输出

0.333
0.667

0.000
1.000

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int win[N],loss[N];
int main(){
    int n,k;
    while(cin>>n){
        if(n==0) break;
        cin>>k;
        memset(win,0,sizeof(win));
        memset(loss,0,sizeof(loss));
        int t1,t2;
        string s1,s2;
        int m=k*n*(n-1)/2;
        for(int i=0;i<m;i++){
            cin>>t1>>s1>>t2>>s2;
            if(s1[0]=='r'&&s2[0]=='s'||s1[0]=='s'&&s2[0]=='p'||s1[0]=='p'&&s2[0]=='r'){
                win[t1]++;
                loss[t2]++;
            }else if(s1[0]=='s'&&s2[0]=='r'||s1[0]=='p'&&s2[0]=='s'||s1[0]=='r'&&s2[0]=='p'){
                win[t2]++;
                loss[t1]++;
            }
        }
        for(int i=1;i<=n;i++){
            if(win[i]==0&&loss[i]==0) cout<<"-\n";
            else{
                double t=1.0*win[i]/double(win[i]+loss[i]);
                printf("%.3f\n",t);
            }
        }
        cout<<endl;
    }
    return 0;
}

Brackets Sequence（括号序列）

没做出来的一个题，整个年级就一个人做出来了（汗），经典的区间 dp

题目描述

Let us define a regular brackets sequence in the following way:

  1. Empty sequence is a regular sequence.
  2. If S is a regular sequence, then (S) and [S] are both regular sequences.
  3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters ‘(‘, ‘)’, ‘[‘, and ‘]’ is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 … an is called a subsequence of the string b1 b2 … bm, if there exist such indices 1 = i1 < i2 < … < in = m, that aj = bij for all 1 <= j< = n.

输入

The input file contains at most 100 brackets (characters ‘(‘, ‘)’, ‘[‘ and ‘]’) that are situated on a single line without any other characters among them.

输出

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

样例输入

([(]

样例输出

([(]

代码

// dp[i][j] 从i到j需要添加括号的个数
// dp[i][j]=dp[i+1][j-1] match(i,j)
// dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 256;
char br[MAXN];
int dp[MAXN][MAXN], pos[MAXN][MAXN];
int len;
void print_br(int i, int j)
{
    if (i > j)
        return;
    if (i == j)
    {
        if (br[i] == '(' || br[j] == ')')
            printf("()");
        else
            printf("[]");
    }
    else if (pos[i][j] == -1)
    {
        printf("%c", br[i]);
        print_br(i + 1, j - 1);
        printf("%c", br[j]);
    }
    else
    {
        print_br(i, pos[i][j]);
        print_br(pos[i][j] + 1, j);
    }
}
bool match(int i, int j)
{
    if (br[i] == '(' && br[j] == ')')
        return true;
    if (br[i] == '[' && br[j] == ']')
        return true;
    return false;
}
int main()
{
    int i, j, k, mid, t;
    while (gets(br) != NULL)
    {
        memset(dp, 0, sizeof(dp));
        len = strlen(br);
        for (i = 0; i < len; i++)
        {
            dp[i][i] = 1;
        }
        for (k = 1; k < len; k++)
        {
            for (i = 0; i + k < len; i++)
            {
                j = i + k;
                dp[i][j] = 0x7fffffff;
                if (match(i, j))
                {
                    dp[i][j] = dp[i + 1][j - 1];
                    pos[i][j] = -1;
                }
                for (k = i; k < j; k++)
                {
                    if (dp[i][j] > (t = dp[i][k] + dp[k + 1][j]))
                    {
                        dp[i][j] = t;
                        pos[i][j] = k;
                    }
                }
            }
        }
        print_br(0, len - 1);
        printf("\n");
    }
}

sort2

应该叫基数排序吧，我感觉，其实我也不知道

题目描述

给你 n 个整数，请按从大到小的顺序输出其中前 m 大的数。

输入

每组测试数据有两行，第一行有两个数 n,m(0<n,m<1000000)，第二行包含 n 个都处于区间[-500000,500000]的整数，整数可能会重复出现。

输出

对每组测试数据按从大到小的顺序输出前 m 大的数。

样例输入

10 5
1 2 3 4 5 6 7 7 8 9

样例输出

9 8 7 7 6

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int a[N];
int main(){
    int n,m,t;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>t;
        a[t+500000]++;
    }
    int ans=0;
    for(int i=1000000;i>=0;i--){
        if(ans==m) break;
        while(a[i]!=0){
            cout<<i-500000<<' ';
            ans++;
            a[i]--;
            if(ans==m) break;
        }
    }
    return 0;
}