CF Round 403(Div 2)

发表于 | 更新于

Link

这次的题目除了D可以算得上短小精悍吧。。都非常好写 然而被D题意杀+细节杀最后只过了ABC

Solution

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "lucida"
const int MAXN=1e5+11;
int main() {
//	freopen("input","r",stdin);
	int n;is>>n;
	static int a[MAXN<<1],stat[MAXN];//0 bag 1 table 2 robe
	int cnt=0,Ans=0;
	for(int i=1;i<=2*n;++i) {
		is>>a[i];
		if(stat[a[i]]==0) {
			stat[a[i]]=1;
			cnt++;
		} else {
			stat[a[i]]=2;
			cnt--;
		}
		chkmx(Ans,cnt);
	}
	os<<Ans<<'\n';
	return 0;
}

B

二分时间 貌似还可以三分？有待研究 

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
#include "lucida"
const int MAXN=6e4+11;
const double eps=1e-7;
int x[MAXN],v[MAXN],n;
struct Range {
	double l,r;
	Range(){l=0,r=1e100;}
	Range(double l,double r):l(l),r(r){}
	Range &operator &=(Range x) {
		chkmx(l,x.l);
		chkmn(r,x.r);
		return *this;
	}
};
bool check(double t) {
	Range rg;
	for(int i=1;i<=n;++i) {
		Range able(1.0*x[i]-t*v[i],1.0*x[i]+t*v[i]);
		rg&=able;
	}
	return rg.r-rg.l>eps;
}
int main() {
//	freopen("input","r",stdin);
	is>>n;
	for(int i=1;i<=n;++i) 
		is>>x[i];
	for(int i=1;i<=n;++i)
		is>>v[i];
	double L=0,R=1e9;
	while((R-L)>eps) {
		double Mid=(L+R)/2;
		if(check(Mid)) R=Mid;
		else L=Mid;
	}
	os<<L<<'\n';
	return 0;
}

C

直接按照题意构造。。直观感受一下应该也没有什么别的办法了。。。 

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
#include "lucida"
const int MAXN=2e5+11;
using std::set;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t);
}*id[MAXN];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
int fa[MAXN],cc,col[MAXN],us[MAXN],ut;
void Impl(int pos) {
	++ut;
	us[col[fa[pos]]]=ut;
	us[col[pos]]=ut;
	int asc=1;
	for(Edge *e=id[pos];e;e=e->pre) {
		int u=e->to;
		if(u==fa[pos]) continue;
		fa[u]=pos;
		while(us[asc]==ut) {
			asc++;
			chkmx(cc,asc);
		}
		us[asc]=ut;
		col[u]=asc;
	}
	for(Edge *e=id[pos];e;e=e->pre) {
		int u=e->to;
		if(u==fa[pos]) continue;
		Impl(u);
	}
}
int main() {
//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	col[1]=1;
	Impl(1);
	os<<cc<<'\n';
	for(int i=1;i<=n;++i) 
		os<<col[i]<<(i==n?'\n':' ');
	return 0;
}

D

比赛的时候，题意稀里糊涂，思路十分凌乱，随便写了一个WA了3次 当时是把所有第一个名字相同的选上第二个名字，如果第二个名字有重复就NO 然鹅还有一种情况，就是第一个名字互不相同，但是某一个的第一个名字和另一个的第二个名字相同。这样的话也需要换成第二个名字。同时还有可能引发别的变化。那就需要用一个队列来依次处理所有的变动了。 

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
#include "lucida"
using std::string;
using std::queue;
using std::cin;
using std::cout;

const int MAXN=1000+11;
string op[MAXN][2];
int chs[MAXN];
bool inq[MAXN];
int main() {
//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		string s1,s2;
		cin>>s1>>s2;
		op[i][0]=s1.substr(0,3);
		op[i][1]=s1.substr(0,2)+s2[0];
	}
	queue<int> Q;
	#define pq(x) (inq[x]=inq[x]?1:(Q.push(x),1))
	for(int i=1;i<=n-1;++i)
		for(int j=i+1;j<=n;++j)
			if(op[i][0]==op[j][0]) {
				pq(i);
				pq(j);
				chs[i]=chs[j]=1;
			}
	while(!Q.empty()) {
		int cur=Q.front();Q.pop();
		for(int i=1;i<=n;++i)
			if(i!=cur && chs[i]!=1 && op[cur][1]==op[i][0]) {
				pq(i);
				chs[i]=1;
			}
	}
	bool yes=1;
	for(int i=1;i<=n-1 && yes;++i) 
		for(int j=i+1;j<=n && yes;++j)
			if(op[i][chs[i]]==op[j][chs[j]])
				yes=0;
	if(yes) {
		cout<<"YES"<<'\n';
		for(int i=1;i<=n;++i) 
			cout<<op[i][chs[i]]<<'\n';
	}
	else
		cout<<"NO"<<'\n';
	return 0;
}

E

在考试的时候看到D题交的人虽然多，但是AC率比E小。于是觉得E有可能简单一些。于是看E>>什么？？构造经过所有点的路径？？还有个数限制？？并没有什么好办法。当时脑子也比较乱，想了一会儿没办法，只好回去刚D题了。 完成之后，点开一个Solution，一眼生成树DFS序，，然后， 限制是⌈2nk⌉\lceil\dfrac {2n}k\rceil 生成树的DFS路径就有2n−12n-1个点！ 只要把它们分给每个clone就好了！！！！！！ 

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
#include "lucida"
using std::swap;
const int MAXN=2e5+11;
struct Edge{
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t);
}*id[MAXN<<1];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
struct FUS {
	int fa[MAXN];
	int Root(int x){
		return fa[x]==0?x:fa[x]=Root(fa[x]);
	}
	void Union(int x,int y){
		if(rand()&1) swap(x,y);
		fa[Root(x)]=Root(y);
	}
}S;
int dfs[MAXN<<1],dc;
bool ud[MAXN];
void DFS(int pos) {
	ud[pos]=1;
	dfs[++dc]=pos;
	for(Edge *e=id[pos];e;e=e->pre) {
		int u=e->to;
		if(ud[u]) continue;
		DFS(u);
		dfs[++dc]=pos;
	}
}
int main() {
//	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int n,m,K;is>>n>>m>>K;
	for(int i=1;i<=m;++i) {
		int x,y;
		is>>x>>y;
		if(S.Root(x)==S.Root(y)) continue;
		S.Union(x,y);
		Adde(x,y);
	}
	DFS(1);
	int dp=0,lim=ceil(2.0*n/K);
	for(int k=1;k<=K;++k) {
		static int seq[MAXN<<1];
		int sc=0;
		while(dp<dc && sc<lim) {
			seq[++sc]=dfs[++dp];
		}
		if(!sc)
			os<<"1 1\n";
		else {
			os<<sc<<' ';
			for(int i=1;i<=sc;++i) 
				os<<seq[i]<<(i==sc?'\n':' ');
		}
	}
	return 0;
}

F

其实作为一个F题，感觉比402的要简单一些。 看看题面，就有一种强烈的NOIP开车旅行既视感。 于是就想到倍增。 然而倍增之后不会构造路径，看了看Solution，还是倍增构造路径。 优化：用bitset除掉一个widthwidth 是不是floyd跑传递闭包都可以O(n3width)O(\dfrac {n^3}{width})了。。。233 

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
#include "lucida"
using std::bitset;
const int MAXN=500+11,LOG=60,MAXLOG=LOG+3;
const int64 UP=1000000000000000000ll;
bitset<MAXN> da[2][MAXLOG][MAXN],vis[MAXLOG];
int n;
int main() {
//	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {//m
		int v,u,t;
		is>>v>>u>>t;
		da[t][0][v][u]=1;//u,v,v,u写反了。
		//std::cout<<da[t][0][u][v]<<'\n';
	}
	for(int lg=1;lg<=LOG;++lg)		
		for(int t=0;t<=1;++t)
			for(int i=1;i<=n;++i)
					for(int k=1;k<=n;++k)		
						if(da[t][lg-1][i][k])
							da[t][lg][i]|=da[t^1][lg-1][k];
	int64 Ans=0;
	vis[LOG+1][1]=1;
	for(int lg=LOG,op=0;~lg;--lg) {
		for(int i=1;i<=n;++i)
			if(vis[lg+1][i]) {
				vis[lg]|=da[op][lg][i];
			}
		if(vis[lg].none()) {
			vis[lg]=vis[lg+1];
			continue;
		}
		Ans+=(1ll<<lg);
		op^=1;
		if(Ans>UP) {
			Ans=-1;
			break;
		}
	}
	os<<Ans<<'\n';
	return 0;
}

Tips

现在看的话E题是非常可搞的。 遇到题意杀的题除非万不得已，就不要去刚题意了。见SDOI2016R2day1T2 构造合法方案的题真的可以出的很水。要好好研究给的限制条件，看看能否转化成简单的问题