本来是打算所有半夜进行的CF都不参加的，但看到这次比赛22：35就开始，还是没有忍住orz……晚上总是不够清醒，做题思维不如白天活跃，低级错误常常出现。出的比较早的C因为一个书写错误有点小bug，在比赛快结束时被hack，还好一下子就发现改正了过来，b题很水，却刚开始没想到合适的做法，也卡了比较久。D题因为刚学到DP，还很不熟练，比赛前没能写完。整体来说这一场实在是表现的菜的一塌糊涂。不过因为现在rating低，还在神奇的上分，算是一点慰藉了。
A
简要题意：
输入一个整数n，输出1378的n次方的个位数。
思路分析：
只要看8的n次方个位数是多少。显然是有循环节的，写几项发现循环节为4，所以只需要看n模4余几，注意n=0时要特殊判断一下，任何非0数的0次方都是1.
参考代码：
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
if(n==)
{
printf("1\n");
}
else if(n%==)
{
printf("8\n");
}
else if(n%==)
{
printf("4\n");
}
else if(n%==)
{
printf("2\n");
}
else if(n%==)
{
printf("6\n");
}
return ;
}
B
简要题意：
给若干数，要求判断这些这些数有多少对异或值为给定的另一个数。（每一对顺序固定，按给定时的顺序）
思路分析：
注意到x^y=z则x^z=y。利用此，建立数组记录每个数出现的次数，因为每一对顺序固定，对于一个数x，只需看出现在x之前的（x^“目标数”）出现了多少次，就多形成了多少对。注意异或值可能会比给出的数的范围大，所以把数组大小开大一点。
参考代码：
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int INF=1e6+;
ll an=;
int ci[INF],n,mu,i,tem;
int main()
{
memset(ci,,sizeof(ci));
scanf("%d%d",&n,&mu);
for(i=;i<n;i++)
{
scanf("%d",&tem);
an+=ci[tem^mu];
ci[tem]++;
}
printf("%I64d\n",an);
return ;
}
C
简要题意：
一个有向图，每一个点有且只有一条出的线。求最小的n，使任意从一点走2n步之后就回到本身。
思路分析：
显然，有向图中的每一点入度都需要恰为1，否则必然有入度为0的点，那么不管n取多少，从这点都走不回这一点。而当满足每一点入度都恰为1时就一定可以找到符合要求的n。只需要求所有形成的环的“长度”（如果长度为偶数2x，n取x即可走2x步就回到本身，所以用于计算的“长度”取值为x）的最小公倍数即可。
参考代码：
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int gcd(int x,int y)
{
while(x%y!=&&y%x!=)
{
if(y>x)
y=y%x;
else
x=x%y;
}
if(x%y==)
{
return y;
}
else
{
return x;
}
}
int main()
{
int n,a[],i,an=,len=,j,b[],cnt=;
bool vi[];
memset(vi,false,sizeof(vi));
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
vi[a[i]]=true;
}
for(i=;i<=n;i++)
{
if(!vi[i])
{
printf("-1\n");
return ;
}
}
memset(vi,false,sizeof(vi));
for(i=;i<=n;i++)
{
len=;
if(!vi[i])
{
j=a[i];
len=;
while(j!=i)
{ vi[j]=true;
len++;
j=a[j];
}
b[cnt++]=len;
}
}
if(b[]%!=)
an=b[];
else
an=b[]/;
for(i=;i<cnt;i++)
{
if(b[i]%!=)
an*=(b[i]/gcd(an,b[i]));
else
an*=((b[i]/)/gcd(an,b[i]/));
}
printf("%d\n",an);
return ;
}
D
简要题意：
有若干人，，每个人有一个体重值和颜值，且若干人组成一组，这一组必须全取或取小于等于1个人。要找到一种总体重小于等于W，而颜值之和最大的选人办法。
思路分析：
0、1背包，不同的是题目中的限制。只需要先根据题意把同一组的标记出来，这一组的每个人，和这一组的整体作为第i个可选物品进行0、1背包即可。
参考代码：
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define num 1010
vector <int> group[num];
int pre[num],w[num],b[num],ww[num],bb[num],dp[num][num],cnt,fpre[num],org;
int n,m,W,i,l,r,an=;
int trimax(int x,int y,int z)
{
if(x>=y&&x>=z)
return x;
if(y>=x&&y>=z)
return y;
if(z>=x&&z>=y)
return z;
}
int trace (int s)
{
if(pre[s]==s)
return s;
else
return trace(pre[s]);
} int main()
{
scanf("%d%d%d",&n,&m,&W);
for(i=;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(i=;i<=n;i++)
{
scanf("%d",&b[i]);
}
for(i=;i<=n;i++)
{
pre[i]=i;
}
for(i=;i<=m;i++)
{
scanf("%d%d",&l,&r);
if(trace(l)!=trace(r))
pre[trace(l)]=trace(r);
}
cnt=;
for(i=;i<=n;i++)
{
int st=-;
int org=trace(i);
int j;
for(j=;j<cnt;j++)
{
if(fpre[j]==org)
{
st=j;
break;
}
}
if(st==-)
{
ww[cnt]+=w[i];
bb[cnt]+=b[i];
group[cnt].push_back(i);
fpre[cnt++]=org;
}
else
{
ww[st]+=w[i];
bb[st]+=b[i];
group[st].push_back(i);
}
}
for(i=;i<cnt;i++)
{
for(int k=W;k>=;k--)
{
if(k>=ww[i])
dp[i][k]=trimax(dp[i][k],dp[i-][k],dp[i-][k-ww[i]]+bb[i]);
else
dp[i][k]=max(dp[i][k],dp[i-][k]);
}
for(int j=;j<group[i].size();j++)
{
for(int k=W;k>=;k--)
{
if(k>=w[group[i][j]])
dp[i][k]=trimax(dp[i][k],dp[i-][k],dp[i-][k-w[group[i][j]]]+b[group[i][j]]);
else
dp[i][k]=max(dp[i][k],dp[i-][k]);
}
}
}
for(i=;i<=W;i++)
if(dp[cnt-][i]>an)
an=dp[cnt-][i];
printf("%d\n",an);
return ;
}
E
简要题意：
n对情侣坐在一个圆桌上（情侣都是一男一女的，没有别的情况），给他们发两种食物，要求：
1、一对情侣食物不同
2、任意连续3个人，必须2种食物都出现
思路分析：
大家初看可能觉得是二分图匹配，但其实并不是，只是一个普通的图随便整一下。
下面是对必定有解的证明。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N=;
vector <int> a[N];
int b[N],g[N];
int an[N];
bool vi[N];
void dfs(int x,int t)
{
vi[x]=true;an[x]=t;
for(int i:a[x])
{
if(!vi[i])
dfs(i,(t^));}
}
int main()
{
memset(vi,false,sizeof(vi));
int n,i;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&b[i],&g[i]);
a[b[i]].push_back(g[i]);
a[g[i]].push_back(b[i]);
}
for(i=;i<=n;i++)
{
a[*i-].push_back(*i);
a[*i].push_back(*i-);
}
for(i=;i<=*n;i++)
if(!vi[i])
dfs(i,);
for(i=;i<=n;i++)
printf("%d %d\n",an[b[i]]+,an[g[i]]+);
return ;
}