CF 7月25日-7月31日做题记录

Color the Picture（ GOOD）

题意： 给定二维网格矩阵。可以使用$k$种颜色给每个网格涂色，其中第i种颜色至多可涂$a_i$个网格。问是否存在一种方法使得每个格点上下左右四个格点至少有三个格点与其自身颜色完全一致。（这里的上下左右假设是环状的上下左右即假设矩阵上下相连左右相连）
思路：由于有对称性所以随机选一格点涂上任意一种颜色，然后随机选其邻居三个格点涂上与其自身同样的颜色。然后不断试探可知要想达成目标必须每种颜色能图满涂上2列或2行。

#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)

题意：给定数组a和一整数q。从前往后遍历数组a，设当前遍历到a[i],可以进行下列操作之一：

• count++。如果a[i]>q则q- -否则什么都不做.
• count不变

求使得count最大时对应count++的i集合。
数据范围：
$len(a)\le 1e^5,1e^9\ge a[i]\ge 1$
题解：
如何分析最优解所满足的性质减小搜索空间呢？
找一个解假定他是最优解并看他第一个使得q减少的点(假定为点$a_q$)，在此点之后若有跳过的点我们看第一个跳过的点(假设为点$a_p$)，实际上我们跳过$a_q$转而去不跳过$a_p$得到的解肯定必原来假定的最优解更优。重复执行上述步骤容易看出最优解必须满足的性质是有某个点i，i到n每个下标均要count++,i之前下标是否count++仅是$a_j\le q$对应的下标j.由于i-n全部都要count++显然i越小则可能跳过的点越少即可能参与的比赛越多。我们二分查找这样的最小的i即可。

#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的智商是否能够维持住接下来的所有
    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;
}