郧阳中学12/24周考题解
命题人
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时间，通关的期望。转移：
- 若进行第i关前已经重置，这一关的期望变为K
- 若进行第i关用时为A_i，则期望 (dp[i+1][j+A_i]+A_i)*P_i
- 若进行第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;
}
题目来源
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;
}
