Jan.8th
注：黑粗体为超链接
比较水的Meet in the Middle了
搜索玩保存的时候只需要保存$L$,$M-L$,$W-L$以及操作序列就行
时间复杂度$O(3^{\frac{n}{2}}*2*log_{2}3^{\frac{n}{2}})$
C++ Code By WTRC
|
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 81 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int fr,bh,n,cnt,l[26],m[26],w[26]; int Ans1=-1<<30,Ans2,Ans3; struct Opr{ int bs,sc,td,seq; bool operator <(const Opr&x)const{return sc==x.sc?(td==x.td?bs<x.bs:td<x.td):sc<x.sc;} }a[600000]; int find(int sc,int td){ int l=1,r=cnt; while (l<r){ int mid=l+r+1>>1; if (a[mid].sc<sc||(a[mid].sc==sc&&a[mid].td<=td)) l=mid; else r=mid-1; } if (a[l].sc==sc&&a[l].td==td) return l; else return 0; } void DFS1(int now,int L,int M,int W,int seq){ if (!now){ a[++cnt]=(Opr){L,M-L,W-L,seq}; return; } DFS1(now-1,L+l[now],M+m[now],W,seq*3); DFS1(now-1,L+l[now],M,W+w[now],seq*3+1); DFS1(now-1,L,M+m[now],W+w[now],seq*3+2); } void Solve(int Ans,int len){ Rep(i,1,len){ if (Ans%3==0) puts("LM"); else if (Ans%3==1) puts("LW"); else puts("MW"); Ans/=3; } } void DFS2(int now,int L,int M,int W,int seq){ if (now==fr){ int Ans=find(L-M,L-W); if (Ans&&a[Ans].bs+L>Ans1){Ans1=a[Ans].bs+L;Ans2=a[Ans].seq;Ans3=seq;} return; } DFS2(now-1,L+l[now],M+m[now],W,seq*3); DFS2(now-1,L+l[now],M,W+w[now],seq*3+1); DFS2(now-1,L,M+m[now],W+w[now],seq*3+2); } int main(){ n=IN(); Rep(i,1,n) l[i]=IN(),m[i]=IN(),w[i]=IN(); if (n==1){ if (l[1]==m[1]) return puts("LM"),0; if (l[1]==w[1]) return puts("LW"),0; if (m[1]==w[1]) return puts("MW"),0; return puts("Impossible"),0; } fr=n/2; DFS1(fr,0,0,0,0); sort(a+1,a+cnt+1); DFS2(n,0,0,0,0); if (Ans1>=-3e8){ Solve(Ans2,fr); Solve(Ans3,n-fr); } else puts("Impossible"); } |
先跪VP半小时A掉的神犇Dirak
首先 在一个符合标准的关系图中
如果存在A喜欢B，那么如果B讨厌C，那么A就必须讨厌C；
反之如果B喜欢C，那么A也要喜欢C；
A讨厌B时也是一个道理
所以可以将初始图中每个连通块分为两个阵营，每个阵营中的人互相喜欢，并且讨厌任何一个其他阵营中的人
判断初始图是否合法可以把一个点拆为正点和反点
如果两个点的正点相连或者反点相连就说明它们是一个阵营
如果一个点的正点和另一个点的反点相连就说明他们是两个阵营
然后并查集维护每个阵营的人
如果发现一个点的正点和反点是一个阵营就直接输出0
否则对于每两个联通块我们都有两种连法
所以假设连通块数量为$cnt$，则$Ans=2^{cnt-1}$
C++ Code By WTRC
|
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 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define maxn 200005 #define MOD 1000000007 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int QPow(int Base,int Pow){ int ret=1; for (;Pow;Pow>>=1,Base=1ll*Base*Base%MOD) if (Pow&1) ret=1ll*ret*Base%MOD; return ret; } int n,m,cnt,to[maxn*2],next[maxn*2],head[maxn],fa[maxn]; bool vis[maxn]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void AddEdge(int u,int v){ to[cnt]=v;next[cnt]=head[u];head[u]=cnt++; to[cnt]=u;next[cnt]=head[v];head[v]=cnt++; fa[find(v)]=find(u); } void DFS(int u){ vis[u]=1; for (int i=head[u];~i;i=next[i]){ if (vis[to[i]]) continue; DFS(to[i]); } } int main(){ n=IN(),m=IN(); Rep(i,1,n*2) fa[i]=i; cnt=0;memset(head,-1,sizeof head); Rep(i,1,m){ int u=IN(),v=IN(),w=IN(); if (w) AddEdge(u,v),AddEdge(u+n,v+n); else AddEdge(u,v+n),AddEdge(v,u+n); } Rep(i,1,n) if (find(i)==find(i+n)) return puts("0"),0; int pow=0; Rep(i,1,n*2) if (!vis[i]) DFS(i),pow++; printf("%d\n",QPow(2,pow/2-1)); } |
首先二分最弱城市的$strength$
然后验证 怎么验证呢？
首先把每个点的邻接点数全都记为$neb$
然后开始验证，因为堡垒是肯定不能选的，
因此把每个堡垒的邻居的最大安全点（记为$cap$）直接-1
在这个过程中如果有发现某个点的$\frac{cap}{neb}<strength$，
那就说明这个点一定不可选
那就把它当做堡垒执行同样的操作
最后看有没有剩下可以选的点就可以了
C++ Code By WTRC
|
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 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } ll Base=100000000ll; int to[200005],next[200005],head[100005],cnt; bool vis[100005]; int n,m,k,fort[100005],neb[100005],cap[100005]; void AddEdge(int u,int v){ to[cnt]=v;next[cnt]=head[u];head[u]=cnt++; to[cnt]=u;next[cnt]=head[v];head[v]=cnt++; neb[u]++;neb[v]++; } queue<int>Q; bool Solve(ll str){ memset(vis,0,sizeof vis); Rep(i,1,k) vis[fort[i]]=1,Q.push(fort[i]); memcpy(cap,neb,sizeof neb); while (!Q.empty()){ int u=Q.front();Q.pop(); for (int i=head[u];~i;i=next[i]){ if (vis[to[i]]) continue; int v=to[i];cap[v]--; if (Base*cap[v]<str*neb[v]){ vis[v]=1;Q.push(v); } } } Rep(i,1,n) if (!vis[i]) return 1; return 0; } void Print(){ int Ans=0; Rep(i,1,n) if (!vis[i]) Ans++; printf("%d\n",Ans); Rep(i,1,n) if (!vis[i]) printf("%d ",i); } int main(){ n=IN(),m=IN(),k=IN(); Rep(i,1,k) fort[i]=IN(); cnt=0;memset(head,-1,sizeof head); Rep(i,1,m){int u=IN(),v=IN();AddEdge(u,v);} ll l=0,r=Base; while (l<r){ ll mid=l+r+1>>1; if (Solve(mid)) l=mid;else r=mid-1; } Solve(l);Print(); } |
——————————————————————————————
评论 (0)
