NOIP 시뮬레이션 10.21

전송문(MZOJ)
T1(일정):
시뮬레이션 문제, 매번 시뮬레이션을 삭제하고 추가하면 됩니다.두 가지 주의점: 1.답은 l o n g   l o n g long\long longlong 2. v i s vis 수조는 5 e 7 5 e7 5 e7 5 e7
Code

#include
#define ll long long
#define mod 1000000007
#define rep(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int maxn=3e6+10;
const int maxm=5e7+10;
ll x[maxn],ans[maxn],sum[maxn],q[maxn];
bool vis[maxm];
ll m,n,a,b,c;

template <class t> inline void read(t &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

void readdata() {
	read(n),read(m),read(a),read(b),read(c);
	x[0]=0;
	rep(i,1,m) {
		x[i]=(a*x[i-1]+b)%(2*n*c);
	}
}

void work() {
	rep(i,1,m) {
		if(x[i]<(n*c)) {
			ll pos=floor(x[i]/c)+1;
			if(vis[pos]==0) {
				vis[pos]=1;
				q[i]=(q[i-1]+1)%mod;
				ans[i]=(ans[i-1]+pos)%mod;
			}
			else {
				q[i]=(q[i-1])%mod;
				ans[i]=(ans[i-1])%mod;
			}
		}
		if(x[i]>=(n*c)) {
			ll pos=floor(x[i]/c)-n+1;
			if(vis[pos]==1) {
				vis[pos]=0;
				q[i]=(q[i-1]-1)%mod;
				ans[i]=(ans[i-1]-pos)%mod;
			}
			else {
				q[i]=(q[i-1])%mod;
				ans[i]=(ans[i-1])%mod;
			}
		}
	}
	ll ans1=0,ans2=0;
	rep(i,1,m) ans1=(ans1+q[i])%mod;
	rep(i,1,m) ans2=(ans2+ans[i])%mod;
	printf("%lld %lld",ans1,ans2);
}

int main() {
	//freopen("schedule.in","r",stdin);
//	freopen("schedule.out","w",stdout);
	readdata();
	work();
	return 0;
}

T2(연결 지점):
배증 최적화수의 역행
각 노드마다 공헌하는 것이 유일하다. 배로 늘리는 방식으로 공헌하는 점을 찾아 왼쪽 아들인지 오른쪽 아들인지 판단하면 된다.
작은 최적화가 있어요.
현재 v[i] v[i] v[i]를 1로 줄이고 공헌하는 점 아래로 뛰어내려 왼쪽 아들인지 오른쪽 아들인지 판단하기 편합니다.거리가 v[i] v[i] v[i]일 때 우리는 v[i] v[i] v[i] v[i]를 2진수로 나누어야 한다. 이 점을 위로 v[i] v[i] v[i] 이렇게 많이 걸어야 하기 때문에 이 2진수에 대해 어느 분이 1 1 1 1 1 1이면 우리는 2 2 2 2의 이렇게 많은 차형을 위로 뛸 수 있다.
예컨대 7, 우리는 먼저 20 2 ^0 20, 다시 2 1 2 ^1 21, 다시 2 2 2 ^2 22를 뛸 수 있다
Code

#include
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int maxm=1e3+10;
const int maxn=2e5+10;
int n,cnt;
int a[maxn],head[maxn],l[maxn],r[maxn],dep[maxn],f[maxn][21],son[maxn];

template <class t> inline void read(t &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

struct node{
	int v,nex;
}e[maxn];

void add(int u,int v) {
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void readdata() {
	read(n);
	rep(i,1,n) read(a[i]);
	rep(i,1,n) {
		int x,y;
		read(x),read(y);
		if(x!=0) {add(i,x);son[x]=1;}
		if(y!=0) {add(i,y);son[y]=0;}
	}
}

void dfs_first(int u,int fa,int deep) {
	dep[u]=deep;
	f[u][0]=fa;
	rep(i,0,19) f[u][i+1]=f[f[u][i]][i];
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].v;
		if(v==fa) continue;
		dfs_first(v,u,deep+1);
	}
}

void work() {
	memset(l,false,sizeof(l));
	memset(r,false,sizeof(r));
	dfs_first(1,0,1);
	rep(u,1,n) {
		int x=u;a[x]--;
		rep(i,0,19) {
			if((1<<i)&a[u]) x=f[x][i];
		}
		if(son[x]) l[f[x][0]]++;
		else r[f[x][0]]++;
	}
	rep(i,1,n) {
		printf("%d %d
",l[i],r[i]);
	}
}

int main() {
//	freopen("node.in","r",stdin);
//	freopen("node.out","w",stdout);
	readdata();
	work();
	return 0;
}

T3 (퀴즈 전송)
전이 방정식 f[u] [o] = m a x(f[u] [o] g [i] + f [v] [j] f[u] [o] =max(f[u] [o] g[i] + f[v] [j]) f[u] =max(f[u] [o] g[i] + f[v] [j])
f[i][k]f[i][k]f[i][k]는 ii를 뿌리로 하고 선택한 점의 거리는 적어도 kkk의 가장 좋은 거리임을 나타낸다.
Code

#include
#define inf 100000000
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int maxn=1e5+10;
const int maxm=1e3+10;
int n,K,cnt;
int a[maxn],head[maxn];
int f[maxn][110],g[maxn];

template <class t> inline void read(t &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

struct node{
	int v,nex;
}e[maxn<<1];

void add(int u,int v) {
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void readdata() {
	read(n);read(K);
	rep(i,1,n) read(a[i]);
	rep(i,1,n-1) {
		int x,y;
		read(x),read(y);
		add(x,y);add(y,x);
	}
}

void dfs(int u,int fa) {
	f[u][0]=a[u];
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		memcpy(g,f[u],sizeof(f[u]));
		for (int a = 0;a <=K;++a) {
			for (int b = K - a;b <= K;++b) {
				f[u][min(a,b+1)] = max(f[u][min(a,b+1)],g[a]+f[v][b]);
			}
		}
	}
}

void work() {
	int ans=-inf;
	dfs(1,0);
	rep(i,1,K) ans=max(ans,f[1][i]);
	printf("%d
",ans);
}

int main() {
	freopen("score.in","r",stdin);
	//freopen("score.out","w",stdout);
	readdata();
	work();
	return 0;
}