160104 HAOI 2013 요약

T1
한쪽은 무게가 많이 나가고, 반대로 여러 배낭을 한 번 뛰고, 그 인형은 왼쪽과 오른쪽의 돈을 일일이 세어 보았다.
시험장상수를 오래 끊었는데 데이터가 100이 터진 거예요.
T2
dp[I]를 설정하면 현재 점 검은색이 이기려면 반드시 몇 개의 잎사귀 노드를 획득해야 합니다
만약 현재 흰색 노드의 결정점이라면 dp[I]=sigmadp[son[i]]
만약 현재 검은색 노드의 결정점이라면 dp[I]=min{dp[son[i]}
경계는 잎 노드 dp=1
시험장에서 부주의로 첫 번째 수와 두 번째 수를 반대로 출력했다...100->10
T3
폭력

//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
using namespace std;
inline void splay(int &v){
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
int dp1[1005][1005];
int dp2[1005][1005];
int a[1005],b[1005],c[1005];
int main(){
	freopen("bag.in","r",stdin);
	freopen("bag.out","w",stdout);
	int n;splay(n);
	for(int i=1;i<=n;i++){
		splay(a[i]),splay(b[i]),splay(c[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1000;j>=0;j--){
			for(int k=0;k<=c[i];k++){
				if(j-k*a[i]<0)break;
				int l=dp1[i-1][j-k*a[i]]+k*b[i];
				if(l>dp1[i][j])dp1[i][j]=l;
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=1000;j>=0;j--){
			for(int k=0;k<=c[i];k++){
				if(j-k*a[i]<0)break;
				int l=dp2[i+1][j-k*a[i]]+k*b[i];
				if(l>dp2[i][j])dp2[i][j]=l;
			}
		}
	}
	int q,lim,money;splay(q);
	for(int i=1;i<=q;i++){
		splay(lim),splay(money);
		int ans=0;lim++;
		for(int i=0;i<=money;i++){
			int p=dp1[lim-1][i]+dp2[lim+1][money-i];
			if(p>ans)ans=p;
		}
		printf("%d
",ans);
	}
}

//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define white 0
#define black 1
#define inf 1000000000
using namespace std;
inline void splay(int &v){
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
struct Edge{
	int to,next;
}edge[400010];
int first[200010],size,n;
void addedge(int x,int y){
	size++;
	edge[size].to=y;
	edge[size].next=first[x];
	first[x]=size;
}
int dp[200010];
bool isblack[200010],iswhite[200010];
bool is[200010];int col[200010];
void dfs(int now,int fa){
	col[now]=(col[fa]^1);is[fa]=false;
	for(int u=first[now];u;u=edge[u].next){
		if(edge[u].to!=fa){
			dfs(edge[u].to,now);
		}
	}
}
void treedp1(int now,int fa){
	if(is[now]){dp[now]=1;return;}
	dp[now]=((col[now]==black)?inf:0);
	for(int u=first[now];u;u=edge[u].next){
		if(edge[u].to==fa)continue;
		treedp1(edge[u].to,now);
		if(col[now]==black)dp[now]=min(dp[now],dp[edge[u].to]);
		if(col[now]==white)dp[now]+=dp[edge[u].to];
	}
}
void treedp2(int now,int fa){
	if(is[now]){dp[now]=1;return;}
	dp[now]=((col[now]==black)?0:inf);
	for(int u=first[now];u;u=edge[u].next){
		if(edge[u].to==fa)continue;
		treedp2(edge[u].to,now);
		if(col[now]==white)dp[now]=min(dp[now],dp[edge[u].to]);
		if(col[now]==black)dp[now]+=dp[edge[u].to];
	}
}
void dfs1(int now,int fa){
	if(is[now]){isblack[now]=true;return;}
	for(int u=first[now];u;u=edge[u].next){
		if(edge[u].to==fa)continue;
		if(col[now]==white)dfs1(edge[u].to,now);
		else if(dp[edge[u].to]==dp[now])dfs1(edge[u].to,now);
	}
}
void dfs2(int now,int fa){
	if(is[now]){iswhite[now]=true;return;}
	for(int u=first[now];u;u=edge[u].next){
		if(edge[u].to==fa)continue;
		if(col[now]==black)dfs2(edge[u].to,now);
		else if(dp[edge[u].to]==dp[now])dfs2(edge[u].to,now);
	}
}
void calc_black(){
	treedp1(1,0);dfs1(1,0);
}
void calc_white(){
	treedp2(1,0);dfs2(1,0);
}
int main(){
	int _q=20<<20;
	char *_p=(char*)malloc(_q)+_q;
	__asm__("movl %0, %%esp
"::"r"(_p));
	freopen("gametree.in","r",stdin);
	freopen("gametree.out","w",stdout);
	splay(n);memset(is,true,sizeof(is));
	for(int i=2;i<=n;i++){
		int x;splay(x);
		addedge(i,x),addedge(x,i);
	}
	dfs(1,0);calc_black();calc_white();
	int ans1=0,ans2=0,ans3=0;
	for(int i=n;i>=1;i--){
		if(isblack[i]&&iswhite[i]){
			ans1++;ans2=i;ans3^=i;
		}
	}
	printf("%d %d %d
",ans2,ans1,ans3);
}

//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-7
#define E 1000000000
using namespace std;
inline void splay(int &v){
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
int n,lastans,tot;
int num[100010],id[100010];double h[100010];
int main(){
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	splay(n);while(n--){
		int opt;splay(opt);
		if(!opt){
			int x;splay(x);x=(x+lastans-1)%39989+1;
			printf("%d
",lastans=num[x]);
		}
		else{
			int x,y,xx,yy;splay(x),splay(y),splay(xx),splay(yy);
			x=(x+lastans-1)%39989+1;y=(y+lastans-1)%1000000000+1;++tot;
			xx=(xx+lastans-1)%39989+1;yy=(yy+lastans-1)%1000000000+1;
			if(x>xx)swap(x,xx),swap(y,yy);
			double k=double(yy-y)/double(xx-x),b=double(y)-k*double(x);
			for(int j=x;j<=xx;j++){
				if(k*j+b>h[j]){
					h[j]=k*j+b,num[j]=tot;
				}
			}
		}
	}
}