Codeforces杂题

CF559D

题意

给出一个 $n$ 个点的凸包，等概率选则该凸包点集的大于等于三的子集形成一个新凸包，问该凸包内部整点的期望值。 $3\leq n\leq 10^5,-10^9\leq x_i,y_i\leq 10^9$

题解

皮克定理: $S=n+\frac{s}{2}-1$
枚举每一条边对应的（劣弧）上的正点数+面积算出期望的内部整点 $num$ ，贡献为
$ $num\cdot \frac{2^{n-k}-1}{2^n-1-n-C_n^2}$ $
最后通过总面积-期望面积

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
int n;
const int N = 210000;
struct Node {
 double x, y;
    Node operator - (const Node u) {
        return (Node){x-u.x,y-u.y};
    }
    double operator *(const Node u) {
        return x * u.y - y*u.x;
    }
}a[N], tmp, l, r;
double bin[N];
int Gcd(int x, int y) {
    if(!y) return x;
    return Gcd(y, x %y);
}
int gcd(int x, int y) {
    return Gcd(abs(x), abs(y));
}
double kk;
ll c1, c2, kkz;
double tot, now, ans;
#define nxt(x) ((x%n+1))
#define pick(u,v) ((u)+1.0-0.5*(v))
#define cal(u) (n>=100? 1 / bin[u + 1] : (bin[n - k - 1] - 1.0) / kk)
int main() {
    n = read();
    bin[0] = 1;
    for(int i = 1; i <= n; ++i) {
        a[i].x = read();
        a[i].y = read();
        bin[i] = bin[i - 1] * 2;
    }
    kk = bin[n] - 1 - n - (double)n * (n - 1) / 2;
    tmp = a[n] - a[1];
    c1 += gcd(tmp.x, tmp.y);
    r = a[2] - a[1];
    c1 += gcd(r.x, r.y);
    for(int i = 3; i <= n; ++i) {
        l = a[i] - a[1];
        tmp = a[i] - a[i - 1];
        tot += r * l / 2;
        c1 += gcd(tmp.x, tmp.y);
        r = l;
    }
    for(int i = 1; i <= n; ++i) {
        r = a[nxt(i)] - a[i];
        c2 = gcd(r.x, r.y);
        now = 0;
        for(int j = nxt(nxt(i)), k = 2; k <= 35 && nxt(j) != i; j = nxt(j), ++k) {
            l = a[j] - a[i];
            tmp = l - r;
            c2 += ((kkz = gcd(l.x, l.y)) + gcd(tmp.x, tmp.y));
            now += r * l / 2;
            ans += (pick(now, c2) + (nxt(j) == i ? 0 : kkz - 1)) * cal(k);
            r = l;
            c2 -= kkz;
        }
    }
    printf("%.7lf\n", pick(tot, c1) - ans);
    return 0;
}

CF559E

题意

数轴上有 $n(n\le100)$ 个聚光灯，每个聚光灯可以照亮的区间为 $[p_i-l_i,p_i]$ 或者 $[p_i,p_i+l_i]$ ，问所有聚光灯能照到的长度。

题解

错误解法

如果是从结尾，往前找前驱，可能会受前驱的前驱干扰

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 110;
const int inf = 1 << 30;
int f[N][N][2], ans, n;
// f[i][j][k] 到第i个灯，目前覆盖到区间最右边的是第j个，第j个方向为k 
struct T {
    int x, y;
}a[N]; 
bool cmp(T x, T y) {
    return x.x + x.y <y.x + y.y;
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i].x = read();
        a[i].y = read();
    }
    sort(a + 1, a +1 + n, cmp);
    a[0].x = -1e9;
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= i; ++j) {
            for(int k = 0; k < 2; ++k) {
                int L, R;
                if(k == 0) {
                    L = a[j].x - a[j].y;
                    R = a[j].x;
                } else {
                    L = a[j].x;
                    R = a[j].x + a[j].y;
                }
                int len = R - L;

                for(int l = 0; l < j; ++l) {
                    for(int m = 0; m < 2; ++m) {
                        int nl, nr;
                        if(m == 0) {
                            nl = a[l].x - a[l].y;
                            nr = a[l].x;
                        } else {
                            nl = a[l].x;
                            nr = a[l].x + a[l].y;
                        }
//                        if(i == 2 && k == 1) {
//                            printf("(%d,%d,%d)->(%d,%d,%d) (%d,%d)(%d,%d) (%d->) %d\n", i - 1, l, m, i, j, k, nl, nr, L, R,f[i-1][l][m],f[i][j][k]);
//                        }
                        if(nr < L)
                            f[i][j][k] = max(f[i][j][k], f[i - 1][l][m] + len);
                        else {
                            if(nr > R) continue;

//                            assert(nr>R); 
//                            f[i][j][k] = max(f[i][j][k], f[i - 1][l][m] + abs(R - nr));
//                            f[i][j][k] = max(f[i][j][k], )
                        }
                    }
                }
                f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
                ans = max(ans, f[i][j][k]);
            }
        }
    }
    writeln(ans);
    return 0;
}

正解

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 110;
const int inf = 1 << 30;
int f[N][N][2], ans, n;
// f[i][j][k] 到第i个灯，目前覆盖到区间最右边的是第j个，第j个方向为k 
struct T {
    int x, y;
}a[N]; 
bool cmp(T x, T y) {
    return x.x + x.y <y.x + y.y;
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i].x = read();
        a[i].y = read();
    }
    sort(a + 1, a +1 + n, cmp);
    a[0].x = -1e9;
    int ans = 0;
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= i; ++j) {
            for(int d = 0; d < 2; ++d) {
                ans = max(ans, f[i][j][d]);
                int pre = a[j].x + a[j].y * d;
                for(int k = i + 1, Mx = -1e9, x, y; k <= n; ++k) {
                    for(int d2 = 0; d2 < 2; ++d2) {
                        int nxt = a[k].x + a[k].y * d2;
                        if(nxt > Mx) Mx = nxt, x = k, y = d2;
                        f[k][x][y] = max(f[k][x][y], f[i][j][d] + min(a[k].y, nxt - pre) + Mx - nxt);
                    }
                }
            }
        }
    }
    writeln(ans);
    return 0;
}

CF111D

题意

Petya喜欢计数。他想计算：

用 $K$ 种颜色绘制尺寸为 $n*m$ ( $n$ 行， $m$ 列)的矩形棋盘的方法数。

此外，着色应满足以下要求：

对于沿格子的线穿过的任何垂直线，会将棋盘分成两个非空的部分，这两个部分中的(不同颜色）的数量应相同。

帮助 $Petya$ 对这些颜色进行计数。

题解

CF679B

题意

有若干积木体积为 $1^3,2^3,\cdots k^3$ ，对于一个总体积 $X$ 要求每次贪心地取 $\leq X$ 的最大积木拼上去（每个积木有无限个）使得，最后总体积恰好为 $X$ ，求给定的 $1\sim m$ 内使选取的积木数量最大的 $X$ ，相同数量取 $X$ 较大者。 $m\leq 10^{15}$ 。

题解

假设当前剩余 $v$ ，那么选取下一个有两种可能.
假设 $a=\max \{x\}(x^3\leq v)$

选 $a^3$ ，那么剩余 $v-a^3$
选 $a^3$ , 那么剩余 $a^3-1-(a-1)^3$

因为 $a^3-1-(a-1)^3 > (a-1)^3-1-(a-2)^3$
所以不用考虑选 $(a-2)^3$

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
ll m;
vector<ll> a;
#define pa pair<ll,ll> 

pa dfs(ll v, ll h, ll x) { // 剩余体积，得到的高度，最大的体积 
    pa res;
    if(v == 0) {
        return make_pair(h, x);
    }
    int pos = upper_bound(a.begin(), a.end(), v) - a.begin() - 1;
    res = dfs(v - a[pos], h + 1, x + a[pos]);
    --pos;
    if(pos >= 0) res = max(res, dfs(a[pos + 1] - a[pos] - 1, h + 1, x + a[pos]));
    return res;
}

int main() {
    m = read();
    for(ll i = 1; i <= 1e5; ++i)
        a.push_back(i*i*i);
    pa ans = dfs(m, 0, 0);
    printf("%lld %lld\n", ans.first, ans.second);
    return 0;
}

CF360B

题意

定义
$ $C(a)=\max_{1\leq i\leq n - 1} |a_{i+***_i|,n>1; c(a)=0,0\leq n\leq 1.$ $现在给出一个长度为$ n $的数组$ a $，可以进行最多$ K $次修改，每次修改可以把任意一个$ a $元素替换成任意一个数字，问能得到的$ C(a)$的最小值

题解

二分答案， $f_i$ 表示从 $[1,i]$ 中， $a_i$ 强制不改变，前面都符合条件所需最少修改次数。
$ $f_i=\min_{j<i,abs(a_i-a_j)\leq (i-j)\times x}\{ f_j + (i-j+1)\}$ x$是二分的答案

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;


const int N = 2100;
int n, K;
ll f[N], a[N];
ll check(ll x) {
    f[1] = 0;
    for(int i = 2; i <= n ;++i) {
        f[i] = i - 1;
        for(int j = 1; j < i; ++j)
            if(abs(a[i] - a[j]) <= (i - j) * x)
                f[i] = min(f[i], f[j] + (i - j - 1));
    }
    ll ans = 1e9;
    for(int i = 1; i <= n; ++i)
        if(f[i] + n - i <= K) return 1;
    return 0;
}
int main() {
    n = read(), K = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    ll l = -1, r = 2e9 + 666;
    while(r - l > 1) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    writeln(r);
    return 0;
}

CF1108F

题意

给出 $n$ 个点， $m$ 条边的图。保证没有重边和自环。
每条边用 $(u,v,w)$ 表示。
它的最小生成树代价是 $k$ ，你每一次可以操作一条边使得其代价 $+1$ ，问最小的操作次数使得这张图的最小生成树代价为 $k$ 且唯一。

题解

先求出MST,然后枚举不在MST上的边。若两点之间的最大边权 $=W$ ，那么 $ans=ans+1$ 。否则这条边一定不在MST上

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 3e5 + 666;
int n, m;
struct G {
    struct Edge {
        int u, v, nxt, w;
    }e[N << 1];    
    int en, head[N];
    void addl(int x, int y, int z) {
        e[++en].u = x, e[en].v = y, e[en].w= z, e[en].nxt = head[x], head[x] = en;
    }
    int f[N][21], d[N], g[N][21];
    void dfs(int x, int F) {
        d[x] = d[F] + 1;
        for(int i = head[x]; i;i = e[i].nxt) {
            int y = e[i].v;
            if(y == F) continue;
            f[y][0] = x;
            g[y][0] = e[i].w;
            for(int j = 1; j <= 20; ++j) {
                f[y][j] = f[f[y][j - 1]][j - 1];
                g[y][j] = max(g[y][j - 1], g[f[y][j - 1]][j - 1]);
            }
            dfs(y, x);
        }
    }
    int get(int x, int y) {
        if(d[x] > d[y]) swap(x, y);
        int res = -1e9;
        for(int i = 20; ~i; --i)
            if(d[f[y][i]] >= d[x]) {
                res = max(res, g[y][i]);
                y = f[y][i];
            }

        if(x == y) return res;
        for(int i = 20; ~i; --i)
            if(f[x][i] != f[y][i]) {
                res = max(res, max(g[y][i], g[x][i]));
//                printf("x=%d,y=%d,i=%d,(%d,%d)\n", x, y, i, g[y][i], g[x][i]);
                x=  f[x][i];
                y = f[y][i];
            }
        return max(res, max(g[x][0], g[y][0]));
    }
}g;
struct Edge {
    int u, v, w;
}e[N << 1];
bool ok[N];
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}
int fa[N];
int Find(int x) {
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        e[i].u = read();
        e[i].v = read();
        e[i].w = read();
    }
    for(int i = 1; i <= n; ++i) fa[i] = i;
    sort(e + 1, e+1 +m,cmp);
    for(int i = 1; i <= m; ++i) {
        int x = e[i].u;
        int y = e[i].v;
        if(Find(x) != Find(y)) {
            g.addl(e[i].u, e[i].v, e[i].w);
            g.addl(e[i].v, e[i].u, e[i].w);
            fa[Find(x)] = Find(y);
            ok[i] = 1;
        }
    }
    g.dfs(1, 0);
    ll ans = 0;
    for(int i = 1; i <= m; ++i)
        if(!ok[i]) {
            int v = g.get(e[i].u, e[i].v);
            if(v == e[i].w )++ans;
        }
    writeln(ans);
    return 0;
}

CF1132D

题意

有 $n$ 个学生要打一场 $k$ 分钟的比赛（当然要用电脑）。

每个学生的电脑有初始电量 $a_i$ 和每分钟耗电量 $b_i$ （电量在这一分钟的最后一刻结算，即在下一分钟时才会减少，电量允许为负）。

这样肯定是无法打完比赛的，所以学生们买了一个充电器，功率为任意值，每分钟可以使电量增加 $x$ ，结算规则与耗电量一样，它可以在任一分钟给任一学生的电脑充电任意时长。

问题：求最小的 $x$ ，使所有学生的电脑的电量在 $k$ 分钟内（不包括第 $k$ 分钟）都不为负。
( $1 \le n \le 2 \cdot 10^5$ , $1 \le k \le 2 \cdot 10^5$ ) $1 \le a_i \le 10^{12}$ $1 \le b_i \le 10^7$

题解

二分裸体

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;


const int N = 3e5 + 666;
int n, m;
ll a[N], b[N];
#define pa pair<ll,ll>
struct Node {
    ll x, i, tim;
    bool operator <(Node B) const {
        return tim > B.tim;
    }
};
bool check(ll x) {
 priority_queue<Node> q;
 for(int i = 1; i <= n; ++i) q.push({a[i], i, a[i] / b[i]});
    ll tim = 0;
    while(!q.empty()) {
        Node now = q.top(); q.pop();
        if(now.tim >= m - 1) return 1;
        if(tim > now.tim) return 0;
        now.x += x;
        ++tim;
        now.tim = now.x / b[now.i];
        q.push(now);
        if(tim >= m) return 0; //careful 
    }
    return 0;
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i) b[i] = read();
    ll l = -1, r = 1e15; //be carefull of range 
    while(r - l > 1) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
 if(!check(r))puts("-1");
    else
        writeln(r);
    return 0;
}

CF1132E

题意

你有一个容量为 $W$ 的背包，和 $8$ 种物品，重量分别为 $1$ ~ $8$ 的整数，分别有 $cnt_1,cnt_2...cnt_8$ 个。
求背包中最多能装上多大的重量。

题解

$LCM(1,2,\cdots , 8)=850$ ,所以留下 $850+K(k\leq 850)$ 体积，然后做倍增背包即可。

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
ll w;
ll c[9], ans;
ll tw;
ll v[6666], tot;
ll f[6500];
int main() {
    w = read();
    for(int i = 1; i <= 8; ++i) c[i] = read();
    ll sum = 0;
    for(int i = 1; i <= 8; ++i) sum += c[i] * i;
    if(sum <= w) { //carefull
        writeln(sum);
        return 0;
    }
    tw = max(0ll, w - 850);
    w -= tw;
    for(int i = 1; i <= 8; ++i) {
        ll t = min(c[i], tw / i);
        if(c[i] - t < 10) t = max(0ll, c[i] - 10);
        ans += t * i;
        c[i] -= t;
        tw -= i * t;
    }
    w += tw;
    for(int i = 1; i <= 8; ++i) {
        ll t = 1;
        for(int j = 0; c[i] > 0; ++j) {
            ll cur = min(t, c[i]);
            c[i] -= cur;
            v[++tot] = cur * i;
            t <<= 1;
        }
    }
    for(int i = 1; i <= tot; ++i)
        for(int j = w; j >= v[i]; --j)
            f[j] = max(f[j], f[j - v[i]] + v[i]);
        writeln(ans + f[w]);
    return 0;
}

CF1099F

题意

$Mitya$ 和 $Vasya$ 正在玩一个有趣的游戏。

他们有一颗有根树，根节点的标号为1.对于标号为 $i$ 的节点 $(i≥2)$ ,他的父节点为 $p_i$ 。

每个节点上有一些饼干，节点 $i$ 上有 $x_i$ 个饼干， $Mitya$ 在节点 $i$ 上每吃一块饼干需要 $t_i$ 时间。

对于标号为 $i$ 的节点 $(i≥2)$ ,通过连接他的父节点和他自己的路径需要花费 $l_i$ 时间。

$Mitya$ 和 $Vasya$ 轮流进行游戏， $Mitya$ 先走。

在进行游戏的过程中，有以下两点规则：

$Mitya$ 每次可以从当前点走到自己的任意一个儿子节点
$Vasya$ 每次可以在所有的连接 $Mitya$ 所在点与其所在点的儿子的路径中选择一条，并移除它。每一回合， $Vasya$ 都可以选择不删除任意一条路径。

$Mitya$ 可以在任意一个他的回合停止游戏。停止游戏后，他会沿着先前走过的路径回到根节点，并在沿路中吃掉一些饼干。

$Mitya$ 吃饼干，从根节点到别的节点以及从别的节点返回到根节点的总时间不能超过 $T$ 。

问： $Mitya$ 最多能吃多少饼干。

注意： $Mitya$ 和 $Vasya$ 都是绝顶聪明的

题解

树状数组、dp

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 3e6 + 666;
int n;

ll T, X[N], t[N];
int L[N];
struct Tree {
    ll c[N];
    void add(int x, ll v) {
        for(; x <= 1e6; x += x&-x)
            c[x] += v;
    }
    ll query(int x) {
        ll res = 0;
        for(; x; x -= x & -x)
            res += c[x];
        return res;
    }
}t1, t2;
vector<int> g[N];
ll f[N];
void dfs(int x, ll dis) {
    if(T < dis*2) return;
    t1.add(t[x], X[x] * t[x]);
    t2.add(t[x], X[x]);
    int l = 0, r = 1e6 + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(t1.query(mid) <= (T - (dis << 1))) l = mid;
        else r = mid;
    }
//    printf("x=%d,l=%d (%d,%d)\n", x, l, x[X], t[x]);
    f[x] = t2.query(l);
    ll val = T - (dis << 1) - t1.query(l);
    if(l < 1e6)f[x] += val / (l + 1);
//    printf("%d:%d\n", x, f[x]);
    for(int y : g[x]) dfs(y, dis + L[y]);
    t1.add(t[x], -X[x] * t[x]);
    t2.add(t[x], -X[x]);    
}
ll ans[N];
void dfs(int x) {
    ll m1 = 0, m2 = 0;
    for(int y : g[x]) {
        dfs(y);
        if(ans[y] >= m1) {
            m2 = m1;
            m1 = ans[y];
        }else if(ans[y] >= m2) m2= ans[y];
    }
    if(x == 1) ans[x] = max(f[x], m1);
    else ans[x] = max(f[x], m2);
}
int main() {
    n = read(), T = read();
    for(int i = 1; i <= n; ++i) X[i] = read();
    for(int i = 1; i <= n; ++i) t[i] = read();
    for(int i = 2; i <= n; ++i) {
        g[read()].push_back(i);
        L[i] = read();
    }
    dfs(1, 0);
    dfs(1);
    writeln(ans[1]);
    return 0;
}

CF731E

题意

有长度为 $n$ 的序列， $A$ 和 $B$ 轮流操作， $A$ 是先手。
每一次操作，选一个长度 $\ge 2$ 的前缀，他们的和为 $s$ ，然后删掉他们，把 $s$ 加入到序列的左边。并且操作者得到分数 $s$
当序列的长度变成 $1$ 后游戏结束。 $A$ 和 $B$ 都想让自己得的分更大。

题解

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
/*
f[i][0] 先手从i到n使得先手值-后手指最大
f[i][1] 后手从i到n使得先手值-后手值最小 
*/
const int N = 210000;
ll a[N], n; 
ll sum[N];
ll f[N][2];
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i];        
    }
    f[n][0] = sum[n];
    f[n][1] = -sum[n];
    for(int i = n - 1; i >= 1; --i) {
        f[i][0] = max(f[i + 1][1] + sum[i], f[i + 1][0]);
        f[i][1] = min(f[i + 1][0] - sum[i], f[i + 1][1]);
    }
    writeln(f[1][0]);
    return 0;
}

CF850C

题意

给出 $n$ 个正整数 $a_i$ , $A$ 和 $B$ 两人轮流操作， $A$ 是先手。每次选出一个素数 $p$ 和一个数 $k$ 即 $p^k$ ，
如果该 $n$ 个数中有 $p^k$ 的倍数，那么所有的这些数都除以 $p^k$ 。不能操作者败，问先手是否必胜

题解

SG函数

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 110;
int a[N], n;
map<int,int> sg;
void solve(ll x) {
    if(sg.count(x)) return;
    vector<int> mex(30, 0);
    for(int i = 0; x >> i; ++i) {
        ll nx = ((x>>(i+1)) | (x & ((1 << i) - 1)));
        solve(nx);
        mex[sg[nx]] = 1;
    }
    int ret = 0;
    for(; mex[ret]; ++ret);
    sg[x] = ret;
}
int main() {
    n = read();
    set<int> p;
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        int t = a[i];
        for(int j = 2; j <= t / j; ++j) {
            if(t % j == 0) {
                p.insert(j);
                while(t % j == 0) t /= j;
            }
        }
        if(t > 1) p.insert(t);
    }
    sg[0] = 0;
    int ret = 0;
    for(auto y : p) {
        int st = 0;
        for(int i = 1; i <= n; ++i) {
            int cnt = 0;
            while(a[i] % y == 0) {
                a[i] /= y;
                ++cnt;
            }
            if(cnt) st |= (1 << (cnt - 1));
        }
        solve(st);
        ret ^= sg[st];
    }
    puts(ret ? "Mojtaba" : "Arpa");
    return 0;
}

CF965E

题意

给出 $n$ 个两两不同的由26个小写字母组成的字符串，你可以给任意的某几个字符串只保留其前缀，这个前缀可以是自身，问最后能使得字符串依旧两两不同且所有字符串的总长度最小。

题解

CF490F

题意

给出一棵树，每个节点有一个权值，让你求它的最长上升子序列 $n\leq 6000$

题解

force

考虑从每一个点做一遍dfs，然后用 $n \log n$ 的复杂度做单次dfs。

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 6100;

int a[N], n;
vector<int> g[N];
int f[N];
int ans;
void dfs(int x, int F) {
    int pos = lower_bound(f + 1, f + 1 + n, a[x]) - f;
    int tmp = f[pos];
    f[pos] = a[x];
    int t = lower_bound(f + 1, f + 1 + n, 0x3f3f3f3f) - f - 1;
    ans = max(ans, t);
    for(int y : g[x]) if(y != F) {
        dfs(y, x);
    }
    f[pos] = tmp;
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i < n; ++i){
        int  x = read(), y = read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; ++i) {

        dfs(i, 0);
    }
    writeln(ans);
    return 0;
}

std

$f_{i,0},f_{i,1}$ 表示子树 $x$ 内，以 $i$
这个权值结尾的最长 $LIS$ 和 $LDS$ 。
然后用线段树合并

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 6100;

int a[N], n, b[N];
vector<int> g[N];
int tot;
int mx[2][N << 4];
int ls[N << 4], rs[N << 4];
int rt[N];
void ins(int &k, int l, int r, int x, int v, int id) {
    if(!k) k = ++tot;
    if(l == r) {
        mx[id][k] = max(mx[id][k], v);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) ins(ls[k], l, mid, x, v, id);
    else ins(rs[k], mid + 1, r, x, v, id);
    mx[id][k] = max(mx[id][ls[k]], mx[id][rs[k]]);
}
int query(int k, int l, int r, int ql, int qr, int id) {
    if(!k) return 0;
    if(ql <= l && qr >= r) return mx[id][k];
    int mid = (l + r) >> 1;
    if(qr <= mid) return query(ls[k], l, mid, ql, qr, id);
    if(ql > mid) return query(rs[k], mid + 1, r, ql, qr, id);
    return max(query(ls[k], l, mid, ql, qr, id), query(rs[k], mid + 1, r, ql, qr, id));
}
int ans = 0;
int merge(int l, int r) {
    if(!l || !r) return l | r;
    int rt = l;
    mx[0][rt] = max(mx[0][l], mx[0][r]);
    mx[1][rt] = max(mx[1][l], mx[1][r]);
//    ans = max(ans, max(mx[0][ls[l]] + mx[1][rs[r]], mx[1][ls[l]] + mx[0][rs[r]])); // careful
    ans = max(ans, max(mx[0][ls[l]] + mx[1][rs[r]],mx[0][ls[r]] + mx[1][rs[l]])); // careful
    ls[rt] = merge(ls[l], ls[r]);
    rs[rt] = merge(rs[l], rs[r]);
    return rt;
}

void dfs(int x, int F) {
    int mx1 = 0, mx2 = 0;
    for(int y : g[x]) if(y != F) {
        dfs(y, x);
        int v1 = query(rt[y], 1, *b, 1, a[x] - 1, 0);
        int v2 = query(rt[y], 1, *b, a[x] + 1, *b, 1);
        ans = max(ans, max(mx1 + v2, mx2 + v1) + 1);
        rt[x] = merge(rt[x], rt[y]);
        mx1 = max(mx1, v1);
        mx2 = max(mx2, v2);
    }
    ins(rt[x], 1, *b, a[x], mx1 + 1, 0);
    ins(rt[x], 1, *b, a[x], mx2 + 1, 1);
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), b[++*b] = a[i];
    b[++*b] = -1e9;
    b[++*b] = 1e9;
    for(int i = 1; i < n; ++i){
        int  x = read(), y = read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sort(b+1,b+1+*b);
    *b = unique(b + 1, b + 1 + *b) - b - 1;
    for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + *b, a[i]) - b;
    dfs(1, 0);
    writeln(ans);
    return 0;
}

CF1132G

题意

对于一个数组 $C$ ，他的优秀子序列 $P$ ，满足 $1\leq p_1<p_2<\cdots <p_l\leq |C|$ ,并且对于每一个 $i\in[1,l-1]$ ， $p_{i+1}$ 是最小的整数满足 $p_{i+1}>p_i$ 并且 $c[p_{i+1}]>c[p_i]$ 。
对于每一个子段 $[1,k],[2,k+1],\cdots,[|c|-k+1,|c|]$ ，求出它的最长优秀子序列长度。

题解

对每一个点，向后第一个比它大的点连边，最后形成一个森林（可以建立虚点，向没有后继的点连边，成为树）。以虚点为根，建立线段树。加入一个点，那么他的子树每个点都 $+1$ ，删一个点 $-1$ 。
那么答案就是所有点的最大值了。

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 2e6 + 666;
int n, m;

int a[N];
vector<int> g[N];
int st[N], top;
void build() {
    st[++top] = n + 1;
    a[n + 1] = 1e9;
    for(int i = n; i >= 1; --i) {
        while(top && a[st[top]] <= a[i]) --top;
        g[st[top]].push_back(i);
        st[++top] = i;
    }
}

int L[N], R[N], num;
int tran[N];
void dfs(int x, int F) {
    L[x] = ++num;
    tran[num] = L[x];
    for(int y : g[x]) dfs(y, x);
    R[x] = num;
}
int ls[N << 2], rs[N << 2];
int mx[N << 2], tag[N << 2];
#define lch (o<<1)
#define rch (o<<1|1)
void up(int o) {
    mx[o] = max(mx[lch], mx[rch]);
}
void build(int o, int l, int r) {
    ls[o] = l; rs[o] = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(l <= mid) build(lch, l, mid);
    if(r > mid) build(rch, mid + 1, r);
    up(o);
}
void upd(int o, int v) {
    tag[o] += v;
    mx[o] += v;
}
void down(int o) {
    if(tag[o]) {
        upd(lch, tag[o]);
        upd(rch, tag[o]);
        tag[o] = 0;
    }
}
void ins(int o, int l, int r, int v) {
    if(l <= ls[o] && r >= rs[o]) {
        upd(o, v);
        return;
    }
    int mid = (ls[o] + rs[o]) >> 1;
    down(o);
    if(l <= mid) ins(lch, l, r, v);
    if(r > mid) ins(rch, l, r, v);
    up(o);
}



int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    build();
    dfs(n + 1, 0);
    build(1, 1, n + 1);
    for(int i = 1; i <= n; ++i) {
        if(i <= m) ins(1, L[i], R[i], 1);
        else {
            ins(1, L[i - m], R[i - m], - 1);
            ins(1, L[i], R[i], 1);
        }
        if(i >= m) printf("%d ", mx[1]);
    }
    return 0;
}

CF896B

Description

交互题，有 $n$ 个空格，每次给一个 $[1,c]$ 的数字，回答填入哪一个格子，如果这个格子之前已经填过，那么新数字可以替换这个格子的数。要求在 $m$ 轮内使 $n$ 格填满且数列不递减

Hint

$n,m\ge 2,1\leq c\leq 1000,1\leq n \cdot \lceil\frac{c}{2}\rceil\leq 1000$

Solution

考虑最简单的贪心，对于给出的一个数 $x$ ，每一次从左至右找到第一个严格大于 $x$ 或者空白的格子，填入。那么要填满 $n$ 个格子，至少要 $c\times (n-1)+1$ 次
把颜色分成 $[1,\frac{c}{2}]$ 和 $[\frac{c+1}{2},c]$ 两个部分，对于前者由左至右填入到第一个严格大于 $x$ 的格子或者空白格子；对于后者由右至左填入到一个严格小于 $x$ 的格子或者空白格子。此时需要的最差总轮数为 $(n-1)\cdot \frac{c}{2}+1$

CF15C

Description

有 $n$ 个采石场，每个采石场有 $m_i$ 辆采矿车，对于一个采石场第 $j$ 个采矿车有 $x_i+j-1$ 个石头。两个人进行 $NIM$ 博弈，问先手和后手那个必胜

Hint

$1\leq n\leq 10^5$ ， $1\leq x_i,m_i\leq 10^{16}$

Solution

求 $0\oplus1\oplus2\oplus\cdots\oplus(x-1)\oplus x$

$x\mod{4}\equiv 0$ ， $(0,1),(2,3),\cdots,(x-2,x-1)$ 互相配对，他们的异或和为 $\frac{x}{2}$ (是个偶数)个 $1$ 的异或和，那么答案就是 $x$
$x\mod{4}\equiv 1$ ， $(0,1),(2,3),\cdots,(x-1,x)$ 互相配对，共 $\frac{x+1}{2}$ 个 $1$ ，此时答案为 $1$
$x\mod{4}\equiv 2$ ， $(0,1),(2,3),\cdots,(x-2,x-1)$ 互相配对，共 $\frac{x-1}{2}$ 个 $1$ ，答案是 $x\oplus 1$
$x\mod{4}\equiv 3$ ， $(0,1),(2,3),\cdots,(x-3,x-2),(x-1,x)$ 互相配对，共 $\frac{x+1}{2}$ 个 $1$ ，答案就是 $0$

key

数学

CF135C

Description

给出一个长度为 $n$ 的串，由0，1,?三种字符组成。?可以被替代成0或1。问A和B轮流删除一个字符，A先，删除到最后只剩下两个字符游戏结束，问最后结束时的游戏状态有几种。A要使得最后的结果最小，B要使得最后的结果最大，假设两个人足够聪明。

Hint

$2\leq n\leq 10^5$

Solution

一个显然的贪心：每一次A从左向右删第一个1，B从左向右删第一个0。
考虑没有?的情况。
假设1的个数为 $a$ ，0的个数为 $b$ 。
结果为00当且仅当 $a<b$
结果为11当且仅当 $a>b+1$
当 $a=b$ 或者 $a=b+1$ 的时候，结果为01或者10，取决于最后一个字符为1或者0。
考虑包含了?，假设结果为01,如果最后一个字符是?,那么 $c=c-1$ , $a=a+1$ 。
假设 $c$ 个?中有 $x$ 个变成 $1$
$a+x=b+1+(c-x)+((a+b+c)\mod 2)$
如果 $x\ge 0$ 且 $x\leq c$ 且 $x\mod 2 = 0$ ，那么就是可能的。
10的情况类似。

CF605E

Description

有 $n$ 个点，每个时刻第 $i$ 个点和第 $j$ 个点之间有 $p_{i,j}$ 的概率存在一条边。每个时刻可以沿着一条边走或者留在原地。求从 $1$ 号点走到 $n$ 号点的最优的期望时间。

Hint

$1\leq n\leq 1000$

Solution

$f_i$ 表示从 $i$ 点到 $n$ 点的期望步数。 $f_n=0$ ,考虑类似于 $dijkstra$ ，每次从 $f_n$ 最小的点扩展。
假设 $x$ 是当前第 $f$ 值第 $i$ 小的编号， $A_i$ 表示 $f$ 值为第 $i$ 小的编号
$ $f_x = 1 + \sum_{j=1}^if_{a_j}\times p_{a_j,x}\times \prod_{k=1}^{j-1}(1-p_{A_k,x})$ $解方程一下：$ $f_x=\frac{1+\sum_{j=1}^{i-1}f_{a_j}\times p_{a_j,x}\times \prod_{k=1}^{j-1}(1-p_{A_j,x})}{1-p_{x,x}\times \prod_{k=1}^{i-1}(1-p_{a_k,x})}$ $直接暴力转移更新即可。这份代码是另一份写法，算$ f_x $时把$ 1$放在式子里算，不是单独拿出来。

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 1100;
double p[N][N];
double f[N], g[N], s[N];
bool vis[N];
int n;
void solve() {
    for(int i = 1; i < n; ++i) g[i] = 1, f[i] = 1e99;
    f[0] = 1e99;
    for(int i = 1; i <= n; ++i) {
        int x = 0;
        for(int j = 1; j <= n; ++j)
            if(!vis[j] && f[j] < f[x]) x = j;
        vis[x] = 1;
        for(int j = 1; j <= n; ++j) if(!vis[j] && p[x][j] > 0) {
            s[j] += (f[x] + 1)* p[x][j] * g[j];
            g[j] *= (1 - p[x][j]);
            f[j] = (s[j] + g[j])/ (1 - g[j]);
        }
    }
    printf("%.10lf\n", f[1]);
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            p[j][i] = read() / 100.0;
    solve();
    return 0;
}

BZOJ2698

Description

有 $n$ 个格子，每一次会等概率选取一段长度在 $[S,T]$ 之间的连续段染成白色，染色 $M$ 次，问最后被染成白色的格子个数的期望值。

Hint

$1\leq S\leq T\leq N\leq 1000000,0\leq M\leq 1000000$

Solution

考虑每一个格子对答案的贡献即可。期望的线性性：
所有格子染成白色的期望个数 $=\sum P_j\times 1$
其中 $P_j$ 表示第 $j$ 个格子被染成白色的概率。

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 1200000;
ll n, m, s, t;
double ans = 0;
bool vis[N];
ll f[N], g[N];
int main() {
    n = read(), m = read(), s = read(), t = read();
    for(int i = 1; i <= n; ++i) {
        f[i] = (s + t) * (t - s + 1) / 2;
        g[i] = (n + 1) * (t - s + 1) - (s + t) * (t - s +1) / 2;
    }
    for(ll i = 1; i <= t; ++i) {
        f[i] -= (max(s, i) + t) * (t - max(s, i) + 1) / 2 - min(t - i + 1, t - s + 1) * i;
        f[n - i + 1] -= (max(s, i) + t) * (t - max(s, i) + 1) / 2 - min(t - i + 1, t - s + 1) * i;
    }
    for(int i = 1; i <= n; ++i)
        ans += 1 - pow(1 - 1.0 * f[i] / g[i], m);
    printf("%.3lf\n", ans);
    return 0;
}

BZOJ2698

Description

有一个大小为 $W\times H$ 的方阵，每一次小M会等概率随机选两个格子（可以是同一个），把以这两个格子为对角线的子矩阵染成白色，问 $K$ 轮之后方阵的白色格子的期望个数是多少？

Hint

$1\leq W,H\leq 1000,0\leq K\leq 100$

Solution

同BZOJ2698，大力分类讨论

#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 1100;

ll K, n, m;
int a[N][N], b[N][N];
double ans = 0;
double t;
int main() {
    K = read(), n = read(), m = read();
/*    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j)
            for(int x = 1; x <= n; ++x)
                for(int y = 1; y <= m; ++y)
                    {
                        for(int r = min(i, x); r <= max(i, x);++r)
                            for(int c = min(j, y); c <= max(j, y); ++c)
                                ++b[r][c];
                    }
    }*/
    ll tot = n * m * n * m;
    double res = 0;
    /*for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j)
            printf("%d ", b[i][j]), res += (double) b[i][j] / tot;
        puts("");
    }
    cout<<res<<endl;

    printf("tot=%lld\n", tot);*/
    for(ll i = 1; i <= n; ++i) {
        for(ll j = 1; j <= m; ++j) {
            ll s = i * j * (n - i + 1) * (m - j + 1) * 2;
            s += (n - i + 1) * j * i * (m - j + 1) * 2;
            s -= (i * (n - i + 1) + j * (m - j + 1)) *2 - 1;
    //        printf("(%d,%d) s=%lld, v=%lf\n", i, j, s, (double) s/ tot);
            ans += 1 - pow(1 - (double)s / tot, K);
        }
    } 
    //cout<<ans<<endl;
    printf("%lld\n", (ll)floor(ans + 0.5));
    return 0;
}

「第一弹」Codeforces杂题

Codeforces杂题

CF559D

题意

题解

CF559E

题意

题解

错误解法

正解

CF111D

题意

题解

CF679B

题意

题解

CF360B

题意

题解

CF1108F

题意

题解

CF1132D

题意

题解

CF1132E

题意

题解

CF1099F

题意

题解

CF731E

题意

题解

CF850C

题意

题解

CF965E

题意

题解

CF490F

题意

题解

force

std

CF1132G

题意

题解

CF896B

Description

Hint

Solution

CF15C

Description

Hint

Solution

key

CF135C

Description

Hint

Solution

CF605E

Description

Hint

Solution

BZOJ2698

Description

Hint

Solution

BZOJ2698

Description

Hint

Solution