2019 The 19th Zhejiang University Programming Contest

感想：

　　今天三个人的状态比昨天计院校赛的状态要好很多，然而三个人都慢热体质导致签到题wa了很多发。最后虽然跟大家题数一样(6题)，然而输在罚时。

　　只能说，水题还是刷得少，看到签到都没灵感实在不应该。

---

题目链接：http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=391

　　A：简单贪心，按高度sort一下就好了，这里用优先队列处理

#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

int M[100005], F[100006];

int main(void)
{
    int T;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            int n, m;
            priority_queue <int, vector<int>, greater <int>> fu, fd, mu, md;
            scanf("%d %d", &n, &m);
            for (int i = 0; i < n; i++)
            {
                scanf("%d", &M[i]);
            }
            for (int i = 0; i < m; i++)
            {
                scanf("%d", &F[i]);
            }
            for (int i = 0; i < n; i++)
            {
                int flag;
                scanf("%d", &flag);
                if (flag)
                {
                    mu.push(M[i]);
                }
                else
                {
                    md.push(M[i]);
                }
            }
            for (int i = 0; i < m; i++)
            {
                int flag;
                scanf("%d", &flag);
                if (flag)
                {
                    fu.push(F[i]);
                }
                else
                {
                    fd.push(F[i]);
                }
            }
            int ans = 0;
            // fu <-> md
            while (!fu.empty() && !md.empty())
            {
                if (fu.top() < md.top())
                {
//                  printf("pop: %d %d
", fu.top(), md.top());
                    fu.pop();
                    md.pop();
                    ans++;
                }
                else
                {
//                  printf("pop: %d
", md.top());
                    md.pop();
                }
            }
            // fd <-> mu
            while (!mu.empty() && !fd.empty())
            {
                if (mu.top() < fd.top())
                {
//                  printf("pop: %d %d
", mu.top(), fd.top());
                    mu.pop();
                    fd.pop();
                    ans++;
                }
                else
                {
//                  printf("pop: %d
", fd.top());
                    fd.pop();
                }
            }
            printf("%d
", ans);
        }
    }
    return 0;
}

　　B：找规律，显然是不停把n除二加起来，高精就用java

import java.util.*;
import java.lang.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        while (cin.hasNextInt())
        {
            int t=cin.nextInt();
            while (t-->0){
                BigInteger ans=BigInteger.ZERO;
                BigInteger x=cin.nextBigInteger();
                while (!x.equals(BigInteger.ONE)){
                    x=x.divide(BigInteger.valueOf(2));
                    ans=ans.add(x);
                }
                System.out.println(ans);
            }
        }
    }
}

　　C：模拟

#include <cstdio>

char t[2002][2002];
bool vis[2002][2002];

const int p3[] = {1, 3, 9, 27, 81, 243};

const int movement[4][2] =
{
    {1, 0}, // DOWN
    {0, 1},  // RIGHT
    {-1, 0}, // UP
    {0, -1} // LEFT
};

void init(int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            vis[i][j] = false;
        }
    }
}

int solve(void)
{
    int ans = 0;
    int n, m;
    int a, b;
    long long int k;
    scanf("%d %d", &n, &m);
    scanf("%d %d %lld", &a, &b, &k);
    a--;
    b--;
    char cmd[300];
    scanf(" %s", cmd);
    init(n, m);
    for (int i = 0; i < n; i++)
    {
        scanf(" %s", t[i]);
        for (int j = 0; j < m; j++)
        {
            t[i][j] -= '0';
        }
    }
    while (k--)
    {
        int x = p3[4] * t[a][b]
                + p3[3] * t[a - 1][b]
                + p3[2] * t[a + 1][b]
                + p3[1] * t[a][b - 1]
                + p3[0] * t[a][b + 1];
        if (vis[a][b])
        {
            return ans;
        }
        vis[a][b] = true;
        if (cmd[x] == 'D')
        {
            int na = a + movement[0][0], nb = b + movement[0][1];
            if (t[na][nb] == 1) return ans;
            else a = na, b = nb;
        }
        else if (cmd[x] == 'R')
        {
            int na = a + movement[1][0], nb = b + movement[1][1];
            if (t[na][nb] == 1) return ans;
            else a = na, b = nb;
        }
        else if (cmd[x] == 'U')
        {
            int na = a + movement[2][0], nb = b + movement[2][1];
            if (t[na][nb] == 1) return ans;
            else a = na, b = nb;
        }
        else if (cmd[x] == 'L')
        {
            int na = a + movement[3][0], nb = b + movement[3][1];
            if (t[na][nb] == 1) return ans;
            else a = na, b = nb;
        }
        else if (cmd[x] == 'P')
        {
            if (t[a][b] == 2)
            {
                t[a][b] = 0;
                ans++;
                init(n, m);
            }
        }
        else if (cmd[x] == 'I')
        {
            return ans;
        }
    }
    return ans;
}

int main(void)
{
    int T;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            printf("%d
", solve());
        }
    }
    return 0;
}

　　D：上一题的人工智能版，要你构造特定程序捡垃圾。方法是走回字形，比如我们选定顺时针方向走，那么当我们走到左边靠墙位置的时候，如果右手边有垃圾，那么我们往右走一格再继续往上走。如果走到地图中间位置(四周没垃圾)就往上走。如果机器人走了连续相同方向n次就让机器人“抖动”一下(属实人工智能调参)。然而cy他们队就是A了(神仙啊

　　E：从右往左扫一次就好了，队友没开LL导致wa一发要批评

#include <cstdio>

long long int a[200], b[200];

int main(void)
{
    int T;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            int n;
            scanf("%d", &n);
            for (int i = 0; i < n; i++)
            {
                scanf("%lld", &a[i]);
            }
            for (int i = 0; i < n; i++)
            {
                scanf("%lld", &b[i]);
            }
            bool flag = true;
            for (int i = n - 1; i >= 0; i--)
            {
                if (b[i] >= a[i])
                {
                    if (i)
                    {
                        b[i - 1] += b[i] - a[i];
                    }
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            printf(flag ? "Yes
" : "No
");
        }
    }
    return 0;
}

　　F：神仙题

　　G：非常简单的贪心

#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

int M[100005], F[100006];

int main(void)
{
    int T;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            int n, k;
            scanf("%d %d", &n, &k);
            priority_queue <long long int> pos, neg;
            for (int i = 0; i < n; i++)
            {
                int tmp;
                scanf("%d", &tmp);
                if (tmp > 0)
                {
                    pos.push(tmp);
                }
                else
                {
                    neg.push(-tmp);
                }
            }
            long long int ans = 0, maxn = 0;
            while (!pos.empty())
            {
                ans += 2 * pos.top();
                maxn = max(pos.top(), maxn);
                int cnt = k - 1;
                pos.pop();
                while (cnt-- && !pos.empty())
                {
                    pos.pop();
                }
            }
            while (!neg.empty())
            {
                ans += 2 * neg.top();
                maxn = max(neg.top(), maxn);
                int cnt = k - 1;
                neg.pop();
                while (cnt-- && !neg.empty())
                {
                    neg.pop();
                }
            }
            printf("%lld
", ans - maxn);
        }
    }
    return 0;
}

　　H：救公主，边双相关的题目(然而队友最后没撸出来)

　　 I：要求逆元的看不懂的题目

　　J：签到(wa了7次，三个人都没睡醒。这里我马上想到了可以输出n×2和n×3，然而忘记特判n==1的情况……)

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

typedef long long ll;

ll read()
{
    ll x = 0; char c = getchar(); ll flag = 1;
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            flag = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')x = x * 10ll + c - '0', c = getchar();
    return x;
}

int main()
{
    ll T;
    while (scanf("%lld", &T) == 1)
    {
        while (T--)
        {
            ll x;
            x = read();
            if (x % 2 == 0)
            {
                printf("4 %lld
", 4 + x);
            }
            else
            {
                printf("15 %lld
", 15 + x);
            }
        }
    }

    return 0;
}