Preface
运动会来了，可以趁机搞一波AGC
这场打的很奇怪，ADF是自己做的（难得做出F），B菜了没想到暴力优化一下复杂度对了，C想到了最后一步但求答案不会，E确实没想到
A - Candy Distribution Again
贪心，有手就行
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,a[N],ans,x;
int main()
{
RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i]);
for (sort(a+1,a+n+1),i=1;i<=n&&x;++i) if (x>=a[i]) x-=a[i],++ans; else x=0;
return printf("%d",x?ans-1:ans),0;
}
B - Garbage Collector
刚开始想到如果确定了搬运次数(i)就可以确定一个最优方案，每隔(frac{n}{i})个为一组搬运即可
就是一个(O(n^2))的做法
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int n,c,x[N]; long long tp,ans=1e18; vector <int> v[N];
inline long long calc(CI k,long long ret=0)
{
RI i,j,ct=0; for (i=1;i<=k;++i) v[i].clear(),v[i].push_back(0);
for (i=1;i<=n;++i) v[(i-1)%k+1].push_back(x[i]);
for (i=1;i<=k;++i) for (ret+=v[i][v[i].size()-1],ct=1,j=v[i].size()-1;j;--j,++ct)
ret+=1LL*(v[i][j]-v[i][j-1])*(ct+1)*(ct+1);
return ret+1LL*(n+k)*c;
}
int main()
{
RI i,j; for (scanf("%d%d",&n,&c),i=1;i<=n;++i) scanf("%d",&x[i]);
for (i=1;i<=n;++i) ans=min(calc(i),ans); return printf("%lld",ans),0;
}
后来习惯nt地就想答案是和(i)有关的函数可能存在某些性质，结果并没有当场去世
看了题解才发现每次相邻的(frac{n}{i})个垃圾的贡献是一样的，因此每次第二维的复杂度其实是(O(frac{n}{i}))的
因此运用调和数相关总复杂度就是(O(nln n))
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,c,x[N]; __int128 dlt[N],pfx[N],ret,ans=1e36;
int main()
{
RI i,j,p; for (scanf("%d%d",&n,&c),i=1;i<=n;++i)
scanf("%d",&x[i]),pfx[i]=pfx[i-1]+x[i];
for (dlt[1]=dlt[2]=5,i=3;i<=n;++i) dlt[i]=dlt[i-1]+2;
for (i=1;i<=n;++i)
{
for (ret=1LL*(n+i)*c,j=n,p=1;j>0;j-=i,++p)
ret+=dlt[p]*(pfx[j]-(j>i?pfx[j-i]:0)); ans=min(ans,ret);
}
return printf("%lld",ans),0;
}
C - ABland Yard
首先掏出画图画一波，容易发现一个环一定是(AABB)的循环
只知道这个很难搞，我们考虑把点权化为边权，当两点不同时两点之间的边权为(1)，否则为(0)
因此现在题目就变成了找长度是(4)的倍数的(01)环
然后我们发现每当出现一个(1)字符就会变一次，因此环上的(1)个数必为偶数，因此这样的(01)环长度必然为(4)的倍数，因此只需要找一个(01)环即可
考虑一个非常诡异的做法，考虑进行一个类似拓扑排序的过程，每次删掉一个连边都是同一个字符的点
如果还存在剩下的点，说明存在(01)环（因为只有(01)环不会被删掉）
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
struct edge
{
int to,nxt;
}e[N<<1]; int n,m,cnt,x,y,head[N],deg[N][2],q[N]; bool vis[N]; char s[N];
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[x][s[y]&1];
e[++cnt]=(edge){x,head[y]}; head[y]=cnt; ++deg[y][s[x]&1];
}
int main()
{
RI i,H=0,T=0; for (scanf("%d%d%s",&n,&m,s+1),i=1;i<=m;++i)
scanf("%d%d",&x,&y),addedge(x,y); for (i=1;i<=n;++i)
if (!deg[i][0]||!deg[i][1]) vis[i]=1,q[++T]=i;
while (H<T)
{
int now=q[++H]; for (i=head[now];i;i=e[i].nxt)
if (!vis[e[i].to]&&!(--deg[e[i].to][s[now]&1]))
vis[e[i].to]=1,q[++T]=e[i].to;
}
for (i=1;i<=n;++i) if (!vis[i]) return puts("Yes"),0;
return puts("No"),0;
}
D - Modulo Matrix
首先我们发现(m)越小越好，所以直接令(m=1)
考虑给矩阵的所有间隔的点（即(2|x+y)）的点填上一个数，然后所有未填数的点（即(2 ot | x+y)）的点的值为周围点的(operatorname{lcm})再加(1)
现在我们考虑不能出现重复的数，首先容易想到给每行每列一个不重复的质数，每个给定点填的就是这两个质数的乘积
但我们考虑这样对于一个周围有四个给定点的格子，它所填的数就是(6)个质数的乘积，显然无法通过
然后我们发现给定点其实在矩阵中都在对角线上，因此我们把质数给对角线，这样对于一个周围有四个给定点的格子，它所填的数就是(4)个质数的乘积
把质数错排一下可以很轻松的通过
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,P[N<<1],t[N<<1],vis[500005],cnt,x1,y1,x2,y2; long long a[N][N];
inline void init(CI m,CI n=500000)
{
RI i,j; for (i=2;i<=n;++i)
{
if (!vis[i]) P[++cnt]=i; if (cnt==m) break;
for (j=1;j<=cnt&&i*P[j]<=n;++j)
if (vis[i*P[j]]=1,i%P[j]==0) break;
}
}
int main()
{
//freopen("ans.txt","w",stdout);
RI i,p,q; scanf("%d",&n); init(n*2-1);
if (n==2) return puts("4 7
23 10"),0;
for (p=1,q=cnt,i=1;i<=cnt;++i) t[i]=(i&1?P[p++]:P[q--]);
for (i=1;i<=cnt;++i) P[i]=t[i];
for (p=1;p<=n;++p) for (q=1;q<=n;++q) a[p][q]=1;
for (x1=y1=x2=1,y2=(n&1?n:n-1),i=1;i<=cnt;++i)
if (i&1)
{
for (p=x1,q=y1;p>=1&&q<=n;--p,++q) a[p][q]*=P[i];
if (x1==n) y1+=2; else if ((x1+=2)>n) y1=x1-n+1,x1=n;
}
else
{
for (q=x2,p=y2;p<=n&&q<=n;++p,++q) a[p][q]*=P[i];
if (y2==1) x2+=2; else if ((y2-=2)<1) x2=1-y2+1,y2=1;
}
for (p=1;p<=n;++p) for (q=1;q<=n;++q) if (a[p][q]==1)
{
for (i=0;i<4;++i)
{
x1=p+dx[i]; y1=q+dy[i]; if (x1<1||x1>n||y1<1||y1>n) continue;
a[p][q]=1LL*a[p][q]/__gcd(a[p][q],a[x1][y1])*a[x1][y1];
}
++a[p][q];
}
for (p=1;p<=n;++p) for (q=1;q<=n;++q)
printf("%lld%c",a[p][q],"
"[q==n]);
/*long long mx=0; for (p=1;p<=n;++p) for (q=1;q<=n;++q)
mx=max(mx,a[p][q]); printf("%lld
",mx);*/
return 0;
}
E - ABBreviate
一道思路很诡异的题，首先判掉无法操作的情况，并且设(a=1,b=2)
容易发现此时的变换并不会影响序列的和(mod 3)的结果
然后要证明一个结论：一个字符串(s)能变成一个字符(c)的充要条件是字符串(s)之和(mod 3)的余数与(c)对应的值相同且(s)中有可变换的位置（即不是完全由(ab)重复构成）
证明的过程简单来说就是考虑如果我们转化到某一步让(s)无法再变换了，我们可以退回到上一步并改为合并另外一对位置，自己画画图就可以发现必然存在悔改的方案
因此我们直接枚举变换后的串的每个位置的字符，然后贪心地从左到右填写，显然可以用一个(O(n))的DP维护
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=1e9+7;
char s[N]; int n,pfx[N],nxt[N][3],f[N],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j; scanf("%s",s+1); n=strlen(s+1); bool flag=1;
for (i=1;i<n&&flag;++i) if (s[i]==s[i+1]) flag=0;
if (flag) return puts("1"),0;
for (i=1;i<=n;++i) pfx[i]=(pfx[i-1]+(s[i]&1)+1)%3;
for (i=0;i<3;++i) nxt[n+1][i]=n+1;
for (i=n;i;--i) { for (j=0;j<3;++j) nxt[i][j]=nxt[i+1][j]; nxt[i][pfx[i]]=i; }
for (f[0]=1,i=0;i<=n;++i)
{
if (i&&pfx[i]==pfx[n]) inc(ans,f[i]);
for (j=1;j<3;++j) inc(f[nxt[i+1][(pfx[i]+j)%3]],f[i]);
}
return printf("%d",ans),0;
}
F - Grafting
思维难度比较低的一道F，在和陈指导的不断出解和Hack的过程中就会了（然而因为一个循环清空变量打错调了好久的说）
首先我们考虑两棵无根树是很难判断同构的，因此我们考虑定下一个根
但是选哪个点为根呢，因为黑点不能再操作了，因此我们容易想到枚举第一个操作的点(x)，然后再枚举一个新连接的点，此时两棵树显然可以以(x)为根
有根树的同构就很容易了，同构就意味着对应点的父节点相同，因此我们发现如果一种情况合法操作次数是显然的，就是对应点的父节点不相同的点的个数
然后我们发现对于第一棵树，除去对应点的父节点相同的点之外，剩下的每个点都必须在儿子选了之后选
对于第二棵树，同样除去对应点的父节点相同的点之外，剩下的每个点都必须在子节点操作之前操作
我们发现这形成了一种拓扑关系，当我们把这种关系连有向边的时候，容易发现成环是就不合法了
同时还要注意还需要先判断如果某个对应点的父节点不相同的点子树内存在对应点的父节点相同的点，必然无解
最后加上特判的两棵树本来就同构的情况这道题就做完了
#include<cstdio>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
#define pb push_back
#define Ms(f) memset(f,0,sizeof(f))
using namespace std;
typedef vector <int>:: iterator VI;
const int N=55,INF=1e9;
int t,n,x,y,ans,lf[N],lst[N],fa[N],fb[N],deg[N],q[N];
vector <int> A[N],B[N],G[N]; bool r[N],flag;
inline void DFSA(CI now,CI fat=0)
{
for (VI to=A[now].begin();to!=A[now].end();++to)
if (*to!=fat) fa[*to]=now,DFSA(*to,now);
}
inline void DFSB(CI now,CI fat=0)
{
for (VI to=B[now].begin();to!=B[now].end();++to)
if (*to!=fat) fb[*to]=now,DFSB(*to,now);
}
inline void DFS(CI now,CI fat=0,const bool& tp=1)
{
if (fa[now]==fb[now]) if (r[now]=1,!tp) flag=0;
for (VI to=A[now].begin();to!=A[now].end();++to)
if (*to!=fat) DFS(*to,now,tp&&r[now]);
}
inline int check(CI rt)
{
Ms(r); fa[rt]=fb[rt]=0; DFSA(rt); DFSB(rt); flag=1; DFS(rt);
if (!flag) return -1; int ret=0; for (RI i=1;i<=n;++i) ret+=r[i]; return ret;
}
inline bool Top_Sort(void)
{
RI i,H=0,T=0; for (i=1;i<=n;++i) if (!deg[i]) q[++T]=i;
while (H<T)
{
int now=q[++H]; for (VI to=G[now].begin();to!=G[now].end();++to)
if (!(--deg[*to])) q[++T]=*to;
}
return T==n;
}
inline void remove(vector <int>& v,CI val)
{
for (VI it=v.begin();it!=v.end();++it)
if (*it==val) return (void)(v.erase(it));
}
inline void clear(void)
{
Ms(lf); for (RI i=1;i<=n;++i) A[i].clear(),B[i].clear();
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j,k; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),A[x].pb(y),A[y].pb(x),
++lf[x],++lf[y],lst[x]=y,lst[y]=x; ans=INF;
for (i=1;i<n;++i)
scanf("%d%d",&x,&y),B[x].pb(y),B[y].pb(x);
if (check(1)==n) { puts("0"); clear(); continue; }
for (i=1;i<=n;++i) if (lf[i]==1) for (j=1;j<=n;++j) if (i!=j)
{
if (j!=lst[i]) remove(A[i],lst[i]),remove(A[lst[i]],i),A[i].pb(j),A[j].pb(i);
int tp; if (~(tp=check(i)))
{
for (Ms(deg),k=1;k<=n;++k) G[k].clear();
for (k=1;k<=n;++k) if (!r[k]&&!r[fa[k]]) G[fa[k]].pb(k),++deg[k];
for (k=1;k<=n;++k) if (!r[k]&&!r[fb[k]]) G[k].pb(fb[k]),++deg[fb[k]];
if (Top_Sort()) ans=min(ans,n-tp+(j!=lst[i]));
}
if (j!=lst[i]) remove(A[i],j),remove(A[j],i),A[i].pb(lst[i]),A[lst[i]].pb(i);
}
if (ans==INF) puts("-1"); else printf("%d
",ans); clear();
}
return 0;
}
Postscript
以后争取每天做一场AGC吧，CSP之前刷到20不是梦想