| Solved | A | B | C | D | E |
|---|---|---|---|---|---|
| 5/5 | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给定一个$n$个节点的树和$m$个简单路，求有多少个选择$k$个给定简单路并使得这$k$个简单路交于同一点的方案。答案对$1e9+7$取模。
解题思路
先用树上差分求出每个点经过的简单路个数$path[i]$，再用$C(path[i],k)$求出该点的贡献，但显然会有重复。显然，所有路径的交点至少为一个$LCA$，故只需记录每一个点作为$LCA$做出的贡献即可。记录每一个点作为$LCA$的个数$num[i]$，则答案为$\sum_{i=1}^{n}C(path[i],k)-C(path[i]-num[i],k)$。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
int e,n;
}e[N<<1];
int d[N],fa[N][22],lg[N],hd[N],cnt,n,m,k;
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
void dfs(int now,int f){
d[now]=d[f]+1;
fa[now][0]=f;
int i;
for(i=1;(1<<i)<=d[now];i++)fa[now][i]=fa[fa[now][i-1]][i-1];
for(i=hd[now];i;i=e[i].n){
int p=e[i].e;
if(p!=f)dfs(p,now);
}
}
int lca(int x,int y){
int i;
if(d[x]<d[y]){int t=x;x=y;y=t;}
while(d[x]>d[y])x=fa[x][lg[d[x]-d[y]]];
if(x==y)return x;
for(i=lg[d[x]];~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int path[N],num[N];
void init(int now,int f){
int i,q;
for(i=hd[now];i;i=e[i].n){
q=e[i].e;
if(q!=f){
init(q,now);
path[now]+=path[q];
}
}
}
ll jc[N]={1},inv[N]={1},w=1000000007;
ll c(int n,int m){
if(n<m)return 0;
return jc[n]*inv[m]%w*inv[n-m]%w;
}
ll qpow(ll a,ll b){
int i;
ll ans=1;
for(i=b;i;i>>=1,a=a*a%w)if(i&1)ans=ans*a%w;
return ans;
}
int main(){
int i,t,u,v;
for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
for(i=1;i<N;i++)jc[i]=jc[i-1]*i%w,inv[i]=qpow(jc[i],w-2);
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(1,0);
for(i=0;i<m;i++){
scanf("%d%d",&u,&v);
int w=lca(u,v);
path[w]--;path[fa[w][0]]--;
path[u]++;path[v]++;
num[w]++;
}
init(1,0);
ll ans=0;
for(i=1;i<=n;i++)
ans=((ans+c(path[i],k)-c(path[i]-num[i],k))%w+w)%w;
printf("%lld\n",ans);
memset(hd,0,sizeof(int)*(n+1));cnt=0;
memset(d,0,sizeof(int)*(n+1));
memset(path,0,sizeof(int)*(n+1));
memset(num,0,sizeof(int)*(n+1));
memset(fa,0,sizeof(int)*(n+1)*22);
}
return 0;
}
B
题目描述
有$n$个战斗回合，$boss$无限血量，初始状态战斗力$A=0$，预备增量$D=0$。
每一个回合有三个参数$a[i],b[i],c[i]$可以任选下面三种策略之一：
- 攻击，伤害为$A+a[i]$
- 不攻击，$A+=b[i]$
- 不攻击，$D+=c[i]$
每回合结束之后，$A+=D$。
求$n$回合后的最大伤害。所有数在$[1,1e9]$范围内。
解题思路
开始想了半天如何$DP$，死活无法推出式子。
后来经nikkukun同学的提点，发现可以从后到前递推。原因是：
操作具有后效性但不具有前效性。
故考虑用$f[i][j]$表示到第$i$个人，已经干了$j$架的最大伤害。
推一下状态转移方程：
$f[i][j]=max(f[i+1][j]+max(x\times b[i],j\times c[i]),f[i+1][j-1]+a[i])$
前半部分表示选择不攻击的两种方法对答案的贡献，后半部分表示选择攻击的贡献。但是这里出现了一个莫名其妙的$x$，代表的是操作②对答案的贡献，它的值为所有后续打架的位置和当前位置的距离之和，而这里是一个不能确定的变量。
于是增加第三维：所有攻击操作的下标之和。于是就可以愉快地递推了，$x=k-i\times j$。然后快乐地提交，获得了$MLE$。所以需要滚动一下。
AC代码
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
typedef long long ll;
using namespace std;
ll f[2][102][5052],a[110],b[110],c[110],ans;
int main(){
int i,t,j,n,k;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
for(i=0;i<2;i++)for(j=0;j<=n;j++)for(k=0;k<=n*(n+1)/2;k++)f[i][j][k]=-1;
f[0][1][n]=a[n];
int p=0;
for(i=n-1;i;i--){
p^=1;
for(j=n-i+1;j;j--){
for(k=n*(n+1)/2;k>=n;k--){
if(k-i>=n&&j>=2&&~f[p^1][j-1][k-i])f[p][j][k]=f[p^1][j-1][k-i]+a[i];
if(~f[p^1][j][k])f[p][j][k]=max(f[p][j][k],f[p^1][j][k]+max(c[i]*j,(k-i*j)*b[i]));
}
}
for(j=0;j<=n;j++)for(k=0;k<=n*(n+1)/2;k++)f[p^1][j][k]=-1;
}
for(i=1;i<=n;i++)
for(j=1;j<=n*(n+1)/2-i*(i-1)/2;j++)
ans=max(ans,f[p][i][j]);
printf("%lld\n",ans);
}
return 0;
}
C
题目描述
给定两个长度$2\leq |s|\leq 10^6,1\leq |t|<|s|$的字符串，求满足以下要求的三元组$(i,j,k)$的个数：
- $1\leq i\leq j\leq |s|$
- $1\leq k\leq |t|$
- $j-i+1>k$
- 把$[s[i],s[j]]$和$[t[1],t[k]]$拼接起来的新串为回文串。
解题思路
题目可以转化为：在$s$中找到连续的串$a,b$，在$t$中找到串$c$，且$a,b,c$不空，$b$为回文串且$a$和$c$倒序相等。
可以先$manacher$处理出$s$中每一个$i$开头的回文串个数（用差分思想），再在旋转过的$b$串后缀中字符串哈希二分查找最长公共子串长度，乘起来再求和即可。
AC代码
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
typedef long long ll;
ll hs[N],ht[N],pw[N];
char s[N],t[N];
char a[N]={'.'};
int len[N];
int p[N];
using namespace std;
int ls,lt;
ll hashf(ll*a,int l,int r){
return ((a[r]-a[l]*pw[r-l])%mod+mod)%mod;
}
int check(int x,int i){
return hashf(ht,lt-x,lt)==hashf(hs,i-x,i);
}
int main(){
int i;
pw[0]=1;
for(i=1;i<N;i++)pw[i]=pw[i-1]*base%mod;
scanf("%s%s",s,t);
ls=strlen(s),lt=strlen(t);
reverse(t,t+lt);
for(i=0;i<ls;i++){
a[2*i+1]='#';
a[2*i+2]=s[i];
}
a[2*ls+1]='#';
int mr=0,mid=0;
for(i=1;i<=2*ls+2;i++){
if(mr>i)len[i]=min(mr-i,len[2*mid-i]);
else len[i]=1;
while(a[i+len[i]]==a[i-len[i]])len[i]++;
if(i+len[i]>mr){
mr=i+len[i];
mid=i;
}
}
for(i=1;i<2*ls+2;i++){
p[(i-len[i])/2]++;
p[(i)/2]--;
}
for(i=1;i<=ls;i++)p[i]+=p[i-1];
hs[0]=ht[0]=1;
for(i=1;i<=ls;i++)hs[i]=(hs[i-1]*base+s[i-1]-'a')%mod;
for(i=1;i<=lt;i++)ht[i]=(ht[i-1]*base+t[i-1]-'a')%mod;
ll ans=0;
for(i=1;i<ls;i++){
if(s[i-1]!=t[lt-1])continue;
int l=1,r=min(lt,i);
while(l<r){
int mid=(l+r)>>1;
if(check(mid,i))l=mid+1;
else r=mid;
}
if(!check(l,i))l--;
ans+=p[i]*1LL*l;
}
printf("%I64d",ans);
return 0;
}
D
题目描述
有$n$个人，每个人能打$t[i]$个怪兽，分别为$m[i][j]$。每个人最多只能打一只怪兽。
这时候提供了$k$个膜法药水，一个人最多可以喝一瓶，喝了一瓶之后最多就能打两只怪兽了。问最好的分配情况下，一共能打多少只怪兽。
解题思路
非常裸的网络流，从源点到每个人、每个怪兽到汇点建长度为$1$的边，每个人与他能打的怪兽之间建长度为$1$的边。再考虑膜法药水，从源点到新增节点$magic$建长度为$k$的边，从$magic$到每个人建长度为$1$的边，跑一遍最大流即可。
AC代码
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
typedef long long ll;
using namespace std;
int s,t,magic;
struct Edge{
int end,near,len;
}e[N*N];
int head[N],cnt=1,cur[N];
int n,m,k;
void add(int a,int b,int l){
e[++cnt].end=b;
e[cnt].near=head[a];
e[cnt].len=l;
head[a]=cnt;
}
queue<int>Q;
int dep[N];
int bfs(){
int i,p,q;
memset(dep,0,sizeof(dep));
for(i=0;i<=magic;i++)cur[i]=head[i];
Q.push(s);dep[s]=1;
while(!Q.empty()){
p=Q.front();Q.pop();
for(i=head[p];i;i=e[i].near){
q=e[i].end;
if(e[i].len&&!dep[q]){
dep[q]=dep[p]+1;
Q.push(q);
}
}
}
return dep[t];
}
int dfs(int p,int flow){
if(p==t)return flow;
int i,q;
for(i=cur[p];i;i=e[i].near){
cur[p]=i;
q=e[i].end;
if(dep[q]==dep[p]+1&&e[i].len){
int ans=dfs(q,min(flow,e[i].len));
if(ans){
e[i].len-=ans;
e[i^1].len+=ans;
return ans;
}
}
}
return 0;
}
int dinic(){
int d,ans=0;
while(bfs()){
while((d=dfs(s,1e6)))
ans+=d;
}
return ans;
}
int main(){
int i,j,M,T;
scanf("%d%d%d",&n,&m,&k);
s=0;
t=n+m+1;
magic=t+1;
for(i=1;i<=n;i++){
scanf("%d",&T);
for(j=0;j<T;j++)scanf("%d",&M),add(i,M+n,1),add(M+n,i,0);
}
add(s,magic,k),add(magic,s,0);
for(i=1;i<=n;i++){
add(s,i,1),add(i,s,0);
add(magic,i,1),add(i,magic,0);
}
for(i=1;i<=m;i++)add(i+n,t,1),add(t,i+n,0);
printf("%d",dinic());
return 0;
}
E
题目描述
给定一个有$n$个数（$1\leq n\leq 10^6$）的正整数序列$a[i]$，$1\leq a[i]\leq 10^6$。。
定义$mul(l,r)=\prod_{i=l}^{r}a[i]$，$fac(l,r)$为$mul(l,r)$中的所有质因数种数之和。求$\sum_{i=1}^{n}\sum_{j=i}^{n}fac(i,j)$。
解题思路
考虑每一个质因数的贡献，设它出现的位置为$p[1],p[2],…,p[m]$。不妨设$p[0]=0,p[m+1]=n+1$，则其贡献为$\frac{n\times (n+1)}2-\sum_{i=0}^{m}\frac{(p[i+1]-p[i])(p[i+1]-p[i]-1)}2$。枚举每一个$a[i]$，计算出其对应的所有质因数，最后统计即可。
AC代码
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
typedef long long ll;
using namespace std;
int n,prime[N],a[N]={1,1},cnt;
ll ans;
vector<int>num[N];
ll f(ll a,ll b){return (b-a+1)*(b-a+2)/2;}
int main(){
int i,j,p;
for(i=2;i<N;i++){
if(!a[i])prime[cnt++]=i,a[i]=cnt-1;
for(j=0;i*prime[j]<N&&j<cnt;j++){
a[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
scanf("%d",&n);
for(i=0;i<cnt;i++)num[i].push_back(0);
for(i=1;i<=n;i++){
scanf("%d",&p);
for(j=0;j<cnt&&prime[j]*prime[j]<=p;j++){
if(p%prime[j]==0){
num[j].push_back(i);
while(p%prime[j]==0)p/=prime[j];
}
}
if(p>1)num[a[p]].push_back(i);
}
for(i=0;i<cnt;i++)num[i].push_back(n+1);
for(i=0;i<cnt;i++){
ans+=1LL*(n+1)*n/2;
for(j=1;j<num[i].size();j++)
ans-=f(num[i][j-1]+1,num[i][j]-1);
}
printf("%lld",ans);
return 0;
}