2024icpc武汉站邀请赛F.Custom-Made Clothes（交互题）

       2024 
      
     
       i 
      
     
       c 
      
     
       p 
      
     
       c 
      
     
       武汉站邀请赛 
      
     
       F 
      
     
       . 
      
     
       C 
      
     
       u 
      
     
       s 
      
     
       t 
      
     
       o 
      
     
       m 
      
     
       − 
      
     
       M 
      
     
       a 
      
     
       d 
      
     
       e 
      
     
       C 
      
     
       l 
      
     
       o 
      
     
       t 
      
     
       h 
      
     
       e 
      
     
       s 
      
     
    
   
  
    \Huge{2024icpc武汉站邀请赛F.Custom-Made Clothes} 
   
  
2024icpc武汉站邀请赛F.Custom−MadeClothes

文章目录

题目链接：F. Custom-Made Clothes

题意

本题是一道交互题。

给出一个

     n 
    
   
     × 
    
   
     n 
    
   
  
    n\times n 
   
  
n×n的矩阵， 
 
  
   
    
    
      a 
     
     
     
       i 
      
     
       − 
      
     
       1 
      
     
       , 
      
     
       j 
      
     
    
   
     ≤ 
    
    
    
      a 
     
     
     
       i 
      
     
       , 
      
     
       j 
      
     
    
   
     , 
    
    
    
      a 
     
     
     
       i 
      
     
       , 
      
     
       j 
      
     
       − 
      
     
       1 
      
     
    
   
     ≤ 
    
    
    
      g 
     
     
     
       i 
      
     
       , 
      
     
       j 
      
     
    
   
     ， 
    
   
     ( 
    
   
     1 
    
   
     ≤ 
    
    
    
      a 
     
     
     
       i 
      
     
       , 
      
     
       j 
      
     
    
   
     ≤ 
    
    
    
      n 
     
    
      2 
     
    
   
     ) 
    
   
  
    a_{i-1,j} \le a_{i,j},a_{i,j-1} \le g_{i,j}，(1\le a_{i,j}\le n^2) 
   
  
ai−1,j​≤ai,j​,ai,j−1​≤gi,j​，(1≤ai,j​≤n2)， 
 
  
   
   
     1 
    
   
     ≤ 
    
   
     n 
    
   
     ≤ 
    
   
     1000 
    
   
  
    1\le n \le 1000 
   
  
1≤n≤1000。

题目首先给出

     n 
    
   
     , 
    
   
     k 
    
   
  
    n,k 
   
  
n,k，求矩阵中第k大的值，提供不超过 
 
  
   
   
     50000 
    
   
  
    50000 
   
  
50000次查询。

题目有两种输出：

• ? i j x：表示查询 a i , j ≤ x a_{i,j} \le x ai,j​≤x。返回 0 0 0或 1 1 1。
• ! x：表示输出结果，即 x x x为第 k k k大的值。

思路

通过观察发现，矩阵每行和每列都具有单调性，并且答案具有单调性。

• 因此我们可以二分答案，然后计算出当前答案为第几大的值。
• 在计算当前答案为第几大时，直接计算显然会超过交互次数，因此我们根据每行每列的单调性来计算。
• 对于二分过程中的 m i d mid mid，如果第 i i i行第 j j j列后面都大于 m i d mid mid，那么第 i + 1... n i+1...n i+1...n行第j列后都会大于 m i d mid mid。
• 优化后减少至少一半询问，则不会超过查询次数。

标程

boolquery(int x,int y,int v){
    cout <<"? "<< x <<' '<< y <<' '<< v << endl;fflush(stdout);int t; cin >> t;return t;}voidSolved(){int n, k; cin >> n >> k;
    k = n * n - k +1;int l =1, r = n * n, mid, res =1;while(l <= r){
        mid = l + r >>1;int now = n, tmp =0;for(int i =1; i <= n; i ++){while(now >=1&&query(i, now, mid)==0) now --;
            tmp += now;if(tmp >= k)break;}if(tmp >= k) r = mid -1, res = mid;else l = mid +1;}
    
    cout <<"! "<< res << endl;}