模拟赛小结：2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

比赛链接：传送门

跌跌撞撞6题摸银。

封榜后两题，把手上的题做完了还算舒服。就是罚时有点高。

开出了一道奇奇怪怪的题（K），然后ccpcf银应该比区域赛银要难吧，反正很开心qwq。

Problem A. Mischievous Problem Setter 00：14 （-2） Solved by Dancepted

良心签到题。WA2吃乳猪。

代码：

#include <iostream>

#include <cmath>

#include <map>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <set>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <iomanip>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<<x) // be conscious if mask x exceeds int

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

template <typename T>

inline void write(T x) {

    int len = ; char c[]; if (x < ) putchar('-'), x = -x;

    do{++len; c[len] = x% + '';} while (x /= );

    for (int i = len; i >= ; i--) putchar(c[i]);

}

template <typename T, typename... Args>

inline void write(T x, Args ... args) { write(x), write(args...); }

struct Node{

    int d, t;

    bool operator < (const Node& x) const {

        return d < x.d;

    }

}nodes[N];

int main() {

    fast;

    int T; cin >> T;

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

        int n, m; cin >> n >> m;

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

            cin >> nodes[i].d;

        }

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

            cin >> nodes[i].t;

        }

        sort(nodes+, nodes++n);

        int ans = ;

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

            if (nodes[i].t <= m) {

                m -= nodes[i].t;

                ans++;

            }

            else {

                break;

            }

        }

        cout << "Case " << kase << ": " << ans << endl;

    }

    return ;

}

Problem L. Ultra Weak Goldbach's Conjecture 00：47（+） Solved by xk （miller rabin + 素数密度 + 哥德巴赫猜想）

根据素数密度为$log^{2}N$的结论，可以用米勒-拉宾的板子O(logn)判断大素数，暴力找出比n小的最大的一个大素数。

哥德巴赫猜想在小数据范围内成立，剩下部分如果是奇数就分成2 + 2 + 3 + 两个素数，如果是偶数就是2 + 2 + 2 + 两个素数。

（xk才是真正的数学选手，我连哥德巴赫猜想都不知道，就是打酱油的）

代码：$O(T × log^{3}N)$

#include <iostream>

#include <cmath>

#include <map>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <set>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <iomanip>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define INF 0x3f3f3f3f

#define sz(x) ((int)x.size())

#define mp(a,b) make_pair(a, b)

#define endl '\n'

using namespace std;

typedef long long ll;

typedef double db;

int random(int l, int r)

{

    return rand() % (r - l) + l;

}

ll fmul(ll a, ll b, ll mod)

{

    a %= mod;

    ll res = ;

    for(;b;b>>=) {

        if(b & ) res = (res + a) % mod;

        a = (a + a) % mod;

    }

    return res;

}

ll fpow(ll a, ll b, ll mod)

{

    ll res = ;

    for(;b;b>>=) {

        if(b & ) res = fmul(res, a, mod);

        a = fmul(a, a, mod);

    }

    return res;

}

bool witness(ll a, ll n, ll u, ll t)

{

    ll x0 = fpow(a, u, n), x1;

    for(int i = ; i <= t; i++)

    {

        x1 = fmul(x0, x0, n);

        if(x1 ==  && x0 !=  && x0 != n - ) return false;

        x0 = x1;

    }

    if(x1 != ) return false;

    return true;

}

bool isprime(ll n, int times = )

{

    if(n == ) return true;

    if(n <  || !(n & )) return false;

    ll u = n - , t = ;

    while(u %  == ) {

        t++;

        u>>=;

    }

    while(times--)

    {

        ll a = random(, n - );

        if(!witness(a, n, u, t)) return false;

    }

    return true;

}

int main()

{

    srand(time());

    fast;

    int T;

    cin >> T;

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

    {

        cout << "Case " << kase << ": ";

        ll n;

        cin >> n;

        if(n < ) {

            cout << "IMPOSSIBLE\n";

            continue;

        }

        for(ll i = n - ; ; i--)

        {

            if(isprime(i)) {

                n -= i;

                cout << i;

                break;

            }

        }

        if(n & )

        {

            cout << " 2 2 3";

            n -= ;

        }

        else

        {

            cout << " 2 2 2";

            n -= ;

        }

        for(ll i = ; i <= n / ; i++)

        {

            if(isprime(i) && isprime(n - i))

            {

                cout << ' ' << i << ' ' << n - i << endl;

                break;

            }

        }

    }

}

Problem G. Pastoral Life in Stardew Valley 01：13 （+） Solved by Dancepted （平方和公式）

设$f_{n, m}$表示n × m的草地上放稻草人的方案数，则：

$f_{n, m} = \sum_{i=1}^{n-2} \sum_{j=1}^{m-2}(n-i+1) × (m-j+1) = \frac{(n-1)(n-2) × (m-1)(m-2)}{4}$

设$F_{n, m}$表示n × m的土地上的答案，则：

$F_{n, m} = \sum_{i=3}^{n}\sum_{j=3}^{m} (n-i+1)×(m-j+1)×f_{i, j} $

$= \sum_{i=3}^{n}\sum_{j=3}^{m} (n-i+1)×(m-j+1)×\frac{1}{4}i(i-1) × i(i-1)$

$= \frac{1}{4} \sum_{i=3}^{n}(n-i+1)(i-1)(i-2)\sum_{j=3}^{m}(m-j+1)(j-1)(j-2)$

令$g_{x} = \frac{1}{2} \sum_{i=3}^{x}(x-i+1)(i-1)(i-2)$，则$F_{n, m} = g_{n} * g_{m}$。

考虑预处理$g_{x}$：

①：$g_{3} = 1$

②：若已知$g_{x} = \frac{1}{2} \sum_{i=3}^{x}(x-i+1)(i-1)(i-2)$，则：

$g_{x+1} = \frac{1}{2} \sum_{i=3}^{x+1}(x-i+1+1)(i-1)(i-2)$

$= \frac{1}{2} \sum_{i=3}^{x+1}(x-i+1)(i-1)(i-2) + \frac{1}{2}\sum_{i=3}^{x+1}(i-1)(i-2) $

令$h_{x} = \frac{1}{2}\sum_{i=3}^{x}(i-1)(i-2) $，则：

$g_{x+1} = g_{x} + h_{x}$，其中，用平方和公式和等差数列求和公式可以O（1）地计算$h_{x}$。

代码：O(T + N)

#include <iostream>

#include <cmath>

#include <map>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <set>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <iomanip>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<<x) // be conscious if mask x exceeds int

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

template <typename T>

inline void write(T x) {

    int len = ; char c[]; if (x < ) putchar('-'), x = -x;

    do{++len; c[len] = x% + '';} while (x /= );

    for (int i = len; i >= ; i--) putchar(c[i]);

}

template <typename T, typename... Args>

inline void write(T x, Args ... args) { write(x), write(args...); }

#define md 1000000007

ll mul(ll a, ll b) {

    return a * b % md;

}

ll add(ll a, ll b) {

    ll res = (a+b) % md;

    if (res < ) res += md;

    return res;

}

ll fpow(ll a, ll p) {

    ll res = ;

    for (; p; p >>= ) {

        if (p & )

            res = mul(res, a);

        a = mul(a, a);

    }

    return res;

}

ll inv6, inv2;

ll g[N];

ll h(ll x) {

    ll res = ;

    res = add(res, mul(mul(x, mul(x+, *x+)), inv6));

    res = add(res, mul(mul(x, x+), inv2));

    res = mul(res, inv2);

    return res;

}

void init() {

    g[] = ;

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

        g[i] = add(g[i-], h(i-));

    }

}

int main() {

    fast;

    int T; cin >> T;

    inv2 = fpow(, md-);

    inv6 = fpow(, md-);

    init();

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

        int n, m; cin >> n >> m;

        ll ans = mul(g[n], g[m]);

        cout << "Case " << kase << ": " << ans << endl;

    }

    return ;

}

Problem K. Mr. Panda and Kakin 02：36 （-2） Solved by Dancepted & xk （欧拉定理逆元素数密度）

根据欧拉定理的推论，$i^{a}$ mod n的循环节长度为$\phi(n)$，并且把n分解为$\sum_{p\in prime}p_{i}^{m_{i}}$后若$m_{i}$ <= 1，则$i^{a}$ mod n为纯循环（参考纯循环小数意会一下）。

那么只要能把$FLAG^{2^{30}+3}$凑成$FLAG^{1 mod \phi(n)}$就行了。

实际上$(x^{a})^{b} = x^{a×b}$，所以如果我们能求出$2^{30}+3$关于$phi(n)$的逆元，那么就有$(Flag^{2^{30}+3})^{逆元} = Flag^{1 mod \phi(n)} = Flag$。

而这个逆元是肯定存在的，因为$2^{30}+3$是一个质数，而且考虑到n的生成方式，n = p × q，phi(n) = (p-1)×(q-1)。而 p-1，q-1 < $2^{30}+3$，因此（$2^{30}+3， \phi(n)$）= 1。

求$\phi(n)$的时候考虑素数密度，可以$O(log^{2}n)$暴力地找出n的两个素因子。

然后快速幂会爆long long，要用快速乘，然后这题的log又比较大，$log^{2}$会tle，所以要用O(1)的快速乘。

PS：第一次写脑抽了以为$(x^{a})^{c} = x^{a+b}$，幸好没过样例。

PPS：这里吹爆jls在ccpc-camp讲的数论div2，听完之后碰到欧拉定理完全不虚，然后在comet oj的直播回放里就可以看（jls的盛世美颜）了。

代码：O（T×logn）

#include <iostream>

#include <cmath>

#include <map>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <set>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <iomanip>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<<x) // be conscious if mask x exceeds int

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

typedef long double ldb;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

template <typename T>

inline void write(T x) {

    int len = ; char c[]; if (x < ) putchar('-'), x = -x;

    do{++len; c[len] = x% + '';} while (x /= );

    for (int i = len; i >= ; i--) putchar(c[i]);

}

template <typename T, typename... Args>

inline void write(T x, Args ... args) { write(x), write(args...); }

ll gcd(ll a, ll b) {

    return b ==  ? a : gcd(b, a%b);

}

ll fmul(ll a, ll b, ll md) {

    a %= md, b %= md;

    ll c = (ldb) a * b / md;

    ll ans = a * b - c * md;

    if (ans < ) ans += md;

    else if (ans >= md) ans -= md;

    return ans;

}

ll fpow(ll a, ll p, ll md) {

    ll res = ;

    for (; p; p >>= ) {

        if (p & )

            res = fmul(res, a, md);

        a = fmul(a, a, md);

    }

    return res;

}

ll exgcd(ll a, ll b, ll &x, ll &y) {

    if (a ==  && b == ) return -;

    if (b == ) {x = , y = ; return a;}

    ll d = exgcd(b, a%b, y, x);

    y -= a/b*x;

    return d;

}

ll mod_reverse(ll a, ll n) {

    ll x, y;

    ll d = exgcd(a, n, x, y);

    if (d == ) return (x % n + n) % n;

    return -;

}

int main() {

    // fast;

    int T; cin >> T;

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

        ll n, c; read(n, c);

        ll g = gcd(n, c);

        ll flag = , phin = ;

        if (g == ) {

            ll x = sqrt(n+0.5);

            if (x %  == )

                x--;

            for (ll i = x; i >= ; i -= ) {

                if (n % i == ) {

                    phin = (i-) * (n/i -);

                    break;

                }

            }

        }

        else {

            phin = (g-) * (n/g - );

        }

        ll p = mod_reverse((<<)+, phin);

        flag = fpow(c, p, n);

        printf("Case %d: %I64d\n", kase, flag);

    }

    return ;

}

/*

3

181857896263 167005790444

218128229323 156323229335

352308724847 218566715941

*/

Problem I. Cockroaches 04：19 （-1） Solved by Dancepted & lh & xk

大概是个思维题吧。。。封榜20分钟才调出来qwq。（不过好像是第一次封榜后过题？）

能消灭的最多的小强数量只有两种情况。设小强数最多的行和列对应的小强数是r和c，那么能消灭最多的数量要么是r+c，要么是r+c-1。

然后遍历小强数最多的行（列）上的小强，统计能消灭r+c和r+c-1的方案数就行了。

具体的就是遍历小强数最多的行（列）上的小强的时候，看这些小强是否恰巧在小强数最多的列（行），如果在的话，说明激光中心在这个小强所在点上时，能消灭的数量是r+c-1而不是r+c。

若r+c的数量为0，那么用同样的方法再统计一下小强数次多的行（列）与小强数最多的列（行）对r+c-1的贡献就行了。

小强的坐标上限是1e9，要离散化一下。

特别地：依次最多消灭小强数为2的时候要特判一下，防止在两个不同点消灭了两个相同小强。

代码：O（T×nlogn）

#include <iostream>

#include <cmath>

#include <map>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <set>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <iomanip>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 200005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<<x) // be conscious if mask x exceeds int

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

template <typename T>

inline void write(T x) {

    int len = ; char c[]; if (x < ) putchar('-'), x = -x;

    do{++len; c[len] = x% + '';} while (x /= );

    for (int i = len; i >= ; i--) putchar(c[i]);

}

template <typename T, typename... Args>

inline void write(T x, Args ... args) { write(x), write(args...); }

int n;

vector<int> vals;

map<int, int> id;

// int id[N<<1];

struct Node{

    int r, c;

}ns[N];

vector <Node> vc[N], vr[N];

int cntr1 = -, cntr2 = -, lenr1 = -, lenr2 = -;

int cntc1 = -, cntc2 = -, lenc1 = -, lenc2 = -;

void init() {

    sort(vals.begin(), vals.end());

    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    for (int i = ; i < sz(vals); i++) {

        id[vals[i]] = i;

        vc[i].clear();

        vr[i].clear();

    }

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

        int idr = id[ns[i].r], idc = id[ns[i].c];

        vr[idr].push_back(ns[i]);

        vc[idc].push_back(ns[i]);

    }

    cntr1 = -, cntr2 = -, lenr1 = -, lenr2 = -;

    cntc1 = -, cntc2 = -, lenc1 = -, lenc2 = -;

    for (int i = ; i < sz(vals); i++) {

        if (sz(vr[i]) > lenr1) {

            lenr2 = lenr1;

            cntr2 = cntr1;

            lenr1 = sz(vr[i]);

            cntr1 = ;

        }

        else if (sz(vr[i]) == lenr1) {

            cntr1++;

        }

        else if (sz(vr[i]) > lenr2) {

            lenr2 = sz(vr[i]);

            cntr2 = ;

        }

        else if (sz(vr[i]) == lenr2) {

            cntr2++;

        }

        if (sz(vc[i]) > lenc1) {

            lenc2 = lenc1;

            cntc2 = cntc1;

            lenc1 = sz(vc[i]);

            cntc1 = ;

        }

        else if (sz(vc[i]) == lenc1) {

            cntc1++;

        }

        else if (sz(vc[i]) > lenc2) {

            lenc2 = sz(vc[i]);

            cntc2 = ;

        }

        else if (sz(vc[i]) == lenc2) {

            cntc2++;

        }

    }

}

int main() {

    fast;

    int T; cin >> T;

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

        cin >> n;

        id.clear();

        vals.clear();

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

            read(ns[i].r, ns[i].c);

            vals.push_back(ns[i].r);

            vals.push_back(ns[i].c);

        }

        init();

        ll ans1 = lenc1 + lenr1, cnt1 = ;

        ll ans2 = lenc1 + lenr1 - , cnt2 = ;

        for (int i = ; i < sz(vals); i++) {

            if (sz(vc[i]) == lenc1) {

                cnt1 += cntr1;

                if (lenr2 == lenr1 - ) {

                    cnt2 += cntr2;

                }

                for (Node &tmp : vc[i]) {

                    if (sz(vr[id[tmp.r]]) == lenr1) {

                        // share same point

                        cnt1--;

                        cnt2++;

                    }

                    else if (lenr2 == lenr1 -  && sz(vr[id[tmp.r]]) == lenr2) {

                        cnt2--;

                    }

                }

            }

            else if (lenc2 == lenc1 -  && sz(vc[i]) == lenc2) {

                cnt2 += cntr1;

                for (Node &tmp: vc[i]) {

                    if (sz(vr[id[tmp.r]]) == lenr1) {

                        // share same point

                        cnt2--;

                    }

                }

            }

        }

        ll ans = , cnt = ;

        if (cnt1 > ) {

            ans = ans1, cnt = cnt1;

        }

        else {

            ans = ans2, cnt = cnt2;

        }

        if (ans == ) {

            cnt = 1LL * n * (n-) / ;

        }

        printf("Case %d: %I64d %I64d\n", kase, ans, cnt);

    }

    return ;

}

Problem B. Balance of the Force 04：35（+） Solved by lh（贪心）

不能放在同一边的两个人连一条边，如果得到的图中有奇数环，则不可能。

然后枚举最小的能力值。贪心地寻找最小的最大值。

枚举下一个最小的能力值时，仅有当前最小能力值所在的环，和下一个最小能力值所在的环对应的能力值要更新，所以整个贪心可以是O（N）的。

代码：O（T×N）

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <cstring>

#define N 200005

#define INF 0x3f3f3f3f

#define fi first

#define se second

using namespace std;

typedef pair<int,int> pii;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

template <typename T>

inline void write(T x) {

    int len = ; char c[]; if (x < ) putchar('-'), x = -x;

    do{++len; c[len] = x% + '';} while (x /= );

    for (int i = len; i >= ; i--) putchar(c[i]);

}

template <typename T, typename... Args>

inline void write(T x, Args ... args) { write(x), write(args...); }

int T;

int n, m, ednum, top, col[N];

int w[N][];

struct node

{

    int be, w;

    bool operator<(const node &other)const

    {

        return w < other.w;

    }

} s[N << ];

struct Unite

{

    int cur, maxn[], minx[];

} st[N];

int hed[N << ], nxt[N << ], to[N << ];

void add(int u, int v)

{

    to[++ednum] = v;

    nxt[ednum] = hed[u], hed[u] = ednum;

}

bool dfs(int v)

{

    st[top].maxn[] = max(st[top].maxn[], w[v][col[v]]), st[top].minx[] = min(st[top].minx[], w[v][col[v]]);

    st[top].maxn[] = max(st[top].maxn[], w[v][col[v] ^ ]), st[top].minx[] = min(st[top].minx[], w[v][col[v] ^ ]);

    for (int i = hed[v]; i; i = nxt[i])

    {

        int u = to[i];

        if (col[u] == col[v])

            return false;

        if (col[u] != -)

            continue;

        col[u] =  ^ col[v];

        if (dfs(u) == false)

            return false;

    }

    return true;

}

int save[N], ansmax;

bool reduce()

{

    while (top)

    {

        int id = save[top];

        if (st[id].cur == )

            return false;

        ansmax = max(ansmax, st[id].maxn[]), st[id].cur = , --top;

    }

    return true;

}

int main() {

    read(T);

    int u, v, cnt;

    int casecnt = ;

    while (T--)

    {

        ++casecnt;

        read(n, m), ednum = top = , memset(hed, , sizeof(int) * (n + )), memset(col, -, sizeof(int) * (n + ));

        for (int i = ;i <= m; ++i)

            read(u, v), add(u, v), add(v, u);

        for (int i = ;i <= n; ++i)

            read(w[i][], w[i][]);

        bool flag = true;

        ansmax = , top = , cnt = ;

        int ans = INF;

        for (int i = ;i <= n; ++i)

        {

            if (col[i] != -) continue;

            ++top, st[top].cur = , st[top].maxn[] = st[top].maxn[] = ;

            st[top].minx[] = st[top].minx[] = INF, col[i] = , flag &= dfs(i);

            if (flag == false)

                break;

            if (st[top].minx[] > st[top].minx[])

                swap(st[top].minx[], st[top].minx[]), swap(st[top].maxn[], st[top].maxn[]);

            if (st[top].maxn[] >= st[top].maxn[])

                st[top].cur = ;

            else

                s[++cnt] = node{top, st[top].minx[]};

            s[++cnt] = node{top, st[top].minx[]};

            ansmax = max(ansmax, st[top].maxn[st[top].cur]);

        }

        printf("Case %d: ", casecnt);

        if (flag == false)

        {

            puts("IMPOSSIBLE");

            continue;

        }

        sort(s + , s +  + cnt);

        int i = ;

        top = ;

        while (flag && i <= cnt)

        {

            ans = min(ans, ansmax - s[i].w);

            save[++top] = s[i].be;

            if (s[i].w != s[i + ].w)

            {

                flag &= reduce();

                if (!flag)

                    break;

            }

            ++i;

        }

        write(ans), putchar('\n');

    }

    return ;

}

还有不到一周就是CCPC-Final了，这周每两天一套题，冲鸭。

总结：

浮躁的菜逼选手贡献全部罚时。

巴特西

模拟赛小结：2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

最新文章

热门文章