发表于 | 更新于

Link

总算能基本上自己做出来一道题目了虽然是水题

Solution

可以发现，把一棵树从一条边剖开，要合起来最长的直径就是两个子树的直径和 最短的直径就是把两个直径的中点相连。所以主要问题就是快速算直径 设从pospos到fa[pos]fa[pos]的连边把树剖开，pospos的子树中的直径可以预处理，那么另一部分直径有这样几个来源：

  1. fa[pos]fa[pos]祖先们除了fa[pos]fa[pos]所在子树之外的子树中的直径
  2. fa[pos]fa[pos]的子树刨去pospos的子树剩下部分的直径
  3. fa[pos]fa[pos]下面连一条长链，向上伸到一个祖先，再向下连一条长链

观察之后，发现一遍预处理，对于以pp为根的子树，处理出pp子树的直径，pp的子节点的子树的直径的最大、次大值，和从pp向下的前三长的链，就可以做前两个。 第三个只需要在DP的时候在栈上记录一个从祖先来的最长链即可 大体就是这样 写了一个来小时，然后开启了DEBUG被坑模式

Tips

改来改去，其实主要就改了3个错误，而3个错误的外观是一样的：输出方案里有0。 具体地说，是使得直径最小的连边出现了0。

  1. 我在DP的时候记录了每个链的一个端点，输出方案的时候需要找到直径的中点，那就再从端点开始DFS一下就好了。然后一开始我把两个直径的端点设置成了不可访问，导致第一个的DFS几乎搜遍了整个树，把第二遍DFS需要找的点也给搜了！！
  2. 然后我找到了问题，设置成了两个断点不可用，再从端点开始搜，还是出来0。最后发现，把断点设置不可用，直接把一些合法的链截断了！！！！
  3. 然后我找到了问题，设置了每遍DFS都是另一个断点不可用，还是出来0。最后发现，我的DP中因为存在一些 ，我盲目地和00取了max\max，导致一些不存在的状态被合法化了！！！
  4. 然后几乎3h就过去了。

通过做这道题题目使我充分认识到自己能犯的错误有多么SX。 所以，至少要总结这几点经验： 想想遍历之前设置不可用的点截断的是什么 DP，尤其是记录方案的DP，即使是0这样的值也一定要有来由！

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "lucida"

using std::pair;
using std::make_pair;
using std::max;
template <class T>
inline T max(const T &a,const T &b,const T &c) {
	return max(a,max(b,c));
}
const int MAXN=500000+11,INF=0x1f1f1f1f;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),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,1,id[f]);
	id[t]=new Edge(f,1,id[t]);
}
struct Node {
	int v,end;
	Node(){v=-INF;} Node(int v,int end):v(v),end(end){}
	bool operator <(const Node &a) const {
		return v<a.v;
	}
};
template <int d> struct FST {
	Node v[d];
	Node &operator [](int x){
		return v[x];
	}
	void Append(const Node &p) {
		for(int i=0;i<d;++i) 
			if(v[i].v<p.v) {
				for(int j=d-1;j>i;--j)
					v[j]=v[j-1];
				v[i]=p;
				break;
			}
	}
};///;;;;;!!
FST<3> ch[MAXN];
FST<2> sond[MAXN];
Node d[MAXN];
int fa[MAXN],lbd[MAXN],rbd[MAXN],dc;
void Calc(int pos) {
	bool isleaf=1;
	lbd[pos]=++dc;
	for(Edge *e=id[pos];e;e=e->pre) 
		if(e->to!=fa[pos]) {
			int u=e->to;
			isleaf=0;
			fa[u]=pos;
			Calc(u);
			ch[pos].Append(Node(ch[u][0].v+1,ch[u][0].end));
			sond[pos].Append(d[u]);
		}
	if(isleaf) 
		ch[pos][0]=d[pos]=Node(0,pos);
	else 
		d[pos]=max(Node(ch[pos][0].v+max(ch[pos][1].v,0),ch[pos][0].end),sond[pos][0]);
	rbd[pos]=dc;
	
}
Node O_O(int pos,Node parch) {
	int f=fa[pos];
	Node r1,r2=Node(0,f),fsd=(sond[f][0].end!=d[pos].end?sond[f][0]:sond[f][1]),fd=Node(0,f);
	if(ch[f][0].end==ch[pos][0].end) {
		chkmx(fd,Node(ch[f][1].v+max(ch[f][2].v,0),ch[f][1].end));//出现了end为0的不合法
		chkmx(r2,Node(max(ch[f][1].v,0)+parch.v+1,parch.end));
	} else if(ch[f][1].end==ch[pos][0].end) {
		chkmx(fd,Node(ch[f][0].v+max(ch[f][2].v,0),ch[f][0].end));
		chkmx(r2,Node(max(ch[f][0].v,0)+parch.v+1,parch.end));
	} else {
		chkmx(fd,Node(ch[f][0].v+max(ch[f][1].v,0),ch[f][0].end));
		chkmx(r2,Node(max(ch[f][0].v,0)+parch.v+1,parch.end));
	}
	r1=max(Node(0,f),fd,fsd);
	return max(r1,r2);
}
pair<int,int> cut[2],lnk[2];
int Ans[2]={INF,-INF};
//d2：父节点(不包含)以上的部分的直径
//fch：包含父节点的最长链
//DFF：父节点子树之内剩下的部分的直径
//DGF: 父节点的子树之内的一条长链和上面过来的长链构成的长度
//O_O：max(DGF,DFF) 即父节点带来的最长链
//parch 祖先到父节点(不包含)的最长链 也就是到爷节点为止的最长链
pair<int,int> dist;
void DP(int pos,Node d2,Node parch) {
	if(pos!=1) {
		if(fa[pos]!=1)
			chkmx(parch.v,0);
		Node d1=d[pos];
		chkmx(d2,O_O(pos,parch));
		if(chkmn(Ans[0],max(d1.v,d2.v,d1.v-(d1.v>>1)+d2.v-(d2.v>>1)+1))) {
			cut[0]=make_pair(pos,fa[pos]);
			lnk[0]=make_pair(d1.end,d2.end);
			dist=make_pair(d1.v,d2.v);
		}
		if(chkmx(Ans[1],d1.v+d2.v+1)) {
			cut[1]=make_pair(pos,fa[pos]);
			lnk[1]=make_pair(d1.end,d2.end);
		}
		parch.v++;
		chkmx(parch,ch[fa[pos]][0].end!=ch[pos][0].end?ch[fa[pos]][0]:ch[fa[pos]][1]);
		
	}
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			int u=e->to;
			DP(u,d2,parch);
		}
}
bool ud[MAXN];
int stack[MAXN],top;
int DFS(int pos,int d) {
	stack[++top]=pos;
	if(top==d+1)
		return stack[top-(top>>1)];//(d+1)>>1];
	for(Edge *e=id[pos];e;e=e->pre) 
		if(!ud[e->to]) {
			int u=e->to;
			ud[u]=1;
			int res=DFS(u,d);
			if(res)
				return res;
		}
	top--;
	return 0;
}
int main() {
//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int u,v;
		is>>u>>v;
		Adde(u,v);
	}
	Calc(1);
	DP(1,Node(-INF,0),Node(-INF,1));
	ud[cut[0].first]=1;
	top=0;
	ud[cut[0].second]=1;
	ud[cut[0].first]=0;
	lnk[0].first=DFS(lnk[0].first,dist.first);
	top=0;
	ud[cut[0].first]=1;
	ud[cut[0].second]=0;
	lnk[0].second=DFS(lnk[0].second,dist.second);
	
	for(int d=0;d<=1;++d)
		os<<Ans[d]<<' '<<cut[d].first<<' '<<cut[d].second<<' '<<lnk[d].first<<' '<<lnk[d].second<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

如果>s> s的数字有>c> c个，肯定是可以的 否则，设有tt个，那么有c−tc-t个1∗s1*s需要从剩下的≤s\le s的数字中取。总共要取s(c−t)s(c-t)个11，那只要这c−tc-t数字的和≥s(c−t)\ge s(c-t)即可 充分必要性显然

Tips

从最显然的特殊情况(>s> s)看起，有可能可以启发出分类讨论的大体思路，帮助解题。

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
#include "lucida"

using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=1000000+11;
struct Opt {
	char c;
	int x,y;
}op[MAXN];
template <class T>
struct Bit {
	T *a;int n;
	Bit(int n):n(n) {
		a=(T*)malloc((n+1)*sizeof(T));
	}
	#define lowbit(x) (x & -x)
	void Add(int pos,T x) {
		for(;pos<=n;pos+=lowbit(pos))
			a[pos]+=x;
	}
	T Sum(int pos) {
		T res=0;
		for(;pos;pos-=lowbit(pos))
			res+=a[pos];
		return res;
	}
	T Sum(int l,int r) {
		return Sum(r)-Sum(l-1);
	}
	#undef lowbit
};
int main() {
//	freopen("input","r",stdin);
	static int a[MAXN],nums[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {
		is>>op[i].c>>op[i].x>>op[i].y;
		nums[i]=op[i].y;
	}
	nums[m+1]=0;
	sort(nums+1,nums+2+m);
	int nc=unique(nums+1,nums+2+m)-nums-1;
	Bit<int> cnt(nc);
	Bit<int64> sum(nc);
	for(int i=1;i<=n;++i)
		cnt.Add(1,1);
	for(int i=1;i<=m;++i) {
		int cp=lower_bound(nums+1,nums+1+nc,op[i].y)-nums;
		if(op[i].c=='U') {
			int pp=lower_bound(nums+1,nums+1+nc,a[op[i].x])-nums;
			cnt.Add(pp,-1);
			cnt.Add(cp,1);
			sum.Add(pp,-nums[pp]);
			sum.Add(cp,nums[cp]);//pp..
			a[op[i].x]=op[i].y;
		} else {
			int gc=cnt.Sum(cp,nc);
			int64 tol=sum.Sum(1,cp-1);
			int c=op[i].x;
			os<<((gc>=c || tol>=(1ll*c-gc)*op[i].y)?"TAK":"NIE")<<'\n';
		}
	}
	return 0;
}

发表于 | 更新于

Link

Solution

比较常见的技巧吧。 枚举右端点，在线段树的每个节点pp维护序列中点pp到右端点的和，然后就是一个区间修改和区间查询了。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include "lucida"
const int MAXN=1000000+11;
using std::max;
namespace _SegTree_ {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		int64 maxv,add;
		Node();
		void Down();
		void Up();
		void Add(int64);
		void *operator new(size_t);
	}*null=new Node;
	Node::Node(){
		maxv=add=0;
		son[0]=son[1]=null;
	}
	void *Node::operator new(size_t) {
		static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
		return Me++;
	}
	void Node::Down() {
		if(add) {
			son[0]->Add(add);
			son[1]->Add(add);
			add=0;
		}
	}
	void Node::Up() {
		maxv=max(son[0]->maxv,son[1]->maxv);
	}
	void Node::Add(int64 adv) {
		if(this==null) 
			return;
		add+=adv;
		maxv+=adv;
	}
	struct SegTree {
		Node *root;int L,R;
		SegTree(){}
		SegTree(int,int);
		void Build(Node*&,int,int);
		void Edit(Node*,int,int,int,int,int64);
		void Edit(int,int,int64);
		int64 Access(Node*,int,int,int,int);
		int64 Access(int,int);
	};
	SegTree::SegTree(int L,int R):L(L),R(R) {
		root=null;
		Build(root,L,R);
	}
	void SegTree::Build(Node *&pos,int L,int R) {
		pos=new Node;
		if(L!=R) {
			int Mid=(L+R)>>1;
			Build(pos->son[0],L,Mid);
			Build(pos->son[1],Mid+1,R);
		}
	}
	void SegTree::Edit(Node *pos,int L,int R,int l,int r,int64 add) {
		if(L==l && R==r)
			pos->Add(add);
		else {
			int Mid=(L+R)>>1;
			pos->Down();
			if(r<=Mid)
				Edit(pos->son[0],L,Mid,l,r,add);
			else if(Mid+1<=l)
				Edit(pos->son[1],Mid+1,R,l,r,add);
			else {
				Edit(pos->son[0],L,Mid,l,Mid,add);
				Edit(pos->son[1],Mid+1,R,Mid+1,r,add);
			}
			pos->Up();
		}
	}
	void SegTree::Edit(int l,int r,int64 add) {
		if(!l || !r || l>r)
			return;
		Edit(root,L,R,l,r,add);
	}
	int64 SegTree::Access(Node *pos,int L,int R,int l,int r) {
		if(L==l && R==r)
			return pos->maxv;
		else {
			int Mid=(L+R)>>1;
			pos->Down();
			if(r<=Mid)
				return Access(pos->son[0],L,Mid,l,r);
			else if(Mid+1<=l)
				return Access(pos->son[1],Mid+1,R,l,r);
			else
				return max(Access(pos->son[0],L,Mid,l,Mid),Access(pos->son[1],Mid+1,R,Mid+1,r));
		}
	}
	int64 SegTree::Access(int l,int r) {
		return Access(root,L,R,l,r);
	}
}using _SegTree_::SegTree;
int main() {
//	freopen("input","r",stdin);
	static int movie[MAXN],w[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i)
		is>>movie[i];
	for(int i=1;i<=m;++i)
		is>>w[i];
	SegTree seg(1,n);
	static int next[MAXN],pre[MAXN],now[MAXN];
	for(int i=1;i<=n;++i) {
		pre[i]=now[movie[i]];
		next[now[movie[i]]]=i;
		now[movie[i]]=i;
		//pre[i]=pre[i]?pre[i]:1;
	}
	for(int i=1;i<=m;++i)
		next[now[i]]=n+1;//now[m]...
	int64 Ans=0;
	for(int i=1;i<=n;++i) {
		int mv=movie[i];
		//seg.Edit(pre[i],i-1,-w[mv]);
		//seg.Edit(i,next[i]-1,w[mv]);
		seg.Edit(pre[pre[i]]+1,pre[i],-w[mv]);
		seg.Edit(pre[i]+1,i,w[mv]);
		chkmx(Ans,seg.Access(1,i));
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

很喵的想法，，虽然应该比较常见

Solution

当步长比较大的时候，步数就会很小 所以步长>n>\sqrt n的时候暴力走 只计算步长≤n\le \sqrt n的情况，就大大简化了问题！！！ 这样对于小步长的计算，只需要预处理数组sum[pos][B]sum[pos][B]，表示步长为BB的时候走到根节点的权值和。 配合倍增和一点很多细节判断就可以过掉了。

Tips

没错，这种思路要记住：大范围暴力，小范围预处理！(怎么感觉不太对的样子233)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "lucida"

using std::swap;
const int MAXN=5e4+11,B=250,LOG=16,MAXLOG=20,MAXB=B+1;
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++;//Me...!!
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
int dfs[MAXN<<1],par[MAXN][MAXLOG],dep[MAXN]={0,1},dc,lbd[MAXN],rbd[MAXN],w[MAXN],sum[MAXN][MAXB],stack[MAXN],top;
void DFS(int pos) {
	for(int lg=1;lg<=LOG;++lg)
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	stack[++top]=pos;
	dfs[++dc]=pos;lbd[pos]=dc;
	for(int b=1;b<=B;++b) {
		sum[pos][b]=w[pos]+(top>b?sum[stack[top-b]][b]:0);
	}
	for(Edge *e=id[pos];e;e=e->pre) {
		int u=e->to;
		if(u==par[pos][0]) continue;
		par[u][0]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
		dfs[++dc]=pos;
	}
	rbd[pos]=dc;top--;
}
int f[MAXN<<1][MAXLOG],log_2[MAXN<<1];
void SparseTable() {
	log_2[0]=-1;
	for(int i=1;i<=dc;++i) {
		f[i][0]=dfs[i];
		log_2[i]=log_2[i>>1]+1;
	}
	for(int j=1,endj=log_2[dc];j<=endj;++j)
		for(int i=1,endi=dc-(1<<j)+1;i<=endi;++i) {
			int pl=f[i][j-1],pr=f[i+(1<<j>>1)][j-1];
			f[i][j]=dep[pl]<dep[pr]?pl:pr;
		}
}
int LCA(int p1,int p2) {
	p1=lbd[p1],p2=lbd[p2];
	if(p1>p2) swap(p1,p2);
	int lg=log_2[p2-p1+1],pl,pr;
	return dep[pl=f[p1][lg]]<dep[pr=f[p2-(1<<lg)+1][lg]]?pl:pr;
}
int Jump(int pos,int c) {
	for(int lg=log_2[c];~lg;--lg)
		if((1<<lg)<=c) {
			c-=(1<<lg);
			pos=par[pos][lg];
		}
	return pos;
}
int Sum(int s,int t,int c) {
	if(c<B)
		return sum[s][c]-sum[t][c]+w[t];
	int res=w[s];
	while(s!=t) {
		s=Jump(s,c);
		res+=w[s];
	}
	return res;
}
int Walk(int s,int t,int c) {
	//sum[pos][B] 当前位置开始c步间隔跳到根节点的sumval
	int lca=LCA(s,t),rs=0,rt=0;
	//Part 1 让指针s走到最后一个<=lca的节点上
	//Part 2 让指针t走到第一个>lca的节点上
	int len=dep[s]-dep[lca];
	if(len<c)
		rs=w[s];
	else {
		len-=len%c;int dest=Jump(s,len);
		rs=Sum(s,dest,c);
		s=dest;
	}
	if(s!=t) {
		len=dep[t]-dep[lca];
		int dis2next=c-(dep[s]-dep[lca]),
			remain=len-dis2next;
		rt=w[t];
		if(remain>0) {
			len=remain;
			remain=len%c;
			t=Jump(t,remain);
			rt+=(bool)remain*w[t];
			if(len>remain) {
				len-=remain;
				int dest=Jump(t,len);
				rt+=Sum(t,dest,c)-w[t];
			} 
		}
	}
	return rs+rt;
}
int main() {

//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n;++i)
		is>>w[i];
	for(int i=1;i<=n-1;++i) {
		int u,v;
		is>>u>>v;
		Adde(u,v);
	}
	DFS(1);
	SparseTable();
	static int route[MAXN],step[MAXN];
	for(int i=1;i<=n;++i)
		is>>route[i];
	for(int i=1;i<=n-1;++i) {
		is>>step[i];
		os<<Walk(route[i],route[i+1],step[i])<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

考虑最最最暴力的做法 每个限制是一个区间[l,r][l,r]集体小于一个点uu的条件，那就把区间的每个点依次向这个点连长度为11的有向边，然后拓扑序。 好吧显然这个做法是闹着玩的 然后考虑一个优化的做法：每个限制建立一个新点pp，点pp到点uu连11，区间[l,r][l,r]集体到点pp连00，然后拓扑序。(为什么让我想到了SAM的构造233) 这个虽然科学了一些，但显然还是啄急。 然后高能： 考虑到每个限制是一个区间连到点的形式，那就用线段树来优化，把区间拆成logL\log L段，

Tips

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
102
103
#include "lucida"

const int MAXN=100000+11,INF=1e9,MAXM=200000+11,SIZE=(MAXN<<2)+MAXM,
	  SIZE_E=4021928;//m log^2 n+n*4+k?;
void Adde(int,int,int);
int son[SIZE][2],pc,TL,TR,ref[MAXN],a[SIZE],f[SIZE];
void Build(int &pos,int L,int R) {
	pos=++pc;
	f[pos]=1;
	if(L!=R) {
		int Mid=(L+R)>>1;
		Build(son[pos][0],L,Mid);
		Build(son[pos][1],Mid+1,R);
		Adde(son[pos][0],pos,0);
		Adde(son[pos][1],pos,0);
	}
	else ref[L]=pos;
}
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre){}
	void *operator new(size_t);
}*id[SIZE];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((SIZE_E)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
int ind[SIZE];
void Adde(int f,int t,int v) {
	ind[t]++;
	id[f]=new Edge(t,v,id[f]);
}
void Ins(int pos,int L,int R,int l,int r,int to,int v) {
	if(L==l && R==r)
		Adde(pos,to,v);
	else {
		int Mid=(L+R)>>1;
		if(r<=Mid)
			Ins(son[pos][0],L,Mid,l,r,to,v);
		else if(Mid+1<=l)
			Ins(son[pos][1],Mid+1,R,l,r,to,v);
		else {
			Ins(son[pos][0],L,Mid,l,Mid,to,v);
			Ins(son[pos][1],Mid+1,R,Mid+1,r,to,v);
		}
	}
}
void Adde(int l,int r,int t,int v) {
	if(l<=r)
		Ins(1,TL,TR,l,r,t,v);
}
int main() {
//	freopen("input","r",stdin);
	int n,s,m;is>>n>>s>>m;
	int root;Build(root,TL=1,TR=n);
	for(int i=1;i<=s;++i) {
		int p;
		is>>p;
		is>>a[ref[p]];
		f[ref[p]]=a[ref[p]];
	}
	for(int i=1;i<=m;++i) {
		int cur=++pc,l,r,k;
		is>>l>>r>>k;
		while(k--) {
			int p;is>>p;
			Adde(cur,ref[p],1);
			Adde(l,p-1,cur,0);
			l=p+1;
		}
		Adde(l,r,cur,0);
	}
	static int Q[SIZE];
	int he=1,ta=0;
	bool tak=1;
	for(int i=1;i<=pc;++i) 
		if(!ind[i]) 
			Q[++ta]=i;
	while(he<=ta) {
		int cur=Q[he++];
		for(Edge *e=id[cur];e;e=e->pre) {
			int u=e->to;
			if(--ind[u]==0)
				Q[++ta]=u;
			chkmx(f[u],f[cur]+e->v);
			if(f[u]>INF || (a[u] && f[u]>a[u])) {
				tak=0;
				goto out;
			}
		}
	}
out:
	if(ta!=pc) tak=0;
	if(tak) {
		os<<"TAK"<<'\n';
		for(int i=1;i<=n;++i)
			os<<f[ref[i]]<<(i==n?'\n':' ');
	}
	else 
		os<<"NIE"<<'\n';
	return 0;
}

发表于 | 更新于

Link

看出来应该是根据单调性来O(n)O(n)做 双指针？不好弄 三指针？不好弄 五指针？贰叁叁

Solution

预处理出从每个点开始长度为dd的区间和g[]g[] 枚举rr，找出当前合法的最靠前的ll。合法的话，需要保证Sum(l,r)−max{g[l∼r−d+1]}<pSum(l,r)-max\{g[l\sim r-d+1]\}< p 这个最大值用单调队列维护即可。

Tips

基于单调性的O(n)O(n)做法有多种，不应该只纠结于

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
#include "lucida"
using std::partial_sum;
using std::max;
const int MAXN=2000000+11;
int main() {
//	freopen("input","r",stdin);
	static int64 w[MAXN],pref[MAXN],dsum[MAXN];
	static int Q[MAXN],he,ta;
	int n,d;int64 p;is>>n>>p>>d;
	for(int i=1;i<=n;++i)
		is>>w[i];
	partial_sum(w+1,w+1+n,pref+1);
	for(int i=1;i<=n;++i) 
		dsum[i]=pref[i]-pref[i-d>=0?i-d:0];
	int Ans=0;
	for(int l=1,r=1;r<=n;++r) {
		while(he<=ta && dsum[Q[ta]]<dsum[r]) 
			ta--;
		Q[++ta]=r;
		while(l<=r && he<=ta && pref[r]-pref[l-1]-dsum[Q[he]]>p) {
			l++;
			while(he<=ta && Q[he]-d+1<l)
				he++;
		}
		if(pref[r]-pref[l-1]-dsum[Q[he]]<=p)
			chkmx(Ans,r-l+1);
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

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 构造合法方案的题真的可以出的很水。要好好研究给的限制条件，看看能否转化成简单的问题

发表于 | 更新于

Link

被这道题前前后后克了10h。 我也实在不想回头看这道题目了 但是为了让这10h有意义 我还是硬着头皮写点东西吧。

Solution

树形DP 最暴力的状态是f[pos][i][j][k]f[pos][i][j][k]表示在以pospos为根的子树中，pospos的父节点至少安装ii个，pospos安装了jj个，pospos的子节点安装了kk个的最小代价。 优化一下，拆成三个 g[pos][i]g[pos][i]表示在以pospos为根的子树中，表示pospos不安装，pospos的子节点安装了ii个的最小代价 h[pos][i]h[pos][i]表示pospos安装了ii个的最小代价 r[pos][i]r[pos][i]表示pospos不安装，需要父节点安装至少ii个的最小代价 在DP中，还需要一个辅助的状态f[pos][i][j]f[pos][i][j]，表示在以pospos为根的子树中，pospos不安装，pospos的子节点安装了ii个，父节点安装了jj个的最小代价 显然g[pos][i]=min{f[pos][i][j],j≤i}g[pos][i]=\min \{f[pos][i][j],j \le i\} r[pos][i]=min{f[pos][j][j+i]}r[pos][i]=\min\{f[pos][j][j+i]\} h[pos][i]=min{min{g[pos][j]},min{r[pos][1∼i]}}h[pos][i]=\min \{\min\{g[pos][j]\},\min\{r[pos][1\sim i]\}\} 然后剩下的问题就是转移f[][][]f[][][]了 要用每个子节点优化，在寻找最优方案的过程中不能把原数组覆盖，要在一个f′[][][]f'[][][]中计算，最后再 过去。 所以转移就两种情况： 1.让子节点多安装 2.让父节点多安装。 那就枚举每个状态f[pos][i][j]f[pos][i][j]，枚举kk——需要多安装几个 1.f[pos][i][j]+h[u][k]→f′[pos][min{i+k,2}][j]1.f[pos][i][j]+h[u][k]\rightarrow f'[pos][\min \{i+k,2\}][j] 2.f[pos][i][j]+g[u][k]→f′[pos][i][max{2−k,j}]2.f[pos][i][j]+g[u][k]\rightarrow f'[pos][i][\max\{2-k,j\}] 第一个转移里面的min\min很显然：一个点安装两个以上是完全意义不明的 第二个转移的含义相当于多选了孙子节点，就需要多选父节点——根据题意可以感受一下。至于第二个里面的max\max，考虑一下f[pos][i][j]f[pos][i][j]的i+ji+j肯定是需要≥2\ge 2的，否则肯定是不合法的状态。这样做就可以使得合法的值不会进入不合法的状态。好吧其实我也搞不清楚为什么 只是为了让这个状态在增加了一个子树之后变得合法。

Tips

一开始想DP每个点到父节点的连边的代价，导致非常麻烦 费力写出来之后发现有些情况没有考虑 唉还能说什么呢人太弱只能被虐 以后还是慎重考虑在树形DP中DP点到父节点的值吧 花这么久也是醉了 也许以后被克许久之后应该早点看题解？

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
#include "lucida"
using std::min;
using std::max;
using std::pair;
using std::make_pair;

template <class T> inline T min(const T &a,const T &b,const T &c) {return min(a,min(b,c));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d){return min(a,min(b,c,d));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e){return min(a,min(b,c,d,e));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e,const int &f){return min(a,min(b,c,d,e,f));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e,const int &f,const int &g){return min(a,min(b,c,d,e,f,g));}


const int MAXN=200000+11,INF=0x1f1f1f1f;
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]);
}
struct FSMin {
	pair<int,int> v[2];
	FSMin() {
		v[0]=v[1]=make_pair(INF,-1);
	}
	pair<int,int> &operator [](int x){
		return v[x];
	}
	void operator <<(pair<int,int> nv) {
		if(v[0]>nv) {
			v[1]=v[0];
			v[0]=nv;
		} else if(v[1]>nv) {
			v[1]=nv;
		}
	}
};

int f[MAXN][3][3],g[MAXN][3],p[MAXN][3],r[MAXN][3],fa[MAXN],temp[3][3];
void DP(int pos,int fa=0) {
	p[pos][1]=1,p[pos][2]=2;
	f[pos][0][0]=0;
	for(Edge *e=id[pos];e;e=e->pre) if(e->to!=fa) {
		int u=e->to;
		DP(u,pos);
		p[pos][1]+=min(p[u][1],p[u][2],g[u][0],g[u][1],g[u][2],r[u][1]);
		p[pos][2]+=min(p[u][1],p[u][2],g[u][0],g[u][1],g[u][2],r[u][1],r[u][2]);
		memset(temp,31,sizeof(temp));
		for(int i=0;i<=2;++i)
			for(int j=0;j<=2;++j) {
				for(int k=1;k<=2;++k) chkmn(temp[min(i+k,2)][j],f[pos][i][j]+p[u][k]);
				for(int k=0;k<=2;++k) chkmn(temp[i][max(2-k,j)],f[pos][i][j]+g[u][k]);
			}
		 memcpy(f[pos],temp,sizeof(temp));
	}
	for(int i=0;i<=2;++i)
		for(int j=0;j<=i;++j)
			chkmn(g[pos][i],f[pos][i][j]);
	r[pos][1]=min(f[pos][0][1],f[pos][1][2]);
	r[pos][2]=f[pos][0][2];
}
int main() {
	freopen("input","r",stdin);
	memset(f,31,sizeof(f));
	memset(g,31,sizeof(g));
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int a,b;
		is>>a>>b;
		Adde(a,b);
	}
	DP(1);
	int Ans=min(p[1][1],p[1][2],g[1][0],g[1][1],g[1][2]);
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

一眼二分答案+树形DP，写出来之后T了？ 好吧。 正解是一遍树形DP，需要总结一些性质，挺有意思 首先，一个点如果不被子节点策反，那它的父节点也一定不会被策反 然后，一个点如果被策反了，那只要在父节点的子树中占比小，父节点也不会被策反 然后就DP： 设f[pos]f[pos]表示节点pospos不被策反的最小比例 对应上面两种情况，有 f[pos]=max{min{f[u],size[u]size[pos]−1}},u∈son[pos]f[pos]=max\{min\{f[u],\dfrac {size[u]}{size[pos]-1}\}\},u\in son[pos] 边界情况f[pos]=1,son[pos]==∅f[pos]=1,son[pos]==\emptyset 思路对我来说比较新奇，挺有意思

Tips

计算的新思路：先不管某一条性质，求出所有的答案之后再对满足这条性质的点的答案进行处理

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
//Code by Lucida
#include<bits/stdtr1c++.h>
//Universal Declarations
typedef long long int64;
template <class T> inline void get(T &);
template <class T> inline void put(T);
template <> inline void put<double>(double);
template <class T> inline bool chkmx(T &,const T &);
template <class T> inline bool chkmn(T &,const T &);
using std::swap;
using std::max;
using std::min;

//Main Program
const int MAXN=500000+11;
const double eps=1e-7;
inline int fcmp(const double &x) {
	return -eps<x && x<eps?0:(x<0?-1:1);
}
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 *Me=(Edge*)malloc(MAXN*sizeof(Edge));
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
}
int sz[MAXN];
double f[MAXN];
//f[pos]表示pos不被策反的最小rate
//u被策反，sz[u]/(sz[pos]-1)比f[u]小就行
void DP(int pos) {
	sz[pos]=1;
	if(!id[pos])
		f[pos]=1;
	else {
		f[pos]=0;
		for(Edge *e=id[pos];e;e=e->pre) {
			int u=e->to;
			DP(u);
			sz[pos]+=sz[u];
		}
		for(Edge *e=id[pos];e;e=e->pre) {
			int u=e->to;
			chkmx(f[pos],min(f[u],1.0*sz[u]/(sz[pos]-1)));
		}
	}
}
int main() {
	int n,K;get(n),get(K);
	for(int i=2;i<=n;++i) {
		int fa;get(fa);
		Adde(fa,i);
	}
	DP(1);
	double Ans=0;
	for(int i=1;i<=n;++i)
		if(sz[i]>K) chkmx(Ans,f[i]);
	put(Ans),putchar('\n');
	return 0;
}

//Universal Definitions
template <class T> inline void get(T &x) {
	static bool f;static char ch;
	for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
	for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
	x=f?-x:x;
}
template <class T> inline void put(T x) {
	printf("%d",x);
}
template <> inline void put<double>(double x) {
	printf("%lf",x);
}
template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

发表于 | 更新于

看到Menci大神在github上放了一个头文件，感觉很不错的样子。 我也看够了写程序的时候在程序头上的一段声明和#define，于是就以此为契机开始写一下自己的头文件 我之前的程序在开头只有chkmx(),chkmn()和几个IO宏的定义，因为这些都是常用好写但每次都写比较烦的东西。平常在头文件里用这些，可以加快速度，也可以保证在考试之前能迅速写完。 但是之前还是把代码直接放在程序开头，为了美观还是尽量地精简了一下。现在写到头文件里面了，就不用怕是否精简咯。 第一个版本： 

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
//Code by Lucida
#include<bits/stdtr1c++.h>
typedef long long int64;
namespace IO
{
#ifdef FastIO
	const int IN=1e7,OUT=1e7;
#ifdef getchar
	#undef getchar
#endif
#ifdef putchar
	#undef putchar
#endif
	char in[IN],*ip=in,*ie=in,out[OUT],*op=out,*oe=out+OUT;
	#define getchar() ( (ip==ie && (ie=(ip=in)+fread(in,1,IN,stdin),ip==ie))?EOF:*ip++ )
	inline void oflush() {
		fwrite(out,1,op-out,stdout);
		op=out;
	}
	#define putchar(x)( (op==oe?(oflush(),*op++):*op++)=(x) )
#endif
	template <class T> inline void get(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
	}
#ifndef FastIO
	template <> inline void get<double>(double &x) {
		scanf("%lf",&x);
	}
#endif
	template <> inline void get<char>(char &x) {
		while(x=getchar(),((x<'0' || '9'<x) && (x<'a' || 'z'<x) && (x<'A' || 'Z'<x)));
	}
	template <> inline void get<char*>(char *&x) {
		char *cp=x;
		while(*cp++=getchar(),(*cp!=' ' && *cp!='\r' && *cp!='\n' && *cp!=EOF));
		*--cp=0;
	}

	template <class T> inline void put(T x) {
		if(!x)
			putchar('0');
		else {
			if(x<0) {
				putchar('-');
				x=-x;
			}
			static char stack[30]={0};
			char *top=stack;
			for(;x;x/=10) *++top=x%10+'0';
			while(*top) putchar(*top--);
		}
	}
#ifndef FastIO
	template <> inline void put<double>(double x) {
		printf("%lf",x);
	}
#endif
	template <> inline void put<char>(char x) {
		putchar(x);
	}
	template <> inline void put<char*>(char* x) {
		while(*x)
			putchar(*x++);
	}
}

template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

using std::swap;
using std::max;
using std::min;
using IO::get;
using IO::put;

用了一段时间，还是感觉不太爽，因为参数只能有一个，要一下读写一串还得写好几遍函数名。然而参数包模板是C++11才兹瓷的，而C的va_arg还要传一个终止符，感觉非常不爽。 于是就仿照cpp的IO流写了两个类 第二个版本 

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
//Code by Lucida
#include<bits/stdtr1c++.h>
typedef long long int64;

namespace IO {
	struct Ist {
		template <class T> Ist &operator >>(T &x);
		template <class T> Ist &operator >>(T *x);
	}is;
	template <class T> Ist &Ist::operator >>(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
		return *this;
	}
	template <class T> Ist &Ist::operator >>(T *x) {
		while(*x++=getchar(),(*x!=' ' && *x!='\r' && *x!='\n' && *x!=EOF));
		*--x=0;
		return *this;
	}
	template <> Ist &Ist::operator >>(double &x) {
		scanf("%lf",&x);
		return *this;
	}
	template <> Ist &Ist::operator >>(char &x) {
		while(x=getchar(),((x<'0' || '9'<x) && (x<'a' || 'z'<x) && (x<'A' || 'Z'<x)));
		return *this;
	}

	struct Ost {
		template <class T> Ost &operator <<(T x);
		template <class T> Ost &operator <<(T *x);
	}os;
	template <class T> Ost &Ost::operator <<(T x) {
		if(!x)
			putchar('0');
		else {
			if(x<0) putchar('-'),x=-x;
			static char stack[30]={0};
			char *top=stack;
			for(;x;x/=10) *++top=x%10+'0';
			while(*top) putchar(*top--);
		}
		return *this;
	}
	template <class T> Ost &Ost::operator <<(T* x) {
		while(*x) putchar(*x++);
		return *this;
	}
	template <>	Ost &Ost::operator <<(double x) {
		printf("%lf",x);
		return *this;
	}
	template <> Ost &Ost::operator <<(char x) {
		putchar(x);
		return *this;
	}
}

template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

using std::swap;
using std::max;
using std::min;
using IO::is;
using IO::os;

写的时候还学习了一下模板特化的原则

5.模板特化时的匹配规则 (1) 类模板的匹配规则 最优化的优于次特化的，即模板参数最精确匹配的具有最高的优先权 例子： 

1
2
3
template <class T> class vector{//…//}; // (a)  普通型
template <class T> class vector<T*>{//…//};  // (b) 对指针类型特化
template <>   class vector <void*>{//…//};  // (c) 对void*进行特化

每个类型都可以用作普通型（a）的参数，但只有指针类型才能用作（b）的参数，而只有void*才能作为(c)的参数 (2) 函数模板的匹配规则 非模板函数具有最高的优先权。如果不存在匹配的非模板函数的话，那么最匹配的和最特化的函数具有高优先权 例子： 

1
2
3
4
5
6
7
8
9
10
11
12
template <class T> void f(T);  // (d)
template <class T> void f(int, T, double); // (e)
template <class T> void f(T*);  // (f)
template <> void f<int> (int) ; // (g)
void f(double);  // (h)
bool b;
int i;
double d;
f(b); // 以 T = bool 调用 （d）
f(i,42,d) // 以 T = int 调用（e）
f(&i) ; // 以 T = int* 调用（f）
f(d);  //  调用（g）

所以就可以写一个对指针类型的模板，专门处理const char *和char *了。 模板写的差不多了，难道在提交OJ的时候还要粘贴上吗？感觉非常不爽，于是怒写了一个OJ处理程序 

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
#include <lucida>
#include <windows.h>
const char *headerfile="C:\\mingw4.4.5\\lib\\gcc\\i686-mingw32\\4.4.5\\include\\c++\\lucida";
using std::ifstream;
using std::ofstream;
using std::string;
using std::cout;
using std::cin;
using std::ios;

const int IN_SIZE=10000000;
void CtrlC(const char *sourcefile) {
	FILE *infile=fopen(sourcefile,"r");
	char *inbuf=(char*)malloc(IN_SIZE);
	size_t length=fread(inbuf,1,IN_SIZE,infile);
	fclose(infile);

	HGLOBAL clipbuffer=GlobalAlloc(GMEM_DDESHARE,length);
	char *buffer=(char*)GlobalLock(clipbuffer);
	memcpy(buffer,inbuf,length);
	GlobalUnlock(clipbuffer);
	
	if(OpenClipboard(NULL)) {
		EmptyClipboard();
		SetClipboardData(CF_TEXT,clipbuffer);
		CloseClipboard();
	} else {
		os<<"Access Denied\n";
	}
	//string cmd("clip < ");cmd+=sourcefile;system(cmd.c_str());
}
int main(int argc,char **argv) {
	ifstream code(argv[1]),header(headerfile);
	ofstream dest((string(strtok(argv[1],"."))+".oj").c_str(),ios::trunc);
	string str;
	while(getline(code,str))
	{
		if(str[0]!='\\') {	
			if(str.find("<lucida>")!=string::npos) {
				while(getline(header,str))
					dest<<str<<'\n';
				continue;
			}
			if(str.find("freopen")!=string::npos)
				dest<<"//";
			dest<<str<<'\n';
		}
		else
			dest<<str<<'\n';
	}
	code.close();
	dest.close();
	header.close();
#ifdef WIN32
	CtrlC((string(strtok(argv[1],"."))+".oj").c_str());
#endif
	return 0;
}

这样，只要在cmd中调用 

1
oj *.cpp

就会生成*.oj文件，并把其中的内容写入剪贴板。 在实现自动复制的时候，还经历了一番周折：fread函数每次返回的size_t是对的，但是在fread到的数组里总是多了几行！！debug了好久才发现这个问题。。这也许是个C的bug吧。。 写完之后我忽然得知windows的cmd自带了clip命令，可以实现文件内容的复制。。但是试了试，汉字复制之后就乱码了233。。 头文件应该是会持续改动更新的吧。。