命题人

KSkun

题目列表

赛题 #A: 负负得正 | 数学，数论，组合数学
赛题 #B: 疯狂的FGOer | 期望DP，二分答案
赛题 #C: Kirara Fantasia的一天 | 图论，Tarjan，缩点，DAGDP

负负得正

一句话题意

求构建出元素全为1或-1的一个n \times m的矩阵并使得每行每列的乘积都为1或都为-1的方案数。

解法

仅输出0可得25分。

30% 1 \leq n,\ m \leq 10

枚举，瞎搞。
优化：我们知道，枚举出n-1行m-1列后剩下的一行一列的值是可以唯一确定的，所以只需要枚举n-1行m-1列的一个矩阵。
总复杂度O(2^{(n-1)(m-1)})。

50% 1 \leq n,\ m \leq 10^4

我们只需要把n-1行m-1列的矩阵填完，剩下一行一列的值可以确定，而且对于任意填法都可以确定。考虑右下角（即第n行第m列）的元素。假设n-1行m-1列矩阵整个的乘积为p，对于最后一列而言，这个位置应当填k^{m-1}p，而对于最后一行而言，这个位置应当填k^{n-1}p。显然当n和m的奇偶性不同且k为-1时，不存在任何一种填法满足要求。其余情况只要填满了n-1行m-1列矩阵都可以成立。因此总方案数是2^{(n-1)(m-1)}。快速幂处理即可。
这个部分分是因为如果你用int存后面的部分分会爆炸，特意设了一档。
总复杂度O(log_2((n-1)(m-1)))。

80% 1 \leq n,\ m \leq 10^9

写long long。

100% 1 \leq n,\ m \leq 10^{18}

欧拉降幂公式：
a^{k} \equiv a^{k \ mod \ \varphi(m) + \varphi(m)} \ (mod \ m)
继而缩小指数的范围，优化时空复杂度。

代码

// Code by KSkun, 2017/12
#include <cstdio> 

const int MO = 1e9 + 7;
long long n, m, k;

inline long long fpow(long long n, long long k) {
    long long res = 1;
    for(; k; k >>= 1) {
        if(k & 1) res = res * n % MO;
        n = n * n % MO;
    }
    return res;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    if(k == -1 && (n & 1) != (m & 1)) printf("0");
    else printf("%lld", fpow(2, ((n - 1) % (MO - 1)) * ((m - 1) % (MO - 1)) % (MO - 1) + (MO - 1)));
    return 0;
}

题目来源

CF894B – Ralph And His Magic Field

疯狂的FGOer

一句话题意

有一系列任务，每一任务都有一定概率快或慢完成，每个任务完成后可以选择继续完成接下来的任务或是从头开始完成，求一种选择是否从头开始的策略使得完成全部任务的期望值最小。

解法

10% P_i = 1

直接把A_i加起来。
总复杂度O(n)。

一种不完美的写法

出题事故：50%部分分的写法被证实是错误的，因此还没有想到能够用于50%部分分的写法。
原错解：
考虑当我们重置游戏的时候会发生什么。一定是当出现较长时间时重置比较优。如果不重置，每一关的期望应该是上一关期望加上A_i*P_i+B_i*(1-P_i)；而如果重置了，则是(exp_{i-1}+B_i)*prob+A_i。此处prob指尝试的次数，可以由题目提示中的方法算出。比较二者大小然后选择即可。但是对于t限制比较严格的数据，由于这里没有剔除超t的可能性，很容易WA。事实证明，这个方法只能过40%的点。由于时间关系，没有对这一层设置部分分，实在抱歉。

100% 1 \leq n \leq 50

考虑对题目模型加以改造。我们假设从头开始进行完游戏的期望是K。这样一种考虑方案需要我们从末尾开始DP计算期望。设计DP状态为：dp[i][j]表示当前计算到第i关，一共用去了j时间，通关的期望。转移：

1. 若进行第i关前已经重置，这一关的期望变为K
2. 若进行第i关用时为A_i，则期望 (dp[i+1][j+A_i]+A_i)*P_i
3. 若进行第i关用时为B_i，则期望 (dp[i+1][j+B_i]+B_i)*(1-P_i)

对于K这个数字，我们发现，它在较大的时候容易满足条件，满足条件的取值是单调的，具有二分性质。考虑二分答案计算K。每计算出一次通关期望，即用其与所设的K比较，若比K小则显然可行。
复杂度O(n^2logn)。

代码

// Code by KSkun, 2017/12
#include <cstdio>
#include <algorithm>

const double EPS = 1e-8;

double dp[55][5005], p[55];
int a[55], b[55], n, t; 

inline bool check(double x) {
    for(int i = n - 1; i >= 0; i--) {
        for(int j = t + 1; j < 5005; j++) {
            dp[i + 1][j] = x;
        }
        for(int j = 0; j <= t; j++) {
            dp[i][j] = std::min(x, (dp[i + 1][j + a[i]] + a[i]) * p[i] + (dp[i + 1][j + b[i]] + b[i]) * (1 - p[i]));
        } 
    }
    return dp[0][0] < x;
} 

int main() {
    scanf("%d%d", &n, &t);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%lf", &a[i], &b[i], &p[i]);
    }
    double l = 0, r = 1e10, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%.2lf", l);
    return 0;
} 

题目来源

CF865C – Gotta Go Fast

Kirara Fantasia的一天

一句话题意

给一个有向图，边权每次经过时按照一定的规则递减（第一次-1，第二次-2，以此类推），求一条路径使边权最大。

解法

100% 1 \leq n, m \leq 10^6

图这么大，显然跑不动。
考虑强连通分量内部的状况，显然是可以跑多几次使得每条边边权全部为0的，因此主要策略是Tarjan缩点+拓扑序DP（用于最长路，你也可以SPFA，没写过）。
如果想把一条边的边权踩完，你需要对这样一个数列求和
\sum_{i=k}^{w} (w-(1+2+ \cdots +i)) = \sum_{i=k}^{w} (w-\frac{i(i+1)}{2})
其中k是使得数列元素为正值的最大正整数。这个数列求和就变成了
\frac{n(n+1)(n+2)}{6}
因此有了代码中cal()函数的写法。
其他的拓扑序DP找最长路，比较显然，不加以解释。
友情提示：全程用long long，记得写快读。
复杂度O(n+m)。

代码

// Code by KSkun, 2017/12
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
typedef long long LL;

const LL inf = 1e15;

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline LL read() {
        register LL res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read 

struct Edge {
    int to, nxt;
    LL w;
};

struct Graph {
    Edge gra[1000005];
    int head[1000005], rd[1000005], tot;
    LL w[1000005];

    Graph() {
        memset(head, -1, sizeof head);
        tot = 0;
    }

    inline void addedge(int u, int v, LL w) {
        gra[tot].to = v;
        gra[tot].w = w;
        gra[tot].nxt = head[u];
        rd[v]++;
        head[u] = tot++;
    }
}; 

int n, m;
Graph g1, g2;
int dfn[1000005], low[1000005], step = 1, sccno[1000005], scctot = 1;
bool instack[1000005];
std::stack<int> sta;

inline void tarjan(int s) {
    dfn[s] = low[s] = step++;
    instack[s] = true;
    sta.push(s);
    for(int e = g1.head[s]; e != -1; e = g1.gra[e].nxt) {
        int v = g1.gra[e].to;
        if(dfn[v] == 0) {
            tarjan(v);
            low[s] = std::min(low[s], low[v]);
        } else if(instack[v]) {
            low[s] = std::min(low[s], dfn[v]); 
        } 
    } 
    if(dfn[s] == low[s]) {
        LL totw = 0;
        while(sta.top() != s) {
            sccno[sta.top()] = scctot;
            instack[sta.top()] = false;
            sta.pop();
        }
        sccno[sta.top()] = scctot;
        instack[sta.top()] = false;
        sta.pop();
        scctot++;
    }
}

inline LL cal(LL w) {
    LL n = sqrt(2 * w + 0.25) - 0.5;
    return n * w - n * (n + 1) * (n + 2) / 6 + w;
}

inline void calg2() {
    for(int u = 1; u <= n; u++) {
        for(int e = g1.head[u]; e != -1; e = g1.gra[e].nxt) {
            int v = g1.gra[e].to;
            if(sccno[u] == sccno[v]) {
                g2.w[sccno[u]] += cal(g1.gra[e].w);
            } else {
                g2.addedge(sccno[u], sccno[v], g1.gra[e].w);
            }
        }
    }
}

std::queue<int> que;
LL ans = 0, dp[1000005];

inline void toposort(int s) {
    for(int i = 1; i < scctot; i++) {
        dp[i] = -inf;
        if(g2.rd[i] == 0) que.push(i);
    }
    dp[s] = g2.w[s];
    while(!que.empty()) {
        int u = que.front();
        ans = std::max(ans, dp[u]);
        que.pop();
        for(int e = g2.head[u]; e != -1; e = g2.gra[e].nxt) {
            int v = g2.gra[e].to;
            g2.rd[v]--;
            if(dp[u] != -inf) dp[v] = std::max(dp[v], dp[u] + g2.gra[e].w + g2.w[v]);
            if(g2.rd[v] == 0) {
                que.push(v);
            }
        }
    } 
}

int ut, vt, wt;
int st;

int main() {
    n = read();
    m = read();
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        wt = read();
        g1.addedge(ut, vt, wt);
    }
    st = read();
    for(int i = 1; i <= n; i++) {
        if(dfn[i] == 0) tarjan(i);
    }
    calg2();
    toposort(sccno[st]);
    printf("%lld", ans);
    return 0;
}

题目来源

CF894E – Ralph and Mushrooms