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

你的名字 2022-01-30 13:25 225阅读 0赞

# 第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;
    }

评测结果

![1.png][]

# 第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;
    }

评测结果：

![2.png][]

# 第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;
    }

评测结果

![3.png][]

# 第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;
    }

评测结果  
![4.png][]

> 信息学学习、算法答疑请加微信307591841

[1.png]: /images/20220130/415c17e5c56546fe95ceaa51ff3d439e.png
[2.png]: /images/20220130/cdf3a126bfa54ac6bb5c3afff865e450.png
[3.png]: /images/20220130/2e1d3f68e71646b7b0c048329cdda989.png
[4.png]: /images/20220130/95ed148a6f2d4db399ebb24ca5bcdf0b.png