1
8
2016
0

Diary of OI

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
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
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
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
 
#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*2if (!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
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
 
#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();
}
——————————————————————————————
Category: Diary | Tags: codeforces | Read Count: 201

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com