NOIP2014提高组day1

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

这道题是一道很水的模拟题，写的时候注意把表中未给出的输赢关系自己补上就是了。

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

const int MAXN = 205;
int N, Na, Nb;
int out[3][MAXN];
int sco_a, sco_b;

int main()
{
//	freopen("rps.in","r",stdin);
//	freopen("rps.out","w",stdout);
	scanf("%d%d%d", &N, &Na, &Nb);
	for(int i = 1; i <= Na; i++)
		scanf("%d", &out[1][i]);
	for(int i = 1; i <= Nb; i++)
		scanf("%d", &out[2][i]);
	int ia = 1, ib = 1;
	while(N--)
	{
		if(out[1][ia] == out[2][ib])
		{
			sco_a = sco_a;
			sco_b = sco_b;
		} else {
			if((out[1][ia]==0&&out[2][ib]==2) || 
			   (out[1][ia]==0&&out[2][ib]==3) || 
			   (out[1][ia]==1&&out[2][ib]==3) || 
			   (out[1][ia]==2&&out[2][ib]==4) || 
			   (out[1][ia]==3&&out[2][ib]==4) ||
			   (out[1][ia]==1&&out[2][ib]==0) ||
			   (out[1][ia]==2&&out[2][ib]==1) ||
			   (out[1][ia]==3&&out[2][ib]==2) ||
			   (out[1][ia]==4&&out[2][ib]==0) ||
			   (out[1][ia]==4&&out[2][ib]==1))
			{
				sco_a++;
			} else {
				sco_b++;
			}
		} 
		ia++; ib++;
		if(ia > Na) ia = 1;
		if(ib > Nb) ib = 1;
	}
	printf("%d %d", sco_a, sco_b);
	return 0;
}

T2 联合权值

嗯。。。这道题当时做的时候是有想到一个点是可以和他的爷爷或者是兄弟联合的，这个点和爷爷的联合权值很好计算，和他的兄弟的联合权值被卡住了。。。

上代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int N = 400010;

typedef long long ll;

int head[N], rest[N], to[N], tot;

ll w[N];

void add(int u, int v) {
    ++ tot;
    to[tot] = v;
    rest[tot] = head[u];
    head[u] = tot;
}

int fa[N];

const ll mod = 10007LL;

ll ans = 0xcfcfcfcfcfcfcfcfLL, sum;

int n;

/*
 * 1. 往上走到爷爷节点时的贡献
 * 2. 所有儿子中取两个不同得节点的贡献
 */

void dfs(int u) {
    ll ret = 0, cnt = 0;
    ll mx = -1, smx = -1;
    if(fa[fa[u]]) {
        ret = (ret + w[u] * w[fa[fa[u]]]) % mod;
        ans = max(ans, w[u] * w[fa[fa[u]]]);
    }
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(v != fa[u]) {
            fa[v] = u;
            dfs(v);
            ret = (ret + cnt * w[v]) % mod;
            cnt = (cnt + w[v]) % mod;
            if(w[v] >= mx) {
                smx = mx;
                mx = w[v];
            } else if(w[v] >= smx) {
                smx = w[v];
            }
        }
    }
    if(smx != -1) {
        ans = max(ans, mx * smx);
    }
    sum = (sum + ret) % mod;
}

int main() {
    scanf("%d", &n);
    for(int i = 1, u, v ; i < n ; ++ i) {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%lld", &w[i]);
    }
    dfs(1);
    printf("%lld %lld\n", ans, sum * 2 % mod);
}

T3 飞扬的小鸟

我应该想到这道题对我来说比第二题简单一些的，亏了亏了

还有就是一定要记得极大值赋大一点，不然就会疯狂55 55 55，连交3次才AC，哎...

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

int n, m, k;
const int INF = 0x3f3f3f3f, MAXN = 10005;
int l[MAXN], h[MAXN];//l[i]表示第i根管道沿上的高度，h[i]表示第i根管道沿下的高度 
int dp[MAXN][1005];//dp[i][j]表示在坐标(i,j)处最少跳了几次 
int x[MAXN], y[MAXN];//x[i],y[i]表示在i处点一下上升的高度和不点下降的高度 
bool p[MAXN];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < n; i++)
	{
        scanf("%d%d", &x[i], &y[i]);
        l[i] = 0;
        h[i] = m + 1;
    }//一个初始化 
    l[n] = 0;
    h[n] = m + 1;
    int w;
    for(int i = 0; i < k; i++)
	{
        scanf("%d", &w);
        scanf("%d%d", &l[w], &h[w]);
        p[w] = true;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            dp[i][j] = INF;
    dp[0][0] = INF;
    for(int i = 1; i <= m; i++)
        dp[0][i] = 0;
    for(int i = 1; i <= n; i++)
	{
        for(int j = x[i-1]; j <= m; j++)
		{
            if(j == m)//当我们跳到天花板的时候，继续向上跳是不行的，然而继续点击屏幕也不会死 
                for(w = m-x[i-1]; w <= m; w++)
				{
                    dp[i][j] = min(dp[i][j], dp[i-1][w]+1);//一次跳到顶 
                    dp[i][j] = min(dp[i][j], dp[i][w]+1);//不止一次跳到顶 
                }
            dp[i][j] = min(dp[i][j], dp[i-1][j-x[i-1]]+1);
            dp[i][j] = min(dp[i][j], dp[i][j-x[i-1]]+1);
        }
        for(int j = max(1, l[i]+1); j <= min(m-y[i-1], h[i]-1); j++)
            dp[i][j] = min(dp[i][j], dp[i-1][j+y[i-1]]);
        for(int j = l[i]; j >= 1; j--)
            dp[i][j] = INF;
        for(int j = h[i]; j <= m; j++)
            dp[i][j] = INF;
    }
    int ans = INF, cnt = k;
    for(int i = n; i >= 1; i--)
	{
        for(int j = l[i]+1; j <= h[i]-1; j++)
            ans = min(ans, dp[i][j]);
        if(ans < INF) break;
        if(p[i] == true) k--;
    }
    if(cnt == k) printf("1\n%d", ans);
    else printf("0\n%d", k);
    return 0;
}