刷刷POI，整个人都POI！
BZOJ 1098: [POI2007]办公楼biu 补图联通块直接DFS出来就行了，很容易TLE要用链表及时删点、
|
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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; const int Maxm=2000010; inline int read(){ int x = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x; } struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; int head[Maxn]; Edge e[Maxm*2]; int nume; int n,m; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]);head[u]=nume; e[++nume]=Edge(u,head[v]);head[v]=nume; } int nxt[Maxn],pre[Maxn]; inline void del(int x){ int tmp=pre[x]; nxt[tmp]=nxt[x]; pre[nxt[x]]=tmp; } bool vis[Maxn]; int cnt; int siz[Maxn]; bool noEdge[Maxn]; int que[Maxn]; int l,r; int i; void bfs(int src){ que[0]=src; vis[src]=true; for (l = r = 0; l <= r; ++l){ int x=que[l]; //printf("%d\n",x); siz[cnt]++; for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true; for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i] && !noEdge[i]){ del(i); vis[i]=true; que[++r]=i; } } for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false; } } inline void input(){ freopen("1098.in","r",stdin); //freopen("1098.out","w",stdout); } int main(){ //input(); n=read();m=read(); int x,y; for (i=1;i<=m;i++){ x=read(),y=read(); addEdge(x,y); } for (i=0;i<=n;i++){ nxt[i]=i+1; pre[i+1]=i; } for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i]){ cnt++; del(i); bfs(i); } } sort(siz+1,siz+cnt+1); printf("%d\n",cnt); for (i=1;i<=cnt;i++){ printf("%d ",siz[i]); } printf("\n"); return 0; } |
BZOJ 1097: [POI2007]旅游景点atr 首先SPFA出前k+1个点的最短路,然后做状压DP. pre […]
KMP和KMP是好朋友
BZOJ 1251: 序列终结者 splay模板题,再写一遍找手感!Wa了一次!splay对无用节点的处理真的很重要!(其实是你自己偷懒没有判断到底存不存在子节点吧!
|
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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=50010; int n,m; int k,l,r,v; int id[Maxn]; struct Btree{ int fa; int ch[2]; int val; int max; int siz; int tag; bool rev; }; Btree tree[Maxn]; int root; inline void update(int x){ int l=tree[x].ch[0],r=tree[x].ch[1]; tree[x].siz=tree[l].siz+1+tree[r].siz; tree[x].max=max(tree[x].val,max(tree[l].max,tree[r].max)); } inline void clean(int x){ //printf("%d\n",x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[x].tag){ if (l){ tree[l].max+=tree[x].tag; tree[l].val+=tree[x].tag; tree[l].tag+=tree[x].tag; } if (r){ tree[r].max+=tree[x].tag; tree[r].val+=tree[x].tag; tree[r].tag+=tree[x].tag; } tree[x].tag=0; } if (tree[x].rev){ swap(tree[x].ch[0],tree[x].ch[1]); if (l){ tree[l].rev^=1; } if (r){ tree[r].rev^=1; } tree[x].rev=false; } } inline void rotate(int x,int &k){ int y=tree[x].fa,z=tree[y].fa; int l=(tree[y].ch[1]==x),r=l^1; if (k==y) k=x; else tree[z].ch[tree[z].ch[1]==y]=x; tree[tree[x].ch[r]].fa=y; tree[y].fa=x; tree[x].fa=z; tree[y].ch[l]=tree[x].ch[r]; tree[x].ch[r]=y; update(y); update(x); } inline void splay(int x,int &k){ while(x!=k){ int y=tree[x].fa,z=tree[y].fa; if (y!=k){ if (tree[y].ch[0]==x ^ tree[z].ch[0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int x,int rank){ clean(x); int l=tree[x].ch[0],r=tree[x].ch[1]; if (tree[l].siz+1==rank) return x; if (tree[l].siz>=rank) return find(l,rank); return find(r,rank-tree[l].siz-1); } inline void add(int l,int r,int val){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].tag+=val; tree[z].val+=val; tree[z].max+=val; } inline void rev(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; tree[z].rev^=1; } inline int query(int l,int r){ int x=find(root,l),y=find(root,r+2); splay(x,root);splay(y,tree[x].ch[1]); int z=tree[y].ch[0]; return tree[z].max; } int build(int l,int r,int fa){ if (l>r) return 0; int mid=(l+r)/2; int now=id[mid]; tree[now].tag=0; tree[now].rev=false; tree[now].fa=id[fa]; if (l==r){ tree[now].val=tree[now].max=0; tree[now].siz=1; }else{ tree[now].ch[0]=build(l,mid-1,mid); tree[now].ch[1]=build(mid+1,r,mid); update(now); } return now; } inline void print(){ for (int i=1;i<=n;i++){ printf("%d ",tree[find(root,i+1)].val); } printf("\n"); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n+2;i++) id[i]=i; tree[0].max=tree[0].val=-2100000000; tree[0].siz=0; root=build(1,n+2,0); //printf("Root : %d\n",root); for (int i=1;i<=m;i++){ scanf("%d%d%d",&k,&l,&r); //printf("%d %d %d\n",k,l,r); if (k==1) {scanf("%d",&v);add(l,r,v);} if (k==2) rev(l,r); if (k==3) printf("%d\n",query(l,r)); //print(); } return 0; } |
HDU 5147 Sequence II 树状数组!枚举C，顺带统 […]
Nim游戏
BZOJ 1299: [LLH邀请赛]巧克力棒 对于一个初始局面,如果我们可以把它分成一个P态和一个N态.我们一次头把P态全部取出,对于这个P态我们就是后手了.我们强迫对方取出N态的巧克力,这样对于这个N态我们变成了先手,可以保证必胜了.
|
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 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=20; int n; int num[Maxn]; int sum; bool dfs(int now,int uesd,int sg){ if (sg==0 && uesd>0) return true; if (now>n) return false; return dfs(now+1,uesd,sg)||dfs(now+1,uesd+1,sg^num[now]); } int main(){ for (int i=1;i<=10;i++){ scanf("%d",&n); for (int j=1;j<=n;j++){ scanf("%d",&num[j]); } if (!dfs(1,0,0)) printf("YES\n"); else printf("NO\n"); } return 0; } |
