标签：LD 接力比赛 int read maxn 暑假集训 dp define

暑假集训六

接力比赛

我是真没想到这玩意还能跟背包扯上关系，学到了

但这里写的不是题解的做法，这里写的是类似的一种解法
考虑\(dp\)的定义
\(dp[1 / 0][j]\)表示\(0\)为小白的队伍,\(1\)为小黑的队伍,当\(w\)和为\(j\)的时候，最大的\(v\)是多少
考虑转移,只需要一直维护这最大的\(sum_w\)就可以，相当于是一个大暴力..考虑到所有情况,具体的一看代码其实就可以懂了,
最后答案就是扫一遍\(dp[0][i] + dp[1][i]\)中的最大值，暴力拼凑

here

#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_posair(x, y)
using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;
const int maxn = 1010, maxpf = 1e7 + 10, Mod = 1e9 + 7;
const int Inf = 2147483647;

/*
爱意随风起， 风止意难平
*/
//好像说省选不让用signed，从现在开始改正

/*
虽然不知道这个题是像之前那样排个序就ok的bug题还是
神仙dp，但我还是大暴力
这个题还不能离散化..
想到了一个sb暴力
*/
LL dp[2][maxn * maxn];
int n, m;
struct Player{
    LL w, v;
}bk[maxn], wt[maxn];
#define sort random_shuffle
int main(){
     frein(game);
     freout(game);
    n = read();
    m = read();
    mes(dp, -0x3f);
    dp[0][0] = dp[1][0] = 0;
    fr(i, 1, n){
        wt[i].w = read();
        wt[i].v = read();
    }
    fr(i, 1, m){
        bk[i].w = read();
        bk[i].v = read();
    }
    sort(wt + 1, wt + n + 1);
    sort(bk + 1, bk + m + 1);
    LL Max = 0;
    fr(i, 1, n){
        fp(j, Max, 0){
            if (dp[0][j] >= 0 && dp[0][j + wt[i].w] < dp[0][j] + wt[i].v){
                dp[0][j + wt[i].w] = dp[0][j] + wt[i].v;
                Max = max(Max, j + wt[i].w);
            }
        }
    }
    Max = 0;
    fr(i, 1, m){
        fp(j, Max, 0){
            if (dp[1][j] >= 0 && dp[1][j + bk[i].w] < dp[1][j] + bk[i].v){
                dp[1][j + bk[i].w] = dp[1][j] + bk[i].v;
                Max = max(Max, j + bk[i].w);
            }
        }
    }
    LL ans = 0;
    fp(i, Max, 0){
        ans = max(ans, dp[0][i] + dp[1][i]);
    }
    write(ans);
    return 0;
}
/*
3 4
4 7
3 8
2 2
1 4
5 8
1 3
4 4

1 2
1000 -10000
200 3000
800 5000


*/

挂一个题解的sandom%%%

#define sandom signed
#define fre(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define re register int
using namespace std;
#define int long long 
const int Z = 1e6 + 10;
inline int read() { int x = 0; int f = 0; char c = getchar(); while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }

int n, m, k = 1e9, ans;
int w[Z], v[Z], pre[Z];
int f[Z], g[Z];
inline void calc(int n, int dp[])
{
    for (re i = 1; i <= n; i++)
    {
        w[i] = read(), v[i] = read();
        pre[i] = pre[i - 1] + w[i];
    }
    dp[0] = 0; k = min(k, pre[n]);
    for (re i = 1; i <= n; i++)
        for (re j = pre[i]; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

sandom main()
{
    // fre(test);
    fre(game);
    n = read(), m = read();
    memset(f, -63, sizeof(f)); memset(g, -63, sizeof(g));
    calc(n, f); calc(m, g);
    for (re j = 0; j <= k; j++)
    {
        // printf("%d %d %d\n", j, f[j], g[j]);
        ans = max(ans, f[j] + g[j]);
    }
    cout << ans;
    return 0;
}
/*
IN
3 4 
4 7 
3 8 
2 2 
1 4 
5 8 
1 3 
4 4 
OUT
30
IN
1 2 
1000 -10000
200 3000
800 5000
OUT
0
*/

树上竞技

赛后讨论了大概三个小时，终于把它搞明白了

按照边去考虑，如果在一条边 \(E\) 的两侧分别有 \(i\) 和 \(m-i\) 个关键点，

不妨令 \(i\leqslant m-i\) 那么最后的汇聚点一定在 \(m-i\) 这个方向，

这样可以只让 \(i\) 条边经过 \(E\)，代价较小

然后设某条边两侧分别共有 \(s\) 和 \(n-s\) 个点(这里的\(S\)实际上就是\(size\))，发现我们需要求

\[\large\sum\limits_{i=1}^{m-1}\min\{i,\ m-i\}\times C_{s}^{i}C_{n-s}^{m-i} \]

循环到\(m - 1\)是因为如果到\(m\)那另外一边没有点相当于没有贡献(我统计最小代价的总和，那边没有特殊点，根本没有代价)

发现 \(\min\) 不是很好处理，考虑把它拆开来,还要加上 \(m\) 为偶数的情况,因为如果\(m - 1\)是奇数,那么\(\frac{m - 1}{2}\)向下取整之后就会掠过一个，但我们实际上应该选择到\(\frac{m - 1}{2} + 1\)个
,举例来说\(m - 1 = 7\)则除二后为\(3\)但应该选到\(4\)也就是\(\frac{m}{2}\),所以单独拿出来\(\frac{m}{2}\)的情况(因为\(m - 1\)是奇数,所以\(m\)为偶数)

\(\operatorname{DFS}\) 预处理节点子树大小，原式可以化成

\[ans=\sum\limits_{u=2}^{n}\sum\limits_{i=1}^{\frac{m-1}{2}}i\times C_{size[u]}^{i}C_{n-size[u]}^{m-i}+i\times C_{size[u]}^{m-i}C_{n-size[u]}^{i}+[m\%2==0]\frac{m}{2}\times C_{s}^{\frac{m}{2}}C_{n-s}^{\frac{m}{2}} \]

能把\(min\)拆开是因为\(i\)和\(m - i\)相当于是对半分的

注意此时不能像题解一样乘以二,因为我们此时循环到\(\frac{m - 1}{2}\)中\(i\)是恒小于\(m - i\)的,所以组合数会反过来一部分

后面的一小点式子可以暴力硬扫，考虑前面的怎样优化

不妨设 \(k=\frac{m}{2}\)

我们可以化简上边的柿子

\(\sum\limits_{i=1}^{k}i\times C_{s}^{i}C_{n-s}^{m-i}=s\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}\)(只考虑左边的)

(把 \(C_{s}^{i}\)展开,把\(i\)乘进去再把\(S\)抽出来)

那么右边的同理可得

\(\sum\limits_{i=1}^{k}i\times C_{s}^{m - i}C_{n-s}^{i}=(n - s)\sum\limits_{i=1}^{k}C_{n - s-1}^{i-1}C_{s}^{m-i}\)

(把 \(C_{n - s}^{i}\)展开,把\(i\)乘进去再把\(n - s\)抽出来)

因为两个柿子形式相同,所以我们此时只考虑一边,写成函数形式

不妨令 \(dp(s)=\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}\)，那么答案就是 \(\sum\limits_{u=2}^{n}dp(size[u])+ dp(n-size[u])\)

考虑如何求出 \(dp(s)\)，发现它的组合意义是 \(n-1\) 个物品里选择了 \(m-1\) 个(两个\(C\)的下加下，上加上),同时加了一个限制,前面 \(s-1\) 个物品中选择 \(k-1\) 个的方案数

考虑如何递推 \(dp(s)\) ？

不难发现，\(dp(s)\) 变成 \(dp(s+1)\) 变少的部分就是前 \(s-1\) 个点中选择 \(k-1\) 个，选择了 \(s\) 为第 \(k\) 个点，后面 \(n-s-1\) 个点里选择了 \(m-k-1\) 个点

因为\(dp(s + 1)\)实际上只有两种情况
- 没有选择 \(s\) 作为第 \(k\) 个点
  - 此时前 \(s\) 个点中选择 \(k-1\) 个点和前 \(s-1\) 个点中选择 \(k-1\) 个是等价的,那么方案其实是相通的
- 选择 \(s\) 作为第 \(k\) 个点
  - 如图,那么第\(k\)个点实际上是可以选择在之后的其他位置的,我们的方案数会少，少的是前\(s - 1\)个中选择\(k - 1\)个和之后\(m - k -1\)其他的配对数,也就是\(C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}\)

因为我们的\(s\)是连续的,此时要递推,我们应该固定\(k\)在\(s\)处,否则方案会算重

也就是说 \(dp[s+1]=dp[s]-C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}\)

统计答案即可

here

#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_pair(x, y)
using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;
const int maxn = 2001000, Mod = 1e9 + 7;
const int Inf = 2147483647;
// #define int long long
LL ans;
#define int long long
int n, m;
struct Node{
    int to, next;
}wmx[maxn << 2];
int tim = 0;
int len = 0, head[maxn];
fuc(void, Qian)(int from, int to){
    wmx[++len].to = to;
    wmx[len].next = head[from];
    head[from] = len;
}
fuc(LL, qpow)(LL x, LL y){
    LL res = 1;
    while (y){
        if (y & 1)res = (res * x) % Mod;
        x = (x * x) % Mod;
        y >>= 1;
    }
    return res;
}
LL inv[maxn], fac[maxn];
fuc(void, init)(){
    inv[0] = fac[0] = 1;
    fr(i, 1, maxn - 1){
        fac[i] = fac[i - 1] * i % Mod;
    }
    inv[maxn - 1] = qpow(fac[maxn - 1], Mod - 2);
    fp(i, maxn - 2, 0){
        inv[i] = inv[i + 1] * (i + 1) % Mod;
    }
}
int sz[maxn];

fuc(void, dfs)(int x, int pre){
    sz[x] = 1;
    for (Re i = head[x]; i; i = wmx[i].next){
        int to = wmx[i].to;
        if (to == pre)continue;
        dfs(to, x);
        sz[x] += sz[to];
    }
}
fuc(int, C)(int n, int m){ return fac[n] * inv[m] % Mod * inv[n - m] % Mod; }

int dp[maxn];

signed main(){
    frein(meeting);
    freout(meeting);
    n = read(), m = read();
    fr(i, 1, n - 1){
        int x = read();
        Qian(i + 1, x);
        Qian(x, i + 1);
    }
    init();
    // fr(i, 1, 5){
    //     printf("fac[%d] = %d inv[%d] = %d\n", i, fac[i], i, inv[i]);
    // }
    dfs(1, 0);
    if (!(m & 1)){//sb位运算，以后都加括号，不加括号我是狗，汪汪
        fr(i, 2, n){
            ans = (ans + C(sz[i], m / 2) * C(n - sz[i], m / 2) % Mod * (m / 2) % Mod) % Mod;
        }
    }
    int tmp = (m - 1) / 2;
    if (tmp) dp[1] = C(n - 1, m - 1);
    fr(i, 1, n - 1)dp[i + 1] = (dp[i] - C(i - 1, tmp - 1) * C(n - i - 1, m - tmp - 1) % Mod + Mod) % Mod;
    fr(i, 1, n) dp[i] = dp[i] * i % Mod;
    fr(i, 2, n) ans = (ans + dp[sz[i]] + dp[n - sz[i]]) % Mod;
    write(ans % Mod);
    return 0;
}

虚构推理

赛时以为是一个打磨你...然后码了\(200\)行左右,我是\(sb\)

首先注意本题是\(24\)制,所以我们统计度数的时候应该注意
另外,本题模拟的是真实的时钟,所以秒针转的时候分针也在转，分针转的时候,时针也在转
因为本题考虑最大夹角,所以那\(n\)个时刻的时针和分针的对应其实就没有意义了，我们可以求出度数来\(sort\)一下,考虑对于一个答案，与他夹角最大的时刻一定在它旋转\(180^{。}\)后的左右,所以我们就可以\(lower_bound\)一下了,然后,,,就没有然后了

here

#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_posair(x, y)
using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;
const int maxn = 50010, Mod = 1e9 + 7;
const int Inf = 2147483647;

/*
莫名想起真的虚构推理
女主还是很可的
男主姐姐也帅的一批
经典名梗《* * 之痛》
*/
int n;
const LD eps = 1e-7;

LD ans = 361.0;
LD hour[maxn], miu[maxn];
fuc(LD, aabs)(LD x){ return (0 - x > eps) ? -x : x; }
fuc(LD, maxx)(LD x, LD y){ return (x - y) > eps ? x : y; }
fuc(LD, minn)(LD x, LD y){ return (x - y > eps) ? y : x; }
fuc(LD, Min)(LD x, LD y){ return minn(aabs(x - y), 360 - aabs(x - y)); }
fuc(void, now)(int hr, int m, LD sec, LD& hour, LD& minute){//求出角
    hour = 30.0 * hr + 0.5 * m + 0.5 * sec / 60.0;
    minute = 6.0 * m + 0.1 * sec;
}
fuc(LD, work)(LD res, LD type []){
    int x, y;
    if (180.0 - res > eps)x = lower_bound(type + 1, type + 1 + n, res + 180.0) - type, y = x - 1;
    else x = lower_bound(type + 1, type + 1 + n, res - 180.0) - type, y = x - 1;
    if (x == n + 1)x = 1;
    if (y == 0) y = n;
    return maxx(Min(type[y], res), Min(type[x], res));
}

int main(){
    frein(unreal);
    freout(unreal);
    n = read();
    fr(i, 1, n){
        int hr = read(), mi = read(), sec = read();
        if (hr >= 12)hr -= 12;
        now(hr, mi, sec, hour[i], miu[i]);
    }
    sort(hour + 1, hour + n + 1);
    sort(miu + 1, miu + n + 1);
    fr(hr, 0, 11){
        fr(m, 0, 59){
            for (LD sec = 0; sec < 60; sec += 0.1){
                LD nowhr, nowmiu;
                now(hr, m, sec, nowhr, nowmiu);
                ans = minn(ans, maxx(work(nowhr, hour), work(nowmiu, miu)));
            }
        }
    }
    printf("%.8lf", ans);
    return 0;
}
/*

2
12:30:00
02:40:00
*/

记忆碎片

还不会,先咕掉

标签：LD,接力比赛,int,read,maxn,暑假,集训,dp,define
From： https://www.cnblogs.com/kiritokazuto/p/16600319.html

暑假集训六[接力比赛,树上竞技,虚构推理,记忆碎片]

暑假集训六

接力比赛

我是真没想到这玩意还能跟背包扯上关系，学到了

树上竞技

赛后讨论了大概三个小时，终于把它搞明白了

虚构推理

赛时以为是一个打磨你...然后码了\(200\)行左右,我是\(sb\)

记忆碎片

还不会,先咕掉

相关文章

赞助商

阅读排行