Codeforces Round #475 (Div. 1)

解题报告......

A. Alternating Sum

显然直接等比数列求和就好了,注意特判 \(q=1\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P=1e9+9;
char a[100005];
int n,K;
LL A,B,ans;
LL Pow(LL a,LL b,LL P){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int main(){
scanf("%d%lld%lld%d",&n,&A,&B,&K); B=B*Pow(A,P-2,P)%P;
scanf("%s",a);
for(int i=0;i<=K-1;i++){
LL t=(n-i)/K+1,a1=Pow(B,i,P),q=Pow(B,K,P);
if(q==1) (ans+=(a[i]=='+'?1:-1)*a1%P*t%P)%=P;
(ans+=(LL)(a[i]=='+'?1:-1)*a1%P*(Pow(q,t,P)-1)%P*Pow(q-1,P-2,P)%P)%=P;
}
ans=ans*Pow(A,n,P)%P;
printf("%lld\n",(ans+P)%P);
return 0;
}

B. Destruction of a Tree

可以发现叶子一定最后删,对于非叶节点,考虑非叶之间的边,若相邻非叶点被删,该点度数会减 \(1\)

若一个点的相邻叶节点数是奇数,他一定不能在删完相邻非叶节点之后删。

为了避免这种情况,考虑优先删相邻非叶节点最少的,即接近叶子的。

然后就过了。

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
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5+10;
vector<int>G[N];
int vis[N],rt=0;
void print(int x){
vis[x]=1;
printf("%d\n",x);
for(int i=0;i<G[x].size();i++){
int v=G[x][i];
if(!vis[v]) print(v);
}
}
void DFS(int u,int fa){
int d=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]) DFS(v,u);
}
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]) d++;
}
if(fa) d++;
if(d%2==0){
printf("%d\n",u);
vis[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!vis[v]) print(v);
}
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int fa;
scanf("%d",&fa);
if(!fa) rt=i;
else G[fa].push_back(i);
}
if((n&1)==0) printf("NO\n");
else{
printf("YES\n");
DFS(rt,0);
}
return 0;
}

C. Cutting Rectangle

我太菜了。可以发现,若有解,一定满足对于不同的 \(w\) ,其不同 \(h\) 的个数比,即

\(cnt(w,1):cnt(w,2):cnt(w,3)...\) 是相同的。

然后考虑,一种 \(w\) 可以拆到若干列,拆的列数一定是 \(gcd(cnt(w,1),cnt(w,2)...)\) 的约数。

一种 \(w\) 拆的列数确定了,其他 \(w\) 也就确定了,所以答案就是所有 \(cnt(w,h)\)\(gcd\) 的约数个数......

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double Ld;
const int maxn=400005;
struct data{ LL w,h,c; } a[maxn];
int n;
LL d,w[maxn],h[maxn];
vector<LL> cnt[maxn];
LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i].w,&a[i].h,&a[i].c);
w[++w[0]]=a[i].w; h[++h[0]]=a[i].h; d=gcd(d,a[i].c);
}
sort(w+1,w+1+w[0]); w[0]=unique(w+1,w+1+w[0])-w-1;
sort(h+1,h+1+h[0]); h[0]=unique(h+1,h+1+h[0])-h-1;
if(w[0]*h[0]!=n) return puts("0"), 0;
for(int i=1;i<=w[0];i++) cnt[i].resize(h[0]+5);
for(int i=1;i<=n;i++){
a[i].w=lower_bound(w+1,w+1+w[0],a[i].w)-w;
a[i].h=lower_bound(h+1,h+1+h[0],a[i].h)-h;
cnt[a[i].w][a[i].h]=a[i].c;
}
for(int i=1;i<=w[0]-1;i++){
for(int j=2;j<=h[0];j++){
Ld t1=(Ld)cnt[i][j]/cnt[i][j-1];
Ld t2=(Ld)cnt[i+1][j]/cnt[i+1][j-1];
if(fabs(t1-t2)>1e-8) return puts("0"), 0;
}
}
LL ans=0;
for(int i=1;(LL)i*i<=d;i++)
if(d%i==0){
ans++; if((LL)i*i!=d) ans++;
}
printf("%lld\n",ans);
return 0;
}

D. Frequency of String

直接上后缀树,转化成每次求一个子树中的 \(firstpos\) 集合最段的包含 \(k\)\(firstpos\) 的区间。

然后感觉一脸不可做......实际上,由于题目保证询问串不同,所以总询问 \(firstpos\) 个数是 \(n\sqrt 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
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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,maxe=maxn;
namespace SAM{
int N_sam,lst,ch[maxn][26],par[maxn],pos[maxn],Max[maxn];
int newnode(int t){ Max[++N_sam]=t; return N_sam; }
void Extend(int c,int id){
int p=lst, np=newnode(Max[lst]+1); pos[np]=id;
while(p&&!ch[p][c]) ch[p][c]=np, p=par[p];
if(!p) par[np]=1; else{
int q=ch[p][c];
if(Max[q]==Max[p]+1) par[np]=q; else{
int nq=newnode(Max[p]+1);
memcpy(ch[nq],ch[q],sizeof(ch[q]));
par[nq]=par[q]; par[q]=nq; par[np]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq, p=par[p];
}
}
lst=np;
}
};
int N_seg,sum[maxn*2*20],ch[maxn*2*20][2];
int Build(int L,int R){
int p=++N_seg;
if(L==R) return sum[p]=0, p;
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
return p;
}
void maintain(int p){
sum[p]=sum[ch[p][0]]+sum[ch[p][1]];
}
int Update(int pre,int L,int R,int pos){
int p=++N_seg; sum[p]=sum[pre]; ch[p][0]=ch[pre][0]; ch[p][1]=ch[pre][1];
if(L==R) return sum[p]++,p;
int mid=(L+R)>>1;
if(pos<=mid) ch[p][0]=Update(ch[pre][0],L,mid,pos);
else ch[p][1]=Update(ch[pre][1],mid+1,R,pos);
maintain(p); return p;
}
int v[maxn];
void Travel(int p1,int p2,int L,int R){
if(sum[p1]-sum[p2]==0) return;
if(L==R) return sum[p1]-sum[p2]?v[++v[0]]=L:0, void();
int mid=(L+R)>>1;
Travel(ch[p1][0],ch[p2][0],L,mid);
Travel(ch[p1][1],ch[p2][1],mid+1,R);
}
char s[maxn];
int K,m,Q;
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dfn[maxn],out[maxn],idfn[maxn],rt[maxn],Tim;
void dfs(int x){
dfn[x]=++Tim; idfn[Tim]=x;
for(int j=fir[x];j;j=nxt[j]) dfs(son[j]);
out[x]=Tim;
}
int main(){
scanf("%s",s+1); m=strlen(s+1);
SAM::lst=SAM::newnode(0);
for(int i=m;i>=1;i--) SAM::Extend(s[i]-'a',i);
for(int i=2;i<=SAM::N_sam;i++) add(SAM::par[i],i);
dfs(1); rt[0]=Build(1,m);
for(int i=1;i<=SAM::N_sam;i++){
rt[i]=rt[i-1];
if(SAM::pos[idfn[i]]) rt[i]=Update(rt[i-1],1,m,SAM::pos[idfn[i]]);
}
scanf("%d",&Q);
while(Q--){
scanf("%d%s",&K,s+1); int len=strlen(s+1);
int p=1; for(int i=len;i>=1;i--) p=SAM::ch[p][s[i]-'a'];
if(!p){ puts("-1"); continue; }
v[0]=0; Travel(rt[out[p]],rt[dfn[p]-1],1,m);
int res=1e9; if(v[0]<K){ puts("-1"); continue; }
for(int i=1;i<=v[0]-K+1;i++) res=min(res,v[i+K-1]-v[i]+len);
printf("%d\n",res);
}
return 0;
}

E. Circles of Waiting

可能是个套路...... 网格图这种高斯消元可以做到 \(n^2\)

就是编号的时候按顺序,具体看代码.....

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
#include<bits/stdc++.h>
using namespace std;
const int P=1000000007,N=55,Tr[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
typedef long long LL;
int R,id[N<<1][N<<1],tot,b[N*N<<2][2],A[7850][7850];
LL p[4],E[N*N<<2];
LL Pow(LL a,LL b){
LL res=1; a%=P;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
void Gauss(){
int m=0;
for(int i=1;i<=tot;i++){
m=max(m,id[b[i][0]][b[i][1]+1]);
for(int j=i+1;j<=m;j++){
LL t=P-Pow(A[i][i],P-2)*A[j][i]%P;
for(int k=i;k<=m;k++) (A[j][k]+=t*A[i][k]%P)%=P;
(A[j][tot+1]+=t*A[i][tot+1]%P)%=P;
}
}
}
int main(){
scanf("%d%d%d%d%d",&R,&p[0],&p[1],&p[2],&p[3]);
LL allp=Pow((p[0]+p[1]+p[2]+p[3])%P,P-2);
for(int t=0;t<=3;t++) p[t]=p[t]*allp%P;
for(int y=-R;y<=R;y++)
for(int x=-R;x<=R;x++)
if(x*x+y*y<=R*R) id[x+N][y+N]=++tot, b[tot][0]=x+N, b[tot][1]=y+N;
for(int i=1;i<=tot;i++){
int x=b[i][0],y=b[i][1];
A[i][i]=P-1; A[i][tot+1]=1;
for(int t=0;t<=3;t++)
if(id[x+Tr[t][0]][y+Tr[t][1]]) A[i][id[x+Tr[t][0]][y+Tr[t][1]]]=p[t];
}
Gauss();
E[tot+1]=1;
for(int i=tot;i>=1;i--){
for(int j=i+1;j<=tot+1;j++) (E[i]+=P-E[j]*A[i][j]%P)%=P;
E[i]=E[i]*Pow(A[i][i],P-2)%P;
}
printf("%lld",E[id[N][N]]);
return 0;
}