ACM比赛划水记录

发表于2021-08-29更新于2021-10-20阅读次数

Test!Test! “ ” 比赛！比赛！

2021.8.28 ccpc网络赛

众所周知 2021年8.28没有CCPC网赛
只有CCPC“网络”选拔赛

涨姿势了

Power Sum HDU - 7105

点击查看思路 
  
    当时想到了平方差凑数，可惜差一步。不难发现，x方-(x+1)方-（x+2）方+（x+3）方=4；那么我们直接让n%4，接下来只要凑出0,1,2,3即可，0不用考虑，1的话就是1方，2的话就是4方-3方-2方-1方，3的话就是2方-1方。于是我们就可以凑出n了。注意到这里k最大为n+2，不过我们按照这个方法凑出来的刚好最大长度也是n+2。
    

！！！！！！！
注意下这里的输出，因为输出最多有1e6，用字符串输出会更快
printf输出指定长度字符串的方法是：printf(“%.*s\n”,l,ar);很离谱的是用这个输出 C++WA，G++AC。。。
字符串输出指定长度,除了用上面这种不太靠谱的方法,还有就是用string,对于string,可以直接加上一个字符串”1001”,比一个个push_back快一些.
还有就是对于分情况对数赋值，可以直接用个数组来弄，就像方向数组，比ifelse代码简介不少。
可以对比下两个代码，就知道代码量的区别了。
本弱鸡代码：


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
#include<stdio.h>
typedef long long ll;
const ll maxn=1e6+11;
char ar[maxn];
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        ll cnt=n/4;
        ll ys=n%4;
        ll tmp=0;
        if(ys==0){ ; }
        else if(ys==1){
            ar[tmp++]='1';
        }
        else if(ys==2){
            ar[tmp++]='0',ar[tmp++]='0',ar[tmp++]='0',ar[tmp++]='1';
        }
        else if(ys==3){
            ar[tmp++]='0',ar[tmp++]='1';
        }
        for(ll i=0;i<cnt;i++){
            ar[tmp++]='1',ar[tmp++]='0',ar[tmp++]='0',ar[tmp++]='1';
        }
        printf("%lld\n",tmp);
        printf("%.*s\n",tmp,ar);
    }
    return 0;
}




高质量代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
using namespace std;
int t, n;
const int ki[] = {0, 1, 4, 2};
const string ti[] = {"", "1", "0001", "01"};
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        string ans = ti[n % 4];
        int k = ki[n % 4];
        while (n >= 4) {
            ans += "1001";
            k += 4;
            n -= 4;
        }
        cout << k << endl << ans << endl;
    }
    return 0;
}



！！！！！！！

经典套路-好题

Command Sequence HDU - 7108
题意，给一个只含UDRL的长度为n<1e5的串，问有多少子串的U个数==D个数,R个数==L个数，(个数可以为0).

点击查看思路 
  
    又是一道子串的题目，前缀和就是为子串量身定制的吧。
    前缀和妙用，真的太妙了。感觉这道题可以延伸一下，但是现在在寝室，有人打游戏太吵了，静不下心来，延伸不了。。
    

在这里插入图片描述


！！！！！！！！！！！！！！！！！！！！！
原来map可以pair到value，牛啊，map
！！！！！！！！！！！！！！！！！！！！！

2021.8.29 混合组队赛

676 C Vasya and String
题意：给你一个长度为n<1e5的只含a，b的串，可以允许修改k个位置，问能得到最长的“一样串”的长度是多少。“一样串”即只含a或只含b的串。

点击查看思路 
  
    先讨论只含a的情况，尺取即可，b同理。

1469 B Red and Blue
题意：给你两个长度分别为n和m的整数列a和b，将a和b数列并成一个数列c，即c的长度为n+m，要求数列c中，对于a的每个数保持原先a的顺序，b同理。问c的最大前缀和。

点击查看思路 
  
    贪心，整数不用多说，对于a中的负数，只要后面有正数能使其和为正，则加上这个负数，无则不加。b同理。

巧用，看思路

988 C Equal Sums
题意：给你k<2e5个数列，每个数列长度为ni,数据保证ni的和<2e5，每个数的范围为−1e4 to 1e4。从中任意选择两个数列，两个数列必须减去有且仅有各自的一个数后，若两个数列的和相等，则输出这两个数列的序号ni，和减去的数。若不存在这样的两个数列，输出NO。结果多组情况输出一组即可，ni可以任意顺序输出。

点击查看思路 
  
    我一开始想复杂了，想着这就是不能有重复元素，我就先把每个数列去个重，然后再把他们都弄到一个数列里面，排个序看是否有重复元素。
    简单方法就是，判断有无重复元素，直接看a[i]是否等于1就可以了嘛，但这道题由于i最大为1e9，所以需要hash或者map，平常的map是map[i]=k，然后再拉个结构体数组存数列ni和x，


！！！！！！！！！！！！！
这里有个简单方法就是直接将i映射为pair,pair存的就是ni和x，举一反三我们以后也可以将i map到一个结构体
注意下这里的map的赋值操作：mp[sum]=make_pair(i,j);，结构体的话直接=号赋值就可以了。
！！！！！！！！！！！！！

总结

做了三个签到题，其余全靠队友带飞，数学大佬hly，图论大佬ly。这次比赛体验良好，跟队友配合的都挺好的。刚好我们看的题，都是自己擅长的(滑稽
还有代码能力有待加强，主要是细节错误挺多，写个尺取都要wa。。。

2021.9.5 线段树专题测试

有些题能模拟，但是纯模拟会很麻烦，细节很多，基本写不了，而且关键自己写着写着会把自己心态写炸。为避免这种模拟题写到一半发现写不了的尴尬情况，应该提前想好大致思路，确定能写在写。

2021.9.10 2021第十一届山东省大学生程序设计竞赛

比赛
咳咳，蒟蒻，全靠hly大佬带飞
过了5道，CDGHM 一队过了7道，剩下的两道有机会出的，说明运气好，把会做的都做了还是能拿金的。
F题字符串思路想到了，可惜没有码出来。
B题想复杂了，一看要算n*n个gcd，就以为是自己没学过的知识，不敢下笔了，以后不要怕！至少要分析一波，分析不出来就算了，不能分析都不分析就放弃。
因为这道题n很大的时候，是有特殊情况，可以直接输出的。。。

思维题可还行

C Cat Virus
题意：给定一棵树，黑白染色方案，满足一个黑点的子树都是黑点，白点任意。你现在构造一棵树，使得它的染色方案数为K(1<=k<=1e18)

点击查看思路 
  
思想：按hly的思路，首先是想到一条链，然后这条链长度为n，方案数就是n+1，但不过K太大，输出会超限。
然后想到以1为根节点，其下有n个**子树**，大佬的想法就是不一样，直接子树，统一处理。
然后这n个子树，每个子树的涂色方案为ai,那么整棵树的方案就为a1到an的乘积+1。
按照这个思路，我们一开始以1为根节点，剩余方案数为k-1，如果k-1%2==0，则在1下增加一个子节点，如果方案数ki%2仍==0，则继续在1下增加子节点，
当遇到奇数时，我们则想到一开始的k-1，所以我们就以这个子结点为根结点，开一个新树，递推即可。

DG签到题，H二维背包，表示不会。。

思维题有点意思

M Matrix Problem
题意：给定0/1矩阵C，n行m列，(n,m<500)构造两个矩阵A,B,要求A,B各自的1都互相连通，并且对于C中所有位置，若是1，则A,B对应位置必须都是1,否则，A为0则B为1，B为0则A为1。保证C阵的边框都是0。

点击查看思路 
  
思路：这种构造A，B矩阵输出的题，一般是按规律构造的，几乎不可能想着模拟去构造，太麻烦，比如本题。
注意到这个保证边框都是0没，可以从这里做文章，把A最左边一列是1，B最右边一列是1，然后行分奇偶全染成1。

最小生成树+GCD可还行

B Build Roads
题意：给定一个n<2e5个点的无向完全图，i和j之前的边权是gcd(ai,aj),数组ai范围在[l,r]<2e5,保证数组a随机,求MST。

点击查看思路 
  
思路：考虑素数分布， int 范围内两个素数之间的最大间距不到几百，（算了一下，是282，1e9范围内素数50847534个）而如果随出来的数组里有素数答案就是n-1
了，所以[l,r]或n范围很大时答案就是n-1,但注意如果[l,r]范围很大n很小，那么就得gcd(a1....an)乘(n-1)。范围很小的时候暴力一下就行了。还需要稍微注意一下l==r的情况。

2021.9.12 排位赛

又是爆0的一天呢

DFS BFS傻傻分不清

C Brexit
题意：给一个n<1e5个点，m<1e5条边的无向图，删去其中某个点，如果剩余的点中，删去的边数*2>=初始有的边数，则删去这个点，如此连环反应，问最终x点是否会被删去。

点击查看思路 
  
思路：一开始想着写dfs，因为dfs简单些，然后就dfs哇了n遍，改成bfs一遍过了。究其根本原因是dfs的搜索方式与这道题不符，所以这道题用dfs是出不了的。这道题很明显是得用bfs搜的。

Dijskra好题

E Charles in Charge
题意：1e5级别的图，求从a点到b点的所有不大于l的路中，每条路的最大边长的最小值。

点击查看思路 
  
思路：很明显直接dfs搜会超时，正确做法二分边长，对于二分的边长mid，将边长小于mid的边来建图。

2021 ICPC 网赛 第二场

L题思路想到了，可惜最后只有半个小时来码代码，加上不熟，不然能出😂

思维题

题意

点击查看思路 
  


思路：就正常的二进制按位加法，然后分类讨论下不同符号位对应的本位和进位情况。


  

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
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-27 19:05:00
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e2+11;
ll a[maxn],b[maxn],s[maxn],ans[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    for(ll i=1;i<=n;i++)  cin>>s[i];
    for(ll i=1;i<=n;i++)  cin>>a[i];
    for(ll i=1;i<=n;i++)  cin>>b[i];
    for(ll i=1;i<=n;i++){
        ll x=ans[i]+a[i]*s[i]+b[i]*s[i];
        if(s[i]==1){
            if(x==-1){
                ans[i+1]=-1;
                ans[i]=1;
            }
            else{
                ans[i+1]=x/2;
                ans[i]=x%2;
            }
        }
        else{
            if(x==1){
                ans[i+1]=1;
                ans[i]=1;
            }
            else{
                ans[i+1]=x/2;
                ans[i]=-1*x%2;
            }
        }
    }
    for(ll i=1;i<=n;i++){
        if(i==n)  cout<<ans[i];
        else  cout<<ans[i]<<" ";
    }
    return 0;
}

Segment Tree beats 维护一个数列

题意

这里对于100以内的25个质数的维护，可以状态压缩，即用一个int的一位二进制表示改质数是否存在。也就是再拉个线段树维护25个质数。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
#define Debug(x)  cout<<#x<<": "<<x<<endl;
#define lson l,m,now<<1
#define rson m+1,r,now<<1|1
typedef long long ll;
const ll maxn=1e5+11;
const ll mo=998244353;
ll t[maxn<<2],rr[maxn<<2],x[maxn],lazy[maxn<<2],ar[111];
ll tmp;
ll is(ll x){
    for(ll i=2;i*i<=x;i++)  if(x%i==0)  return 0;
    return 1;
}
void init(){
    tmp=0;
    for(ll i=2;i<=100;i++){
        if(is(i))  ar[tmp++]=i;
    }
}
ll fy(ll x){//计算x的欧拉值
    ll ans=x;
    for(ll i=0;i<25;i++){
        if(x%ar[i]==0){
            ans=ans*(ar[i]-1)/ar[i];
        }
    }
    return ans;
}
ll wei(ll x){
    ll ans=0;
    for(ll i=0;i<25;i++){
        if(x%ar[i]==0){
            ans=ans|(1<<i);
        }
    }
    return ans;
}
void push_up(ll now){
    t[now]=(t[now<<1]+t[now<<1|1])%mo;
    rr[now]=rr[now<<1]&rr[now<<1|1];
}
void push_down(ll l,ll r,ll now){
    if(lazy[now]>1){
        t[now<<1]=t[now<<1]*lazy[now]%mo;
        lazy[now<<1]=lazy[now<<1]*lazy[now]%mo;
        t[now<<1|1]=t[now<<1|1]*lazy[now]%mo;
        lazy[now<<1|1]=lazy[now<<1|1]*lazy[now]%mo;
        lazy[now]=1;
    }
}
void build(ll l,ll r,ll now){
    lazy[now]=1;
    if(l==r){
        t[now]=fy(x[l]);rr[now]=wei(x[l]);
        return ;
    }
    ll m=l+((r-l)>>1);
    build(lson);build(rson);
    push_up(now);
}
void update(ll L,ll R,ll w,ll val,ll l,ll r,ll now){
    if(L<=l && r<=R && (rr[now]&val)==val){
        t[now]=t[now]*w%mo;lazy[now]=lazy[now]*w%mo;
        return ;
    }
    if(l==r){
        t[now]=t[now]*w;
        for(ll i=0;i<25;i++){
            if(((rr[now]>>i)&1)==0 && ((val>>i)&1)==1){
                t[now]=t[now]*(ar[i]-1)/ar[i];
            }
        }
        t[now]=t[now]%mo;
        rr[now]=rr[now]|val;  
        return ;
    }
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    if(L<=m)  update(L,R,w,val,lson);
    if(R>m)  update(L,R,w,val,rson);
    push_up(now);
}
ll getsum(ll L,ll R,ll l,ll r,ll now){
    if(L<=l && r<=R)  return t[now];
    ll m=l+((r-l)>>1);
    push_down(l,r,now);
    ll sum=0;
    if(L<=m)  sum=getsum(L,R,lson)%mo;
    if(R>m)  sum=(sum+getsum(L,R,rson))%mo;
    return sum;
}
int main(){
    init();
    ll n,m;cin>>n>>m;
    for(ll i=1;i<=n;i++)  cin>>x[i];
    build(1,n,1);
    for(ll i=1;i<=m;i++){
        ll op,l,r,w;
        cin>>op;
        if(op==0){
            cin>>l>>r>>w;
            if(w==1)  continue;
            update(l,r,w,wei(w),1,n,1);
        }
        if(op==1){
            cin>>l>>r;
            cout<<getsum(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}

2021.9.26排位赛

J题最后10几min做出来了，而且是压着时限过的，真是刺激。

思维题(easy-medium)

Elegant Construction HDU - 5813;

题意：给一个有向图，n<1e3个点，接下来n个数表示与第i个点直接或间接相连的点的个数。

点击查看思路

模拟-思维(easy-medium)

https://acm.hdu.edu.cn/showproblem.php?pid=5818

解题思路挺多的：

1、标解：

2.启发式合并

合并的时候都是选择将小的栈合并到大的

3、指针前驱

转载

2021.10.17排位赛

C题题目老长了，定义了一堆变量，结果全是烟雾弹，真正有用的话就一句，晕晕
下次不要再被长题面吓到了

2021.10.18 排位赛 2020ICPC上海站

1.B题是个思维构造题，没想到

2.D题有两种做法

1.二分

可以二分时间，也可以二分路程。

2.分类讨论

不过这个分类讨论挺复杂的，惊讶于这么复杂的分类讨论，我们当时居然过了！！！
真的是十分Amazing，主要得益于当时分类讨论的思路清晰，看来只要思路清晰，啥题都能做出来
而且一道题目真的有多种解法，比如这道题。