Codeforces Round 940 (Div. 2) and CodeCraft-23
前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。
A题：题意：给出n个木棍，最多组成多少个多边形
Solution：统计各长度木棍的数量，全部贪心成三角形
1
2
3
4
5
6
7
8
9
| void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
map<int,int>mp;
for(int i=1;i<=n;i++)mp[a[i]]++;
int ans=0;
for(auto [x,y]:mp)ans+=y/3;
cout<<ans<<endl;
}
|
B:题意：给出n和k，要求把k拆成n个非负整数，希望最大化n个数的或和的二进制的1的数量
Solution:对于n=1进行特判，无法拆分。从一般情况考虑我们只需要找到k的最高的二进制的位的数tmp=(1<<__lg(k))-1,和k-tmp,剩下的数全部为0.考虑这种情况的代价是把最高位的1消耗去获得低位所有的1.
上述贪心显然存在反例就是舒适就是二进制全1的，那么我们考虑特判这类数即可。代码实现过程中直接对两种构造的答案取max，谁大就用谁的构造方案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int cal(int x){
int res=__builtin_popcount(x);
return res;
}
void solve(){
int k;cin>>n>>k;
if(n==1){
cout<<k<<endl;
return ;
}
int len=__lg(k);
int ans=cal(k);
int tmp=(1<<len)-1;
if(ans>=cal(tmp)){
cout<<k<<" ";
for(int i=1;i<=n-1;i++)cout<<0<<" ";
}
else {
cout<<tmp<<" "<<k-tmp<<" ";
for(int i=1;i<=n-2;i++)cout<<0<<" ";
}
cout<<endl;
}
|
C：题意：人和电脑在正方形网格图里下国际象棋。人每次放白车，人放（x,y)，电脑放黑车(y,x).如果人放对角线，电脑不回应，人继续先手。一个车所在一行一列不能出现第二个车。
现在棋盘大小，给出前k步棋谱，求最终局面有多少种局面
Solution:考虑给出递推的证明。首先注意到问题只和当前还有几行几列空闲有关，已经被占领的行无法对方案做出贡献。考虑现在填一个n行n列的空白棋盘。由于顺序与最终方案无关，所以根据任意性，我们假设考虑第一步就在第n行落子，也就是说第n行的落子可能是在第j步，当前钦定第一步放，就去除了重复局面 对计算造成的影响。
dp[n]=dp[n−1]+2∗(n−1)∗dp[n−2].含义是如果落子在第n行的对角线则问题划归到n-1规模，如果落子在第n行非对角线，则电脑对应位置落黑车，会减少两行两列，问题划归到n-2规模.考虑可以在第n列对称，方案数直接*2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int dp[N];
void solve(){
int k;
cin>>n>>k;
for(int i=1;i<=k;i++){
int x,y;cin>>x>>y;
if(x==y)n-=1;
else n-=2;
}
cout<<dp[n]<<endl;
}
|
D题意：(⨁x≤i≤zai)⊕ay>(⨁x≤i≤zai)，求满足条件的x，y，z有多少对，其中x<=y<=z
首先套路的，对于区间异或和提前预处理前缀异或和，考虑不等式成立条件，从ay的二进制最高位考虑，当对应区间异或和该位为0的时候不等式成立。为0的条件的区间异或和两个端点需要同时为1或者为0.
所以我们可以预处理拆位的前缀和，后缀和，每次统计的是1的数量，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
| onst int len=__lg((ull)2e9);
bitset<5>b;
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>s(n+1,0);
for(int i=1;i<=n;i++)s[i]=s[i-1]^a[i];
vector<vector<int>>pre(n+2,vector<int>(len+2,0));
vector<vector<int>>suf(n+2,vector<int>(len+2,0));
for(int i=1;i<=n;i++){
for(int j=len;j>=0;j--){
int u=(s[i]>>j)&1;
if(u==1)pre[i][j]=1;
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<=len;j++){
suf[i][j]=suf[i+1][j]+pre[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=len;j++){
pre[i][j]+=pre[i-1][j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
int u=__lg(a[i]);
int c1=pre[i-1][u];
int c2=suf[i][u];
ans+=c1*c2;
ans+=(max(i-c1,0LL))*(max(n-i+1-c2,0LL));
}
cout<<ans<<endl;
}
|
E:定义一种F运算，求i=1∑nj=1∑i(F(i,j)modj).给出F(i,j)的定义是从i个元素中选j个元素进行圆排列的方案数。显然F(i,j)=C(i,j)∗(j−1)!
Solution：我们需要进一步变形上面式子F(i,j)modj=ji(i−1)⋯(i−j+1)modj=((j−1)!×⌊ji⌋)modj
考虑对将组合数拆成阶乘，然后发现分子连续j项一定构成modj的剩余系，所以可以进一步化简成下取整形式。
- 考虑威尔逊定理，对于所有质数(j−1)!≡−1modj
- 对于所有大于4的合数，(j−1)!≡0modj
因此我们需要计算对于固定质数j，不同的i对其的贡献，这里就是交换了求和次序。
对于固定j，不同的i造成的贡献如何快速计算？
一般地，对于i从kp到k(p+1)-1，他们的贡献是相同的，我们希望这段i每个数都加上-k modj的贡献，静态区间加我们使用差分维护贡献。最后我们求一遍前缀和得到每个i的贡献，再求一遍得到前n个数的贡献，也就是答案了
我们还需要对4进行单独计算，作为特例。
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
| int minp[N];
int prime[N];
int cnt=0;
int ans[N];
int g[N];
void init(){
for (int i = 2; i < N; i++)minp[i] = i;
int cnt = 0;
for (int i = 2; i < N; i++) {
if (minp[i] == i) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] * i < N; j++) {
minp[prime[j] * i] = prime[j];
if (i % prime[j] == 0) break;
}
}
for(int i=0;i<cnt;i++){
int p=prime[i];
for(int j=p;j<=1000000;j+=p){
int u=-j/p;u=(u%p+p)%p;
g[j]+=u;g[j]%=mod;
if(j+p<N){g[j+p]-=u;g[j+p]+=mod;g[j+p]%=mod;}
}
}
int p=4;
for (int j=4;j<=1000000;j+=4){
int u=2*j/p;u%=p;
g[j]+=u;g[j]%=mod;
if(j+p<N){g[j+p]-=u;g[j+p]+=mod;g[j+p]%=mod;}
}
for(int i=1;i<=1000000;i++){
g[i]+=g[i-1];g[i]%=mod;
ans[i]=ans[i-1]+g[i];ans[i]%=mod;
}
}
|
