憋问我为什么今天发 昨天慌着出去耍忘了存...今天重打
就很烦 不知道markdown的格式哪里炸了... 在Typora上好好的在博客园上就炸了
翻转游戏
如图，有这样一个4*4的棋盘。每次可以操作一个棋子，这个棋子本身及其周围四个方向的棋子（如果存在）都会被翻转，翻转即由黑变白由白变黑。问最少需要多少步能够使所有棋子都变成同种颜色。
emmm我写的状压dp 反正数据小随便乱搞
大佬说第一排的方案确定了下面的方案也就都确定了
我的状压
#include
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=1000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int a[10][10],f[1<<20],st=0;
char aa[10][10];
template void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int qsta(int i,int j,int sta){
sta^=(1<<((i<<2)+j))^(1<<(((i+1)<<2)+j))^(1<<((i<<2)+j+1));
if(i==3) sta^=(1<<(((i+1)<<2)+j));
if(i) sta^=(1<<(((i-1)<<2)+j));
if(j==3) sta^=(1<<((i<<2)+j+1));
if(j) sta^=(1<<((i<<2)+j-1));
return sta;
}
int main(){
//freopen("T1.txt","r",stdin);
//freopen("xor.out","w",stdout);
for(int i=0;i<4;++i) scanf("%s",aa[i]);
memset(f,inf,sizeof(f));
for(int i=0;i<4;++i)
for(int j=0;j<4;++j)
if(aa[i][j]=='b') st^=(1<<((i<<2)+j));
f[st]=0;
for(int i=0;i<4;++i)
for(int j=0;j<4;++j){
for(int sta=0;sta<1<<16;++sta)
if(f[sta]!=inf){
int to=qsta(i,j,sta);
f[to]=Min(f[to],f[sta]+1);
}
}
int ans=Min(f[0],f[(1<<16)-1]);
if(ans==inf) puts("Impossible");
else printf("%d",ans);
return 0;
} dalao's
//ID: LRL52 Date: 2019.8.17
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include
using namespace std;
const int N = 155, M = 2055;
const int inf = 0x3f3f3f3f;
char s[N];
int a[N][N], b[N][N], ans = inf, nowans, cnt;
void flip(int i, int j){
++nowans;
b[i][j] ^= 1;
if(i > 0) b[i - 1][j] ^= 1;
if(j > 0) b[i][j - 1] ^= 1;
if(i < 3) b[i + 1][j] ^= 1;
if(j < 3) b[i][j + 1] ^= 1;
}
void Solve(int color){
for(int i = 0; i < (1 << 4); ++i){
memcpy(b, a, sizeof(a)); nowans = 0;
for(int j = 0; j < 4; ++j)
if((1 << j) & i) flip(0, 3 - j);
for(int j = 1; j < 4; ++j)
for(int k = 0; k < 4; ++k)
if(b[j - 1][k] != color) flip(j, k);
cnt = 0;
for(int j = 0; j < 4; ++j)
for(int k = 0; k < 4; ++k)
cnt += b[j][k] == color;
if(cnt == 16) ans = min(ans, nowans);
}
}
int main(){
//freopen("game.in", "r", stdin);
//freopen("game.out", "w", stdout);
rep(i, 0, 3){
scanf("%s", s);
rep(j, 0, 3)
a[i][j] = s[j] == 'w' ? 0 : 1;
}
Solve(0);
Solve(1);
if(ans != inf) printf("%d
", ans);
else puts("Impossible");
return 0;
} 岛屿
从前有一座岛屿，这座岛屿是一个长方形，被划为N*M的方格区域，每个区域都有一个确定的高度。不幸的是海平面开始上涨，在第i年，海平面的高度为t[i]。如果一个区域的高度小于等于海平面高度，则视为被淹没。那些没有被淹没的连通的区域够成一个连通块。现在问第i年，这样的连通块有多少个。 例如：第一年海平面高度为1，有2个连通块。 第二年海平面高度为2，有3个连通块。 
我想到了倒着做并查集的(我爱lch) 但...我居然没有想出来怎么处理连通块的个数
然后就打了个暴力 它还炸了
倒着来每次将冒出来的点加入 然后发现它和之前的连通块连在一起 就数量减一
然后从三点调到五点死都没看出来我把数组h大小开成N了...
30昏
#include
using namespace std;
#define ll long long
#define rg register
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=3000+5,M=1e5+5,inf=0x3f3f3f3f,P=19650827;
int n,m,t,tot,mx,mn=inf,h[N*N],a[M],ans[M];
int cnt=0,bl[N*N];
template void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
void print(int x,int k){
if(x>tot) return;
if(x+m<=tot&&!bl[x+m]&&h[x+m]>a[k]) bl[x+m]=bl[x],print(x+m,k);
if(x>m&&!bl[x-m]&&h[x-m]>a[k]) bl[x-m]=bl[x],print(x-m,k);
if(x%m&&!bl[x+1]&&h[x+1]>a[k]) bl[x+1]=bl[x],print(x+1,k);
if(x>1&&!bl[x-1]&&h[x-1]>a[k]) bl[x-1]=bl[x],print(x-1,k);
}
int main(){
//freopen("T2.txt","r",stdin);
//freopen("xor.out","w",stdout);
rd(n),rd(m),tot=n*m;
for(int x=1;x<=tot;++x) rd(h[x]),mx=Max(mx,h[x]),mn=Min(mn,h[x]);
rd(t);
for(int i=t;i;--i) rd(a[i]);
for(int k=1;k<=t;++k){
if(a[k]>=mx) continue;
if(a[k]
100昏
#include
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=3000+5,M=1e5+5,inf=0x3f3f3f3f,P=19650827;
int n,m,T,H,tot,ans,t[M],h[N*N],Ans[M];
template void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
struct node{
int hei,id;
bool operator<(const node&A)const{return hei>A.hei;}
}a[N*N];
int f[N*N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void Union(int x,int y){
if(h[x]<=H) return;
if(find(x)!=find(y)) --ans,f[f[x]]=f[y];
}
void inser(int id){
if(id%m) Union(id+1,id);
if((id-1)%m) Union(id-1,id);
if(id>m) Union(id-m,id);
if(id+m<=tot) Union(id+m,id);
}
int main(){
// freopen("T2.txt","r",stdin);
//freopen("xor.out","w",stdout);
rd(n),rd(m),tot=n*m;
for(int i=1;i<=tot;++i) rd(h[i]),a[i].id=f[i]=i,a[i].hei=h[i];
sort(a+1,a+tot+1);
rd(T);
for(int i=T;i;--i) rd(t[i]);
int pos=1;
for(int i=1;i<=T;++i){
H=t[i];
while(pos<=tot&&a[pos].hei>H) ++ans,inser(a[pos++].id);
Ans[i]=ans;
}
for(int i=T;i;--i) printf("%d ",Ans[i]);
return 0;
}
吴神的择偶原则
给出Ｎ个数，求每一个数中与其它数相与的结果为0，如果有多个，选最大的，如果没有输出0
80昏
#include
using namespace std;
#define ll long long
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=1e6+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,a[N],f[N];
template void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int main(){
freopen("T3.txt","r",stdin);
freopen("xor.out","w",stdout);
rd(n);
for(int i=1;i<=n;++i) rd(a[i]);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) if(!(a[i]&a[j])) f[i]=Max(f[i],a[j]),f[j]=Max(f[j],a[i]);
for(int i=1;i<=n;++i) printf("%d ",f[i]);
return 0;
}
正解
正难则反：一个数A，取反为B，对于C，如果A&C=0 , 则有C|B=B
dp[B] = max(dp[C]) C满足C|B=B
这几天疯狂把数组大小开小
#include<bits/stdc++.h>
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=1e6+5,M=150000+5,inf=0x3f3f3f3f,P=19650827;
int n,mx,a[N],f[1<<21];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int main(){
freopen("T3.txt","r",stdin);
// freopen("xor.out","w",stdout);
rd(n);
for(int i=1;i<=n;++i) rd(a[i]),f[a[i]]=a[i],mx=Max(mx,a[i]);
int cnt=0;
while((1<<cnt)<=mx) ++cnt;
for(int i=0;i<(1<<cnt);++i)
for(int j=0;j<cnt;++j)
if(!((1<<j)&i)) f[i|(1<<j)]=Max(f[i|(1<<j)],f[i]);
for(int i=1;i<=n;++i) printf("%d ",f[((1<<cnt)-1)^a[i]]);
return 0;
}
summary
- 这次真的很水
- 脑子容易短路