T1 分糖果
https://gxyzoj.com/d/hzoj/p/3752
因为是三的倍数，所以按余数分为三种情况，分别是：3个0,3个1，3个2，012
显然，当012的组数超过2时，就会出现3组相同余数的，所以枚举012的组数即可
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100005],cnt[3],b[3][100005],ans,p;
int main()
{
// freopen("data19.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]%=3;
b[a[i]][++cnt[a[i]]]=i;
}
ans=0;
for(int i=0;i<3;i++)
{
int x=cnt[0]-i,y=cnt[1]-i,z=cnt[2]-i;
int tmp=x/3+y/3+z/3+i;
if(tmp>ans)
{
ans=tmp,p=i;
}
}
printf("%d\n",ans);
for(int i=0;i<3;i++)
{
for(int j=cnt[i]-2;j>p;j-=3)
{
printf("%d %d %d\n",b[i][j+2],b[i][j+1],b[i][j]);
}
}
for(int i=1;i<=p;i++)
{
printf("%d %d %d\n",b[0][i],b[1][i],b[2][i]);
}
return 0;
}
T2 乒乓球
https://gxyzoj.com/d/hzoj/p/3753
如果两个人的比分相等且大于11，那与11:11等价
如果两个人的比分相差1且大于11，那与11:10等价
所以可以循环枚举每一个周期，记录在这个周期结束时的两人的比分，如果重复出现，则找到了大周期
在这个过程中，可以记录每个人赢的次数
此时，可以直接算出在n个球中属于大循环的所有球的胜负情况，剩余暴力枚举即可
代码：
#include<cstdio>
#include<string>
#include<iostream>
#define ll long long
using namespace std;
ll n,sa[15][15],sb[15][15],t[15][15],k;
string s;
ll a=0,b=0,cnta=0,cntb=0;
int main()
{
// freopen("data06.in","r",stdin);
scanf("%lld%lld",&n,&k);
cin>>s;
for(int i=0;i<12;i++)
{
for(int j=0;j<12;j++)
{
sa[i][j]=sb[i][j]=t[i][j]=-1;
}
}
sa[0][0]=sb[0][0]=t[0][0]=0;
ll tmp=0;
while(tmp*k<=n)
{
for(int i=1;i<=k;i++)
{
if(s[i-1]=='A') a++;
else b++;
if(a>=11&&a-b>=2)
{
cnta++,a=b=0;
}
if(b>=11&&b-a>=2)
{
cntb++,a=b=0;
}
if(a==b&&a>=11) a=b=11;
if(a>=11&&a-b==1) a=11,b=10;
if(b>=11&&b-a==1) a=10,b=11;
}
tmp++;
if(t[a][b]!=-1) break;
t[a][b]=tmp,sa[a][b]=cnta,sb[a][b]=cntb;
// printf("%d %d %d %d\n",a,b,cnta,cntb);
}
ll tim=(tmp-t[a][b])*k,A=cnta-sa[a][b],B=cntb-sb[a][b];
if(tim)
{
ll tmp1=(n-t[a][b]*k)/tim;
A=A*tmp1+sa[a][b],B=B*tmp1+sb[a][b];
tmp=n-t[a][b]*k-tim*tmp1;
tmp=n-tmp;
}
else tmp=0;
// printf("%lld ",tmp);
for(ll i=tmp;i<n;i++)
{
int p=i%k;
if(s[p]=='A') a++;
else b++;
if(a>=11&&a-b>=2)
{
A++,a=b=0;
}
if(b>=11&&b-a>=2)
{
B++,a=b=0;
}
if(a==b&&a>11) a=b=11;
}
printf("%lld:%lld",A,B);
return 0;
}
T3 与或
https://gxyzoj.com/d/hzoj/p/3754
显然，将所有的&放在最前面值最优的，但是要求字典序最小，所以考虑先算出理论最大值，然后进行枚举
假如当前放|不会影响结果，就放，但是如何check
显然，直接枚举会T，考虑前缀和，通过记录每一位上1的个数，从而得到最终结果
代码:
#include<cstdio>
#define ll long long
using namespace std;
int n,k;
ll sum[200001][61],cnt[65],a[200005];
ll check(int st,ll now,int k1)
{
if(st<=n-k1)
{
for(int i=0;i<60;i++) cnt[i]=0;
for(int i=0;i<60;i++) cnt[i]=sum[n-k1][i]-sum[st-1][i];
for(int i=0;i<60;i++)
{
if(cnt[i]!=n-k1-st+1&&((now>>i)&1))
{
now^=(1ll<<i);
}
}
}
if(n-k1+1<=n)
{
for(int i=0;i<60;i++) cnt[i]=0;
for(int i=0;i<60;i++) cnt[i]=sum[n][i]-sum[n-k1][i];
for(int i=0;i<60;i++)
{
if(cnt[i])
{
now|=(1ll<<i);
}
}
}
return now;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
for(int j=0;j<60;j++)
{
sum[i][j]=sum[i-1][j];
if((a[i]>>j)&1) sum[i][j]++;
}
}
ll ans=check(2,a[1],k);
printf("%lld\n",ans);
ll nowk=k,tmp=a[1];
for(int i=2;i<=n;i++)
{
// printf("%d\n",check(i+1,a[i]|tmp,nowk-1));
if(nowk>0&&check(i+1,a[i]|tmp,nowk-1)==ans)
{
printf("|");
tmp=(a[i]|tmp);
nowk--;
}
else
{
printf("&");
tmp=(a[i]&tmp);
}
}
return 0;
}