首页 > 其他分享 >Atcoder Educational DP Contest 部分做题记录

Atcoder Educational DP Contest 部分做题记录

时间：2022-10-17 17:34:23浏览次数：44  
标签：Atcoder Educational Contest int ll long solve using dp

G.Longest Path

拓扑排序dp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dp[100010], d[100010];
void solve() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> g[n + 1];
    for (int i = 1;i <= m;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        d[b] ++;
    }
    queue<int> q;
    for (int i = 1;i <= n;i++) if (!d[i]) q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto y : g[x]) {
            if (dp[x] + 1 > dp[y]) {
                
                dp[y] = dp[x] + 1;
            }
            d[y] --;
            if (!d[y]) q.push(y);
        }
    }
    printf("%d\n", *max_element(dp + 1, dp + n + 1));
}
 
int main() {
    solve();
    return 0;
}

I.Coins

\(dp_{i,j}\)表示，当前枚举到第\(i\)个硬笔，有\(j\)个硬币正面向上的概率。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;
long double dp[3010][3010];
 
void solve() {
    int n; cin >> n;
    vector<long double> p(n + 1);
    for (int i = 1;i <= n;i++) cin >> p[i];
    dp[1][0] = 1.0 - p[1];
    dp[1][1] = p[1];
    for (int i = 2;i <= n;i++) {
        for (int j = 0;j <= i;j++) {
            dp[i][j] = dp[i - 1][j] * (1.0 - p[i]);
            if (j > 0) dp[i][j] += dp[i - 1][j - 1] * p[i];
        }
    }
    long double ans = 0;
    for (int i = n / 2 + 1;i <= n;i++) ans += dp[n][i];
    cout << fixed << setprecision(10) << ans << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

K.Stones

博弈论中，如果一个状态能够转移到必败态，则该状态为必胜态。
预处理出所有的必败态，由必败态进行状态转移。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int dp[100010], vis[100010];
int a[110];
void solve() {
    int n, k; cin >> n >> k;
    set<int> s;
    for (int i = 0;i < n;i++) {
        int x; cin >> x;
        s.insert(x);
        dp[x] = 1;
        vis[x] = 1;
        a[i] = x;
    }
    for (int i = 0;i < *s.begin();i++) dp[i] = 0, vis[i] = 1;
    for (int i = 0;i <= k;i++) {
        if (vis[i]) continue;
        vis[i] = 1;
        for (auto v : s) {
            if (i - v >= 0) {
                dp[i] |= (dp[i - v] == 0 ? 1 : 0);
            }
            else break;
        }
    }
    cout << (dp[k] == 1 ? "First\n" : "Second\n");
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

L.Deque

两个人都想要自己的得分最大化。
记\(dp_{l,r}\)为在\(l-r\)这一段进行游戏的最终\(x-y\)的大小。
那么我们可以类似搜索，用区间\(dp\)求解。

#include <bits/stdc++.h>
#define pb push_back
#define endl '\n'
using namespace std;
using ll = long long;

ll dp[3010][3010];
void solve() {
    int n; cin >> n;
    vector<ll> a(n + 1);
    memset(dp, -0x3f, sizeof dp);
    for (int i = 1; i <= n;i++) {
        cin >> a[i];
        dp[i][i] = a[i];
    }
    for (int len = 2;len <= n;len ++) {
        for (int l = 1;l <= n;l ++) {
            int r = l + len - 1;
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
        }
    }

    cout << dp[1][n] << endl;

}
signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr) -> ios::sync_with_stdio(false);
    solve(); 
    return 0;
}

M.Candies

记\(dp_{i,j}\)表示到第i个人，分j份糖果的方案数。
但是我们需要用前缀和优化转移方程。

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;

ll dp[110][100010], pre[110][100010];
void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    ll sum = 0;
    for (int i = 1;i <= n;i++ ) {
        cin >> a[i];
        sum += 1ll * a[i];
    }
    if (sum < k && k != 0) {
        cout << 0 << endl;
        return;
    }

    for (int i = 0;i <= k;i++) pre[0][i] = 1;
    for (int i = 1;i <= n;i++) pre[i][0] = 1;

    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= k;j++) {
            int r = min(j, a[i]);
            dp[i][j] = pre[i - 1][j];
            if (j - r - 1 >= 0) dp[i][j] = (dp[i][j] - pre[i - 1][j - r - 1] + mod) % mod;
        }

        for (int j = 1;j <= k;j++) pre[i][j] = (dp[i][j] + pre[i][j - 1]) % mod;
    }
    cout << (dp[n][k] + mod) % mod << endl;
}
signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr) -> ios::sync_with_stdio(false);
    solve(); 
    return 0;
}

M.Matching

状态压缩dp

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;

int dp[23][1 << 23];
void solve() {
    int n; cin >> n;
    vector<int> have(n + 1);
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < n;j++) {
            int x; cin >> x;
            if (x == 1)  have[i] |= (1 << j);
        }
    }    
    dp[0][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < (1 << n);j++) {
            if (__builtin_popcount(j) == i - 1) {
                for (int k = 0;k < n;k++) {
                    if ((have[i] >> k & 1) and (j >> k & 1) == 0) {
                        dp[i][j | (1 << k)] = (dp[i][j | (1 << k)] + dp[i - 1][j]) % mod;
                    }
                }
            }
        }
    }

    cout << dp[n][(1 << n) - 1] << '\n';
}

signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr)->ios::sync_with_stdio(false);
    solve(); 
    return 0;
}

P.Independent Set

类似没有上司的舞会，树形dp。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;

ll dp[100010][2];
void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1;i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    auto dfs = [&](auto self, auto &g, auto x, auto fa)->void {
        dp[x][0] = dp[x][1] = 1;
        for (auto y : g[x]) {
            if (y == fa) continue;
            self(self, g, y, x);
            dp[x][0] = dp[x][0] * (dp[y][0] + dp[y][1]) % mod;
            dp[x][1] = dp[x][1] * dp[y][0] % mod;  
        }
        return;
    };
    dfs(dfs, g, 1, -1);
    cout << (dp[1][0] + dp[1][1]) % mod << endl;
}

signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr)->ios::sync_with_stdio(false);
    solve(); 
    return 0;
}

Q.Flowers

树状数组优化状态转移。
由于我们的dp值大小只会增大，所以可以用树状数组维护前缀最大值。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;
constexpr int N = 200010;
int n;
ll dp[200010], c[N];
void add(int x, ll d) {
    while ( x <= n) {
        c[x] = max(c[x], d);
        x += x & -x;
    }
}
ll query(int x) {
    ll res = 0;
    while (x > 0) {
        res = max(res, c[x]);
        x -= x & -x;
    }
    return res;
}
void solve() {
    cin >> n;
    vector<int> a(n + 1), h(n + 1);
    for (int i = 1;i <= n;i++) cin >> h[i];
    for (int i = 1;i <= n;i++) cin >> a[i];

    for (int i = 1;i <= n;i++) {
        ll res = query(h[i] - 1);
        dp[i] = max(dp[i], res + a[i]);
        add(h[i], dp[i]);
    }
    cout << *max_element(dp + 1, dp + n + 1) << endl;
    
}

signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr)->ios::sync_with_stdio(false);
    solve(); 
    return 0;
}

标签：Atcoder,Educational,Contest,int,ll,long,solve,using,dp
From： https://www.cnblogs.com/coldarra/p/16799974.html

相关文章

  • 2019-2020 ACM-ICPC Latin American Regional Programming Contest F
    https://codeforces.com/gym/102428首先，令\(dp[i][j]\)表示最下层的有\(i\)块，包括最下层总共还有\(j\)块的方案数容易想到状态方程：$dp[i][j]=\sum_{k=1}^i......
  • [题解] Atcoder Regular Contest ARC 151 A B C D E 题解
    点我看题昨天刚打的ARC，题目质量还是不错的。A-EqualHammingDistances对于一个位置i，如果\(S_i=T_i\)，那么不管\(U\)的这个位置填什么，对到\(S\)和\(T\)的海明距离增量......
  • 【2022 CCPC Henan Provincial Collegiate Programming Contest #K】复合函数
    题目链接K.复合函数输入文件：standardinput输出文件：standardoutput时间限制：1second空间限制：512megabytes给定正整数\(n\)，并记\(I_n={1,2,\cdots,n}\)。给定......
  • AtCoder Beginner Contest 273 题解
    第一次AtCoder体验，不是很好。ARecursiveFunction原题链接大水题。只要会递归就会做。点击查看代码#include<cstdio>#include<iostream>#definelllonglong......
  • [Editorial] Codeforces Contest 878D
    中文题面好题，写篇题解记录一下。首先如果值域是\(\{0,1\}\)，那么直接搞一个bitset维护一下。由于只有\(2^k\)中不同的初始取值，所以维护\(2^k\)长度即可。然后考虑值......
  • Educational Codeforces Round 117 D
    D.X-MagicPair显然对于两个操作可以一眼识别是辗转相减可是我们怎么利用这个信息我们可以发现如果a>b;我们将更小的b替换成|a-b|那么我们显然又转回来了我们考虑......
  • AtCoder Regular Contest 150 B Make Divisible 贪心 整除分块
    给出一个A和B想要找到一个X和Y使得\(A+X|B+Y\).同时使得X+Y最小求出X+Y的最小值。值域是\([1,10^9]\)直接枚举X不太行会被某种数据卡掉。考虑正解：先固定K另\(\frac{B......
  • Educational Codeforces Round 127 D
    D.InsertaProgression显然我们可以对a1——a2之间的数全部都插入期间显然是没有贡献的并且我们我们的1-x只用维护最小1和最大x即可显然要是我们要是mn中没有1......
  • AtCoder Beginner Contest 272 G - Yet Another mod M // 随机化
    题目来源：AtCoderBeginnerContest272G-YetAnothermodM题目链接：ABC272G-YetAnothermodM题意给定一个大小为\(N\)，元素各不相同的数组\(A\)。求一个数字\(......
  • [Leetcode Weekly Contest]314
    链接：LeetCode[Leetcode]2432.处理用时最长的那个任务的员工共有n位员工，每位员工都有一个从0到n-1的唯一id。给你一个二维整数数组logs，其中logs[i]=[idi......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99