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); }
}

OI Comments(1) Nov 08, 2016 05:01:18 AM

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]);
}

OI Comments(2) Oct 24, 2016 03:16:49 PM

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);
}

OI Comments(1) Oct 19, 2016 01:52:01 PM

Codeforces Round #376 (Div. 2) Analyses

OI Comments(2) Oct 17, 2016 03:45:13 AM