return's Blog

Code
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	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `//#include<iostream>` `#include<cmath>` `#include<queue>` `#include<map>` `#include<string>` `#include<vector>` `using` `namespace` `std;` `#define INF 2000000000` `#define Clear(x, Num) memset(x, Num, sizeof(x))` `#define Low(x) ((x>='a') && (x<='z'))` `#define Cap(x) ((x>='A') && (x<='Z'))` `#define Dig(x) ((x>='0') && (x<='9'))` `#define Neg(x) (x=='-')` `#define G_c() getchar()` `typedef` `long` `long` `ll;` `int` `n, m, a[2010], Cnt[2010], Change;` `inline` `int` `gcd(int` `x,` `int` `y) {` `if` `(!y)` `return` `x;` `return` `gcd(y, x%y); }` `inline` `void` `read(int` `&x){` `char` `ch;` `int` `N=1;` `while` `((ch=G_c()) && (!Dig(ch)) && (!Neg(ch)));` `if` `(Neg(ch)) { N=-1;` `while` `((ch=G_c()) && (!Dig(ch))); } x=ch-48;` `while` `((ch=G_c()) && (Dig(ch))) x=x10+ch-48; x=N; }` `//inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }` `int` `main()` `{` `read(n); read(m);` `for` `(int` `i=1; i<=n; i++)` `{` `read(a[i]);` `if` `(a[i]<=m) Cnt[a[i]]++;` `}` `for` `(int` `i=1; i<=m; i++)` `{` `int` `More=(Cnt[i]<(n/m))?(n/m-Cnt[i]):0;` `if` `(More)` `for` `(int` `j=1; j<=n; j++)` `if` `((a[j]>m) \|\| (Cnt[a[j]]>n/m))` `{` `if` `(a[j]<=m) Cnt[a[j]]--;` `a[j]=i; Change++; More--;` `if` `(!More)` `break;` `}` `}` `printf("%d %d\n", n/m, Change);` `for` `(int` `i=1; i<=n; i++)` `printf("%d ", a[i]);` `puts("");` `}`

D.Lakes in Berland

Problems：给你一个地图，其中"*"为sand，"."为lake，一个湖的定义为不和边界有交点并被沙子包围，填湖的代价为湖的面积，求湖的个数<=k的最小代价

Analysis：这题反而水了，直接dfs出湖，sort一下贪心就可以了。

Tags:Greedy, Dfs and similar

Code
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	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `//#include<iostream>` `#include<cmath>` `#include<queue>` `#include<map>` `#include<string>` `#include<vector>` `using` `namespace` `std;` `#define INF 2000000000` `#define Clear(x, Num) memset(x, Num, sizeof(x))` `#define Low(x) ((x>='a') && (x<='z'))` `#define Cap(x) ((x>='A') && (x<='Z'))` `#define Dig(x) ((x>='0') && (x<='9'))` `#define Neg(x) (x=='-')` `#define G_c() getchar()` `typedef` `long` `long` `ll;` `struct` `Data` `{` `int` `x, y, Area;` `}Lake[10010];` `int` `n, m, k, Map[110][110], Ans, Cnt, Ant;` `bool` `flag;` `inline` `int` `gcd(int` `x,` `int` `y) {` `if` `(!y)` `return` `x;` `return` `gcd(y, x%y); }` `inline` `void` `read(int` `&x){` `char` `ch;` `int` `N=1;` `while` `((ch=G_c()) && (!Dig(ch)) && (!Neg(ch)));` `if` `(Neg(ch)) { N=-1;` `while` `((ch=G_c()) && (!Dig(ch))); } x=ch-48;` `while` `((ch=G_c()) && (Dig(ch))) x=x10+ch-48; x=N; }` `//inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }` `inline` `bool` `Cmp(const` `Data &a,` `const` `Data &b) {` `return` `a.Area<b.Area; }` `inline` `int` `dfs(int` `_x,` `int` `_y,` `int` `Color)` `{` `if` `((_x<1) \|\| (_x>n) \|\| (_y<1) \|\| (_y>m) \|\| (Map[_x][_y]==Color) \|\| (!Map[_x][_y]))` `return` `0;` `if` `((_x==1) \|\| (_x==n) \|\| (_y==1) \|\| (_y==m)) { flag=1;` `return` `0; }` `Map[_x][_y]=Color;` `return` `dfs(_x-1, _y, Color)+dfs(_x+1, _y, Color)+dfs(_x, _y-1, Color)+dfs(_x, _y+1, Color)+1;` `}` `int` `main()` `{` `scanf("%d%d%d", &n, &m, &k);` `char` `x=G_c();` `for` `(int` `i=1; i<=n; i++)` `{` `for` `(int` `j=1; j<=m; j++)` `{` `x=G_c();` `if` `(x=='.') Map[i][j]=-1;` `}` `x=G_c();` `}` `/for (int i=1; i<=n; i++)` `{ for (int j=1; j<=m; j++) printf("%d ", Map[i][j]); puts(""); }/` `for` `(int` `i=1; i<=n; i++)` `for` `(int` `j=1; j<=m; j++)` `if` `(Map[i][j]==-1)` `{` `flag=0;` `int` `Area=dfs(i, j, ++Cnt);` `if` `(!flag) Lake[Cnt].x=i, Lake[Cnt].y=j, Lake[Cnt].Area=Area;` `else` `Cnt--;` `}` `sort(Lake+1, Lake+Cnt+1, Cmp);` `for` `(int` `i=1; i<=Cnt-k; i++) Ans+=Lake[i].Area, dfs(Lake[i].x, Lake[i].y, 0);` `printf("%d\n", Ans);` `for` `(int` `i=1; i<=n; i++)` `{` `for` `(int` `j=1; j<=m; j++)` `if` `(Map[i][j])` `printf(".");` `else` `printf("*");` `puts("");` `}` `}`

E.One-Way Reform

Problems：将一个无向图修改，使得入度==出度的点数尽可能的多，并输出方案

Analysis：首先度数为奇的点必然不是答案，那么Res=n-度数为奇的点，再考虑这些点，每次选择从一个点出发进行修改一条路径（直到另一个奇点），经过的点都走偶数次，直到该点度数为0，即可

Tags:Greedy, Dfs and similar, Graphs

Code
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<cstdio>` `#include<cstring>` `#include<algorithm>` `//#include<iostream>` `#include<cmath>` `#include<queue>` `#include<map>` `#include<string>` `#include<vector>` `using` `namespace` `std;` `#define INF 2000000000` `#define Clear(x, Num) memset(x, Num, sizeof(x))` `#define Dig(x) ((x>='0') && (x<='9'))` `#define Neg(x) (x=='-')` `#define G_c() getchar()` `typedef` `long` `long` `ll;` `struct` `Data` `{` `int` `x, y;` `}Edge[40010];` `int` `T, n, m, x, y, Edge_Cnt, Res, In[2010];` `int` `G[2010][2010];` `inline` `int` `gcd(int` `x,` `int` `y) {` `if` `(!y)` `return` `x;` `return` `gcd(y, x%y); }` `inline` `void` `read(int` `&x){` `char` `ch;` `int` `N=1;` `while` `((ch=G_c()) && (!Dig(ch)) && (!Neg(ch)));` `if` `(Neg(ch)) { N=-1;` `while` `((ch=G_c()) && (!Dig(ch))); } x=ch-48;` `while` `((ch=G_c()) && (Dig(ch))) x=x10+ch-48; x=N; }` `//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }` `inline` `void` `dfs(int` `u)` `{` `while` `(In[u])` `{` `for` `(int` `i=1; i<=n; i++)` `if` `(G[u][i])` `{` `int` `v=i;` `Edge[++Edge_Cnt].x=u, Edge[Edge_Cnt].y=v;` `In[u]--, In[v]--; G[u][v]=G[v][u]=0;` `u=v;` `break;` `}` `}` `}` `int` `main()` `{` `read(T);` `while` `(T--)` `{` `read(n); read(m);` `Edge_Cnt=0; Res=n;` `for` `(int` `i=1; i<=n; i++) { In[i]=0;` `for` `(int` `j=1; j<=n; j++) G[i][j]=0; }` `for` `(int` `i=1; i<=m; i++)` `{` `read(x), read(y);` `G[x][y]=G[y][x]=1;` `In[x]++, In[y]++;` `}` `for` `(int` `i=1; i<=n; i++) Res-=(In[i]&1);` `printf("%d\n", Res);` `for` `(int` `i=1; i<=n; i++)` `if` `(In[i]&1)` `while` `(In[i]) dfs(i);` `for` `(int` `i=1; i<=n; i++)` `while` `(In[i]) dfs(i);` `for` `(int` `i=1; i<=Edge_Cnt; i++)` `printf("%d %d\n", Edge[i].x, Edge[i].y);` `}` `}`

F.st-Spanning Tree

Problems：给你一张图，求一颗生成树，使得源点s度数不超过ds，汇点t度数不超过dt，并按照输入顺序输出

Analysis：先考虑和s,t无关的点集，每个点集只有三种连法

1. 和s和t均相连：标记

2. 和s或者t中的一个相连：直接和另一个点相连。

3. 孤立点：无法构成要求的生成树

对于这些标记点集，若不和s和t联通，则考虑是否可以将s和t相连，若不可以，则无法构成要求的生成树

剩下的点只需要考虑s或者t相连即可

Tags：Greedy, Dsu, Graphs

Code
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	`#include<cstdio>` `#include<cstring>` `#include<algorithm>` `//#include<iostream>` `#include<cmath>` `#include<queue>` `#include<map>` `#include<string>` `#include<vector>` `using` `namespace` `std;` `#define INF 2000000000` `#define Clear(x, Num) memset(x, Num, sizeof(x))` `#define Dig(x) ((x>='0') && (x<='9'))` `#define Neg(x) (x=='-')` `#define G_c() getchar()` `#define Maxn 200010` `#define Maxe 800010` `typedef` `long` `long` `ll;` `vector<int` `>Point[Maxn];` `int` `n, m, x[Maxe], y[Maxe], To[Maxe], Next[Maxe], Id[Maxe], Head[Maxn], Cnt;` `int` `source, sink, dep_s, dep_t;` `int` `f[Maxn], Ans_s[Maxn], Ans_t[Maxn], Cnt_s, Cnt_t;` `bool` `Used[Maxe];` `inline` `int` `Get_f(int` `x) {` `return` `(x==f[x])?(x):(f[x]=Get_f(f[x])); }` `inline` `int` `gcd(int` `x,` `int` `y) {` `if` `(!y)` `return` `x;` `return` `gcd(y, x%y); }` `inline` `void` `read(int` `&x){` `char` `ch;` `int` `N=1;` `while` `((ch=G_c()) && (!Dig(ch)) && (!Neg(ch)));` `if` `(Neg(ch)) { N=-1;` `while` `((ch=G_c()) && (!Dig(ch))); } x=ch-48;` `while` `((ch=G_c()) && (Dig(ch))) x=x10+ch-48; x=N; }` `inline` `void` `Insert(int` `u,` `int` `v,` `int` `w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; }` `int` `main()` `{` `read(n); read(m);` `for` `(int` `i=1; i<=n; i++) Head[i]=-1; Cnt=0;` `for` `(int` `i=1; i<=m; i++)` `{` `read(x[i]); read(y[i]);` `Insert(x[i], y[i], i), Insert(y[i], x[i], i);` `}` `read(source); read(sink); read(dep_s); read(dep_t);` `for` `(int` `i=1; i<=n; i++) f[i]=i;` `for` `(int` `u=1; u<=n; u++)` `if` `((u^source) && (u^sink))` `for` `(int` `p=Head[u]; p!=-1; p=Next[p])` `{` `int` `v=To[p];` `if` `((v==source) \|\| (v==sink))` `continue;` `int` `Anc_u=Get_f(u), Anc_v=Get_f(v);` `if` `(Anc_u^Anc_v) Used[Id[p]]=1, f[Anc_u]=Anc_v;` `}` `for` `(int` `i=1; i<=n; i++) Point[Get_f(i)].push_back(i);` `for` `(int` `u=1; u<=n; u++)` `if` `((u^source) && (u^sink) && (f[u]==u))` `{` `int` `Link_source=0, Link_sink=0;` `for` `(int` `p=0; p<Point[f[u]].size(); p++)` `{` `int` `v=Point[u][p];` `if` `(f[v]==u)` `{` `for` `(int` `_p=Head[v]; _p!=-1; _p=Next[_p])` `{` `int` `_v=To[_p];` `if` `(_v==source) Link_source=Id[_p];` `else` `if` `(_v==sink) Link_sink=Id[_p];` `}` `if` `((Link_source) && (Link_sink))` `break;` `}` `}` `if` `((!Link_source) && (!Link_sink)) {` `puts("No");` `return` `0; }` `if` `((Link_source) && (Link_sink)) Ans_s[++Cnt_s]=Link_source, Ans_t[++Cnt_t]=Link_sink;` `else` `{` `if` `(Link_source) dep_s--, f[u]=source, Used[Link_source]=1;` `if` `(Link_sink) dep_t--, f[u]=sink, Used[Link_sink]=1;` `}` `}` `if` `(Cnt_s) dep_s--, dep_t--, Used[Ans_s[1]]=1, Used[Ans_t[1]]=1;` `else` `{` `int` `Anc=Get_f(1);` `for` `(int` `i=1; i<=n; i++)` `if` `(Get_f(i)^Anc) { Anc=-1;` `break; }` `if` `(Anc==-1)` `{` `bool` `flag=0;` `for` `(int` `p=Head[source]; p!=-1; p=Next[p])` `{` `int` `v=To[p];` `if` `(v==sink) { flag=1; Used[Id[p]]=1;` `break; }` `}` `if` `(!flag) {` `puts("No");` `return` `0; }` `dep_s--; dep_t--;` `f[source]=sink;` `}` `}` `for` `(int` `i=2; i<=Cnt_s; i++)` `{` `if` `(dep_s) { dep_s--, Used[Ans_s[i]]=1;` `continue; }` `dep_t--, Used[Ans_t[i]]=1;` `}` `if` `((dep_s<0) \|\| (dep_t<0)) {` `puts("No");` `return` `0; }` `puts("Yes");` `for` `(int` `i=1; i<=m; i++)` `if` `(Used[i])` `printf("%d %d\n", x[i], y[i]);` `}`

return

日历

最新评论

标签云

链接

计数器

Codeforces Round #375 (Div. 2) Analyses

二月
日	一	二	三	四	五	六
						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