20190817

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;} 

来源：https://www.icode9.com/content-4-395351.html