CF question making record from July 25th to July 31st

Color the Picture（ GOOD）

The question ： Given a two-dimensional grid matrix . have access to $k$ Color each grid with two colors , Among them the first i Colors can be painted at most $a_i$ Grid (s) . Ask whether there is a way to make at least three of the four grid points above, below, left and right of each grid point completely consistent with its own color .（ Here, the upper, lower, left and right assumptions are circular, that is, assume that the matrix is connected up and down, left and right ）
Ideas ： Due to the symmetry, a grid point is randomly selected and painted with any color , Then randomly choose three grid points of their neighbors and paint them with the same color as themselves . Then I kept trying to know that in order to achieve the goal, every color must be painted 2 Column or 2 That's ok .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

bool solve(int a[],int m,int n,int k)
{
    
    int pre = 0;
    for(int i = k - 1;i>=0;i--)
    {
    
        if(a[i]/n < 2) return false;
        pre += a[i]/n - 2;
        if(2 * (k - i) <= m && (2 * (k - i) + pre)>=m) return true;
    }
    return false;
}


int main()
{
    
    int t;
    scanf("%d",&t);
    for(int i  = 0;i<t;i++)
    {
    
        int n,m,k; scanf("%d%d%d",&n,&m,&k);
        int a[k];
        for(int j=0;j<k;j++)
        {
        
            scanf("%d",&a[j]);
        }
        sort(a,a+k);
        if(solve(a,n,m,k) || solve(a,m,n,k)) printf("YES\n"); else printf("NO\n");
    }
    system("pause");
    return 0;
}

Doremy’s IQ(1600 GOOD)

The question ： Given array a And an integer q. Traversing arrays from front to back a, Set the current traversal to a[i], You can do one of the following ：

• count++. If a[i]>q be q- - Otherwise, do nothing .
• count unchanged

To make count The maximum time corresponds to count++ Of i aggregate .
Data range ：
$len(a)\le 1e^5,1e^9\ge a[i]\ge 1$
Answer key ：
How to analyze the properties of the optimal solution to reduce the search space ？
Find a solution, assume that it is the optimal solution, and see that it first makes q Reduced points ( Assume point $a_q$), If there is a skipped point after this point, let's look at the first skipped point ( Assume point $a_p$), In fact, we skip $a_q$ Instead of skipping $a_p$ The obtained solution must be better than the original assumed optimal solution . By repeating the above steps, it is easy to see that the optimal solution must satisfy a certain point i,i To n Each subscript must count++,i Whether the previous subscript count++ Is only $a_j\le q$ The corresponding subscript j. because i-n We need all of them count++ obviously i The smaller the size, the less points you may skip, that is, the more games you may participate in . Let's find the smallest one in two i that will do .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;


int check(int q,int m,int n,int a[])
{
       
    int count = 0;
    for(int i = 0 ;i < m;i++) if(a[i]<q) count++;
    //q Is your IQ able to maintain all the following 
    count += (n - m);
    for(int i = m;i<n;i++)
    {
    
        if(a[i] <= q) continue;
        else if(a[i] > q)
        {
    
            q--;
            if(q < 0) return -1;
        }
    }
    return count;
}

int main()
{
    
    int t;scanf("%d",&t);
    for(int i =  0;i<t;i++)
    {
    
        int n,q; scanf("%d%d",&n,&q);
        int a[n];
        for(int k = 0;k<n;k++) scanf("%d",&a[k]);
        int l = 0,r = n;
        int ans = 0;
        while(l < r)
        {
    
            int m = (l + r) >> 1;
            int temp = check(q,m,n,a);
            if(temp != -1) r=m; else l = m + 1;
        }
        for(int k  =   0;k<l;k++) if(a[k]<=q) printf("1"); else printf("0");
        for(int k = l;k<n;k++) printf("1"); 
        printf("\n");
    }
    return 0;
}