「NOIP模拟赛」人偶师
「题目描述」
n点m双向边的图，每个点有2个状态：开和关。每次操作改变一个点的状态，以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。
「输入格式」
第一行2个整数n,m。
第二行n个整数，第i个数表示第i点的状态，0为关，1为开。
第3..m+2行，每行2个整数a,b，表示a和b直接相连，同一条边不会出现多次。
「输出格式」
第一行一个整数k表示最少的操作次数，所有数据保证至少有一组可行解。
第二行k个整数，表示操作的点的编号。
「样例输入」
4 3
1 1 0 0
2 3
1 3
2 4
「样例输出」
3
1 2 3
「数据范围」
对于30%的数据，1<=n<=10，0<=m<=40
对于60%的数据，1<=n<=30，0<=m<=100
对于100%的数据，1<=n<=40，0<=m<=500
善良的学长:虽然解可能不只一个，但是你只要输出任意一个即可得分0.0
题解
dfs直接可得60分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline ll read() { ll 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*10+ch-'0';ch=getchar();} return x*f; } int n,m,mn=inf; int a[45]; ll ed,p[45],bin[45]; bool used[45],ans[45]; void dfs(int x,int now,int k) { if(k>=mn)return; if(x==n+1) { if(now==ed) { mn=k; for(int i=1;i<=n;i++) ans[i]=used[i]; } return; } dfs(x+1,now,k); used[x]=1; dfs(x+1,now^p[x],k+1); used[x]=0; } int main() { //freopen("alice.in","r",stdin); //freopen("alice.out","w",stdout); bin[1]=1; for(int i=2;i<45;i++)bin[i]=bin[i-1]<<1; n=read();m=read();ed=1<<n;ed--; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++) { int a=read(),b=read(); p[a]+=bin[b];p[b]+=bin[a]; } for(int i=1;i<=n;i++)p[i]+=bin[i]; int now=0; for(int i=1;i<=n;i++) if(a[i]) now+=bin[i]; dfs(1,now,0); printf("%d\n",mn); for(int i=1;i<=n;i++) if(ans[i])printf("%d ",i); return 0; } |
可以分成两半搜索然后hash
我偷懒用了map只有95，卡时也不行
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #include<ctime> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; 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*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,m,cnt,mn=inf; int a[55]; ll ed,ans,p[55],bin[55]; map<ll,ll> b; inline int cal(ll x) { int sum=0; for(int i=1;i<=n;i++) if(bin[i]&x)sum++; return sum; } void dfs(int x,ll now,ll used) { if(clock()>500)return; if(x==cnt+1) { if(now==ed) if(cal(used)<mn)mn=cal(used),ans=now; if(!flag) { ll t=b[now]; if(!t)b[now]=used; else if(cal(t)>cal(used))b[now]=used; } else { ll t=b[now^ed]; if(!t)return; int val=cal(t)+cal(used); if(val<mn)mn=val,ans=t+used; } return; } dfs(x+1,now,used); dfs(x+1,now^p[x],used+bin[x]); } int main() { //freopen("alice.in","r",stdin); //freopen("alice.out","w",stdout); bin[1]=1;for(int i=2;i<45;i++)bin[i]=bin[i-1]<<1; n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)if(!a[i])ed+=bin[i]; for(int i=1;i<=m;i++) { int a=read(),b=read(); p[a]|=bin[b];p[b]|=bin[a]; } for(int i=1;i<=n;i++)p[i]|=bin[i]; cnt=n/2;dfs(1,0,0); flag=1; cnt=n;dfs(n/2+1,0,0); printf("%d\n",mn); for(int i=1;i<=n;i++) if(bin[i]&ans)printf("%d ",i); return 0; } |
说点什么
黄学长你的折半搜索好像没有过样例啊……