7.3
一直想挑个好日子开始写做题纪要，防止自己太颓，但是咕了很久。
今天也并不是什么好日子，只是不想再咕了。
不是怎么突然就高二了啊啊啊啊啊。
CF1552H Guess the Perimeter
以为只有 \(4\) 次询问次数会有什么逆天不平凡做法，结果还是二分，不过还是比较牛。
将原本一个格点看做一个格子，设矩形长为 \(a\)，宽为 \(b\)。
先询问所有格子求矩形面积 \(s\)。然后考虑只询问纵坐标为奇数的格子，设返回值为 \(k\)。当 \(b\) 为奇数时，\(k=\dfrac{b\pm 1}{2}\times a\)，又有 \(s=a\times b\)，可得 \(a=\left\vert s-2k \right\vert\)。尽管 \(b\) 为偶数时没法直接做出，但是可以给我们一定启发。
我们将 \(b\) 分解成 \(2^m\times r(2\nmid r)\) 的形式，设 \(k_i\) 为只询问纵坐标 \(\bmod 2^i=1\) 的格子的返回值，那么 \(a=\left\vert k_m-2k_{m+1} \right\vert\)。于是现在要求 \(m\)，直接二分即可，当 \(k_i\times 2^i=s\) 时 \(i\leq m\)。
先查询一次 \(s=k_0\)，剩下二分一下刚好 \(3\) 层，同时由于只在 \([1,7]\) 中二分了 \(3\) 层可以保证 \(k_{m+1}\) 也询问过。注意由于一开始格点转成了格子所以最后要减去四个角。
点击查看代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
int ans,t[10],a,b;
inline int query(int B)
{
cout<<"? "<<(200+B-1)/B*200<<endl;
for(int i=1;i<=200;i+=B)
for(int j=1;j<=200;++j)
cout<<i<<' '<<j<<' ';
cout<<endl;int k;cin>>k;return k;
}
signed main()
{
t[0]=query(1);int l=1,r=7;
while(l<=r)
{
int mid=(l+r)>>1;
t[mid]=query(1<<mid);
if(t[mid]*(1<<mid)==t[0])
ans=mid,l=mid+1;
else r=mid-1;
}
b=abs(t[ans]-2*t[ans+1]),a=t[0]/b;
cout<<"! "<<(a+b)*2-4<<endl;return 0;
}
CF1610G AmShZ Wins a Bet
结论是每次删去的一定是一对匹配的括号，不然可以通过调整法证明不会变劣。
然后只需要从后往前贪心，一个点最多从两个方向转移过来。维护只考虑 \(i\) 后缀的情况下，操作后字典序最小的字符串，倍增一段的哈希值，然后比较两个字符串字典序只需要跳到第一个哈希值不一样的位置。时间复杂度 \(O(n\log n)\)。
点击查看代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#define ll long long
using namespace std;
const int MAXN=3e5+10,mod=1e9+97;
string s;int n,t[MAXN],top;ll b[20];
int dep[MAXN],f[MAXN][20],g[MAXN][20];
inline bool cmp(int x,int y)
{
for(int i=19;~i;--i)
{
if(!f[x][i]||!f[y][i]) continue;
if(g[x][i]==g[y][i]) x=f[x][i],y=f[y][i];
}
if(!f[x][0]||!f[y][0]) return dep[x]<=dep[y];
return g[x][0]<g[y][0];
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
b[0]=3;for(int i=1;i<20;++i)
b[i]=b[i-1]*b[i-1]%mod;
cin>>s;n=s.size(),s=' '+s;
for(int i=n;i;--i)
{
dep[i]=dep[f[i][0]=i+1]+1,g[i][0]=s[i]-'(';
for(int j=1;j<=__lg(dep[i]);++j)
f[i][j]=f[f[i][j-1]][j-1],
g[i][j]=(g[f[i][j-1]][j-1]*b[j-1]+g[i][j-1])%mod;
if(s[i]==')'){t[++top]=i;continue;}
if(!top) continue;int R=t[top]+1;--top;
if(cmp(i,R)) continue;dep[i]=dep[R];
memcpy(f[i],f[R],sizeof(f[i]));
memcpy(g[i],g[R],sizeof(g[i]));
}
for(int p=1;f[p][0];p=f[p][0])
cout<<(char)(g[p][0]+'(');
cout<<'\n';return 0;
}