1. Toy模板网首页
  2. > Toy博客

AtCoder Beginner Contest 317(D-G)

7月前 作者：scanner___yw 分类：Toy博客 阅读(20) 违法举报

这篇具有很好参考价值的文章主要介绍了AtCoder Beginner Contest 317(D-G)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

D - President (atcoder.jp)

        （1）题目大意

AtCoder Beginner Contest 317(D-G),Atcoder,图论,背包类Dp,算法,动态规划,c++

         （2）解题思路

                考虑到z最大不超过1e5，N最多不超过100，因此可以考虑用背包来写，dp[j]表示拿高桥拿j分最少需要花费多少个选民转换，最后把答案取个min即可。

         （3）代码实现

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
PII lose[N];
int cnt = 0;
ll dp[N];
const ll inf = 0x3f3f3f3f3f3f3f3f;
void solve()
{
    int n;
    cin >> n;
    int win = 0,tot = 0;
    for(int i = 1;i <= n;i ++) {
        int x,y,w;
        cin >> x >> y >> w;
        tot += w;
        if(x > y) win += w;
        else lose[++ cnt] = {(x + y + 1) / 2 - x,w};
    }
    if(2 * win > tot) {
        cout << 0 << endl;
        return;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i = 1;i <= cnt;i ++) {
        for(int j = tot;j >= lose[i].se;j --) {
            if(dp[j - lose[i].se] != inf) dp[j] = min(dp[j],dp[j - lose[i].se] + lose[i].fi);
        }
    }
    int has = (tot + 1) / 2 - win;
    ll ok = inf;
    for(int i = has;i <= tot;i ++) {
        ok = min(ok,dp[i]);
    }
    cout << ok << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}

E - Avoid Eye Contact (atcoder.jp)

        （1）题目大意AtCoder Beginner Contest 317(D-G),Atcoder,图论,背包类Dp,算法,动态规划,c++

         （2）解题思路

                考虑预处理出所有障碍物点，或者能被看到得点，跑一遍bfs即可。

         （3）代码实现

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e3 + 10;
int L[N][N],R[N][N],U[N][N],D[N][N];
bool obs[N][N];
int dis[N][N];
string s[N];
const int inf = 0x3f3f3f3f;
int mx[4] = {1,-1,0,0};
int my[4] = {0,0,1,-1};
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for(int i = 1;i <= n;i ++) {
        for(int j = 1;j <= m;j ++) {
            if(s[i][j] == '>') {
                R[i][j] = true;
            }
            else if(s[i][j] == '.') R[i][j] |= R[i][j - 1];
        }
        for(int j = m;j >= 1;j --) {
            if(s[i][j] == '<') {
                L[i][j] = true;
            }
            else if(s[i][j] == '.') L[i][j] |= L[i][j + 1];
        }
    }
    for(int i = 1;i <= n;i ++) {
        for(int j = 1;j <= m;j ++) {
            if(obs[i][j]) cout << i << ' ' << j << endl;
        }
    }
    for(int i = 1;i <= m;i ++) {
        for(int j = 1;j <= n;j ++) {
            if(s[j][i] == 'v') {
                D[j][i] = true;
            }
            else if(s[j][i] == '.') D[j][i] |= D[j - 1][i];
        }
        for(int j = n;j >= 1;j --) {
            if(s[j][i] == '^') {
                U[j][i] = true;
            }
            else if(s[j][i] == '.') U[j][i] |= U[j + 1][i];
        }
    }
    int sx,sy;
    int ex,ey;
    for(int i = 1;i <= n;i ++) {
        for(int j = 1;j <= m;j ++) {
            if(s[i][j] == '#') obs[i][j] = true;
            obs[i][j] |= L[i][j] | R[i][j] | U[i][j] | D[i][j];
            if(s[i][j] == 'S') sx = i,sy = j;
            if(s[i][j] == 'G') ex = i,ey = j;
        }
    }
    
    // for(int i = 1;i <= n;i ++) {
    //     for(int j = 1;j <= m;j ++) {
    //         if(obs[i][j]) cout << i << ' ' << j << endl;
    //     }
    // }
    auto bfs = [&](int sx,int sy) {
        queue<PII> q;
        q.push({sx,sy});
        memset(dis,0x3f,sizeof(dis));
        dis[sx][sy] = 0;
        while(!q.empty()) {
            auto [x,y] = q.front();
            q.pop();
            for(int i = 0;i < 4;i ++) {
                int dx = mx[i] + x,dy = my[i] + y;
                if(dx <= 0 || dy <= 0 || dx > n || dy > m || obs[dx][dy]) continue;
                if(dis[dx][dy] > dis[x][y] + 1) {
                    dis[dx][dy] = dis[x][y] + 1;
                    q.push({dx,dy});
                }
            }
        }
    };
    bfs(sx,sy);
    if(dis[ex][ey] == inf) cout << -1 << endl;
    else cout << dis[ex][ey] << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}

F - Nim (atcoder.jp)

        （1）题目大意AtCoder Beginner Contest 317(D-G),Atcoder,图论,背包类Dp,算法,动态规划,c++

        （2）解题思路

                考虑数字太大，我们用数位dp计数，状态为dp[pos][i][j][k][r1][r2][r3]，表示在二进制位为pos这位时，我们第一个数字填i，第二个数字填j，第三个数字填k，并且三个数得余数分别为r1，r2，r3得方案数有多少。

                显然对于非法情况若某一位i^j^k!=0，则不行，因为在异或操作下，若这一位异或不为零了，那么就永远不可能为0。

                对于答案非法情况，首先全0得方案需要减去，其次是有两个数相同，一个数为0得情况也要减去。

        （3）代码实现文章来源地址https://www.toymoban.com/news/detail-679860.html

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 61;
const ll mod = 998244353;
ll dp[N][2][2][2][2][2][2][10][10][10];
vector<int> nums;
int a,b,c;
ll ksm(ll a,ll b)
{
    ll rs = 1;
    while(b) {
        if(b & 1) rs = rs * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return rs;
}
ll calc(int pos,bool z1,bool z2,bool z3,int pi,int pj,int pk,int r1,int r2,int r3)
{
    if(pos == -1) return (!r1 && !r2 && !r3);
    if(dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3] != -1) return dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3];
    ll res = 0;
    int up1 = z1 ? nums[pos] : 1;
    int up2 = z2 ? nums[pos] : 1;
    int up3 = z3 ? nums[pos] : 1;
    for(int i = 0;i <= up1;i ++) {
        for(int j = 0;j <= up2;j ++) {
            for(int k = 0;k <= up3;k ++) {
                if(i ^ j ^ k) continue;
                int nr1 = (i == 1) ? (r1 + (1ll << pos)) % a : r1;
                int nr2 = (j == 1) ? (r2 + (1ll << pos)) % b : r2;
                int nr3 = (k == 1) ? (r3 + (1ll << pos)) % c : r3;
                res += calc(pos - 1,z1 && i == up1,z2 && j == up2,z3 && k == up3,i,j,k,nr1,nr2,nr3);
                res %= mod;
                // cout << i << ' ' << j << ' ' << k << ' ' << res << endl;
            }
        }
    }
    return dp[pos][z1][z2][z3][pi][pj][pk][r1][r2][r3] = res;
}
void solve()
{
    ll n;
    cin >> n >> a >> b >> c;
    ll rn = n;
    while(n) {
        nums.pb(n % 2);
        n /= 2;
    }
    memset(dp,-1,sizeof(dp));
    calc(sz(nums) - 1,true,true,true,0,0,0,0,0,0);
    ll ans = 0;
    for(int i = 0;i <= 1;i ++) {
    	for(int j = 0;j <= 1;j ++) {
    		for(int k = 0;k <= 1;k ++) {
                for(int z1 = 0;z1 <= 1;z1 ++) {
                    for(int z2 = 0;z2 <= 1;z2 ++) {
                        for(int z3 = 0;z3 <= 1;z3 ++) {
                            if(dp[sz(nums) - 1][z1][z2][z3][i][j][k][0][0][0] != -1) ans += dp[sz(nums) - 1][z1][z2][z3][i][j][k][0][0][0];
                            ans %= mod;
                        }
                    }
                }
            }        
    	}
    }
    n = rn;
    ans -= 1;
    ans -= n / lcm(a,b);
    ans -= n / lcm(a,c);
    ans -= n / lcm(b,c);
    ans = (ans % mod + mod) % mod;
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}

G - Rearranging (atcoder.jp)

        （1）题目大意

AtCoder Beginner Contest 317(D-G),Atcoder,图论,背包类Dp,算法,动态规划,c++

        （2）解题思路

                我们发现这个题很有可能是全部可以得，（事实上确实全部可以，由Hall定理可知），那么考虑怎么构造方案，由Hall定理得，我们得最大完美匹配在删除一些匹配后依旧成立，因此我们只需要一列一列得匹配完即可。

        （3）代码实现

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 105;
bool vis[N];
vector<int> v[N];
int match[N],Ans[N][N];
bool find(int x)
{
    vis[x] = true;
    for(auto y : v[x]) {
        if(!match[y] || (!vis[match[y]] && find(match[y]))) {
            match[y] = x;
            return true;
        }
    }
    return false;
}
void solve()
{
    int n,m;
    cin >> n >> m;
    rep(i,1,n) rep(j,1,m) {
        int x;
        cin >> x;
        v[i].pb(x);
    }
    rep(i,1,m) {
        memset(match,0,sizeof(match));
        rep(j,1,n) {
            memset(vis,false,sizeof(vis));
            if(!find(j)) {
                cout << "No" << '\n';
                return;
            }
        }
        rep(j,1,n) {
            Ans[match[j]][i] = j;
            v[match[j]].erase(find(v[match[j]].begin(),v[match[j]].end(),j));
        }
    }
    cout << "Yes" << '\n';
    rep(i,1,n) {
        rep(j,1,m) cout << Ans[i][j] << ' ';
        cout << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}

到了这里，关于AtCoder Beginner Contest 317(D-G)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解（数位dp)

    目录   E -- Digit Sum Divisibl 题目大意： 思路解析: 代码实现： 给你一个整数n，让你找出小于等于n的数中一共有多少个好整数，并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除，则称这个数为好整数。例如 12 能被 3 整除。 n=10^14。 看到数位之和

    2024年01月16日
    浏览(29)

  • Atcoder Beginner Contest 321 G - Electric Circuit 题解 - 状压dp | 指定最低位

    为了更好的阅读体验，请点击这里 题目链接：G - Electric Circuit 看到了 (N) 的数据范围，因此是显然的状压 dp。 不妨设 (f_S) 为仅使用 (S) 集合中的所有点，能够连成恰好 (1) 个连通块的方案数。 (g_S) 为仅使用 (S) 集合中的所有点的方案数，其中 (cntr(S)) 在 (S) 中为

    2024年02月05日
    浏览(39)

  • AtCoder Beginner Contest 339

    给一个网址，问它的后缀是多少。 找到最后的\\\'.\\\'的位置，然后输出后面的字符串即可。 python 可以一行。 神奇的代码 二维网格，上下左右相连，左上原点。初始全部为白色，位于原点，面朝上。 进行 (n) 次操作，每次操作，将当前格子颜色黑白反转，然后 如果原来是白色

    2024年02月19日
    浏览(19)

  • AtCoder Beginner Contest 336

    给定一个数 (n) ，将 long 中的 o 重复 (n) 次后输出。 模拟即可。 神奇的代码 给定一个数 (n) ，问 (n) 的二进制表示下的末尾零的数量。 即找到最小的 (i) 使得 (n (1 i)) 不为零的位置。枚举即可。 或者直接用内置函数 __builtin_ctz 。（count tail zero? 神奇的代码 定义一个数

    2024年01月20日
    浏览(31)

  • AtCoder Beginner Contest 311

    给定一个字符串，问最短的一个前缀，包含 A B C 这三个字符。 注意到这个前缀的末尾字母一定是这三个字母中的一个，因此答案就是这三个字母出现位置最早的最大值。 神奇的代码 给定 (n) 个人的 (d) 天的空闲与否的情况，问最长的连续天，这 (n) 个人都空闲。 我们找

    2024年02月16日
    浏览(33)

  • AtCoder Beginner Contest 318

    咕咕咕，总力战还没打，凹不过卷狗，躺了.jpg 给定 (n, m, p) ，问有多少个 (i) 满足 (0 m+pi leq n) 减去初始的 (m) ，剩下的就是看 (p) 的倍数个数。 神奇的代码 一个二维空间，有 (n) 个矩形覆盖。 问有多大的空间被覆盖了。重复覆盖算一次。 空间大小只有 (100) ，矩形

    2024年02月10日
    浏览(30)

  • AtCoder Beginner Contest 328

    给定 (n) 个数字和一个数 (x) 。 问不大于 (x) 的数的和。 按找要求累计符合条件的数的和即可。 神奇的代码 给定一年的月数和一个月的天数。 问有多少对 ((i,j)) ，表示第 (i) 个月的第 (j) 日， (i,j) 的数位上每个数字都是一样的。 范围只有 (O(100^2)) ，枚举所有的

    2024年02月05日
    浏览(27)

  • AtCoder Beginner Contest 323

    有的人边上课边打abc 给定一个 (01) 字符串，问偶数位（从 (1) 开始） 是否全为 (0) 。 遍历判断即可。 神奇的代码 给定 (n) 个人与其他所有人的胜负情况。问最后谁赢。 一个人获胜次数最多则赢，若次数相同，则编号小的赢。 统计每个人的获胜次数，排个序即可。 神奇

    2024年02月08日
    浏览(22)

  • AtCoder Beginner Contest 299

    给定一个包含 |*. 的字符串，其中 | 两个， * 一个，问 * 是否在两个 | 之间。 找到两个 | 的下标 (l, r) 以及 * 的下标 (mid) ，看看是否满足 (l mid r) 即可。 神奇的代码 给定 (n) 个人的卡片，颜色为 (c_i) ，数字为 (r_i) 。 如果其中有颜色为 (T) 的牌，则该颜色中数字最大

    2023年04月23日
    浏览(15)

  • AtCoder Beginner Contest 324

    在高铁上加训！ 给定 (n) 个数，问是否都相等。 判断是不是全部数属于第一个数即可。或者直接拿 set 去重。 神奇的代码 给定一个数 (N) ，问是否能表示成 (2^x3^y) 。 指数范围不会超过 (64) ，花 (O(64^2)) 枚举判断即可。 神奇的代码 给定一个字符串 (t) 和若干个字符串

    2024年02月08日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包