纪中爆零之行Day1
又来纪中了心态爆炸
上次来热的跟鬼一样，这次贼凉快，（因为有台风）换了个机房，成功被这个电脑搞成自闭，开机一段时间自动死机，下载东西自动死机，打开XCOJ自动死机，打开安装包自动死机，做个考试开关电脑五六次，（昨天晚上开关十来次）第一天考试，心情毫无波澜
T0 游戏
就是这么个题，第一眼就觉得是博弈论，虽然上次来的时候考过博弈论，但听纪中的dalao们讲完后还是不会，所以放弃思考，结果这题二维前缀和就能过。 定义bool型的二维数组f，f(x,y)表示从(1,1)到(x,y)的矩形先手是不是必赢，最后就只用判断f(n,n)的值就可以了
对于f数组的处理
根据定义我们可以得到如果f(x,y-1)=0，如果最后一列可以删，我们就赢了，同样的，如果f(x-1,y)=0，如果最后一排可以删，我们就赢了，如果两者都为1，则对手必胜
那么怎么判断当前排/列能不能删？
二维前缀和！
定义一个二维的a数组，a(x,y)表示从(1,1)到(x,y)所有元素值的和，处理前缀和的方法就不再赘述（因为连我都会的东西就没必要说了）上代码了
#include<bits/stdc++.h>
#define fa(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
long long a[1010][1010];
bool f[1010][1010];
int n,t;
int main()
{
scanf("%d",&t);
fa(i,1,t){
scanf("%d",&n);
fa(i,1,n){
fa(j,1,n){
scanf("%lld",&a[i][j]);
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
}
}
memset(f,0,sizeof(f));
fa(i,1,n)
fa(j,1,n){
if(f[i-1][j]==0)
if((a[i][j]-a[i-1][j])%2==0){
f[i][j]=1;
continue;
}
if(f[i][j-1]==0)
if((a[i][j]-a[i][j-1])%2==0){
f[i][j]=1;
continue;
}
}
if(f[n][n])
printf("W\n");
else
printf("L\n");
}
return 0;
}T1 六边形
JMY大佬（码王）肝了一上午的题，就是个大模拟，各种循环加花式判断处理出来一个数组然后输出对应的答案就好了，但是码量巨大（不过对JMY来说都是毛毛雨因为他是码王）按照限定条件做处理就好了，解释见代码注释吧
#include<bits/stdc++.h>
#define fa(a,b,c) for(int a=b;a<=c;a++)
#define fd(a,b,c) for(int a=b;a>=c;a--)//今天心血来潮的码风
using namespace std;
int t,n;
int a[10010],num[110],sum[6];
/*
a数组就是目标数组了，也就是按顺序存前10000个出现在图中的数字编号
num数组表示每一圈最后一个数的编号（1~10000）
sum数组来存每个数字在圈中出现的次数
*/
int tot=2,f=7,k=0;
/*
tot是当前圈数
f是变化量，设所填数是第x个，则当前数不能等于第x-f个数（上一圈中与之相邻的数）
f通过找规律可以确定
k用来控制f的变化
*/
int main()
{
a[1]=1,a[2]=2,a[3]=3,a[4]=4,a[5]=5,a[6]=2,a[7]=3,a[8]=1,a[9]=4;
sum[1]=2,sum[2]=2,sum[3]=2,sum[4]=2,sum[5]=1;
num[1]=7;
//把特殊情况赋好值
fa(i,2,60)
num[i]=num[i-1]+6*i;
//预处理num数组
fa(i,10,10000){//枚举
int minn=0x7fffffff;
//选数时需要更新出现次数最小值，下皆同
if(i==num[tot]){
f++;//变化
fd(j,5,1){//选数，为确保是最小值要从5开始递减到1
if(j==a[i-1])
continue;
if(j==a[num[tot-1]+1])
continue;
if(j==a[i-f])
continue;
if(sum[j]<=minn)
minn=sum[j],a[i]=j;
}
sum[a[i]]++;
continue;
}
if(i==num[tot]+1){//某圈的第一个数
fd(j,5,1){
if(j==a[i-1])
continue;
if(j==a[i-f])
continue;
if(sum[j]<=minn)
minn=sum[j],a[i]=j,k=1;
}
sum[a[i]]++;
tot++;
continue;
}
k++;
if(k==tot){//k的变化与圈数有关系，第x圈需要x次变化
f++;
k=0;
fd(j,5,1){
if(j==a[i-1])
continue;
if(j==a[i-f])
continue;
if(sum[j]<=minn)
minn=sum[j],a[i]=j;
}
sum[a[i]]++;
continue;
}
fd(j,5,1){//非特殊情况判断
if(j==a[i-1])
continue;
if(j==a[i-f])
continue;
if(j==a[i-f-1])
continue;
if(sum[j]<=minn)
minn=sum[j],a[i]=j;
}
sum[a[i]]++;
}
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",a[n]);//从已预处理过的数组中输出对应数
}
return 0;
}T2 数列
上午做的第一道题，就感觉题面没有什么花里胡哨的东西（而且可以暴力）就做了这道题，没错还是暴力别问我为什么因为我弱，所以只得了10分，正解是前缀和+数论，前段讲数论消化的不是很好所以有点难搞，在JMY大佬和ZX大佬一晚上的讲解后终于明白了，看我打个表先
这是样例的一个数据，通过找规律可以发现，前缀和数组里如果有两个数的差%k为0，那么这就是一个合法的区间，求两个数的差%k为0可以转化为求余数相等的两个前缀和，效果是一样的（大佬讲给我的我也没证明反正很对），那么就好办了，搞一个桶，统计下前缀和%k相等的数的个数，我们知道两个边界可以构成一个合法区间，根据排列组合的知识，方案总数ans计算公式应该为[（首项+末项）x项数]/2
需要特别注意的就是桶里面下标为0的数，如果一个数对k取模为0，那么它本身就是一个合法的子序列了，但通过排列组合计算出的只是有两个余数相等时的合法区间，没有计算取模为0的子区间的个数，所以最后的ans应该再加上s[0]。上代码
#include<bits/stdc++.h>
#define fa(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int a,tot;
int n,t,k;
long long ans;
int s[1000010];
int main()
{
scanf("%d",&t);
fa(i,1,t){
ans=0,tot=0;
memset(s,0,sizeof(s));
scanf("%d%d",&k,&n);
fa(i,1,n){
scanf("%d",&a);
tot=(tot+a)%k;
s[tot]++;
}
for(int i=0;i<k;i++)
if(s[i])
ans+=(s[i]*(s[i]-1)/2);
ans+=s[0];
printf("%lld\n",ans);
}
return 0;
}