NOIP 普及组复赛C/C++参考答案

第1题 标题统计

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

int main()
{
    freopen("title.in", "r", stdin);
    freopen("title.out", "w", stdout);
    string title;
    getline(cin, title);
    int len = title.size();
    for(int i = 0; i < (int)title.size(); i++)
    {
        if(' ' == title[i])
        {
            len--;
        }
    }

    cout << len;

    return 0;
}

评测结果

第2题 龙虎斗

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

#define LL long long

int main()
{
    freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
    int n, i, m, p1, p2;
    cin >> n;
    LL c[n + 1], s1, s2;
    for(i = 1; i <= n; i++)
    {
        cin >> c[i];
    }

    cin >> m >> p1 >> s1 >> s2;
    c[p1] += s1;

    LL lPower = 0; // 龙*
    for(i = 1; i < m; i++)
    {
        lPower += c[i] * (m - i);
    }

    LL rPower = 0;
    for(i = m + 1; i <= n; i++)
    {
        rPower += c[i] * (i - m);
    }

    //cout << lPower << ' ' << rPower << endl;

    LL gap = abs(lPower - rPower); // 双方的气势差
    p2 = m; //默认放在m位置
    for(i = 1; i <= n; i++)
    {
        if(i < m)   // 神兵加到左侧龙*
        {
            if(abs(lPower + s2 * (m - i) - rPower) < gap)
            {
                gap = abs(lPower + s2 * (m - i) - rPower);
                p2 = i;
            }
        }
        else if(i > m) // 神兵加到右侧虎*
        {
            if(abs(rPower + (i - m) * s2 - lPower) < gap)
            {
                gap = abs(rPower + (i - m) * s2 - lPower);
                p2 = i;
            }
        }
    }
    cout << p2 << endl;

    return 0;
}

评测结果：

第3题 摆渡车

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

int n,m;
int data[1024];
int sum[1024];
int dp[1024][128];

int main()
{
//    freopen("bus.in", "r", stdin);
//    freopen("bus.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", data + i);
    }

    sort(data+1, data+n+1);

    for(int i=1; i<=n; ++i)
    {
        sum[i] = sum[i-1] + data[i];
    }

    // i代表第i个人（可能不止一个）
    for(int i = 1; i <= n; ++i)
    {
        // j表示当前这个人可能的候车时间，取值[0,m-1)
        for(int j = 0; j < m; ++j)
        {
            int curBusTime=data[i] + j;
            if(j)
            {
                dp[i][j] = dp[i][j - 1];
            }
            else
            {
                dp[i][j] = curBusTime*i - sum[i];
            }

            // 最近的一趟车可能出发的时间
            for(int lastBusTime = max(curBusTime - 2 * m + 1, 0); lastBusTime <= curBusTime - m; ++lastBusTime)
            {
                // lastCarry表示被上一辆车接走的学生人数
                int lastCarry = lower_bound(data + 1, data + n + 1, lastBusTime + 1)- (data + 1);
                // lastWait表示上一个人的候车时间
                int lastWait = min(lastBusTime - data[lastCarry], m - 1);
                // 动态转移方程
                int tmp = dp[lastCarry][lastWait] + (i - lastCarry) * curBusTime - (sum[i] - sum[lastCarry]);
                if(tmp<dp[i][j])
                {
                    dp[i][j]=tmp;
                }
            }
        }
    }

    printf("%d\n",dp[n][m-1]);

    return 0;
}

评测结果

第4题 对称二叉树

#include<cstdio>

inline int max(int x, int y)
{
	return x > y ? x : y;
}

const int MAXN = 1000000;
int cnt[MAXN + 5], lef[MAXN + 5], rig[MAXN + 5], ans;
int v[MAXN + 5]; // 节点的权值

// 检查左右子树是否对称
bool checkSym(int leftId, int rightId)
{
    if(leftId == -1 && rightId == -1)
    {
        // 若左右子节点都不存在，则认为是对称
        return true;
    }

	if(v[leftId] != v[rightId])
    {
        // 左子节点值 不等于 右子节点值，说明不对称
        return false;
    }
	else
    {
        // 左子节点值等于右子节点值，则左左=右右且右左=左右，说明对称；否则不对称。注意要递归下去
        return checkSym(lef[leftId], rig[rightId]) && checkSym(rig[leftId], lef[rightId]);
    }
}

// 求第nodeId个节点为根节点的二叉树，所包含的节点总数
int nodeCnt(int nodeId)
{
    // 当前节点不存在
	if(-1 == nodeId)
    {
        return 0;
    }
	else
    {
        // 左子树节点数 + 右子树节点树 + root本身的节点数1
        return cnt[nodeId] = nodeCnt(lef[nodeId]) + nodeCnt(rig[nodeId]) + 1;
    }
}

void dfs(int nodeId)
{
    // 空节点为递归终止的条件
	if(-1 == nodeId)
    {
        return;
    }

    // 左子树节点总数 等于 右子树节点总数，这是对称的前提
	if(cnt[lef[nodeId]] == cnt[rig[nodeId]])
    {
        if(checkSym(lef[nodeId], rig[nodeId]))
        {
            // 若对称，获取总的节点数，并与原先的ans比较
            ans = max(ans, cnt[nodeId]);
        }
    }

    // 左子树下是否包含对称二叉树
	dfs(lef[nodeId]);
	// 右路子树是否包含对称二叉树
    dfs(rig[nodeId]);
}

int main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);

	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
    {
        scanf("%d", &v[i]);
    }
	for(int i=1; i<=n; i++)
    {
		scanf("%d%d", &lef[i], &rig[i]);
	}

	nodeCnt(1);
	dfs(1);
	printf("%d\n", ans);

	return 0;
}

评测结果

少儿编程、信息学竞赛咨询请加微信307591841或QQ群581357582