USACO 2020年1月铜级比赛题解报告

àì夳堔傛蜴生んèń 2023-07-06 13:16 8阅读 0赞

# T1 Word Processor #

## 题目 ##

http://www.usaco.org/index.php?page=viewproblem2&cpid=987

## 分析 ##

判断每一行加上新单词后的长度（空格不计算在长度之内），若加上新单词后长度超过K，则新单词要另起一行。注意每行的最后一个单词右边不能有空格。

## AC代码 ##

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main()
    {
        freopen("word.in", "r", stdin);
        freopen("word.out", "w", stdout);
    
        int n, k;
        cin >> n >> k;
        string word;
        int len = 0, wordCnt = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> word;
            len += word.size();
            if(len <= k)
            {
                wordCnt++;
                //每行的非第一个单词前要加空格
                if(1 != wordCnt)
                {
                    cout << ' ';
                }
                cout << word;
            }
            else
            {
                wordCnt = 1;
                cout << endl << word;
                len = word.size();
            }
        }
    
        return 0;
    }

# T2 Photoshoot #

## 题目 ##

http://www.usaco.org/index.php?page=viewproblem2&cpid=988

## 分析 ##

可以逐一求出每个编号，然后判断编号是否合法。如果编号有重复，或小于等于0，或大于N，则不合法。复杂度为O(N2)。

## AC代码 ##

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    
    int N;
    int b[100000], d[100000], ans[100000];
    bool used[100000];
    
    int main()
    {
    	freopen("photo.in", "r", stdin);
    	freopen("photo.out", "w", stdout);
    
    	cin >> N;
    	for(int i=0; i<N-1; i++)
        {
            cin >> b[i];
        }
    
    	for(int a=1; a<b[0]; a++)
    	{
    		ans[0] = a;
    		for(int i = 1; i < N; i++)
            {
                ans[i] = b[i - 1] - ans[i - 1];
            }
    
    		for(int num = 1; num <= N; num++)
            {
                used[num] = false;    //初始化，还没有用到
            }
    
    		bool bad = 0;
    		for(int i=0; i<N; i++)
    		{
    		    // 数被重复使用，或者越界，都是不符合题意
    			if(used[ans[i]] || ans[i] <= 0 || ans[i] > N)
    			{
    				bad = 1;
    				break;
    			}
    			used[ans[i]] = true;
    		}
    
    		if(!bad)
    		{
    			for(int i = 0; i < N; i++)
    			{
    				cout << ans[i];
    				if(i < N - 1)
                    {
                        cout << ' ';
                    }
    			}
    			//cout << '\n';
    			return 0;
    		}
    	}
    
    	return 0;
    }

# T3 Race #

## 题目 ##

http://www.usaco.org/index.php?page=viewproblem2&cpid=989

## 分析 ##

要使所用的时间最少，那么在跑步的过程中，应该使中间的速度尽可能大。  
以K = 10, X = 2为例。  
先看看速度为1、2、2的情况，加起来距离是5米，不够10米。  
再尝试1、2、3、2，加起来是8米，仍然不够10米。  
再尝试1、2、3、3、2，加起来是11米，超过10米。所以用时为5秒。

## AC代码 ##

#include <stdio.h>
    
    int solve(int dist)
    {
        int minSpeed;
        scanf("%d", &minSpeed);
    
        int leftDist = 0;
        int rightDist = 0;
        int time = 0;
        for(int curSpeed = 1;;curSpeed++)
        {
            leftDist += curSpeed;
            time++;
            if(leftDist + rightDist >= dist)
            {
                return time;
            }
    
            if(curSpeed >= minSpeed)
            {
                rightDist += curSpeed;
                time++;
                if(leftDist + rightDist >= dist)
                {
                    return time;
                }
            }
        }
    }
    
    int main()
    {
        freopen("race.in", "r", stdin);
        freopen("race.out", "w", stdout);
    
        int k, n;
        scanf("%d %d", &k, &n);
        for(int i = 0; i < n; i++)
        {
            printf("%d\n", solve(k));
        }
    }

> =======================================  
> 了解信息学奥赛请加微信307591841或QQ群581357582