Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)
A. Parallel Projection
长方体的高是一定会走的，那么只要考虑是如何走哪个侧面，枚举四种情况即可。
void solve(){
int n=read(),m=read(),h=read();
int a=read(),b=read(),c=read(),d=read();
cout<<min(abs(c-a)+min((abs(b)+abs(d)),(abs(m-b)+abs(m-d)))+abs(h),abs(d-b)+min((abs(a)+abs(c)),(abs(n-a)+abs(n-c)))+abs(h))<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
B. Going to the Cinema
首先从小到大排序，显然如果一个人的 \(a[i]\) 大于自己前面的人数即可在自己停下,那么整个序列一定是从前往后取一部分（可以不取）。这样的话只要找前面位置被取而自己可以不被取的位置有几个。
void solve(){
int n=read(),ans=1;
vector<int>a(n+2);
for(int i=1;i<=n;i++){
a[i]=read();
if(a[i]==0&&ans)ans--;
}
sort(a.begin()+1,a.end()-1);
a[n+1]=n+1;
for(int i=1;i<=n;i++){
if(a[i]<=i-1&&a[i+1]>i)ans++;
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
C. Equal Frequencies
可以考虑对于原字符串保留下 \(k\) 个字母。对于 \(n\) 来说，只有可以被整除的 \(k\) 才能成立。对于选取的 \(k\) 也很显然，从大往小取 \(k\) 个，\(k\) 个里多出来的和没被选择的都补充到未满的 \(k\) 个字母里。枚举 \(k\) 即可得到最小值，对于每次记录下要保留的字母是谁就可以输出方案。
PII cnt[30];
int n;
map<int,int>mp;
bool cmp(PII a,PII b){
return a.first>b.first;
}
int cal(int x){
int rst=0,siz=n/x;
mp.clear();
for(int i=1;i<=x;i++){
rst+=max(0,cnt[i].first-siz);
mp[cnt[i].second]++;
}
for(int i=x+1;i<=26;i++){
rst+=cnt[i].first;
}
return rst;
}
void solve(){
n=read();
for(int i=0;i<30;i++){
cnt[i].first=0;
cnt[i].second=i;
}
vector<int>cnp(30);
string s;
cin>>s;
for(auto x:s){
cnt[x-'a'+1].first++;
cnp[x-'a'+1]++;
}
sort(cnt+1,cnt+1+26,cmp);
int ans=inf,nm=-1,chag[30];
for(int i=1;i<=26;i++){
if(n%i==0){
int x=cal(i);
if(ans>x){
ans=x;
nm=n/i;
for(int i=1;i<=26;i++){
chag[i]=mp[i];
}
}
}
}
cout<<ans<<'\n';
vector<int>con(30);
for(auto x:s){
con[x-'a'+1]++;
if(con[x-'a'+1]>nm){
for(int i=1;i<=26;i++){
if(chag[i]==1&&cnp[i]<nm&&con[i]<nm){
cnp[i]++;
cout<<(char)(i+'a'-1);
break;
}
}
}else if(chag[x-'a'+1]==0){
for(int i=1;i<=26;i++){
if(chag[i]==1&&cnp[i]<nm&&con[i]<nm){
cnp[i]++;
cout<<(char)(i+'a'-1);
break;
}
}
}else cout<<x;
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
D. Many Perfect Squares
注意到数据范围和平方数，会想到平方差公式。然后没找到规律就放弃了。
看了题解，事实上确实没规律。但是由平方差公式就可以算让这两个数成为平方数的 \(k\) 是多少，然后枚举所有的 \(pair\) 对，看看哪个 \(k\) 的贡献最大。
int a[N],n;
map<int,int>mp;
void cal(int x){
for(int i=x+1;i<=n;i++){
int d=abs(a[i]-a[x]);
for(int j=1;j*j<=d;j++){
if(d%j==0){
int yy=(j+d/j)/2,xx=(d/j-j)/2;
if(yy*yy-xx*xx==d&&xx*xx>=a[x]) mp[abs(xx*xx-a[x])]++;
}
}
}
}
void solve(){
n=read();
mp.clear();
for(int i=1;i<=n;i++){
a[i]=read();
}
if(n==1){
cout<<1<<'\n';
return ;
}
int ans=0;
for(int i=1;i<=n;i++){
cal(i);
}
int res=0;
for(auto [xx,yy]:mp){
res=max(res,yy);
}
res=ceil(sqrt(res*2));
res=max(res,1ll);
cout<<res<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
E. Rectangle Shrinking
看到题目还是很显然的，答案面积一定是原面积，所以工作主要是去重。
如果是一维上的去重只需要将下一个点的左端点移到上一个点的右端点右边，这里同样是这个思路。首先考虑高度为 \(2\) 的矩形，这种矩形显然越多越好，那么先对这些矩形进行类似于一维的去重。然后排第一层，此时也需要将高度为 \(2\) 的矩形带上，遇到高度为 \(2\) 的大矩形，如果有高度为 \(1\) 的小矩形能在宽度上覆盖它，那么直接把高度为 \(2\) 矩形的第一行删掉，否则保留全部大矩形，向前修改与大矩形有重合面积的小矩形，可以用双指针实现。第二行同理。
struct node{
int u,d,l,r;
}rag[N];
bool cmp(int a,int b){
if(rag[a].l==rag[b].l)return rag[a].r<rag[b].r;
return rag[a].l<rag[b].l;
}
void solve(){
int n=read();
for(int i=1;i<=n;i++){
rag[i].u=read();
rag[i].l=read();
rag[i].d=read();
rag[i].r=read();
}
vector<int>big;
for(int i=1;i<=n;i++){
if(rag[i].u==1&&rag[i].d==2){
big.push_back(i);
}
}
sort(big.begin(),big.end(),cmp);
int nowr=0;
for(auto x:big){
if(rag[x].r<=nowr)rag[x]=(node){0,0,0,0};
else {
rag[x].l=max(rag[x].l,nowr+1);
nowr=rag[x].r;
}
}
vector<int>sma;
for(int i=1;i<=n;i++){
if(rag[i].u==1){
sma.push_back(i);
}
}
sort(sma.begin(),sma.end(),cmp);
nowr=0;
int dq=0;
for(int i=0;i<sma.size();i++){
int x=sma[i];
if(rag[x].d==2){
if(rag[x].r<=nowr){
rag[x].u=2;
}else{
for(;dq<i;dq++){
if(rag[sma[dq]].r>=rag[x].l){
rag[sma[dq]].r=rag[x].l-1;
}
}
nowr=rag[x].r;
}
continue;
}
if(rag[x].r<=nowr)rag[x]=(node){0,0,0,0};
else {
rag[x].l=max(rag[x].l,nowr+1);
nowr=rag[x].r;
}
}
sma.clear();
for(int i=1;i<=n;i++){
if(rag[i].d==2){
sma.push_back(i);
}
}
sort(sma.begin(),sma.end(),cmp);
nowr=0;dq=0;
for(int i=0;i<sma.size();i++){
int x=sma[i];
if(rag[x].u==1){
if(rag[x].r<=nowr){
rag[x].d=1;
}else{
for(;dq<i;++dq){
if(rag[sma[dq]].r>=rag[x].l){
rag[sma[dq]].r=rag[x].l-1;
}
}
nowr=rag[x].r;
}
continue;
}
if(rag[x].r<=nowr)rag[x]=(node){0,0,0,0};
else {
rag[x].l=max(rag[x].l,nowr+1);
nowr=rag[x].r;
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(rag[i].u>rag[i].d||rag[i].l>rag[i].r){
rag[i]=(node){0,0,0,0};
}
if(rag[i].u&&rag[i].r&&rag[i].d&&rag[i].l)ans+=(rag[i].r-rag[i].l+1)*(rag[i].d-rag[i].u+1);
}
cout<<ans<<'\n';
for(int i=1;i<=n;i++){
cout<<rag[i].u<<" "<<rag[i].l<<" "<<rag[i].d<<" "<<rag[i].r<<'\n';
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}