Tag: 思路题

题目传送门：http://codeforces.com/contest/712/problem/C
官方题解：http://codeforces.com/blog/entry/47050
中文题面：http://blog.csdn.net/queuelovestack/article/details/52503162

这个题目考试的时候，看到都有1000+的人A掉了
然而我还是一脸懵逼
虽然看了题解以后，感觉题还不错，但为什么一点不觉得这个题好QAQ
一定是被恶心到了…..

考虑倒着贪心。
首先每一条边，只会成为限制，且这个限制越大越好
所以，肯定是每一次选择一条边加到上限
至于是哪一条边，肯定是最短的那条边对于周长的贡献最大

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	int arr[4],pur=read(),vout=0;
	arr[1] = arr[2] = arr[3] = read();
	while (arr[1] < pur) {
		arr[1] = min(pur,arr[2]+arr[3]-1);
		sort(arr+1,arr+1+3); vout++;
	} cout<<vout<<endl;
	return 0;
}

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=741

虽然是“网络流24题”之一，然而可以O(n)搞
来来来，我们一起来推式子！
6541324587

#include<bits/stdc++.h>
using namespace std;

const int N = 100+9;

int n,arr[N],sum,vout,sta;

inline int read(){
	char c=getchar(); int ret = 0, f = 1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	n = read(); 
	for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n;
	for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1];
	nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2];
	for (int i=1;i<=n;i++) vout += abs(arr[i]-sta);
	cout<<vout<<endl;  
	return 0;
} 

感觉真的是好神奇啊！

题目传送门：http://pan.baidu.com/s/1hsLh92W
OJ传送门：http://oi.cdshishi.net:8080/Problem/1712

这一道题，我一眼看到的时候，也是“啊”的。博弈论？不会啊QAQ
最后只能打了暴力，结果还打错了QAQ

来说一说正解。
我们定义三种节点：
1.无名必胜
2.有名必胜
3.先手必胜

再来讨论一下这三种节点间的关系：
假如一个节点的儿子中，1、2两种类型的节点一样多，则为类型3
否则，1、2哪种多，该节点就是那种节点

于是搞一个树形DP，就可以搞出根节点的类型
显然，如果是类型3，则无解
如果是类型2，则只有部分节点可选
如果是类型1，则全部的叶子结点都可选

另外，本题还要注意，因为非叶子结点的颜色，最终会取决于它儿子节点的颜色
所以，第一步走的节点，一定是叶子结点，否则，并没有什么卵用QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;

int n,vout,que[MAXN],type[MAXN],num[MAXN][3];
vector<int> G[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void init(){
	n = read();
	for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0;
	for (int i=1;i<=n;i++) G[read()].push_back(i);
	for (int i=1;i<=n;i++) type[i] = read() + 1;
	
	int fro,bak; que[fro=bak=1] = 1;
	while (fro < n) {
		int w = que[bak++];
		for (int i=0;i<(int)G[w].size();i++)
			que[++fro] = G[w][i];
	} 
}

void GetAns(int w){
	if ((int)G[w].size() == 0) {
		if (type[w] == 0) que[++vout] = w;
	} else {
		int t = num[w][2] - num[w][1];
		if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++)
			GetAns(G[w][i]);
	}
}

int main(){
	freopen("ah.in","r",stdin);
	freopen("ah.out","w",stdout);
	int T; cin>>T;
	while (T--) {
		init();
		for (int k=n,i=que[k];k;i=que[--k]){
			if ((int)G[i].size() == 0) continue;
			else { 
				for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++;
				if (num[i][2] == num[i][1]) type[i] = 0;
				else if (num[i][1] > num[i][2]) type[i] = 1;
				else type[i] = 2;
			}
		} if (type[1] == 1) {
			int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i;
			printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl;
		} else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;}  
		else printf("-1\n"); 
	}
	return 0;
}