return's Blog

神他喵难的一场cf 

A.The New Year: Meeting Friends

Problems：三个人要走到一个地方，给定x1，x2，x3，问最小代价。

Analysis：思维题，讨论一下就知道答案为max({x1, x2, x3})-min({x1, x2, x3})

Tags:Math, Sorting

B.Text Document Analysis

Problems：给定一串字符串，只会出现字母，_以及左右括号，问括号外最长的单词长度以及括号内有几个单词

Analysis：一开始以为括号可以嵌套，感觉巨烦，然而，简单模拟

Tags:Implementation

C.Polycarp at the Radio

Problems：题面神他喵的烦，其实就是给定一串序列，让你将其修改，使得1-m数目最小的出现次数最大，且修改次数最小

Analysis：首先出现次数的答案是固定的，即n/m（平均分配）。接下去就是分配的问题了，对于那些>m的数，如果存在一个数小于min(m,n/m)，那么就直接修改，否则就不动。之后寻找是否有出现次数<n/m的数，将那些出现次数>n/m的数修改过去就好了

Tags:Greedy

#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=x*10+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

#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=x*10+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

#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=x*10+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

#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=x*10+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]);
}