GDCPC2023 游寄

xujindong_ · 2023-05-15 22:27:57 · 个人记录

Day -?

mzx 邀请组队，后来加了 lhn。队名叫钢铁是怎样炼成的，寓意打铁。

Day -1

Educational Codeforces Round 148 不会 C，狂下百分，警钟撅烂。感觉每次打比赛前后 CF 都会寄。气死我了。至少一段时间内会改打 AT。

Day 0

热身赛。

对面坐的是铁一和华附的几个巨佬，压迫感很强。

A：一个长 n 的序列划分为 k 段，求每段种类数之和的最大值。

B：5\times n 的矩阵，值为 0,1，用 3\times 3 的矩形覆盖所有为 1 的点的最小个数。

C：签到模拟，题面太长忘了。

D：\sum_{i=1}^n\sum_{j=1}^n\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}

lhn 看清题意后切了 C。

mzx 又切了 D，并说莫反很简单。

尝试切 B，试着 dp 但写挂，贡献三发罚时。换成 mzx 写，又吃三发罚时。A 感觉是决策单调性优化 dp 之类的，没想出。最后 2 AC 离场。全队唯一负贡献，我是 LZOI 之耻，回去得恶补数论了。

对面铁一一队 AK 了，orz。

Day 0

正式赛。

A：比赛从 y_1 年开始办，一年一次，有若干年不办，问 y_2 年是第几届。

B：长 n 序列，m 个区间，要求选一些点使每个区间内都有点，求最小代价。

C：n 家店，第 i 家买卖价格为 a_i，可以买卖 b_i 次，求最大利润。

D：n 个人住 m 间房，第 i 个人有邻居的满意度为 a_i，没邻居的满意度为 b_i，求最大满意度。

E：n 个字符串中选 k 个，最小化字典序最大的两两的 \operatorname{lcp}。

F：长 n 序列，有权值和颜色，单点修改权值或颜色，或给定开始点和一个颜色集合，只能向左右走颜色集合内的点，求能走到的权值和。

G：长 n 序列，交换两个位置最大化 \max_{1\leq k<n}\{\operatorname{and}_{i=1}^k a_i+\operatorname{and}_{i=k+1}^n a_i\}。

H：长 n 序列，初始为 0，m 个操作会将两个位置赋值为 1 或 2，安排操作顺序使权值和最大。

I：n\times m 的矩阵，0\sim n\times m-1 的数各出现一次，求从左上走最短路径到右下经过位置权值最大的 \operatorname{mex}。

J：给 x,y,A,B，求 a\leq A,a\leq B 使 x 在 a 进制和 y 在 b 进制下的表示相同。

K：独立钻石

L：一张完全图，给定一些边的权值，如果一条边的权值没有给定则为编号之差，求最小生成树。

M：一个凸多边形，连接一条对角线使分成的两个多边形的直径和最小。

A 是签到，枚举即可。5 min 切了。

mzx 开了 F，写了一个分块套 bitset，T 了。

我写 C，显然可以贪，低价买入高价卖出，双指针模拟即可。

然后 mzx 写 I，二分答案，检查路径是否满足只往右或下即可。不过看他的做法还用到了树状数组，不太看得懂。总之过了。

尝试写 E，把串扔进 Trie 里，在 Trie 上贪心。结果 WA 了，吃了若干发罚时。

mzx 写 K，这题满足 n,m,k\leq 6，直接搜即可。

lhn 想出了 D，就是先假设全部隔开，再取 a_i-b_i 最大的一些成为邻居。扫一遍处理出所有可能的有邻居数的答案，对能塞进 m 个房里的情况取 min。

mzx 写 B，搞出来一个 dp 式，结果写了一个神秘的最短路，吃了若干发罚时。

我继续调 E，又吃若干发罚时，最后 B、E、F 都挂了。5AC 离场。

中间还想过 J 和 L。J 应该是根号分类讨论，分成两位和两位以上两种，L 完全图最小生成树大概是 Borůvka。结果 J 没推出来两位的根号做法，L 直接就想不动了。

结果竟然 rk82 打银，有点意外。本来以为这么寄的一次也许是打铁或铜，结果 5AC 很多，而且别的队罚时更多，踩线 Ag。cyr 他们队（哈姆） rk33 差点 Au，%。zc 他们队（铁牌分界线）罚时更多，打铜了。

Day ?

可以在 gym104369 评测。

A：看 y_2 之前有几个年份没办。年份完全可以开 1e18。

#include<bits/stdc++.h>
using namespace std;
int t,t1,n,s[105],t2;
int main(){
  cin>>t;
  while(t--){
    cin>>t1>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)cin>>s[i];
    cin>>t2;
    for(int i=1;i<=n;i++)cnt+=s[i]<t2;
    cout<<t2-t1+1-cnt<<'\n';
  }
  return 0;
}

B：设 f_i 为前 i 个位置，第 i 个位置建了基站的最小代价，枚举上一个基站，有 f_i=\min_{j=p_{i-1}-1}^{i-1}f_j+a_i，其中 p_i 表示最晚的位置使 [p_i,i] 没有完整的区间。然后就可以单调队列优化了。

官方题解求 p 用的是双指针。感觉麻烦了，只要对右端点小于等于 i 的区间的左端点取 \max 即可。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a)
{
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args)
{
  in(a),in(args...);
}
int t,n,m,p[500005],q[500005],bp,fp;
long long a[500005],f[500005];
vector<int>e[500005];
int main(){
  in(t);
  while(t--){
    in(n),a[n+1]=0;
    for(int i=1;i<=n;i++)in(a[i]);
    in(m);
    for(int i=1,l,r;i<=m;i++)in(l,r),e[r].push_back(l);
    for(int i=1;i<=n;i++){
      p[i]=p[i-1];
      for(int j=0;j<e[i].size();j++)p[i]=max(p[i],e[i][j]);
    }
    for(int i=1;i<=n+1;i++){
      while(q[bp]<p[i-1]&&bp<=fp)bp++;
      f[i]=f[q[bp]]+a[i];
      while(fp>=bp&&f[q[fp]]>=f[i])fp--;
      q[++fp]=i;
    }
    cout<<f[n+1]<<'\n';
    for(int i=1;i<=n;i++)e[i].clear();
    bp=fp=0;
  }
  return 0;
}

C：每次从最便宜的店买，从最贵的店卖，可以维护两个指针指向当前的两个店。这题卡了输入。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a)
{
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args)
{
  in(a),in(args...);
}
int t,n;
long long ans;
pair<long long,long long>a[1000005];
int main(){
  in(t);
  while(t--){
    in(n);
    for(int i=1;i<=n;i++)in(a[i].first,a[i].second);
    sort(a+1,a+n+1);
    for(int i=1,j=n;i<j;){
      if(a[i].second<a[j].second)a[j].second-=a[i].second,ans+=a[i].second*(a[j].first-a[i].first),i++;
      else if(a[i].second>a[j].second)a[i].second-=a[j].second,ans+=a[j].second*(a[j].first-a[i].first),j--;
      else ans+=a[i].second*(a[j].first-a[i].first),i++,j--;
    }
    cout<<ans<<'\n',ans=0;
  }
  return 0;
}

D：钦定所有人都没有邻居，如果有 k 个人有邻居，就取 a_i-b_i 最大的 k 个变成有邻居，可以扫一遍求出所有 k 的答案，再需要的房子数是否小于等于 m。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a)
{
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args)
{
  in(a),in(args...);
}
int t,n,m;
long long sum,a[500005],b,ans;
int main(){
  in(t);
  while(t--){
    in(n,m);
    for(int i=1;i<=n;i++)in(a[i],b),sum+=b,a[i]-=b;
    sort(a+1,a+n+1,greater<long long>());
    if(2*n-1<=m)ans=sum;
    sum+=a[1];
    for(int i=2;i<=n;i++){
      sum+=a[i];
      if(2*n-i<=m)ans=max(ans,sum);
    }
    cout<<ans<<'\n',sum=ans=0;
  }
  return 0;
}

E：在 Trie 上贪。如果答案就是当前节点，那么每棵子树都只能选一个串，其他串随便选；如果选不到 k 个，就枚举下一个字符，此时这个字符所属的子树和前面的子树可以随便选，后面的子树只能选一个串。找到第一个能选 k 个的字符进入下一层，并减掉这一层选择的串。

#include<bits/stdc++.h>
using namespace std;
int t,n,k,tr[1000005][26],vis[1000005],num[1000005],cnt;
string s;
void insert(string a,int pos=0){
  for(int i=0;i<a.size();i++){
    int t=a[i]-'a';
    if(!tr[pos][t])tr[pos][t]=++cnt;
    num[tr[pos][t]]++,pos=tr[pos][t];
  }
  vis[pos]++;
}
int main(){
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0),cin>>t;
  while(t--){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>s,insert(s);
    int pos=0;
    while(1){
      int t=vis[pos];
      for(int i=0;i<26;i++)if(tr[pos][i])t++;
      if(t>=k){
        puts(pos?"":"EMPTY");
        goto tag;
      }
      for(int i=0;i<26;i++){
        if(tr[pos][i]){
          t+=num[tr[pos][i]]-1;
          if(t>=k){
            putchar(i+'a'),k-=t-num[tr[pos][i]],pos=tr[pos][i];
            break;
          }
        }
      }
    }
    tag:for(int i=0;i<=cnt;i++)memset(tr[i],0,sizeof(tr[i])),vis[i]=num[i]=0;
    cnt=0;
  }
  return 0;
}

F：操作三需要先二分出区间的左右端点再查询区间和，也就是找最后一个位置使得颜色集合里的颜色在区间里的出现次数等于区间长，这可以在数据结构每个节点上开一个哈希表。可以线段树上二分或树状数组上倍增。

如果用线段树上二分需要卡常，不能 pushup，并且要用 pbds。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a)
{
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args)
{
  in(a),in(args...);
}
int tn,n,q,k,c[100005],a[100005];
long long v[100005];
struct node{
  long long v;
  __gnu_pbds::gp_hash_table<int,int>c;
};
template<int maxn>struct SMT{
  node tr[maxn];
  void build(int pos,int nl,int nr,int c[],long long v[]){
    tr[pos].v=0,tr[pos].c.clear();
    for(int i=nl;i<=nr;i++)tr[pos].v+=v[i],tr[pos].c[c[i]]++;
    if(nl==nr)return;
    else{
      int mid=(nl+nr)>>1;
      build(pos<<1,nl,mid,c,v),build(pos<<1|1,mid+1,nr,c,v);  
    }
  }
  void add1(int pos,int nl,int nr,int g,int c,int k){
    tr[pos].c[c]+=k;
    if(nl==nr)return;
    int mid=(nl+nr)>>1;
    if(g<=mid)add1(pos<<1,nl,mid,g,c,k);
    if(g>mid)add1(pos<<1|1,mid+1,nr,g,c,k);
  }
  void add2(int pos,int nl,int nr,int g,long long k){
    tr[pos].v+=k;
    if(nl==nr)return;
    int mid=(nl+nr)>>1;
    if(g<=mid)add2(pos<<1,nl,mid,g,k);
    if(g>mid)add2(pos<<1|1,mid+1,nr,g,k);
  }
  long long query(int pos,int nl,int nr,int gl,int gr){
    if(gl>gr)return 0;
    if(gl<=nl&&nr<=gr)return tr[pos].v;
    int mid=(nl+nr)>>1;
    long long ans=0;
    if(gl<=mid)ans+=query(pos<<1,nl,mid,gl,gr);
    if(gr>mid)ans+=query(pos<<1|1,mid+1,nr,gl,gr);
    return ans;
  }
  int queryl(int pos,int nl,int nr,int g,int k,int a[]){
    if(nl>g)return 0;
    if(nr<=g){
      int cnt=0;
      for(int i=1;i<=k;i++)cnt+=tr[pos].c[a[i]];
      if(cnt==nr-nl+1)return 0;
      if(nl==nr)return nl;
    }
    int mid=(nl+nr)>>1,ans=queryl(pos<<1|1,mid+1,nr,g,k,a);
    return ans?ans:queryl(pos<<1,nl,mid,g,k,a);
  }
  int queryr(int pos,int nl,int nr,int g,int k,int a[]){
    if(nr<g)return 0;
    if(nl>=g){
      int cnt=0;
      for(int i=1;i<=k;i++)cnt+=tr[pos].c[a[i]];
      if(cnt==nr-nl+1)return 0;
      if(nl==nr)return nl;
    }
    int mid=(nl+nr)>>1,ans=queryr(pos<<1,nl,mid,g,k,a);
    return ans?ans:queryr(pos<<1|1,mid+1,nr,g,k,a);
  }
};
SMT<400005>t;
int main(){
  in(tn);
  while(tn--){
    in(n,q);
    for(int i=1;i<=n;i++)in(c[i]);
    for(int i=1;i<=n;i++)in(v[i]);
    t.build(1,1,n,c,v);
    for(int i=1,opt,p,x;i<=q;i++){
      in(opt);
      if(opt==1)in(p,x),t.add1(1,1,n,p,c[p],-1),c[p]=x,t.add1(1,1,n,p,c[p],1);
      else if(opt==2)in(p,x),t.add2(1,1,n,p,x-v[p]),v[p]=x;
      else{
        in(p,k);
        for(int j=1;j<=k;j++)in(a[j]);
        int l=t.queryl(1,1,n,p,k,a),r=t.queryr(1,1,n,p,k,a);
        cout<<t.query(1,1,n,l?l+1:1,r?r-1:n)<<'\n';
      }
    }
  }
  return 0;
}

G：记 f(l,r)=\operatorname{and}_{i=l}^r a_i。记 f(1,i)\ne f(i,i-1) 的 i 为前缀关键点，也就是拿掉这个数对前缀与有影响。一个重要的观察是前缀关键点只有 \log V 个，因为每次出现不同的值说明有若干个位的一变成了零。同理后缀关键点也只有 \log V 个。

分类讨论：

如果交换两个非关键点，由于拿掉关键点不会影响前缀与或后缀与，这相当于前后缀都多与了一个数，一定更劣。

如果交换两个关键点，直接枚举即可，O(n\log^2V)。

如果交换一个关键点 i 和一个非关键点 j，同理选取哪个 j 不影响后缀，所以只需要枚举 i,k，找到使 f(1,i-1)\operatorname{and}f(i+1,k)\operatorname{and}a_j 最大的 j。

其中 i 有 \log V 个，f(i+1,k) 也只有 \log V 个，所以 f(1,i-1)\operatorname{and}f(i+1,k) 只有 \log^2V 个，可以对于每种值记忆化一个后缀 \max 数组。交换后缀关键点同理。复杂度 O(n\log^2V)。

#include<bits/stdc++.h>
using namespace std;
int t,n,a[100005],st[100005][20],lg[100005],t1[20],t2[20],cnt1,cnt2,ans;
unordered_map<int,vector<int>>g1,g2;
void build(int n,int a[]){
  for(int i=1;i<=n;i++)st[i][0]=a[i];
  for(int j=1;1<<j<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=st[i][j-1]&st[i+(1<<(j-1))][j-1];
}
int query(int l,int r){
  return l>r?(1<<30)-1:st[l][lg[r-l+1]]&st[r-(1<<lg[r-l+1])+1][lg[r-l+1]];
}
int query1(int v,int k){
  if(!g1.count(v)){
    g1[v].resize(n+2);
    for(int i=n;i>=1;i--)g1[v][i]=max(g1[v][i+1],v&a[i]);
  }
  return g1[v][k];
}
int query2(int v,int k){
  if(!g2.count(v)){
    g2[v].resize(n+2);
    for(int i=1;i<=n;i++)g2[v][i]=max(g2[v][i-1],v&a[i]);
  }
  return g2[v][k];
}
int main(){
  for(int i=2;i<=100000;i++)lg[i]=lg[i>>1]+1;
  cin>>t;
  while(t--){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(n,a);
    for(int i=1;i<n;i++)ans=max(ans,query(1,i)+query(i+1,n));
    for(int i=1,t=(1<<30)-1;i<=n;i++){
      if((t&a[i])!=t)t1[++cnt1]=i;
      t&=a[i];
    }
    for(int i=n,t=(1<<30)-1;i>=1;i--){
      if((t&a[i])!=t)t2[++cnt2]=i;
      t&=a[i];
    }
    for(int k=1;k<n;k++){
      for(int i=1;i<=cnt1&&t1[i]<=k;i++){
        for(int j=1;j<=cnt2&&t2[j]>k;j++){
          ans=max(ans,(query(1,t1[i]-1)&a[t2[j]]&query(t1[i]+1,k))+(query(k+1,t2[j]-1)&a[t1[i]]&query(t2[j]+1,n)));
        }
      }
    }
    for(int k=1;k<n;k++){
      for(int i=1;i<=cnt1&&t1[i]<=k;i++)ans=max(ans,query1(query(1,t1[i]-1)&query(t1[i]+1,k),k+1)+(query(k+1,n)&a[t1[i]]));
      for(int i=1;i<=cnt2&&t2[i]>k;i++)ans=max(ans,query2(query(k+1,t2[i]-1)&query(t2[i]+1,n),k)+(query(1,k)&a[t2[i]]));
    }
    cout<<ans<<'\n',cnt1=cnt2=ans=0,g1.clear(),g2.clear();
  }
  return 0;
}

H：后面的操作会覆盖前面的操作，考虑时光倒流，此时一个数确定之后不会被更改。

如果一个操作把两个位置改为 2，显然要放在最前。把两个位置改为 1 的操作放在最后。

考虑一个数改成 1，一个数改成 2 的操作的意义。假设将 u 改成 1，v 改成 2。进行这个操作后，v 变成 2，此时如果有一个操作将 v 变成 1，w 变成 2，那么再进行这个操作肯定更优，因为这相当于不花费代价就将 w 变成 2。

同理，对于影响到 w 的操作也可以这么做。这启示我们建图，从变成 1 的点连向变成 2 的点，每次可以选择一个点 DFS，将这个点变成 1，将这个点 DFS 到的点变成 2，并输出 DFS 时访问的边。最优情况是让变成 1 的点最少，则缩点后在所有入度为 0 的强连通分量中各选一个点 DFS 最优。

有特殊情况。在入度为零的强连通分量中，要优先选择被两个数改成 2 的操作影响到的，因为这能够让初始选择的点也变成 2，就白嫖掉了一个 1。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a){
  T cc=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())cc=cc*10+c-'0';
  a=cc;
}
template<typename T,typename... Args>void in(T &a,Args&...args){
  in(a),in(args...);
}
int t,n,m,l[500005],x[500005],r[500005],y[500005],head[500005],cnt=1,num[500005],dfn[500005],low[500005],st[500005],top,cc,d,deg[500005],a[500005],sum;
bool vis[500005];
vector<int>q;
struct edge{
  int v,w,nxt; 
}e[500005];
void add(int u,int v,int w){
  cnt++,e[cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}
void dfs(int pos,edge e[],int head[],int num[]){
  low[pos]=dfn[pos]=++d,st[++top]=pos,vis[pos]=1;
  for(int i=head[pos];i;i=e[i].nxt){
    if(!dfn[e[i].v])dfs(e[i].v,e,head,num),low[pos]=min(low[pos],low[e[i].v]);
    else if(vis[e[i].v])low[pos]=min(low[pos],dfn[e[i].v]);
  }
  if(dfn[pos]==low[pos]){
    cc++;
    do num[st[top]]=cc,vis[st[top]]=0;
    while(st[top--]!=pos);
  }
}
int tarjan(int n,edge e[],int head[],int num[]){
  for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,e,head,num);
  return cc;
}
void dfs1(int pos){
  vis[pos]=1;
  for(int i=head[pos];i;i=e[i].nxt){
    q.push_back(e[i].w);
    if(!vis[e[i].v])dfs1(e[i].v);
  }
}
int main(){
  in(t);
  while(t--){
    in(n,m);
    for(int i=1;i<=m;i++){
      in(l[i],x[i],r[i],y[i]);
      if(x[i]==1&&y[i]==2)add(l[i],r[i],i);
      if(x[i]==2&&y[i]==1)add(r[i],l[i],i);
    }
    for(int i=1;i<=m;i++)if(x[i]==2&&y[i]==2)q.push_back(i);
    tarjan(n,e,head,num);
    for(int i=1;i<=n;i++)for(int j=head[i];j;j=e[j].nxt)if(num[i]!=num[e[j].v])deg[num[e[j].v]]++;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++){
      if(x[i]==2&&y[i]==2){
        if(!deg[num[l[i]]]&&!vis[l[i]])dfs1(l[i]);
        if(!deg[num[r[i]]]&&!vis[r[i]])dfs1(r[i]);
      }
    }
    for(int i=1;i<=n;i++)if(!deg[num[i]]&&!vis[i])dfs1(i);
    for(int i=1;i<=m;i++)if(x[i]==1&&y[i]==1)q.push_back(i);
    for(int i=q.size()-1;i>=0;i--)a[l[q[i]]]=x[q[i]],a[r[q[i]]]=y[q[i]];
    for(int i=1;i<=n;i++)sum+=a[i];
    cout<<sum<<'\n';
    for(int i=q.size()-1;i>=0;i--)cout<<q[i]<<(i?' ':'\n');
    for(int i=1;i<=n;i++)head[i]=num[i]=dfn[i]=deg[i]=a[i]=vis[i]=0;
    cnt=1,cc=d=sum=0,q.clear();
  }
  return 0;
}

I：二分答案，检查是否能找出一条路径含有 0\sim mid-1。可以从上往下枚举这些格子，看有没有格子在另一个格子的左下。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T &a)
{
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename... Args>void in(T &a,Args&...args)
{
  in(a),in(args...);
}
int t,n,m,a[1000005];
bool check(int mid){
  for(int i=1,p=0;i<=n;i++){
    for(int j=1;j<=m;j++){
      if(a[(i-1)*m+j]>=mid)continue;
      if(p>j)return 0;
      p=j;
    }
  }
  return 1;
}
int main(){
  in(t);
  while(t--){
    in(n,m);
    for(int i=1;i<=n*m;i++)in(a[i]);
    int l=0,r=n*m;
    while(l<r){
      int mid=(l+r+1)>>1;
      if(check(mid))l=mid;
      else r=mid-1;
    }
    cout<<l<<'\n';
  }
  return 0;
}

J：考虑根号分类讨论。当 x,y 的进制表示大于两位， a\leq\sqrt x,b\leq\sqrt y；否则 x,y 的进制表示比较简单，可以用数学方法。

当 x,y 的进制表示只有一位，说明 x=y，此时 a=2,b=2 也满足。

当 x,y 的进制表示有两位，枚举高位 t，此时 t 只用枚举到根号。列出所有限制条件：