Codeforces Round #378 (Div. 2) Analyses

懒癌晚期,没的救了xD

A.Grasshopper And the String

Problems:一只蚂蚱从左跳到右,每次只能跳{A,E,I,O,U,Y},问两次跳之间的距离的最大值

Analysis:简单模拟即可

Tags:Implementation

B.Parade

Problems:给你n排士兵及每排士兵的左、右脚分别伸出的数目,可以交换其中一排的左右脚伸出数,问max{|L-R|}

Analysis:鉴于只有10^5,那么暴力交换就可以了

Tags:Implementation

C.Epidemic in Monstropolis

Problems:给你一个序列和另一个序列,对于后者可以进行merge操作,条件为merge的前者大于后者(R)或后者大于前者(L),问是否可以使后者变成前者,并输出方案

Analysis:首先我们知道后面那个序列要是可能变成前者,那么最后构造出来的数肯定是一一对应的,所以可以从前向后构造,如果不能,则输出否即可,那么考虑构造,对于当前目的序列的x,在原序列若找到一段序列和为x,即视为构造成功,之后方案构造只需向右merge后向左merge再向右merge即可,具体可以看代码实现

Tags:Implementation, Two pointers

#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 1010
#define Maxe 100010
typedef long long ll;

struct Data
{
	int m;
	char s;
}Ans[Maxe];
int n, a[Maxn], b[Maxn], k, Cnt;

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 Go_die() { puts("NO"); exit(0); }

int main()
{
    read(n);
    for (int i=1; i<=n; i++) read(a[i]);
    read(k);
    for (int i=1; i<=k; i++) read(b[i]);
    int id=1, last=1;
    for (int i=1; i<=k; i++)
    {
        int Max=0, pos=0, _pos=0, Sig=0;
        for (; (id<=n) && (Sig<b[i]); id++)
        {
            Sig+=a[id];
            if (Sig>b[i]) Go_die();
            if (a[id]>Max) Max=a[id], pos=id;
        }
        if (Sig!=b[i]) Go_die();
        if ((pos==last) && (a[pos+1]==Max)) while (a[pos+1]==Max) pos++;
        _pos=pos+1; int Res=i+pos-last;
        while ((_pos<id) && (a[_pos]<Max))
        {
            Max+=a[_pos++];
            Ans[++Cnt].m=Res; Ans[Cnt].s='R';
        }
        int __pos=pos-1;
        while ((__pos>=last) && (a[__pos]<Max))
        {
            Max+=a[__pos--];
            Ans[++Cnt].m=Res--; Ans[Cnt].s='L';
        }
        while ((_pos<id) && (a[_pos]<Max))
        {
            Max+=a[_pos++];
            Ans[++Cnt].m=Res; Ans[Cnt].s='R';
        }
        if (Max!=b[i]) Go_die();
        last=id;
    }
    if (last!=n+1) Go_die(); 
    puts("YES");
    for (int i=1; i<=Cnt; i++) printf("%d %c\n", Ans[i].m, Ans[i].s);
}

D.Kostya the Sculptor

Problems:给你n个长方形,最多选取两个长方形,问能切割出来的最大的球半径的方案

Analysis:这题反倒是比C题好写了,首先对于每个长方形,我们将边长排序,最大半径显然等于最短边的边长,之后考虑合并,合并肯定是有一个面一样然后让另一条边增长为优,所以只需维护面就可以了,需要用到map(或者离散化???)

Tags:Greedy, Data Structure

#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;

map<pair<int, int> , pair<int, int > > Srh;

int n, a, b, c, Min, Mid, Max, Line_max, Merge, Id;
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++; }

int main()
{
	read(n);
	for (int i=1; i<=n; i++)
	{
		read(a), read(b), read(c);
		Max=max({a, b, c}), Min=min({a, b, c}), Mid=a+b+c-Max-Min;
		if (Min>Line_max) Line_max=Min, Id=i, Merge=-1;
		if (Srh[{Mid, Max}].first)
		{
			Min=min({Mid, Max, Min+Srh[{Mid, Max}].first});
			if (Min>Line_max)
			{
				Line_max=Min;
				Id=i;
				Merge=Srh[{Mid, Max}].second;
			}
		}
		Min=min({a, b, c});
		Srh[{Min, Mid}]=max(Srh[{Min, Mid}], {Max, i});
		Srh[{Min, Max}]=max(Srh[{Min, Max}], {Mid, i});
		Srh[{Mid, Max}]=max(Srh[{Mid, Max}], {Min, i});
	}
	if (Merge==-1) { puts("1"); printf("%d\n", Id); }
	else { puts("2"); printf("%d %d\n", Id, Merge); }
}

Codeforces Round #375 (Div. 2) Analyses

神他喵难的一场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]);
}

Codeforces Round #377 (Div. 2) Analyses

拖了两天、不能再懒更多了

A.Buy a Shovel

Problem:你有∞多的10和一个r∈[0, 9]以及一个物品的价格k,问你买多少该物品可以恰好不用找钱

Analysis:不用找钱 <=> 10的倍数或者10的倍数+r,模拟即可

Tags:Implementation

B.Cormen --- The Best Friend Of a Man

Problem:给定一串长度为n的序列,要求相邻两项之和不得小于k,支持修改,问最小代价

Analysis:贪心显然成立(改变第二天对后继的更优),所以模拟修改的过程即可。然而坑点在于n == 1的情况,是不用特判的

Tags:Greedy

C.Sanatorium

Problem:有个人在医院里不知道呆了几天,只知道自己吃的早饭,中饭,晚饭数量,问你他最少没吃多少餐

Analysis:知道最小天数就可以反向推出他最少没吃多少餐了,而前者显然是max{ breakfast, dinner, supper }-1;

Tags:Math, Greedy

D.Exams

Problem:n天内需要考m门试题,每天可以选择考试(当天只能考当天提供的考试),复习,或者什么都不做、求最小需要的天数

Analysis:二分显然,重点在于如何判断。注意到最后一天其实只能考试了,然后逆推统计复习天数判断是否可行就可以了

Tags:Binary search, 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 Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 100010
typedef long long ll;

int n, m, d[Maxn], a[Maxn];
bool Pass[Maxn];

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 bool Judge(int Day)
{
    Clear(Pass, 0); int Cnt=0;
    for (int i=Day; i>=1; i--)
        if ((d[i]) && (!Pass[d[i]])) Pass[d[i]]=1, Cnt+=a[d[i]];
        else Cnt--, Cnt=max(Cnt, 0);
    if (Cnt) return 0;
    for (int i=1; i<=m; i++) if (!Pass[i]) return 0;
    return 1;
}

int main()
{
    read(n); read(m);
    for (int i=1; i<=n; i++) read(d[i]);
    for (int i=1; i<=m; i++) read(a[i]);
    int l=1, r=n;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (Judge(mid)) r=mid-1; else l=mid+1;
    }
    if (Judge(l)) printf("%d\n", l); else puts("-1");
}

E.Sockets

Problem:有n个电脑需要供电,你有m个电源,和∞多个适配器,每个适配器可以使某个电源电压减半,供电必要的条件为电脑的电压<=电源电压,问最大所连接的电脑数和最小需要的适配器的数量

Analysis:贪心,将电源排序,如果一个小的电源匹配不了的话,那么用更大的加适配器就是浪费,所以从电源电压小的开始匹配,由于数据范围,需要用map来保存。(还有一种优先队列的模拟方法)

Tags:Greedy, Sorting, Implementation

 

#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
typedef long long ll;

struct Socket
{
    int s, id;
}s[Maxn];
int n, m, x, Apt, Match;
int Link[Maxn], Ans[Maxn];
map<int,  vector<int > > Com;

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 bool cmp(const Socket &a, const Socket &b) { return (a.s<b.s) || ((a.s==b.s) && (a.id<b.id)); }
int main()
{
    read(n); read(m);
    for (int i=1; i<=n; i++) read(x), Com[x].push_back(i);
    for (int i=1; i<=m; i++) read(s[i].s), s[i].id=i;
    sort(s+1, s+m+1, cmp);
    for (int i=1; i<=m; i++)
    {
        int Current=s[i].s, Cnt=0;
        while (1)
        {
            if (Com[Current].size()!=0)
            {
                int Cp=Com[Current][Com[Current].size()-1]; Com[Current].pop_back();
                Match++, Apt+=Cnt;
                Link[Cp]=s[i].id, Ans[s[i].id]=Cnt;
                break;
            }
            if (Current==1) break;
            Cnt++, Current=(Current+1)>>1;
        }
    }
    printf("%d %d\n", Match, Apt);
    for (int i=1; i<=m; i++) printf("%d ", Ans[i]); puts("");
    for (int i=1; i<=n; i++) printf("%d ", Link[i]); puts("");
}

F.Tourist Reform

Problem:给你一个无向无环图,让你确定每条边的方向,使得所有点能到达的点的个数种最小值的最大值

Analysis:首先想到二分+缩点,但手推几个图后发现其实答案就是max{ V’ },V’为某个强连通块中的点的个数,那么两遍Tarjan即可,第一遍寻找该节点,第二遍模拟建图

Tags:Dfs and similar, Algorithm

 

#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 400010
#define Maxe 800010
typedef long long ll;

struct Answer
{
    int u, v;
}Link[Maxe];

int n, m, x, y, Res, Cnv, Index, dfn[Maxn], low[Maxn], Stack[Maxe], Point;
int To[Maxe], Id[Maxe], Head[Maxn], Cnt, Next[Maxe];

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 void Init_Tarjan() { for (int i=1; i<=n; i++) dfn[i]=0; Cnv=Index=Res=0; }

inline void Tarjan(int u, int father)
{
    dfn[u]=low[u]=++Index; Stack[++Cnv]=u;
    for (int p=Head[u]; p!=-1; p=Next[p])
    {
        int v=To[p], pos=Id[p];
        if (v==father) continue;
        if (!dfn[v])
        {
            Link[pos].u=v, Link[pos].v=u;
            Tarjan(v, u);
            low[u]=min(low[u], low[v]);
        }
        else Link[pos].u=u, Link[pos].v=v, low[u]=min(low[u], dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        int Tmp, Count=0;
        do
        {
            Tmp=Stack[Cnv--];
            Count++;
        }while (Tmp!=u);
        if (Res<Count) Res=Count, Point=u;
    }
}

/*inline bool Judge(int Current)
{
    for (int i=1; i<=n; i++) dfn[i]=0;
    Cnv=Index=Res=0;
    Tarjan(1, -1);
    return (Res>=Current);
}*/

int main()
{
    read(n); read(m); Clear(Head, -1); Cnt=0;
    for (int i=1; i<=m; i++) read(x), read(y), Insert(x, y, i), Insert(y, x, i);
    /*int l=1, r=n;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (Judge(mid)) l=mid+1; else r=mid-1;
    }*/
    Init_Tarjan();
    Tarjan(1, -1);
    printf("%d\n", Res);
    Init_Tarjan();
    Tarjan(Point, -1);
    for (int i=1; i<=m; i++) printf("%d %d\n", Link[i].u, Link[i].v);
}

Codeforces Round #376 (Div. 2) Analyses

[bzoj3503][Cqoi2014]和谐矩阵

都是水水的啦你们就别看了~~

Solve record Oct.

 
都是水水的啦你们就别看了~~
 

ZJOI2014Day2

Bless All!

Codeforces Round #246 (Div. 2)

第一次打Codeforces的vp。。

毕竟人太弱

[Shoi2014爆o记]Day2.

还是先Refresh Day2吧。毕竟太弱

 

Acme Corporation

Wile E. Coyote is back. He is back in the business. The business of capturing the road runner. Being the most loyal customer to the Acme Corporation, they are hoping to do some great business with him. Although, Acme makes literally every kinds of devices, all of them has a similarity, that has been kept secret for ages. All of their products use a secret element “element X” (this is kept so secret that, only you and the Acme people know about this). The decision makers of the Acme Corp. has already estimated the maximum amount of element X that can be used into manufacture every month.