2017 ACM-ICPC EC-Final ShangHai 东亚洲大陆-上海

比赛链接：传送门

Gym 101775A Chat Group（签到：待补）

Gym 101775B Scapegoat（待补）

Gym 101775C Traffic Light（贪心+思维）

思路：

需要证明两个点：

　　① 所有的N+1个S都是必须要走的，并且可以适当安排使得红灯只用等最长的一个。

　　② 上面这样的安排的答案是S₀+S₁+…+S_N+max(B_i)，而答案不可能比这个小，因为总有一种走法可以等到最长的那个红绿灯，如果其他的红绿灯也要等的话就比上面的方法大了。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

double S[MAX_N];

double A[MAX_N], B[MAX_N];

int main()

{

    int T;

    cin >> T;

    for (int kase = ; kase <= T; kase++) {

        int N;

        cin >> N;

        for (int i = ; i <= N; i++) {

            scanf("%lf", S+i);

        }

        double _max = -;

        for (int i = ; i <= N; i++) {

            scanf("%lf%lf", A+i, B+i);

            _max = max(_max, B[i]);

        }

        for (int i = ; i <= N; i++) {

            _max += S[i];

        }

        printf("Case #%d: %.6lf\n", kase, _max);

    }

    return ;

}

Gym 101775J Straight Master（差分）

好久没见过差分了，早就把这种方法忘掉了。。。比赛的时候企图用贪心+松弛标记强行搓，结果一直WA。

思路：（下面的差分都指与前一个相邻的数的差）

　　大于3的任意长度都可以由3、4、5的长度组成，所以长度大于3的子串都可以构成顺子。因此到第i个位置为止之前的所有正的差分都可以用于更新第i+3个位置及其之后的位置的负差分，如：

　　0 1 2 3 4 4 4 1

　　第4个位置为止正差分的和为4，第 4 + 3 = 7 个位置的差分为-3，则剩余的差分和sum为1。O(n)遍历维护差分和sum即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 2e5 + ;

int N;

ll a[MAX_N];

ll k[MAX_N];

ll dis[MAX_N];

bool solve()

{

    int ind = ;

    if (dis[] <  || dis[] < )

        return false;

    ll sum = ;

    for (int i = ; i <= N+; i++){

        sum += dis[i];

        int j = i+;

        if (j > N+)

            break;

        if (dis[j] < ) {

            sum += dis[j];

            dis[j] = ;

        }

        if (sum < )

            break;

    }

    if (sum != )

        return false;

    return true;

}

int main()

{

    int T;

    cin >> T;

    for (int kase = ; kase <= T; kase++) {

        cin >> N;

        a[] = ;

        for (int i = ; i <= N; i++) {

            scanf("%lld", a+i);

            k[i] = ;

            dis[i] = a[i] - a[i-];

        }

        dis[N+] = - a[N];

        bool ans = solve();

        printf("Case #%d: ", kase);

        if (ans)

            puts("Yes");

        else

            puts("No");

    }

    return ;

}

/*

10

5

3 5 5 2 4

5

3 5 5 2 2

*/

Gym 101775K Downgrade（签到：简单模拟）

思路：

按题意模拟即可。要注意N是10⁹，所以要判断一下状态是否会继续更新。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_A = 1e5 + ;

ll sum[MAX_A], L[MAX_A];

int main()

{

    int T;

    cin >> T;

    for (int kase = ; kase <= T; kase++) {

        ll A, B, N;

        cin >> A >> B >> N;

        sum[] = ;

        for (int i = ; i <= A; i++) {

            scanf("%lld", &L[i]);

            sum[i] = sum[i-] + L[i];

        }

        ll ansa = A, ansb = B;

        ll nxta, nxtb;

        while (N--) {

            int ind = lower_bound(sum+, sum+A+, ansa) - sum;

            nxtb = ansa - sum[ind-];

            nxta = ind;

            if (nxta == ansa && nxtb == ansb)

                break;

            ansa = nxta;

            ansb = nxtb;

        }

        printf("Case #%d: %lld-%lld\n",kase, ansa, ansb);

    }

    return ;

}

/*

3

3 2 2

2 2 2

3 1 2

1 1 1

3 1 1000000000

1 1 1

*/

Gym 101775L SOS（博弈+思维）

思路：

　　博弈有两种题，思维题、SG函数题。不管是哪种，上来先打个表。。。其他的打完了表再说。。。打表发现N为大于5的所有奇数都是Panda，N为大于14的所有偶数都是Sheep，其他的为Draw。

　　然后是证明：只要构造了S _ _ S的局面，然后跟对手一起把其他的空位填满，下一个填字符的人就必输了。根据N奇偶性，填满空位后面临S _ _ S的局面的人是不同的。所以有下面两种情况：

　　① N为奇数的时候：先手Panda要尽可能构造S _ _ S的局面，而Sheep要尽量避免被构造出S _ _ S的局面。当N = 7时，Panda第一次可以在Sheep的干扰下成功构造S _ _ S的局面：

　　Panda: _ _ _ S _ _ _

　　Sheep: _ _ _ S _ _ O

　　Panda: S _ _ S _ _ O

　　不管Sheep放在哪边，Panda都可以在另一边构造S _ _ S的局面。

　　② N为偶数的时候Panda要尽可能避免被Sheep构造出这样的局面，这时候就轮到Sheep来构造S _ _ S的局面了。由①可以发现，当剩下了7个空位时，可以把S放在中间，就能在Panda的干扰下构造S _ _ S的局面。但是有一点需要注意：就是N = 14时：

　　Panda: _ _ _ _ _ _ O _ _ _ _ _ _ _

　　Sheep: _ _ _ _ _ _ O _ _ _ S _ _ _

　　Panda: _ _ _ _ _ _ O _ _ _ S _ _ O

　　Sheep: _ _ _ _ _ _ O S _ _ S _ _ O

　　Panda: _ _ _ _ _ S O S _ _ S _ _ O

　　Game Over.

　　Sheep放第二个S的时候如果是在O的旁边，那就崩盘了。所以N=14的时候Panda还是能反制Sheep的，但是当N = 16时Panda就无还手之力了：

　　Panda: _ _ _ _ _ _ _ O _ _ _ _ _ _ _ _

　　Sheep: _ _ _ _ _ _ _ O _ _ _ _ S _ _ _

　　Panda: _ _ _ _ _ _ _ O _ _ _ _ S _ _ O

　　Sheep: _ _ _ _ _ _ _ O _ S _ _ S _ _ O

#include <bits/stdc++.h>

using namespace std;

const int MAX_N =  + ;

int main()

{

    int T;

    cin >> T;

    int kase = ;

    while (T--) {

        int N;

        cin >> N;

        printf("Case #%d: ", kase++);

        if (N >  && N % )

            puts("Panda");

        else if (N < )

            puts("Draw");

        else

            puts("Sheep");

    }

    return ;

}

Gym 101775M World Cup（签到：待补）

2017 ACM-ICPC EC-Final ShangHai 东亚洲大陆-上海的相关教程结束。