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;
} 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
#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./content-4-395351.html
|
|
|
