首页 > 其他分享 >08-08 题解

08-08 题解

时间：2024-08-10 10:27:14浏览次数：21  
标签：const int 题解 08 long MOD dp define

08-08 题解

地址

A - CF1420E

luogu 翻译更正

if he gives no more that k orders

对于至多 k 次操作, 题面没有翻译出来

思路

怎么算贡献？

贡献 （被保护）出现在 「处在任意两个不同的 0 的连续段的守卫」之间，而处于同一连续段的守卫之间没有贡献

设一共 \(cnt\) 个 \(0\)， 每个连续段分别有 \(c_i\) 个 \(0\)

则 \(contribute = C_{cnt}^{2} - \sum_{i} C_{c_i}^{2}\)

考虑 DP

设 \(dp(i, j, k, l)\) 为考虑到第 \(i\) 个人， 前面一共进行了 \(j\) 步操作， 用了 \(k\) 个 \(1\) ， 当前连续段有 \(l\) 个 \(0\)

但是这样的空间复杂度是 \(O(n^5)\)， 铁定过不了

尝试优化掉一维状态

最后一维是最好优化的， 我们只需要把状态的含义改为 「考虑到第 \(i\) 个人， 他选了 \(1\)」， 这样只需要枚举一个 \(ii\ > i\) ， 表示下一个选 \(1\) 的位置是 \(ii\) ， 转移即可。

而原来的 \(l\) 一维就等于 \(ii - i - 1\)

所以 \(dp(i, j, k) = min\{dp(ii < i\ , jj <= j\ , k - 1)\}\)

注意， 输出答案时要取前缀 \(min\)， 原因见文首 「翻译勘误」

代码

\(O(n^5)\) 加一些剪枝， 跑的飞快

#include<bits/stdc++.h>
using namespace std;
const int N = 81, INF = 1e9;

int n;
int a[N], ps[N], cnt, cntzr;
int dp[N][N * N][N], ans[N * N];

int Calc(int x){
    return x * (x - 1) / 2;
}

signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] == 1) ps[++cnt] = i;
        else ++cntzr;
    }

    int up = Calc(n);
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= up; j++){
            for(int k = 0; k <= n; k++){
                dp[i][j][k] = INF;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        dp[i][abs(ps[1] - i)][1] = Calc(i - 1);
        for(int j = 0; j <= up; j++){
            for(int k = 1; k <= i && k < cnt; k++){
                if(dp[i][j][k] == INF) continue;
                int rem = cnt - k;
                for(int ii = i + 1; ii <= n - rem + 1; ii++){
                    int jj = j + abs(ps[k + 1] - ii);
                    if(jj <= up){
                        dp[ii][jj][k + 1] = min(dp[ii][jj][k + 1], dp[i][j][k] + Calc(ii - i - 1));
                    }
                }
            }
        }
    }

    for(int i = 0; i <= up; i++){
        ans[i] = Calc(cntzr);
    }
    for(int j = 0; j <= up; j++){
        if(j) ans[j] = ans[j - 1];
        for(int i = cnt; i <= n; i++){
            if(dp[i][j][cnt] == INF) continue;
            ans[j] = min(ans[j], dp[i][j][cnt] + Calc(n - i));
        }
    }
    for(int i = 0; i <= up; i++){
        ans[i] = Calc(cntzr) - ans[i];
        cout << ans[i] << " ";
    }
    cout << "\n";
}

B - AGC017D

吐槽 MX 给的题面有误

思路

首先， 父节点的每个子树都可以看成一个独立的游戏， 拆开， 发现形如 Nim 游戏

递归地拆开后， 发现只需要处理父节点只有一个儿子的情况

但是这个游戏比较特殊， 如果当前节点非根， 我们可以一步直接断掉他和根的连边， 结束这颗子树中的游戏

这一点在博弈状态的 DAG 上表示为： 每个非根节点都指向 (SG = 0)

因为 SG(i) 表示 \(i\) 的子游戏的 MEX， 而 \(i\) 直接指向 \(0\) ， 所以实际的 SG = SG(i) + 1（\(i\) 非根的情况下）

代码

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 1e6 + 10, MOD = 20, INF = 1e18;

int n;
int u, v, sg[N];
vector <int> e[N];

void Dfs(int x, int y){
    for(auto i : e[x]){
        if(i == y) continue;
        Dfs(i, x);
        sg[x] ^= (sg[i] + 1);
    }
}

signed main(){
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    Dfs(1, 0);
    if(sg[1]){
        cout << "Alice\n";
    }else{
        cout << "Bob\n";
    }
}

C - AGC052B

经典套路： 把边权转移到点权上

思路

设点权设为从根到他的路径权值的抑或和

这样你就发现了一些神奇的东西： 对于一条边 \((u, v) dep_u < dep_v\)， 操作这条边相当于交换 \(u, v\) 点权， 其他点都不变

但是有特殊情况：根节点没有连向父亲的边， 不妨假想一条

因为题目中的操作不会改变点权集合， 所以如果 \(w_2\) 中的那条虚拟边和 \(w_1\) 中的一样都是 \(0\) 的话， 两个集合应该相等

将 \(w_1, w_2\) 的所有点权抑或起来就是 \(w_2\) 中虚拟边的边权， 将 \(w_2\) 中所有点权与他抑或后比较两个集合是否相等即可

代码

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 1e7 + 10, MOD = 998244353;
const int Inv2 = (MOD + 1) / 2;

int n;
int u, v, wa, wb;
int a[N], b[N];

struct Edge{
    int v, wa, wb;
};
vector <Edge> e[N];

void Dfs(int x, int y, int va, int vb){
    a[x] = va, b[x] = vb;
    for(auto i : e[x]){
        if(i.v == y) continue;
        Dfs(i.v, x, va ^ i.wa, vb ^ i.wb);
    }
}

signed main(){
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> u >> v >> wa >> wb;
        e[u].push_back({v, wa, wb});
        e[v].push_back({u, wa, wb});
    }

    Dfs(1, 0, 0, 0);

    int xr = 0;
    for(int i = 1; i <= n; i++){
        xr ^= (a[i] ^ b[i]);
    }
    for(int i = 1; i <= n; i++){
        b[i] ^= xr;
    }

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        if(a[i] != b[i]){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}

D - CF1710E

二分图博弈， 鸽

E - AGC040C

经典套路：黑白染色

思路

假设我们已经有了一个串， 将他的奇数位染成黑色， 偶数位染成白色

对于 \(AB, BA\) 他们一定是黑白各占一个的

不妨把黑色位置的 \(A, B\) 都改成 \(A\) ， 白色的都改成 \(B\) ， 那么原题中的限制就变成了 「不能删除连续的 \(AA, BB\)」

那么只有当 \(A\) 或 \(B\) 的数量超过一半时才没法变成空串

方案数用组合数算一下就行

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 1e7 + 10, MOD = 998244353;
const int Inv2 = (MOD + 1) / 2;

int n;
int tot;

int fac[N], inv[N];

void Init(){
    int up = 1e7;

    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= up; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    for(int i = 2; i <= up; i++){
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
}

int C(int n, int m){
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int Q_pow(int a, int b){
    int ans = 1, p = a;
    while(b){
        if(b & 1) ans = (ans * p) % MOD;
        b >>= 1;
        p = (p * p) % MOD;
    }
    return ans;
}

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> n;
    Init();
    tot = Q_pow(3, n);
    // cout << tot << "tot\n";

    int st = (n + 1) / 2 + 1;
    // cout << st << "st\n";
    for(int i = st; i <= n; i++){
        int num = C(n, i) * Q_pow(2, n - i) % MOD * 2 % MOD;
        // cout << num << " ";
        tot = (tot - num + MOD) % MOD;
    }
    cout << tot << "\n";
}

F - CF1642F

根号分治， 随机化都行（题解区还有刚上新的同学的做法）

随机化正确率的计算

如果模数是 20， 那么不冲突的概率为 $\frac{C_{15}{5}}{C_{20}{5}} \approx 0.19369195046439628483 $

那么我们做 20 次， 正确率就是 \(1 - (1 - 0.19369195046439628483) ^ {20} \approx 0.98650975275351626002\)， 非常的高啊

代码

#include<bits/stdc++.h>
#define int long long
#define Pii pair <int, int>
using namespace std;
const int N = 1e6 + 10, MOD = 20, INF = 1e18;

int n, m, ans;
int a[N][7], w[N], num[N];
int dp[1 << 21], id[N];

int cnt;
unordered_map <int, int> rid;

void Calc(){
    random_shuffle(id + 1, id + 1 + cnt);

    int upp = (1 << 21) - 1;
    for(int i = 0; i <= upp; i++){
        dp[i] = INF;
    }
    for(int i = 1; i <= n; i++){
        num[i] = 0;
        for(int j = 1; j <= m; j++){
            a[i][j] = id[a[i][j]];
            num[i] |= (1 << (a[i][j] % MOD));
        }
        dp[num[i]] = min(dp[num[i]], w[i]);
    }
    for(int i = 0; i <= 20; i++){
        for(int j = 0; j <= upp; j++){
            if((j >> i) & 1){
                dp[j] = min(dp[j], dp[j ^ (1 << i)]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        ans = min(ans, w[i] + dp[upp ^ num[i]]);
    }
}

signed main(){
    srand(1ll * time(0) * time(0) % 998244353);

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if(!rid[a[i][j]]) rid[a[i][j]] = ++cnt;
            a[i][j] = rid[a[i][j]];
        }
        cin >> w[i];
    }

    for(int i = 1; i <= cnt; i++){
        id[i] = i;
    }

    ans = INF;
    for(int i = 1; i <= 20; i++){
        Calc();
    }

    if(ans == INF){
        ans = -1;
    }
    cout << ans << "\n";
}

标签：const,int,题解,08,long,MOD,dp,define
From： https://www.cnblogs.com/Bubblee/p/18352017

相关文章

  • 提高组：玩具谜题 题解
    题目描述小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：这时singer告诉小南一个谜题：“眼镜藏在我左数第 33 个玩具小人的右数第 11 个玩具小人的左数第......
  • 08-09 题解
    08-09题解A小水题思路假设我们选定了当前子序列的绝对众数\(x\)，那么该序列里最多再放\(num_x-1\)个其他数字为了分出最少的子序列，肯定要让每个子序列在拥有绝对众数的同时能消化尽量多的其他数字由此，可以得到一个贪心策略：每次取出出现次数最多的一个数字，消掉出现......
  • P1725 琪露诺 题解
    思路动态规划，单调队列动态规划观察题目，发现下标为\(i\)的点只能对\([i+l,i+r]\)区间的点产生贡献。设\(f_i\)为到达点\(i\)时的最大冻结指数。易得状态转移方程式：\(f_k\leftarrow\max(f_k,f_i+a_k),(k\in[i+l,i+r])\)。若直接对该方程进行转移，时间复......
  • AT_abc208_d 题解
    题目传送门做完这道题后感觉对Floyd的理解更深了。根据题面要求，设\(f(k,i,j)\)表示从\(i\)到\(j\)的所有只经过\(1\simk\)的点的所有路径的最短距离。很明显\(k\)那一维是阶段，因为它描述了从\(i\)到\(j\)路径中的不同点，而我们就是根据这一条件来划分集合，这......
  • CF908D New Year and Arbitrary Arrangement 题解
    Description给定\(k,pa,pb\)，有一初始为空的序列。每次有\(\dfrac{pa}{pa+pb}\)的概率往序列后面加一个a。每次有\(\dfrac{pb}{pa+pb}\)的概率往序列后面加一个b。当出现大于等于\(k\)个形如ab的子序列（a和b不一定相邻）时停止。求序列最终的ab子序列期望数。So......
  • 【保奖思路】2024年华为杯研究生数学建模D题解题思路分享（点个关注，后续会更新
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的卡片链接，那是获取资料的入口！点击链接加入群聊【2024华为杯研赛资料汇】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=MwNruKbEvR9aZns1l7xXBWmQQKYAEh-F&authKey=igaBN79pz6BhNlDQ6TIZ5YFAbn71aDcYL77uANPquLF%2FTVgeSAhE......
  • 【保奖思路】2024年华为杯研究生数学建模D题解题思路分享（点个关注，后续会更新
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的卡片链接，那是获取资料的入口！点击链接加入群聊【2024华为杯研赛资料汇】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=MwNruKbEvR9aZns1l7xXBWmQQKYAEh-F&authKey=igaBN79pz6BhNlDQ6TIZ5YFAbn71aDcYL77uANPquLF%2FTVgeSAhE......
  • CF1984G Magic Trick II 题解
    前记第一篇黑题题解。难调。好写。码量不大。Description给定一个大小为nnn的排列pp......
  • AGC001 题解
    目录A-BBQEasyB-MysteriousLightC-ShortenDiameterA-BBQEasy先将\(2N\)个数排序，从大到小考虑，最大的数一定不会产生贡献，次大的数可以和最大的数捆绑在一起，并产生贡献，以此类推，这样的贪心正确性还是较为显然的。#include<bits/stdc++.h>#definelllonglongusin......
  • CF1999F.Expected Median 题解
    一.前言这是一道很有趣的数学题目，用到了逆元和组合数学，非常适合新手练手。二.题目大意：给出一个长度为\(n\)的\(01\)数组。找出所有长度为\(k\)的子序列的中位数，求出其和。妥妥的数学题~三.分析首先考虑对答案的贡献。很明显，只有\(1\)作为中位数时才会做出贡献，于是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99