最近几场比赛补题

ACM

不轻易言弃

校赛

过了五题，有的题目还是需要仔细思考一下的。

E题

三进制dp.用一个数组维护余数前缀的所有后缀的种类的个数，这种思想很是巧妙。

+1操作很明显 当转移到达的状态（i）的后缀和j 和 处理好的串的元素（b[i]）相同时，单独一个b[i]也能产生一个后缀和j

对后缀进行划分（自动机dp的常见做法） dp[i][j]: 访问到第i号元素 后缀和必定为j 的 区间[1,i]子串 的取法总数

第二个思想相当的厉害。

F题

pq维护，我维护的是后面的出现的次数，每一次弹出最小的出现的次数。不用维护前面的，因为在pq中肯定不会用到它们

G

网络赛的升级版
队友是打表找规律做出来的。
先贴一个数据规模是100的代码

弱化版

弱化版

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
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
struct Node{
    int x, y;
    int step;
};
int n;
const int INF = 1e9;
//int bfs(){
//    Node s;
//    s.x = s.y = 1;
//    s.step = 0;
//    queue<Node> q;
//    while(!q.empty()) q.pop();
//    q.push(s);
//    while(true){
//        Node temp = q.front();
//        q.pop();
//        if(temp.y == n) {
//            return temp.step;
//        }
//        else{
//            Node temp1 = temp;
//            Node temp2 = temp;
//            temp1.y = temp1.x+temp1.y;
//            temp2.x = temp2.y;
//            temp2.y = 2*temp2.y;
//            temp1.step = temp2.step = temp.step+1;
//            q.push(temp1);
//            q.push(temp2);
//        }
//    }
//    return -1;
//}
const int maxn = 105;
int ans[maxn][maxn];
void dfs(int x, int y){
    //cout<<x<<" "<<y<<endl;
    int tempx = x;
    int tempy = x+y;
    if(tempy<=100){
        if(ans[tempx][tempy]>ans[x][y]+1) ans[tempx][tempy] = ans[x][y]+1;
        dfs(tempx, tempy);
    }
    tempx = y;
    tempy = 2*y;
    if(tempy<=100){
        if(ans[tempx][tempy]>ans[x][y]+1) ans[tempx][tempy] = ans[x][y]+1;
        dfs(tempx, tempy);
    }
    return ;
}
int main()
{
    int t;
    cin>>t;
    for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++) ans[i][j] = INF;
    ans[1][1] = 0;
    dfs(1, 1);
    while(t--){
        cin>>n;
        int ans1 = INF;
        for(int i=0; i<maxn; i++){
            ans1 = min(ans1, ans[i][n]);
        }
        printf("%d\n", ans1);
    }
    return 0;
}

强化版

强化版

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 12;
const int MOD = 1e9 + 7;
int n, m, f, t;
int data[maxn];
int prime[maxn];
void getprime()
{
    memset(prime, 0, sizeof(prime));
    for(int i = 2; i < maxn; i ++)
    {
        if(! prime[i])prime[++ prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= (maxn - 1) / i; j ++)
        {
            prime[prime[j] * i] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}
int main()
{
    getprime();
    data[1] = 0;
    for(int i = 2; i <= 1000000; i ++)
    {
        bool isok = false;
        f = lower_bound(prime + 1, prime + 1 + prime[0], i) - prime - 1;
        if(i == prime[f + 1])
        {
            data[i] = i - 1;
            continue;
        }
        int j = 1;
        for(int k = 1; k <= prime[0]; k ++)
            if(i % prime[k] == 0)
            {
                j = i / prime[k];
                break;
            }
        {
            data[i] = data[j] + i / j - 1;
        }
    }
    scanf("%d", &n);
    while(n --)
    {
        scanf("%d", &f);
        printf("%d\n", data[f]);
    }
    return 0;
}

然后就会发现，答案是n分解质因数之后，所有的(质数-1)的和。
然后啊，我就傻了吧唧的在外面的txt文本中打了409kb的表，发现交不上去。。。
看了队友的代码，发现自己的打表方式并不正确。

选拔第一场

A题

图论签到题，我签了90min，严重导致士气下降。只用判断图中有没有环就行了。最后才想起来用scc…

B

大霸一发ac，并不知道

G思维题

整队都卡了这一道题，看来平时的脑洞还是太少了。

题意

取数组中连续的一段数字，使得它们的和模一个数m的值为0.

题解

维护前缀的模值，当两个前缀的模值相等的时候，去掉中间的部分，不影响原来的模值。（即中间的和模值为0）

T了的代码

我不知道为什么一直T，这明明是O(n)的时间复杂度啊。

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;
const int maxn = 1e5+10;
const int maxm = 1e4+10;
int n, m;
int num[maxn];
struct Node{
    int l, r;
}node[maxm];
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0; i<n; i++){
            scanf("%d", &num[i]);
            int time = num[i]/m;
            if(time<=0){
                num[i] = m*(-1*time+1)+num[i];
            }
            else {
                num[i] = num[i] - time*m;
            }
        }
        for(int i=0; i<maxm; i++){
            node[i].l = node[i].r = -1;
        }
        for(int i=0; i<n; i++){
            if(node[num[i]].l!=-1) {
                node[num[i]].r = i;
            }
            else{
                node[i].l = node[i].r = i;
            }
        }
        int ans = 0;
        for(int i=0; i<maxm; i++){
            ans = max(ans, node[i].r-node[i].l);
        }
        printf("%d\n", ans);
    }
    return 0;
}

J

kmp,要理解next[]的含义。因为是真后缀，前缀和后缀完全相同，在字符串的最后面加一个特殊字符。
然后用kmp的next[]压入一个set中，并且查询，若set中存在，那么前缀也在中间存在过。
时间复杂度O(n+m).
我觉得得补补字符串的坑，此时不填，更待何时！！！！

选拔第二场（模拟专场）

大霸想出来的用pq维护的感觉很巧妙。
然后就是一个fibonacii基的东西，感觉很巧妙，居然是数位dp…我们找了一个半小时规律，感觉还差最后一点点

大霸过的那一道题

先是排序，然后选前面能凑成的数字。前\(1~a_i\)一定可以凑成\(1~sum[i]\), sum[i]为前缀和，想想确实是这样。1,可以凑成，2也可以凑成，3也可以。。。递推着证明

J

删掉一些边分成若干个节点相同的连通图
讲解的博客
再贴一道类似的题目
cf 964里面的D题

未解决的问题

本文标题:最近几场比赛补题

文章作者:Babydragon

发布时间:2018-04-27, 16:33:43

最后更新:2018-04-29, 18:21:13

原始链接:http://baolintian.github.io/2018/04/27/最近几场比赛补题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 校赛
    1. 1.1. E题
    2. 1.2. F题
    3. 1.3. G
      1. 1.3.1. 弱化版
      2. 1.3.2. 强化版
  2. 2. 选拔第一场
    1. 2.1. A题
    2. 2.2. B
    3. 2.3. G思维题
      1. 2.3.0.1. 题意
      2. 2.3.0.2. 题解
      3. 2.3.0.3. T了的代码
  3. 2.4. J
  • 3. 选拔第二场（模拟专场）
    1. 3.1. 大霸过的那一道题
    2. 3.2. J
  • 4. 未解决的问题
    • {{ live2d() }}