ARC 096 Sol.

ARC 096 Sol.

C & D

两道 sb 题。1A 都嫌慢。

那我打 ABC 岂不是可以 AK.

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
    int a, b, c, x, y; read(a, b, c); read(x, y);
    if(a + b <= 2 * c)
    {
        printf("%d\n", a * x + b * y);
        return 0;
    }
    if(x > y) swap(a, b), swap(x, y);
    int ret = x * 2 * c; y -= x;
    ret += min(y * b, y * 2 * c);
    printf("%d\n", ret);
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const long long maxn = 1e5 + 5, maxc = 1e14 + 5;
long long sum[maxn], sum2[maxn], x[maxn], v[maxn], opt[maxn], opt2[maxn];
int main()
{
    int n; long long c; read(n, c);
    for(int i = 1; i <= n; ++i)
        read(x[i], v[i]);
    long long ret = 0, pos = 0, ret2 = 0, pos2 = 0;
    for(int i = 1; i <= n; ++i) 
    {
        sum[i] += sum[i - 1] - x[i] + x[i - 1] + v[i];
        opt[i] = opt[i - 1];
        if(sum[i] > opt[i]) opt[i] = sum[i], pos = i;
    }
    x[n + 1] = c;
    for(int i = n; i; --i) 
    {
        sum2[i] += sum2[i + 1] - x[i + 1] + x[i] + v[i];
        opt2[i] = opt2[i + 1];
        if(sum2[i] > opt2[i]) opt2[i] = sum2[i], pos2 = i;
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        ans = max(ans, max(sum[i], sum[i] - x[i] + opt2[i + 1]));
    }
    for(int i = n; i; --i)
    {
        ans = max(ans, max(sum2[i], sum2[i] - (c - x[i]) + opt[i - 1]));
    }
    printf("%lld\n", ans);
    return 0;
}

E

给 $ n\le5000 $ 个属性。要求选出一些集合,使得每个属性在所有集合出现两次以上。不能有两个集合属性完全一样。统计合法集合族的个数。

Sol.

考虑容斥。由对称性和二项式反演的知识有
$$
A=\sum_{i=0}^n (-1)^i{n\choose i}f_i
$$
其中 $ f_i $ 表示 $ 1..i $ 每个属性至多只出现一次其余不管的方案数,那么 $ A $ 为全不满足这些限制的方案数。显然这就是所求答案。

考虑计算 $ f_i $ . 我们设辅助 $ g_{i,j} $ 表示 $ 1..i $ 每个属性恰好作用在 $ j $ 个集合之上(即这些集合没有空集),那么 $ f_i=2^{2^{n-i}}\sum_{j=0}^i g_{i,j}2^{(n-i)j} $ . 前面表示后面 $ n-i $ 种属性全不考虑的总数,后面表示当前考虑的这些属性的集合是不是还有其他属性存在。可以证明这样就是完备划分的:既不遗漏,又不重复。

计算 $ g_{i,j} $ 十分容易,由定义即有 $ g_{0,0}=1,g_{i,j}=g_{i-1,j-1}+(j+1)g_{i-1,j} $ .

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5e3 + 5;
int C[maxn][maxn], f[maxn][maxn];
int power(int a, int b, int p){int r = 1;for(; b;b >>= 1, a = 1ll * a * a % p)if(b & 1)r = 1ll * r * a % p; return r;}
int main()
{
    int n, m; read(n, m);
    C[0][0] = 1;
    for(int i = 1; i <= n; C[i][0] = 1, ++i) for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;
    f[0][0] = 1;
    for(int i = 1; i <= n; f[i][0] = 1, ++i) for(int j = 1; j <= i; ++j)
        f[i][j] = (f[i - 1][j - 1] + 1ll * f[i - 1][j] * (j + 1) % m) % m;
    int sum = 0;
    for(int i = 0, q = 1; i <= n; ++i, q = m - q)
    {
        int ret = 0, p = power(2, n - i, m);
        for(int j = 0; j <= i; ++j)
            (ret += 1ll * f[i][j] * power(p, j, m) % m) %= m;
        ret = 1ll * ret * power(2, power(2, n - i, m - 1), m) % m;
        ret = 1ll * ret * C[n][i] % m;
        ret = 1ll * ret * q % m;
        (sum += ret) %= m;
    }
    printf("%d\n", sum);
    return 0;
}

F

神仙题。不是很会会。待填。

标签: none

已有 2 条评论

  1. WenDavid WenDavid

    前排差评这个blog的名字
    AGC有#96的嘛?才22次吧……
    应该是ARC#96差不多……

    1. DEL DEL

      typo, sorry... now fixed

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu