NOIp 2014 Day1 题解

T1 生活大爆炸版石头剪刀布

一看就是一道水题。根据得分关系列一张二维表，然后按题意循环就OK了。代码没必要贴。

T2 联合权值

不难看出这是一颗无根树。因为没有环，所以如果两个点同时于另一个点相连，则它们不可能再有边相连，即它们之间的距离为2。于是我们可以枚举每一个点，取其任意两个点，然后进行组合，然后两两相乘，得到最大值与他们的和。将所有值统计一下，输出的时候答案不要忘记乘二。
代码如下：

---

#include<bits/stdc++.h>
using namespace std;
int head[200010],ll,v[200010];
struct st{int to,nxt;}a[400010];
int n,ans,x,y,maxans;
void add(int x,int y){
	a[++ll].to=y,a[ll].nxt=head[x],head[x]=ll;
}
int main(){
	freopen("link.in","r",stdin);
 	freopen("link.out","w",stdout);
	cin>>n;
	for (int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y); add(y,x);
	}
	for (int i=1;i<=n;i++) cin>>v[i];
	for (int i=1;i<=n;i++){
		int sum=0,ma=0,m=0;
		for (int k=head[i];k>0;k=a[k].nxt){
			if (v[a[k].to]>ma) m=ma,ma=v[a[k].to];
			else if (v[a[k].to]>m) m=v[a[k].to];
			ans=(ans+sum*v[a[k].to]) % 10007;
			sum=(sum+v[a[k].to]) % 10007;
		}
		maxans=max(maxans,ma*m);
	}
	cout<<maxans<<" "<<(ans*2)%10007;
}

T3 飞扬的小鸟

为了理解这道题，我特地去下了一个Flappy Bird。真·休闲游戏（摔）。废话不多说，我们来看题。这道题明眼人一看就知道是道DP，而且因为每个时刻可以按很多下，你们想到了什么算法？对，就是完全背包。注意下落的时候还要搞一遍01背包。说说不难，其实小细节非常多。比如场景的高度有限制，有些优化其实会WA等等，就不一一列举了，请自行体会XD

代码如下：

---

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
int n,m,p;
int clic[maxn],uncl[maxn],L[maxn],H[maxn];
int f[maxn][maxm],cnt,INF;
inline int read(){
    int x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    freopen("bird.in","r",stdin);
    freopen("bird.out","w",stdout);
    n=read(),m=read(),p=read();
    for (int i=1; i<=n; i++) clic[i]=read(),uncl[i]=read();
    for (int i=1; i<=n; i++) L[i]=0,H[i]=m+1;
    for (int i=1; i<=p; i++){
        int x=read(); L[x]=read(),H[x]=read();
    }
    memset(f,63,sizeof f),INF=f[0][0],cnt=0;
    for (int i=0; i<=m; i++) f[0][i]=0;
    for (int i=1; i<=n; i++){
        for (int j=1; j<H[i]; j++) if (j>=clic[i]&&j!=m)
        f[i][j]=min(f[i][j],min(f[i-1][j-clic[i]]+1,f[i][j-clic[i]]+1));
        for (int j=1; j<H[i]; j++) if (j+uncl[i]<=m&&j>=L[i]+1)
        f[i][j]=min(f[i][j],f[i-1][j+uncl[i]]);
        if (H[i]==m+1)
            for (int j=m; j>=max(1,m-clic[i]); j--) f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
        bool flythr=0;
        for (int j=L[i]+1; j<H[i]; j++) if (f[i][j]<INF){flythr=1; break;}
        for (int j=0; j<=L[i]; j++) f[i][j]=INF;
        if (!flythr){printf("0\n%d",cnt); return 0;}
        if (L[i]>0||H[i]<m) cnt++;
    }
    int ans=1<<30;
    for (int i=1; i<=m; i++) ans=min(ans,f[n][i]);
    printf("1\n%d",ans);
    return 0;
}

---

以上。