Educational Codeforces Round 21（A-D）（水题 + 尺取 + 构造 + multiset优化）_apart from having lots of holidays throughout the

这是昨天的训练赛，在场上A出四题，场下看能不能再补出一题。

4

1

A题：在年份中有且只有一个非零字符的是lucky year。给定今年，问最近的lucky year在几年后。

一开始使用了pow()函数结果WA了很多发，应该是因为pow的返回值类型是double的缘故，后来手写了一个幂函数就过了

namespace Solver {
    int pp(int x)
    {
        int ans =1;
        for(int i=1; i<=x; i++)
            ans*=10;
        return ans;
    }
 
    void solve(){
        int n;
        cin>>n;
        int p=1;
 
        if(n<10) printf("1\n");
        else {
            while(n/(pp(p))>=10) p++;
            int maxx = (int)(n/(pp(p))+1)*pp(p);
            cout<<maxx - n<<endl;
        }
    }
};

3 2
3 4 7

9.0000000000

B题：求给定n个数中，所有连续k长度中所有数的和，求平均值。

用尺取法在O(n)的复杂度内求出所有连续k长度的和。

void solve(){
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
        long long sum = 0, num = 0;
        int l=0, r=k-1;
        for(int i=0; i<k; i++)
            sum += a[i];
        //printf("sum: %d\n", sum);
        num += sum;
        while(r!=n-1)
        {
            sum = sum + a[++r] - a[l++];
            //printf("sum: %d\n", sum);
            num += sum;
        }
 
        double ans = (double)(num)/(double)(n-k+1);
        printf("%.8f", ans);
    }

2 10
8 7

6 4 

C题：给n个杯子m单位的水。要求每个杯子中的水是整数，且至少是该杯子容量的一半，容量大的杯子里的水不能比容量小的杯子里的水少，m单位的水要倒完。给出任意一种倒法。

因为题目要求给出任意一种解法，那么直接构造就可以了。首先保证每个杯子里的水都是容量的一半，然后从容量大的杯子开始倒水，把m单位的水倒完。

struct Node{
    int id;
    int w;
    int h;
}a[105];
bool cmp1(Node a, Node b){return a.w>b.w;}
bool cmp2(Node a, Node b){return a.id<b.id;}
namespace Solver {
    void solve(){
        int n, m, sum=0;
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++){
            scanf("%d", &a[i].w);
            a[i].id = i;
            a[i].h = (a[i].w+1)/2;
            sum += a[i].h;
        }
        if(sum > m) printf("-1\n");
        else {
            sort(a, a+n, cmp1);
            int y = m - sum;
            int p=0;
            while(y>0){
                //printf("y:%d %d\n", p, y);
                if(y > a[p].w - a[p].h){
                    y -= a[p].w - a[p].h;
                    a[p].h = a[p].w;
                    p++;
                }
                else {
                    a[p].h += y;
                    y=0;
                    p++;
                }
            }
            sort(a, a+n, cmp2);
            for(int i=0; i<n; i++){
                printf("%d%c", a[i].h, i==n-1?'\n':' ');
            }
        }
    }
};

3
1 3 2

YES

D题：定义一种操作，可以将数列中任意位置的数删去后插入到数列任意位置。问能否通过一次操作使得新的数列中存在前一部分和等于后一部分和的情况。

因为只挪动了一个数，所以可以看成在选取了一部分前缀和后，从后一部分找出一个数挪到前面，或者是从前一部分找出一个数挪到后面。用set来查找。

multiset<LL > s, d;
LL a[maxn];
 
 
namespace Solver {
 
    void solve(){
        int n;
        LL sum=0, num=0;
        s.clear();
        d.clear();
        scanf("%d", &n);
        for(int i=0; i<n; i++){
            scanf("%I64d", &a[i]);
            s.insert(a[i]);
            sum += a[i];
        }
        //printf("sum: %I64d\n", sum);
        if(sum&1) puts("NO");
        else {
            bool can = false;
            sum /= 2;
            for(int i=0; i<n; i++)
            {
                num += a[i];
                multiset <LL>::iterator pos = s.find(a[i]);
                s.erase(pos);
                d.insert(a[i]);
                //printf("%d: %I64d %d\n", i, num, s.count(1));
                if(num == sum){
                    can = true;
                    break;
                }
                else if(num < sum){
                    if(s.count(sum - num)){
                        can = true;
                        break;
                    }
                }
                else if(num > sum){
                    if(d.count(num - sum)){
                        can = true;
                        break;
                    }
                }
            }
 
            if(can) puts("YES");
            else puts("NO");
        }
    }
};