2017CCPC杭州站部分题解

作为新的队伍训练赛,整体成绩还算满意。总结下来:算法竞赛不需要证明。(真诚.jpg)

A.Super-palindrome

签到题,能够看出奇数位必定相同,偶数位必定相同。分情况讨论即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000000+10;
char s[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s+1);
int len=strlen(s+1);
map<char,int>mp1,mp2;
int res=0;
int sum=0;
for(int i=1;i<=len;i+=2){
mp1[s[i]]++;
sum=max(sum,mp1[s[i]]);
}
res+=(len+1)/2-sum;
sum=0;
for(int i=2;i<=len;i+=2){
mp2[s[i]]++;
sum=max(sum,mp2[s[i]]);
}
res+=len/2-sum;
printf("%d\n",res);
}
return 0;
}

B.Master pf Phi

题目大意为:求$\sum_{d|n}\phi(d)*\frac{n}{d}$ ,$\phi(n)$ 为欧拉函数。

盲猜出的结论为$n*\prod_{i=1}^{m}\frac{q_i*\phi(p_i)+1}{p_i}$ ,具体推到百度一下,你就知道

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000000+10;
char s[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s+1);
int len=strlen(s+1);
map<char,int>mp1,mp2;
int res=0;
int sum=0;
for(int i=1;i<=len;i+=2){
mp1[s[i]]++;
sum=max(sum,mp1[s[i]]);
}
res+=(len+1)/2-sum;
sum=0;
for(int i=2;i<=len;i+=2){
mp2[s[i]]++;
sum=max(sum,mp2[s[i]]);
}
res+=len/2-sum;
printf("%d\n",res);
}
return 0;
}

C.Hakase and Nano

煜神推出来的题目,吹爆人赢!!!

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
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n,d;
cin>>n>>d;
int x;
// 计算1的个数
int num=0;
for(int i=0;i<n;i++)
{
cin>>x;
if(x>1)
num++;
}
// H先手
if(d==1)
{
// 全是1
if(!num)
{
if(n%3==0)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
else
cout<<"Yes"<<endl;
}
else
{
// 全是1
if(!num)
{
if(n%3==1)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
else
{
if((n%3==0&&num==1)||(n%3==1&&num==1))
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
}
return 0;
}

D.Master of Random

题目大意为:0节点为带权根节点,接下来1~n-1号带权节点都会随机选一个比他自身小的节点作为父节点,问从随机生成的树中挑一棵子树的大小的期望。

这个题目其实也是在纸上猜出来的结论。结论很复杂,对于每一个节点,我们只需要计算它被选中的概率即可。0号节点几率必定为$\frac{1}{n}=\frac{(n-1)!}{n!}$,接下来每个节点被选中的概率为:
$$
p_i=\frac{(n-1)!+\sum_{j=1}^{j=i}\frac{(n-1)!}{j}}{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
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=300000+10;
const int INF=0x3f3f3f3f;
const ll mod=998244353;
ll fac[maxn];
ll inv[maxn];
ll a[maxn];
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void init(){
fac[0]=1;
for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod;
// printf("ok\n");
for(int i=1;i<maxn;i++) inv[i]=qp(i,mod-2);
// printf("ok\n");
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
ll cur=fac[n-1];
ll res=a[0]*cur%mod;
for(int i=1;i<n;i++){
cur=(cur+fac[n-1]*inv[i]%mod)%mod;
res=(res+a[i]*cur)%mod;
}
res=res*qp(fac[n],mod-2)%mod;
printf("%lld\n",res);
}
return 0;
}

E.Master of Subgraph

F.Hearthrock

H.Marriage

I.Master of Connected Component

J.Master of Matrix

I.Master of GCD

题目大意为:初始化一个长度为$n$的全$1$数组,经过m次操作,每次操作将区间$[l,r]$内的数乘以$2$或$3$,问最终所有的数的GCD为多少。

也是签到题,对$2$,$3$分别差分即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000000+10;
const int INF=0x3f3f3f3f;
const ll mod=998244353;
int a[maxn],b[maxn];
int num1[maxn],num2[maxn];
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
int t,x,l,r,m,n;
scanf("%d",&t);
while(t--){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&l,&r,&x);
if(x==2){
a[l]++;
a[r+1]--;
}
else{
b[l]++;
b[r+1]--;
}
}
int cur2=INF,cur3=INF;
int sum2=0,sum3=0;
for(int i=1;i<=n;i++){
sum2+=a[i]; cur2=min(cur2,sum2);
sum3+=b[i]; cur3=min(cur3,sum3);
}
printf("%lld\n",qp(2,cur2)*qp(3,cur3)%mod);
}
return 0;
}

J.Master of Sequence

K.Mod,Xor,and Everything

感谢您的支持
-------------本文结束感谢您的阅读-------------