Preface
打的好鸡啊这把，C写的糙了，100行不说还犯了好多nt错误，最后1min看出来一个符号写反了才过
下次卡题的时候一道题挂三次以上就要换题了的说，这次的D基本一眼秒的，如果先转去做就好了
E是大模拟真心不想写（争取明天Rush了），F后面的根本不敢看
小小地掉了点分，明年再战吧（除夕的那场不知道会不会打）
A. Parallel Projection
按从前后左右四个面哪个面下来讨论一下即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,w,d,h,a,b,f,g;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d%d%d%d%d%d",&w,&d,&h,&a,&b,&f,&g);
int d1=b+g+abs(a-f),d2=d-b+d-g+abs(a-f);
int d3=a+f+abs(b-g),d4=w-a+w-f+abs(b-g);
printf("%d\n",min(min(d1,d2),min(d3,d4))+h);
}
return 0;
}
B. Going to the Cinema
SB题，数组没清空干净WA了一发
考虑枚举去的人数\(t\)，发现所有满足\(a_i\le t-1\)的人是必须去的，且所有满足\(a_i\ge t\)的人是一定不去的
因此开个桶统计下即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],c[N],pfx[N],ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=0;i<=n;++i) pfx[i]=c[i]=0;
for (i=1;i<=n;++i) scanf("%d",&a[i]),++c[a[i]];
for (pfx[0]=c[0],i=1;i<n;++i) pfx[i]=c[i]+pfx[i-1];
for (ans=i=0;i<=n;++i) if ((i?pfx[i-1]:0)==i&&!c[i]) ++ans;
printf("%d\n",ans);
}
return 0;
}
C. Equal Frequencies
我的写法真的烂，狂码100行的答辩调起来真是恶心至极
由于字符集的大小只有\(26\)，因此不妨枚举最后一共出现的字符种类数\(t\)，满足\(1\le t\le2 6\and t|n\)
同时我们统计出原串中出现的字符种类数\(cnt\)，然后讨论一波
- 若\(cnt=t\)，则可以直接把多的补到少的上面
- 若\(cnt>t\)，则我们把前\(cnt-t\)小的字符全部移到后面的字符上，然后套用\(cnt=t\)的方法
- 若\(cnt<t\)，则我们从大往小枚举每种字符，然后把他们超出\(\frac{n}{t}\)的部分尽量多的补到后面即可
然后输出方案的话我的写法就有点烂了，我直接开一个\(26\times 26\)的数组记录下从某个字符变到另一个字符的个数
最后虽然勉强过了但下次写之前还是要想清楚，找到简单的实现方式
复杂度\(O(26^2\times n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
struct element
{
int num,id;
friend inline bool operator < (const element& A,const element& B)
{
return A.num<B.num;
}
}g[30],tg[30],A[30],B[30]; bool v[26],tv[26]; char s[N];
int t,n,c[26],ans,rcd[26][26],trs[26][26],st[26],cnt;
inline int solve(CI tar,CI l,CI r,int cur=0)
{
int ca=0,cb=0; RI i,j; for (i=l;i<=r;++i)
{
if (g[i].num==tar) continue; else
if (g[i].num>tar) A[++ca]=(element){g[i].num-tar,g[i].id};
else B[++cb]=(element){tar-g[i].num,g[i].id};
}
for (i=j=1;i<=ca;++i)
{
while (j<=cb&&A[i].num>=B[j].num)
{
cur+=B[j].num; trs[A[i].id][B[j].id]+=B[j].num;
A[i].num-=B[j].num; B[j++].num=0;
}
if (j>cb) break;
cur+=A[i].num; trs[A[i].id][B[j].id]+=A[i].num;
B[j].num-=A[i].num; A[i].num=0;
}
return cur;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i) ++c[s[i]-'a'];
for (ans=1e9,cnt=0,i=0;i<26;++i) if (c[i]) v[i]=1,g[++cnt]=(element){c[i],i};
sort(g+1,g+cnt+1); memcpy(tg,g,sizeof(g)); memcpy(tv,v,sizeof(v));
for (i=1;i<=26;++i) if (n%i==0)
{
memset(trs,0,sizeof(trs)); memcpy(g,tg,sizeof(g));
int tar=n/i,ret=0,tp; memcpy(v,tv,sizeof(v));
if (cnt==i) ret+=solve(tar,1,cnt); else
{
if (cnt>i)
{
int p=cnt-i+1; for (j=1;j<=cnt-i;++j)
{
while (p<=cnt&&tar-g[p].num<=g[j].num)
{
tp=tar-g[p].num; ret+=tp;
trs[g[j].id][g[p].id]+=tp;
g[j].num-=tp; g[p++].num=tar;
}
if (p>cnt) break;
tp=g[j].num; ret+=tp;
trs[g[j].id][g[p].id]+=tp;
g[j].num=0; g[p].num+=tp;
}
ret+=solve(tar,cnt-i+1,cnt);
} else
{
int lst=0; for (j=cnt+1;j<=i;++j)
{
while (v[lst]) ++lst; v[lst]=1; g[j]=(element){0,lst};
}
int p=cnt+1; for (j=cnt;j>=1;--j)
{
while (p<=i&&tar-g[p].num<=g[j].num-tar)
{
tp=tar-g[p].num; ret+=tp;
trs[g[j].id][g[p].id]+=tp;
g[j].num-=tp; g[p++].num=tar;
}
if (p>i) break;
tp=g[j].num-tar; ret+=tp;
trs[g[j].id][g[p].id]+=tp;
g[j].num=tar; g[p].num+=tp;
}
ret+=solve(tar,1,i);
}
}
if (ret<ans) ans=ret,memcpy(rcd,trs,sizeof(rcd));
}
for (i=0;i<26;++i) c[i]=v[i]=st[i]=0;
for (printf("%d\n",ans),i=1;i<=n;++i)
{
int ch=s[i]-'a'; while (st[ch]<26&&!rcd[ch][st[ch]]) ++st[ch];
if (st[ch]<26) s[i]=st[ch]+'a',--rcd[ch][st[ch]]; putchar(s[i]);
}
putchar('\n');
}
return 0;
}
D. Many Perfect Squares
这个\(n\le 50\)的题我还以为是meet in middle来着，后面发现就是个Brute Force
一次考虑太多数不方便，我们考虑对于某对\(a_i,a_j\ (i<j)\)，使得它们同时为完全平方数的\(x\)怎么快速找出
不妨设\(a_i+x=M^2,a_j+x=N^2\)，等式两边相减得到\(a_j-a_i=N^2-M^2=(N+M)(N-M)\)
由于\(a_j-a_i\)的约数个数是\(\sqrt{10^9}\)量级的，因此我们可以暴枚然后找到所有合法的\(M,N\)
这样我们对于每对\(a_i,a_j\)都找到了若干个\(x\)使得它们同时为完全平方数
那么我们直接把所有可能的\(x\)对应的下标全部存起来，最后枚举每个\(x\)统计答案即可
复杂度大概是\(O(n^2\times \pi(\sqrt{10^9}))\)级别的，总之就是能跑
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,a[N],tot,ans; map <int,int> rst,vis; vector <int> v[1000005];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j,k; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (tot=0,rst.clear(),i=1;i<n;++i) for (j=i+1;j<=n;++j)
{
int tp=a[j]-a[i]; for (k=1;k*k<=tp;++k)
if (tp%k==0)
{
int A=k,B=tp/k; if ((A&1)!=(B&1)) continue;
int C=(B-A)/2,D=C*C-a[i]; if (D<0) continue;
if (!rst.count(D)) rst[D]=++tot;
v[rst[D]].push_back(i); v[rst[D]].push_back(j);
}
}
for (ans=1,i=1;i<=tot;++i)
{
int ret=0; vis.clear(); for (int x:v[i])
if (!vis.count(x)) vis[x]=1,++ret; ans=max(ans,ret);
}
for (i=1;i<=tot;++i) v[i].clear();
printf("%lld\n",ans);
}
return 0;
}