A.Intelligent Warehouse—素数筛+DP

题意：在一串序列中找出一组最长的数，他们两两互为倍数（数最多为 2e5 个，范围在 [1,1e7]）

思路：用 dp[i] 表示当前所选的所有数都是 i 的约束且符合题意的情况下能选的数的个数的最大值，那么最后答案就是这个数组中的最大值。 直观的转移是用当前 dp[i] 去更新 i 的所有倍数的 dp 值但是会 TLE。因为合数总可以被若干个素数的乘积凑数来，所以没必要枚举合数倍去更新，可以先用埃氏筛法打表然后枚举素数倍更新

比赛的时候一直想当前的 dp[i] 回头遍历前面能整除的数 dp 去更新，这样太暴力了转为有目的的向后递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7;

int p;
int a[maxn + 100], dp[maxn + 100], prime[maxn];
bitset<maxn + 100> is_prime; //用于标记数组

void sieve(){
    for(int i = 0; i <= maxn; ++i) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= maxn; ++i){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= maxn; j += i)
            is_prime[j] = 0;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    sieve();
    int n; cin >> n;
    for(int i = 1; i <= n; ++i){
        int x; cin >> x;
        a[x]++; //可能存在相同的数
    }
    int ans = -1;
    for(int i = 1; i <= maxn; ++i){
        dp[i] += a[i]; //自身也算自己的倍数
        ans = max(ans, dp[i]);
        for(int j = 0; j < p && i * prime[j] <= maxn; ++j){ //枚举素数倍递推更新其他的数
            dp[i * prime[j]] = max(dp[i * prime[j]], dp[i]);
        }
    }
    cout << ans << endl;
    //system("pause");
    return 0;
}

B. Smart Browser—签到+模拟

题意：一个 w 自身有一个 /\，同时还可以和相邻的其他 w 凑出 /\，例如 www 由 有 个 /\，ww 有 3 个 /\。给出一各含 w 的字符串求能凑出几个 /\（只能利用 w 凑）

思路：找出相邻的一串 w 的个数就处理一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int cal(int x){ //本身+相邻
    return x+(x-1);
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    string s;cin>>s;
    int len=s.length();
    int sum=0;
    for(int i=0;i<len;++i){
        if(s[i]=='w'){
            int j;
            for(j=i;j<len;++j)
                if(s[j]!='w')break;
            sum+=cal(j-i);
            i=j;
        }
    }
    cout<<sum<<endl;
    //system("pause");
    return 0;
}

I.Walking Machine—思维+BFS

题意：给出一个 n 行 m 列的棋盘，每个块都有一个箭头代表能走向另一个相邻块的位置（对应键盘的 WASD），找出有多少个块可以走出这个棋盘

样例解析

思路：想走出棋盘无疑必须能走到边界的能出去的块，所以我们从边界能出去的块分别反向 BFS，遍历到的块的总个数就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上，下，左，右

int n,m,ans;
char chest[1005][1005];
bool vis[1005][1005];

struct node{
    int x,y; //记录处于第几行第几列
    node(int a,int b):x(a),y(b){}
};

bool judge(node p,int i){
    if(p.x<1||p.x>n||p.y<1||p.y>m)return 0; //越界不走了
    if(vis[p.x][p.y]==1)return 0; //访问过也不走
    if(i==0&&chest[p.x][p.y]=='S')return 1;
    if(i==1&&chest[p.x][p.y]=='W')return 1;
    if(i==2&&chest[p.x][p.y]=='D')return 1;
    if(i==3&&chest[p.x][p.y]=='A')return 1;
    return 0;
}

void bfs(node s){
    vis[s.x][s.y]=1;
    queue<node> que;
    que.push(s);
    while(!que.empty()){
        node now=que.front();
        que.pop();
        for(int i=0;i<4;i++){
            node nex=now;
            nex.x=now.x+dir[i][0],nex.y=now.y+dir[i][1];
            if(judge(nex,i)){ //判断找的点能不能走向它
                ++ans;
                vis[nex.x][nex.y]=1;
                que.push(nex);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin>>chest[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i==1&&chest[i][j]=='W')
                bfs(node(i,j)),++ans;            
            if(j==1&&chest[i][j]=='A')
                bfs(node(i,j)),++ans;           
            if(i==n&&chest[i][j]=='S')
                bfs(node(i,j)),++ans;       
            if(j==m&&chest[i][j]=='D')
                bfs(node(i,j)),++ans;
        }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}

J. Matrix Subtraction—二维差分

题意：给定 n*m 矩阵，可以多次对矩阵中 a*b 的小矩阵全部元素 -1，求是否可以全减为 0

思路：找规律可以发现必定是从左上角的第一个点开始用 a*b 的矩阵来消，直接暴力修改肯定 TLE。套个二维差分的模板成功 AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;

int mat[maxn][maxn], ret[maxn][maxn]; //原矩阵和矩阵的差分

void change(int x, int y, int k, int a, int b){ //(x,y)为左上角长a,宽为b的矩阵值+=k
    int dx = x + a, dy = y + b;
    ret[x][y] += k;
    ret[dx][y] -= k;
    ret[x][dy] -= k;
    ret[dx][dy] += k;
}

void solve(){
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    memset(ret, 0, sizeof ret);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> mat[i][j];
            change(i, j, mat[i][j], 1, 1); //存入相当于一次修改
        }
    }
    //从左上角开始尝试将每一个点修改为0
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(ret[i][j] == 0) continue; //不用修改
            if(ret[i][j] < 0){ //为了使之前的点为0导致这个点变为了负数，说明实现不了
                puts("QAQ");
                return ;
            }
            if(ret[i][j] > 0) { //需要进一步把点修改为0
                if(i + a - 1 > n || j + b - 1 > m){ //不能用a*b矩阵修改了说明也实现不了
                    puts("QAQ");
                    return ;
                }
                else{ //可以用a*b修改
                    change(i, j, -ret[i][j], a, b);
                }
            }
        }
    }
    puts("^_^");
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t; cin >> t;
    while(t--){
        solve();
    }
    //system("pause");
    return 0;
}