签到题，直接模拟就可以了。
满足只能是每个朋友圈中每个人和其他人都是朋友，这样的边数的确定的。
然后并查集求每个朋友圈大小再判断是否合法就可以啦。
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 300000
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std; LL size[maxn],e[maxn];
int fa[maxn],n,m; int find(int x)
{
if (fa[x]!=x) return fa[x]=find(fa[x]);
return x;
}
int main()
{
scanf("%d %d",&n,&m);
rep(i,,n) fa[i]=i,size[i]=,e[i]=;
rep(i,,m) {
int j,k;
scanf("%d %d",&j,&k);
int fa1=find(j),fa2=find(k);
if (fa1!=fa2) fa[fa2]=fa1,e[fa1]+=e[fa2],size[fa1]+=size[fa2];
++e[fa1];
}
int flag=;
rep(i,,n)
if (fa[i]==i && size[i]*(size[i]-)!=e[i]*) {
flag=;
// printf("%d %d %d\n",i,size[i],e[i]);
break;
}
printf("%s\n",flag?"YES":"NO");
return ;
}
构造题，构造方法是每次如果是NO就让第一个跟最后一个不一样就可以啦
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1000
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
using namespace std; int n,m,num[maxn];
char s[]; int main()
{
scanf("%d %d",&n,&m);
int tot=;
rep(i,,m-) num[i]=++tot;
rep(i,m,n) {
scanf("%s",s);
if (s[]=='N') num[i]=num[i-m+];
else num[i]=++tot;
}
rep(i,,n) {
printf("A");
while (num[i]) {
printf("%c",num[i]%+'a');
num[i]/=;
}
printf("%s",i<n?" ":"\n");
}
return ;
}
给一棵树，和一个k（<=5)，表示每次可以跳超过k步，求整个树中任意两个点步数的和。
题解：由于k<=5，树dp
对于每个点记录到这个点步数余数l的和，每个子节点的子树到父亲节点步数对答案的共享，在把子节点的信息并到父节点里面，具体的答案计算
f[x][y]表示x的子树中走到x节点余y的步数总和
if (j+k<m) sum+=f[x][j]*s[too][k]+s[too][k]*s[x][j]+s[x][j]*f[too][k];
else sum+=f[x][j]*s[too][k]+s[too][k]*s[x][j]*2+s[x][j]*f[too][k]；
（具体含义似乎是，大概是子树走到父和父走到子树，f[x][j]*s[too][k]，表示too余k走到x余j一共要走s[too][k]次，s[too][k]*s[x][j]是x到too需要的步数（1步或者两步））
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 300000
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define repedge(i,x) for(int i=fi[x];i;i=e[i].next)
using namespace std; typedef struct {
int toward,next;
}Edge; Edge e[maxn*];
LL f[maxn][],s[maxn][],sum;
int n,tot,m,chose[maxn],fi[maxn]; void addedge(int j,int k)
{
++tot;
e[tot].toward=k;
e[tot].next=fi[j];
fi[j]=tot;
} void dfs(int x)
{
// printf("%d\n",x);
chose[x]=;
f[x][]=,s[x][]=;
repedge(i,x) {
int too=e[i].toward;
if (!chose[too]) {
dfs(too);
rep(j,,m-) if (s[x][j])
rep(k,,m-)
if (s[too][k]) {
if (j+k<m) sum+=f[x][j]*s[too][k]+s[too][k]*s[x][j]+s[x][j]*f[too][k];
else sum+=f[x][j]*s[too][k]+s[too][k]*s[x][j]*+s[x][j]*f[too][k];
// printf("%d\n",sum);
}
// printf("%d\n",sum);
f[x][]+=f[too][m-]+s[too][m-];
s[x][]+=s[too][m-];
rep(j,,m-) f[x][j+]+=f[too][j],s[x][j+]+=s[too][j];
}
}
} int main()
{
scanf("%d %d",&n,&m);
rep(i,,n-) {
int j,k;
scanf("%d %d",&j,&k);
addedge(j,k);
addedge(k,j);
}
dfs();
// rep(i,1,n) {
// printf("\n");
// }
printf("%I64d\n",sum);
return ;
}
过的时候也非常有趣，最后10s debug然后没编译直接提交竟然过了……
给一个长度为n（<=75）的字符串，问要使字符串中不含vk需要的步数。
题解：这道题比赛不会，之后也不会，看了题解还是懵逼，最后看代码才读懂，dp果然是我的弱项。
用dp[i][j][k][l]表示已经使前面i+j+k个合法，i为V的个数，j为K的个数，k为非VK的个数，l取0/1表示最后一位是否为V
然后考虑加入一个数字，由于每次是相邻两个数的交换，所以在之前的调整过程中，除了前面调整选的i+j+k，其他还没被选的字符在字符串中的相对位置还是不变的。现在考虑把一个字符提到i+j+k+1这个位置，那移动步数就是在这个字符前面还没选的字符个数，相同的V，K或者非VK间相对位置一定不变，所以这个移动步数也可以通过扫一边得出来。
然后就是转移，具体就是结尾是V后面就不能K。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define maxn 80
#define inf 1<<28
#define LL long long
using namespace std; vector<int> V,K,X;
char s[];
int n,f[][][][],cost[]; int main()
{
scanf("%d",&n);
scanf("%s",s);
rep(i,,n-) {
if (s[i]=='V') V.push_back(i);
else
if (s[i]=='K') K.push_back(i);
else X.push_back(i);
}
int totv=(int)V.size(),totx=(int)X.size(),totk=(int)K.size();
rep(i,,totv)
rep(j,,totk)
rep(k,,totx)
f[i][j][k][]=f[i][j][k][]=inf;
f[][][][]=;
rep(i,,totv)
rep(j,,totk)
rep(k,,totx) {
// printf("%d %d\n",f[i][j][k][0],f[i][j][k][1]);
int now1=i,now2=j,now3=k;
cost[]=;
rep(l,,n-) {
cost[l]=cost[l-];
if (now1<totv && V[now1]<l) ++cost[l],++now1;
if (now2<totk && K[now2]<l) ++cost[l],++now2;
if (now3<totx && X[now3]<l) ++cost[l],++now3;
}
// printf("%d %d %d\n",i,j,k);
// rep(l,0,n-1) printf("%4d",cost[l]);printf("\n");
if (i<totv)
f[i+][j][k][]=min(f[i+][j][k][],
min(f[i][j][k][],f[i][j][k][])+cost[V[i]]);
if (j<totk) {
f[i][j+][k][]=min(f[i][j+][k][],
f[i][j][k][]+cost[K[j]]);
}
if (k<totx) {
f[i][j][k+][]=min(f[i][j][k+][],
min(f[i][j][k][],f[i][j][k][])+cost[X[k]]);
}
}
printf("%d\n",min(f[totv][totk][totx][],f[totv][totk][totx][]));
return ;
}
学题解用了顺推的dp方式。
总的来说还是太弱了，第三题的构造和第五题的dp在比赛的时候都没有写出来。