EX1 翻转游戏

如图，有这样一个4*4的棋盘。每次可以操作一个棋子，这个棋子本身及其周围四个方向的棋子（如果存在）都会被翻转，翻转即由黑变白由白变黑。问最少需要多少步能够使所有棋子都变成同种颜色。

【输入】

输如一个4*4的矩阵，w表示白色，b表示黑色，不会出现其他字符。

【输出】

输出只有一行，包含所求的最小步数。

---

 

咦，等于4，我就算搜也就2^16=65536

还想什么，看我一发暴力把他A了

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

int dx[6]={0,0,1,-1,0,0},dy[6]={0,0,0,0,1,-1};
int n,m,col[10][10],vis[10];
int ans=17;

inline void dfs(int x,int y,int sum)
{
    
    if(sum>=ans)re;
    
    vis[0]=0,vis[1]=1;
    inc(i,1,4)inc(j,1,4)vis[col[i][j]]=1;
    if(!vis[0]||(!vis[1]))
    {
        ans=sum;re ;
    }
    
    int flag=1,j;
    inc(i,x,4)
    {
         if(flag)flag=0,j=y+1;
         else j=1;
        for(j;j<=4;++j)
        {
            inc(k,1,5)
            {
                int nx=i+dx[k],ny=j+dy[k];
                if(nx<1||ny<1||nx>4||ny>4)continue;
                col[nx][ny]^=1; 
            }
            dfs(i,j,sum+1);
            inc(k,1,5)
            {
                int nx=i+dx[k],ny=j+dy[k];
                if(nx<1||ny<1||nx>4||ny>4)continue;
                col[nx][ny]^=1; 
            }
        }
        
    }
}
int main()
{
     char ss[10];
    inc(i,1,4)
    {
        scanf("%s",ss+1);
        inc(j,1,4)
        if(ss[j]=='b')col[i][j]=1;
        else col[i][j]=0;
    }
    
    dfs(0,4,0);
    
    if(ans==17)printf("Impossible");
    else printf("%d",ans);
    re 0;
} 

咦，怎么只有80

 

       vis[0]=0,vis[1]=1;

想想就后怕，我还有80？？？

数据有多水，人就有多水

EX2 岛屿

从前有一座岛屿，这座岛屿是一个长方形，被划为N*M的方格区域，每个区域都有一个确定的高度。不幸的是海平面开始上涨，在第i年，海平面的高度为t[i]。如果一个区域的高度小于等于海平面高度，则视为被淹没。那些没有被淹没的连通的区域够成一个连通块。现在问第i年，这样的连通块有多少个。 例如：第一年海平面高度为1，有2个连通块。 第二年海平面高度为2，有3个连通块。

【输入】

第一行包含两个数N,M。

接下来是一个N*M的矩阵，第i行第j列表示这个格子的高度h[i][j]

接下来是一个数T，表示有T天，

最后一行有T个数，第i个数表示第i天的水位高度。（保证是递增的）

【输出】

输出包含一行T个数，第i个数表示第i天的连通块个数。

---

 

连通块？并查集十有八九了。

cut the relation between a and b

倒着做就好了

等一下，这数据范围900万？

算了算了

卡一下空间，手动计算

随便写了写，手动对拍了好久

嗯，我一定是对的

80？

nmggo

又怎么了

第一组数据竟然与第十组数据是一样的小数据

我竟然都错了

看了看，没维护天数倒叙的合法性

QAQ

小细节好多

#include<bits/stdc++.h>
#define re return
#define dec(i,l,r) for(int i=l;i>=r;--i) 
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

const int maxn=3005,maxt=100005;
int n,m,T,t[maxt],ans[maxt],fa[maxn*maxn];

int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
struct node{
    int x,val;
    bool operator<(node a)const
    {
        re val>a.val;
    }
}a[maxn*maxn];


inline int find(int x)
{
    re x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
    rd(n);rd(m);
    inc(i,1,n)
    {
        int v=(i-1)*m;
        inc(j,1,m)
        {
            rd(a[v+j].val);
            a[v+j].x=v+j;
        }
    }
    
    rd(T);
    inc(i,1,T)
    rd(t[i]);
    
    sort(a+1,a+n*m+1);
    int j=T;
    for(int i=1;i<=n*m;++i)
    {
        int f=0;
        while(a[i].val<=t[j])
        {
            --j;
            if(!j)
            {
                f=1;
                break;
             } 
　　　　//就是这个地方
            ans[j]=ans[j+1];
        }
        
        if(f)break;
        ++ans[j];
        fa[a[i].x]=a[i].x;
        int y=a[i].x%m;
        if(!y)y=m;
        int x=(a[i].x-y)/m+1;
        for(int k=1;k<=4;++k)
        {
            int nx=(x+dx[k]),ny=y+dy[k];
            if(nx<1||ny<1||nx>n||ny>m)continue;
            nx=(nx-1)*m+ny;
            if(!fa[nx])continue;
            int f1=find(a[i].x),f2=find(nx);
            if(f1!=f2)
            {
                --ans[j];
                fa[f1]=f2;
            }
        }
    }
    
    dec(k,j-1,1)ans[k]=ans[j];
    inc(i,1,T)
    printf("%d ",ans[i]);
    re 0;
}

EX3 吴神的择偶选择

【问题描述】

吴神最常做的一件事,就是在自己的寝室里,仰望着纯白的天花板,寂寞空弹一曲东方花烛夜。

已经成为神的吴神,有无数的fans,也不乏默默爱慕着他的小正太萝莉,但是这些人吴神都不能成为吴神的另一半(吴神表示有自己的原则,不是因为看不上别人),所以虽然早已到了谈婚论嫁的年龄,吴神还是孑然一身。

吴神喜欢哲学,但也不排斥异性恋.无聊的时候,看看集训队里谁和谁比较适合,就成了吴神消磨时间的方式。

在吴神眼里,每个人都有不同的优点,比如高,富,帅,....这些优点被吴神量化成了一个2进制数,每一位表示一种优点是否在这个人身上存在,吴神认为,两个人的优点是不应该有交集的,否则就是浪费!!这对注重效率的吴神是坚决不允许的.比如孜孜的优点可以表示成(1011010) (1011010) ,匀匀的可以表示成(0100100),(1011010)&(0100100)==0(0100100),(1011010)&(0100100)==0 (没有交集),因此在吴神眼里匀匀和孜孜是适合的.吴神是(11111......111111) (11111......111111) ,所以吴神和谁都不合适,因为没有人是没有优点的。

现在吴神要做的事就是:根据每个人的特征值,在给出的n个人中找到与这个人合适的人,如果有多个,输出特征值最大的那一个,一个人可以被多个人配对.如果没有,输出0。

【输入】

第一行为一个n,表示总的人数.第二行是n个数,表示每个人的特征值ai

【输出】

输出一行包含N个数，为每个人对应合适的人的最大特征值

---

 

打表，dp,找规律

个鬼哟！

先打了个n^2的暴力，又打了个满心以为正确的dfs;

拍了会，发现dfs,还没我暴力快

算了，暴力交了一发，竟然水到90pts

正解

正难则反

对于一个数a,如果1111111111……^a=b;

且 b|c=b;

我们可以认为a&c=0

然后你在遍历乱搞一下，差不多就得了

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

int a[1500005],b[1500005];
//a表示原数，b表示包含b[i]的数
 
int main()
{
    freopen("in.txt","r",stdin);
    int n,maxx=0;
    rd(n);
    inc(i,1,n)
    {
        rd(a[i]);
        maxx=max(a[i],maxx);
        b[a[i]]=a[i];
        //存在，初始化 
    }
    
    int cnt=0;
    while((1<<cnt)<=maxx)++cnt;
    
    
    
    inc(i,0,(1<<cnt))
    {
        inc(x,0,cnt)
        if(!((1<<x)&i))
        b[i|(1<<x)]=max(b[i|(1<<x)],b[i]);
        //最大可行解 
    }
    
    inc(i,1,n)
    printf("%d ",b[((1<<cnt)-1)^a[i]]);
    //取反 
    re 0;
}