一些有趣的思维题

· · 个人记录

这篇博客里收录的都是一些个人认为需要一些思维的题目，欢迎各位五分钟爆切这些题的大佬来暴打我。

1.AGC016B Colorful Hats

Step 1: 开上帝视角，发现共有 c 种颜色（注意，c 在后文中是未知的），回到每只猫的视角，如果它的帽子是独一无二的（后文记为“孤独的”），那他看到的颜色数量必然为 c-1 ，否则，他看到的颜色数量必然为 c 。由此我们可以得到第一步结论，当极差大于一时，不可以总司令。

定义最大值 mx, 最小值 mn

Step 2: 分类讨论。先考虑 mx=mn 的情况。如果这些猫都是孤独的，那所有 a_i 的值均为 c-1 ；如果这些猫都不孤独，考虑把他们分组，分组条件是每组至少 2 个，可以知道分组后 mx 的值最大为 n/2 ，判断即可。

Step 3:考虑 mx=mn+1 的情况。首先我们知道，这些猫中，孤独的猫对应的 a_i = mn，不孤独的猫对应 a_i = mx，此时 c=mx。记孤独的猫的个数为 x，其余为 y。考虑每只猫对 c 的贡献，孤独的猫贡献总和显然为 x ，对于不孤独的猫，还是考虑分组，分组条件同上，可知分组后贡献最大值为 y/2 ，最小值为 1，判断即可。

每次判断都是 O(1) 的，时间复杂度为输入复杂度 O(N)

AC代码：

#include<cstdio>
using namespace std; 
int n,a[100005],mx,mn=1e9,x,y;
inline int max(int i,int j){return i>j?i:j;}
inline int min(int i,int j){return i<j?i:j;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        mx=max(mx,a[i]),mn=min(mn,a[i]);
    }
    if(mx-mn>1){printf("No\n");return 0;}
    if(mx==mn){
        if(mx==n-1){printf("Yes\n");return 0;}
        if(mx<=n/2){printf("Yes\n");return 0;}
        printf("No\n");return 0;
    }
    else{
        for(int i=1;i<=n;i++)x+=(a[i]==mn?1:0),y+=(a[i]==mx?1:0);
        if(x+1<=mx&&mx<=x+y/2){printf("Yes\n");return 0;}
        else{printf("No\n");return 0;}
    }
    return 0;
}

2.AGC016C +/- Rectangle

这题据说在谷上原来是个黑，后来一路降降到了绿

最简单的思路，我们考虑把每个满足 x\mod h = 0 且 y \mod w = 0 的点 (x,y) 赋值为 -h \times w ，其余赋值为 1，貌似是可以的。

但有以下反例：

1 3 1 2

按刚才的做法填完后的矩阵为 1 -2 1 ，和为零，不符合要求。考虑把不满足上面的条件的格子填上一个整数 k ，则每一个满足要求的点就应该填 -k \times(h \times w - 1)+1，可过。

AC代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int mod=1e9;
int H,W,h,w,k;
int main(){
    scanf("%d%d%d%d",&H,&W,&h,&w);
    if(H%h==0&&W%w==0)return puts("No"),0;
    printf("Yes\n");
    k=1+rand()%(mod/(H*W));
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            int val=500;
            if(i%h==0&&j%w==0)val=-500*(h*w-1)-1;
            printf("%d ",val);
        }
        printf("\n");
    }
    return 0;
}

3.P4310 绝世好题

DP虐我千百遍，我爱DP如初恋

一个挺有意思的DP题。首先，我们可以轻易地想出类似于最长上升子序列的 90pts 的 O(n^2) 做法。接下来考虑正解。

一般的，这种带有位运算的题，突破口都是位运算。显然的，想要使两个数按位与后值不为零，则必须两个数对应位上都是1。我们考虑把一个数拆解成二进制数，设 F_j 表示第 j 位为1时前方的最长序列长度。

接下来启动转移过程。这个算法是在线进行的。每读入一个数，记录一个值 s，初值为1，然后我们看它每一个为1的位 j，更新 s=max(s, F[j]+1) ，最后把所有的为1的 F_j 更新为 max(F_j,s) 。这里很难说清楚，如有疑问，可参考代码进行理解。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int n,f[35],ans;
int main()
{
    n=read();
    while(n--)
    {
        int x=read(),s=1;
        for(int j=0;j<30;j++)
            if(x&(1<<j))
                s=max(s,f[j]+1);
        for(int j=0;j<30;j++)
            if(x&(1<<j))
                f[j]=max(s,f[j]);
        ans=max(ans,s);
    }
    printf("%d\n",ans);
    return 0;
}