2020-11-11 21:53 已编辑 C++

关注

CSP2020-S2 题解

T1 儒略日

分为两种情况。

在1582年10月4日以前

每4年有一个闰年，我们先确定在答案前4年内的某一年（的1月1日），然后一年一年增加，再一月一月增加，再一日一日增加。

我们可以把公元前x年当作公园-x+1年。
在1582年10月15日以后

每400年有97个闰年，就确定答案前400年的某一年（的1月1日），跟上面一样这么干就OK了。

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define i64 long long

int Q; i64 n;
int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check( int y ){
    return ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
}

int main(){
//    open("julian");
    scanf( "%d", &Q );
    while( Q-- ){
        scanf( "%lld", &n );
        if ( n <= 2299160 ){ // 1582 10 4
            int y = -4712 + n / (365 * 4 + 1) * 4, m = 1, d = 1; n %= (365 * 4 + 1);
            while( n >= 365 + (y % 4 == 0) ) n -= 365 + (y % 4 == 0), ++y;
            while( n >= a[m] + (m == 2 && y % 4 == 0) ) n -= a[m] + (m == 2 && y % 4 == 0), ++m;
            d += n;
            if ( y <= 0 ) printf( "%d %d %d BC\n", d, m, -y + 1 );
            else printf( "%d %d %d\n", d, m, y );
        } else { // 1582 10 15
            n = n - 2299160 + 286;
            int y = 1582, m = 1, d = 1;
            y += n / (365 * 400 + 97) * 400, n %= (365 * 400 + 97);
            while( n >= 365 + check(y) ) n -= 365 + check(y), ++y;
            while( n >= a[m] + (m == 2 && check(y)) ) n -= a[m] + (m == 2 && check(y)), ++m;
            d += n;
            printf( "%d %d %d\n", d, m, y );
        }
    }
    return 0;
}

T2 动物园

我们先把所有动物的编号或起来，如果第x位为1，那对于所有 $p_i=x$ 的i，将 $q_i$ 塞进集合S；对于 $q_i\notin S$ 的i，第 $p_i$ 位不能为1。

连 unsigned long long 都不够。

所以随手写个高精度就可以了。（呵呵

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define i64 long long
#define u64 unsigned long long

const int _ = 1e6 + 55;
int N, M, C, K; u64 S1; bool S2;
bitset<100000055> vs; bool flg[100];
int p[_], q[_];
char str[100]; int n, ans[100];

bool check( int x ){ return ((S1 >> x) & 1) || (x == 64 && S2); }

int main(){
//    open("zoo");
    scanf( "%d%d%d%d", &N, &M, &C, &K ); u64 x; bool y; char t;
    fp( i, 1, N ){
        x = 0, y = 0, scanf( "%s", str );
        if ( strlen(str) > 20 && strcmp(str, "18446744073709551616") >= 0 ) y = 1;
        fp( i, 0, strlen(str) - 1 ) x = x * 10 + (str[i] & 15);
        S1 |= x, S2 |= y;
    }
    fp( i, 1, M ){
        scanf( "%d%d", p + i, q + i );
        if ( check(p[i]) ) vs[q[i]] = 1;
    }
    fp( i, 1, M ) if ( !check(p[i]) && !vs[q[i]] && !flg[p[i]] ) flg[p[i]] = 1, --K;
    ans[n = 1] = 1;
    fp( i, 1, K ){
        fp( j, 1, n ) ans[j] <<= 1;
        fp( j, 1, n ) if ( ans[j] >= 10 ) ans[j + 1] += ans[j] / 10, ans[j] %= 10;
        if ( ans[n + 1] ) ++n;
    }
    ans[1] -= N;
    fp( i, 1, n ) if ( ans[i] < 0 ){ int t((-1 - ans[i]) / 10 + 1); ans[i + 1] -= t, ans[i] += t * 10; } else break;
    while( n > 1 && !ans[n] ) --n;
    fd( i, n, 1 ) printf("%d", ans[i]);
    printf("\n");
    return 0;
}

T3 函数调用

再增加一个3类函数 $0$ ，调用 $f_i$ 。

最终只要调用一次函数 $0$ 再输出答案。

我们将函数视为节点，将 $3$ 类函数 $j$ 向调用的函数 $g^{(j)}_i$ 连有向边。

因为函数不会直接或间接地调用本身，所以建成的有向图是 $DAG$ 。

DFS 一遍 $DAG$ ，如果将所有访问到 $1,2$ 类函数按顺序排成一个序列 $\{p_n\}$ ，按顺序执行后序列就是答案啦。

原序列 $a_i$ 对最终答案的影响为 $a_i\prod_{T_{p_k}=1}V_{p_k}$ 。

$2$ 类函数 $p_j$ 对最终答案的影响为 $V_{p_j}\prod_{k>j,T_{p_k}=1}V_{p_k}$ 。

$s_1[i]$ 表示节点调用函数 $i$ 所有直接/非直接调用的 $2$ 类函数 $V$ 的乘积。

然后再按拓扑序扫一遍，记录一下之后所有系数之和，将贡献全部计算进去就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define i64 long long

const int _ = 1e5 + 55, mod = 998244353;
int N, M, a[_], s1[_], s2[_];
int T[_], P[_], V[_];
vector<int> g[_], e[_];
queue<int> Q; int ind[_], top[_], n;

int main(){
//    open("call");
    scanf( "%d", &N );
    fp( i, 1, N ) scanf( "%d", a + i );
    scanf( "%d", &M ); int x;
    fp( i, 1, M ){
        scanf( "%d", T + i );
        if ( T[i] == 1 ) scanf( "%d%d", P + i, V + i );
        else if ( T[i] == 2 ) scanf( "%d", V + i );
        else if ( T[i] == 3 ){
            scanf( "%d", V + i );
            fp( j, 1, V[i] ){
                scanf( "%d", &x ), g[i].push_back(x);
            }
        }
    }
    fp( i, 1, M ) if ( T[i] == 3 ){
        fp( j, 0, (int)g[i].size() - 1 ) if ( T[g[i][j]] == 3 ) e[i].push_back(g[i][j]), ++ind[g[i][j]];
    }
    T[0] = 3; scanf( "%d", V );
    fp( j, 1, V[0] ){
        scanf( "%d", &x ), g[0].push_back(x);
        if ( T[x] == 3 ) e[0].push_back(x), ++ind[x];
    }
    fp( i, 0, M ) if ( T[i] == 3 && !ind[i] ) Q.push(i);
    while( Q.size() ){
        int u = top[++n] = Q.front(); Q.pop();
        for ( int i = 0; i < (int)e[u].size(); ++i )
            if ( !--ind[e[u][i]] ) Q.push(e[u][i]);
    }
    fd( i, n, 1 ){
        int u = top[i], v; s1[u] = 1;
        fp( j, 0, (int)g[u].size() - 1 ){
            v = g[u][j];
            if ( T[v] == 3 ) s1[u] = (i64)s1[u] * s1[v] % mod;
            else if ( T[v] == 2 ) s1[u] = (i64)s1[u] * V[v] % mod;
        }
    }
    fp( i, 1, N ) a[i] = (i64)a[i] * s1[0] % mod;
    s2[0] = 1;
    fp( i, 1, n ){
        int u = top[i], v, t = s2[u];
        fd( j, (int)g[u].size() - 1, 0 ){
            v = g[u][j];
            if ( T[v] == 1 ) a[P[v]] = (a[P[v]] + (i64)t * V[v]) % mod;
            else if ( T[v] == 2 ) t = (i64)t * V[v] % mod;
            else if ( T[v] == 3 ) s2[v] = (s2[v] + t) % mod, t = (i64)t * s1[v] % mod;
        }
    }
    fp( i, 1, N ) printf( "%d%c", a[i], "\n "[i < N] );
    return 0;
}

T4 贪吃蛇

假如最终进行 $N-1$ 轮， $b_i$ 表示第 $i$ 轮时最强的蛇， $c_i$ 表示第 $i$ 轮最弱的蛇。

那么决斗结束时被吃蛇的序列肯定为 $c_i$ 的前缀。

所以只要我们求出 $b_i,c_i$ 就能 $O(N)$ 求出答案。

我们用 $set$ 维护最强🐍和最弱🐍，复杂度为 $O(N\log N)$ 。加上 $STL$ 可怕的大常数，你可以轻松地 $\color{red}{TLE}$ 。

记得 NOIP2016 蚯蚓么？这题也可以用相似的方法。

题目中 $a_i$ 不下降，倒过来扔进 $Q_1$ ，将每轮的 $b_i$ 扔进 $Q_2$ 。

很明显 $b_i$ 是越来越弱的，如果 $a(b_i)-a(c_i)$ 为最弱的， $i+1$ 轮直接拿来当最弱的🐍；否则 $c_{i+1}$
比 $c_i$ 强，那么 $a(b_{i+1})-a(c_{i+1})$ 要比 $a(b_i)-a(c_i)$ 弱。

这样，就可以 $O(N)$ 得到答案了。

代码

#include<bits/stdc++.h>
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define i64 long long

const int _ = 1e6 + 55;

struct node{
    int i, x; node( int a = 0, int b = 0 ):i(a), x(b){}
    bool operator < ( const node &t )const{ return x == t.x ? i < t.i : x < t.x; }
};

int T, N, M, a[_], b[_], c[_], l[_];
node Q1[_], Q2[_]; int hd1, tl1, hd2, tl2;

int work(){
    hd1 = hd2 = 1, tl1 = tl2 = 0;
    fd( i, N, 1 ) Q1[++tl1] = node(i, a[i]);
    fp( i, 1, N - 1 ){
        node mx, mn;
        if ( hd1 <= tl1 && (hd2 > tl2 || Q2[hd2] < Q1[hd1]) ) mx = Q1[hd1++];
        else mx = Q2[hd2++];
        if ( hd1 <= tl1 && (hd2 > tl2 || Q1[tl1] < Q2[tl2]) ) mn = Q1[tl1--];
        else mn = Q2[tl2--];
        b[i] = mn.i, c[i] = mx.i;
        Q2[++tl2] = node(mx.i, mx.x - mn.x);
    }
    int ed = N - 1;
    fp( i, 1, N ) l[i] = 1e9;
    fd( i, N - 1, 1 ){
        if ( l[c[i]] <= ed ) ed = i - 1;
        l[b[i]] = i;
    }
    return N - ed;
}

int main(){
    // open("snakes");
    scanf( "%d%d", &T, &N ); int x, y;
    fp( i, 1, N ) scanf( "%d", a + i );
    printf( "%d\n", work() );
    while( --T ){
        scanf( "%d", &M );
        fp( i, 1, M ) scanf( "%d%d", &x, &y ), a[x] = y;
        printf( "%d\n", work() );
    }
    return 0;
}