签到题，直接模拟就可以了。
满足只能是每个朋友圈中每个人和其他人都是朋友，这样的边数的确定的。
然后并查集求每个朋友圈大小再判断是否合法就可以啦。
#include#include #include #include #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,1,n) fa[i]=i,size[i]=1,e[i]=0; rep(i,1,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=1; rep(i,1,n) if (fa[i]==i && size[i]*(size[i]-1)!=e[i]*2) { flag=0; // printf("%d %d %d\n",i,size[i],e[i]); break; } printf("%s\n",flag?"YES":"NO"); return 0;}
构造题，构造方法是每次如果是NO就让第一个跟最后一个不一样就可以啦
#include#include #include #include #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[1000];int main(){ scanf("%d %d",&n,&m); int tot=0; rep(i,1,m-1) num[i]=++tot; rep(i,m,n) { scanf("%s",s); if (s[0]=='N') num[i]=num[i-m+1]; else num[i]=++tot; } rep(i,1,n) { printf("A"); while (num[i]) { printf("%c",num[i]%16+'a'); num[i]/=16; } printf("%s",i
给一棵树，和一个k（<=5)，表示每次可以跳超过k步，求整个树中任意两个点步数的和。
题解：由于k<=5，树dp
对于每个点记录到这个点步数余数l的和，每个子节点的子树到父亲节点步数对答案的共享，在把子节点的信息并到父节点里面，具体的答案计算
f[x][y]表示x的子树中走到x节点余y的步数总和
if (j+k
（具体含义似乎是，大概是子树走到父和父走到子树，f[x][j]*s[too][k]，表示too余k走到x余j一共要走s[too][k]次，s[too][k]*s[x][j]是x到too需要的步数（1步或者两步））
#include#include #include #include #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*2];LL f[maxn][5],s[maxn][5],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]=1; f[x][0]=0,s[x][0]=1; repedge(i,x) { int too=e[i].toward; if (!chose[too]) { dfs(too); rep(j,0,m-1) if (s[x][j]) rep(k,0,m-1) if (s[too][k]) { if (j+k
过的时候也非常有趣，最后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#include #include #include #include #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 longusing namespace std;vector V,K,X;char s[100];int n,f[80][80][80][2],cost[100];int main(){ scanf("%d",&n); scanf("%s",s); rep(i,0,n-1) { 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,0,totv) rep(j,0,totk) rep(k,0,totx) f[i][j][k][0]=f[i][j][k][1]=inf; f[0][0][0][1]=0; rep(i,0,totv) rep(j,0,totk) rep(k,0,totx) { // printf("%d %d\n",f[i][j][k][0],f[i][j][k][1]); int now1=i,now2=j,now3=k; cost[0]=0; rep(l,1,n-1) { cost[l]=cost[l-1]; if (now1
学题解用了顺推的dp方式。
总的来说还是太弱了，第三题的构造和第五题的dp在比赛的时候都没有写出来。