首页 > 编程语言 >2024“图森未来杯”程序设计邀请赛

2024“图森未来杯”程序设计邀请赛

时间：2024-05-04 17:23:15浏览次数：26  
标签：ch int long 2024 fa vector 图森 using 邀请赛

https://voj.mobi/contest/242/problems，密码2024ecnutsol

A - 调和与折中

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;


using vi = vector<int>;


i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	i64 a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	if(f * (a * c + b) == c * (d * f + e)) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

B - 数位游戏

如果\(x<10\) 且为奇数，则无解。

否则记\(cnt=bitcnt(p)\)，如果\(cnt\)为偶数，则一定存在一种不进位的方法，则答案为\(cnt/2\)，否则存在一种只进一次位的方法，则答案为\(cnt/2+5\)

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;


using vi = vector<int>;

void solve(){
	string s;
	cin >> s;
	if(s.size() < 2 and (s.front() - '0') % 2 == 1) {
		cout << "-1\n";
		return;
	}
	int cnt = 0;
	for(auto i : s) cnt += i - '0';
	if(cnt % 2 == 0) cout << cnt / 2 << "\n";
	else cout << cnt / 2 + 5 << "\n";
	return;
}

i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int TC;
	for(cin >> TC; TC; TC --)
		solve();
	return 0;
}

C - 抽卡与破防

根据题目可以得到出六星的概率

\[p(x) = \left\{\begin{matrix} \frac {a}{100} & x \le n\\ \min(\frac{a + (x-n)b}{100},100)& x > n \end{matrix}\right. \]

然后可以得到不出六星的概率\(arcp(x) = 1 - p(x)\)

对于出六星是 up 的概率是\(q = \frac{c}{100}\)，歪的概率是\(arcq = 1 - q\)

记\(E(i,j)\)表示从第\(i\)抽抽卡开始，累计\(j\)抽未出六星是，抽出\(up\)的概率是多少

对于没有到达保底的的情况\(i<m\)

\[E(i,j) = 1 + p(j) \times(arcq \times E(i+1,0) + q\times 0) + arcp[j] \times E(i+1,j+1) \]

对于已经到达保底的情况\(i>m\)

\[E(i,j) = 1 + p(j) \times 0 + arcq(j)\times E(i + 1 , j + 1) \]

然后我们递归加记忆化就可以的了，递归的过程中，如果已经到达保底出六星也就是\(arcq[j] = 0\)时就不要在搜索\(E(i+1,j+1)\)

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;


#define int i64

using vi = vector<int>;

const int N = 200, M = 20000, mod = 1e9+7;

int e[M + 1][N + 1], p[N + 1], arcp[N + 1];
int n, m, a, b, c, q, arcq;

int power(int x, int y) {
	int ans = 1;
	while(y) {
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>=1;
	}
	return ans;
}

int inv(int x) {
	return power(x, mod - 2);
}


void init(){
	int inv100 = inv(100);

	q = c * inv100 % mod;
	arcq = (100 - c) * inv100 % mod;

	for(int x = 0; x <= N; x ++){
		if(x <= n) p[x] = a * inv100 % mod;
		else p[x] = min(a + (x - n) * b, 100ll) * inv100 % mod;
		arcp[x] = (1ll - p[x] + mod) % mod;
	}	
	for(int i = 0; i <= M; i ++)
		for(int j = 0; j <= N; j ++) 
			e[i][j] = -1;
	return;
}

int E(int i ,int j) {
	if(e[i][j] != -1) return e[i][j];
	if(i < m) {
		e[i][j] = 1;
		if(arcp[j] % mod != 0) e[i][j] = (e[i][j] + arcp[j] * E(i + 1, j + 1) % mod) % mod; // 没出六星
		e[i][j] = (e[i][j] + p[j] * arcq % mod * E(i + 1 , 0) % mod ) % mod; // 出六星 但不是 up
	
	} else { // 出六星必 up
		e[i][j] = 1;
		if(arcp[j] % mod != 0) e[i][j] = (e[i][j] + arcp[j] * E(i + 1, j + 1)) % mod; // 没出六星
	}
	assert(e[i][j] >= 0);
	return e[i][j] %= mod;
}


i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m >> a >> b >> c;
	init();
	cout << E(0, 0);
	return 0;
}

F - 花狮平衡树

想了很久，最后还是用裸的 splay树实现的。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ll = long long;

using vi = vector<int>;
using pii = pair<int, int>;



const int N = 5e5+5;

int n;

struct Splay {
    int rt, tot, fa[N], ch[N][2], val[N], cnt[N], siz[N];
    int tag[N];
    void push_up(int x) {
        siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
    }
    void push_down(int x) {
        if (x && tag[x]) {
            if (ch[x][0])tag[ch[x][0]] ^= 1;
            if (ch[x][1])tag[ch[x][1]] ^= 1;
            swap(ch[x][0], ch[x][1]);
            tag[x] = 0;
        }
    }
    bool get(int x) { return x == ch[fa[x]][1]; }
    void clear(int x) {
        ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y], chk = get(x);
        push_down(x);
        push_down(y);
        ch[y][chk] = ch[x][chk ^ 1];
        if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
        ch[x][chk ^ 1] = y;
        fa[y] = x;
        fa[x] = z;
        if (z) ch[z][y == ch[z][1]] = x;
        push_up(y);
    }
    void splay(int x, int goal) {
        for (int f = fa[x]; (f = fa[x]) != goal; rotate(x))
            if (fa[f] != goal) rotate(get(x) == get(f) ? f : x);
        if (goal == 0)rt = x;
    }
    void splay(int x) {
        splay(x, 0);
    }
    int kth(int k) {

        int cur = rt;
        while (1) {
            push_down(cur);
            if (ch[cur][0] && k <= siz[ch[cur][0]]) {
                cur = ch[cur][0];
            }
            else {
                k -= cnt[cur] + siz[ch[cur][0]];
                if (k <= 0) {
                    splay(cur);
                    return cur;
                }
                cur = ch[cur][1];
            }
        }
    }
    int find(int x) {
        return kth(x + 1);
    }
    int build(int L, int R, int father) {
        if (L > R) { return 0; }
        int x = ++tot;
        int mid = (L + R) / 2;
        fa[x] = father;
        cnt[x] = 1;
        val[x] = mid;
        ch[x][0] = build(L, mid - 1, x);
        ch[x][1] = build(mid + 1, R, x);
        push_up(x);
        return x;
    }
    void rev(int L, int R) {
        int fl = find(L - 1);
        int fr = find(R + 1);
        splay(fl, 0);
        splay(fr, fl);
        int pos = ch[rt][1]; pos = ch[pos][0];
        tag[pos] ^= 1;
    }
    void dfs(int x) {
        push_down(x);
        if (ch[x][0])dfs(ch[x][0]);
        if (val[x] != 0 && val[x] != (n + 1))cout << val[x] << " ";
        if (ch[x][1])dfs(ch[x][1]);
    }
} tree;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int m;
    cin >> n >> m;
    tree.build(0, n + 1 , 0);
	tree.rt = 1;
	while(m -- ){
		int l , r;
		cin >> l >> r;
		tree.rev(l ,r);
	}
	tree.dfs(tree.rt);
    return 0;
}

H - 橡木蛋糕卷

首先我们计算出每个传送点到所有的蛋糕店的最短距离，然后就转换成了经典旅行商问题，用状压 dp 来解决。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using ll = long long;


using vi = vector<int>;
using pii = pair<int, int>;

const int N = (1 << 18) + 8;

int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

int stos[20][20];

int dp[N][20];

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n,m;cin >> n >> m;

    vector<vector<char>> a(n + 1,vector<char>(m + 1));
    vector<pair<int,int>> t(1),s(1);

    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
            if (a[i][j] == 'S') s.push_back({i,j});
            if (a[i][j] == 'T') t.push_back({i,j});
        }
    }

    auto bfs = [&](int sx,int sy)->vector<vector<int>>{
        queue<pair<int,int>> q;
        q.push({sx,sy});
        vector<vector<int>> vis(n + 1,vector<int>(m + 1));
        vector<vector<int>> d(n + 1,vector<int>(m + 1, 1e9));
        d[sx][sy] = 0;
        vis[sx][sy] = 1;
        while (!q.empty()){
            auto [x,y] = q.front();
            q.pop();
            for (int i = 0;i < 4;i++){
                int u = x + dx[i],v = y + dy[i];
                if (u < 1 || v < 1 || u > n || v > m || vis[u][v] || a[u][v] == '#'){
                    continue;
                }
                q.push({u,v});
                d[u][v] = d[x][y] + 1;
                vis[u][v] = 1;
            }
        }
        return d;
    };
    int siz = s.size() - 1;
    vector<int> ttos(s.size(),1e9);
    int idx = 0;

    for( int i = 0 ; i < 20 ; i ++ )
        for( int j = 0 ; j < 20 ; j ++ )
            stos[i][j] = 1e9;

    for (int i = 1;i < s.size();i++){
        auto [x,y] = s[i];
        auto tmp = bfs(x,y);
        for (int j = 1;j < s.size();j++){
            auto [u,v] = s[j];
            stos[i][j] = min(stos[i][j],tmp[u][v]);
        }
        for (auto [u,v] : t){
            ttos[i] = min(ttos[i],tmp[u][v]);
        }
    }

    for (int i = 1;i < (1 << siz);i++){
        for (int j = 0;j < 20;j++){
            dp[i][j] = 1e9;
        }
    }

    dp[0][0] = 0;

    for (int i = 1;i < (1 << siz);i++){
        for (int j = 1;j <= siz;j++){
            if ((i >> (j - 1)) & 1){ // END
                int tmp = 1e9;
                for (int k = 1;k <= siz;k++){ // ST
                    if ((i >> (k - 1) )& 1 && k != j){
                        tmp = min(tmp,dp[i - (1 << (j - 1))][k]);
                        dp[i][j] = min(dp[i][j],dp[i - (1 << (j - 1))][k] + stos[j][k]);
                    }
                }
                if (tmp == 1e9) tmp = 0;
                dp[i][j] = min(dp[i][j],tmp + ttos[j]);
            }
        }
    }

    int ans = 1e9;

    for (int i = 1;i <= siz;i++){
        ans = min(dp[(1 << siz) - 1][i],ans) ;
    }

    cout << ans << endl;

    return 0;
}

标签：ch,int,long,2024,fa,vector,图森,using,邀请赛
From： https://www.cnblogs.com/PHarr/p/18172480

相关文章

  • 2024-05-04 css实现鼠标移动至盒子，盒子在约定时间内进行放大缩小
    放大缩小css@keyframesscaleAnimation{0%{transform:scale(1);}50%{transform:scale(1.2);}100%{transform:scale(1);}}完整代码：<!DOCTYPEhtml><htmllang="en"><head><metacharset=&q......
  • 2024-05-04：用go语言，给定一个起始索引为0的字符串s和一个整数k。 要进行分割操作，直到字
    2024-05-04：用go语言，给定一个起始索引为0的字符串s和一个整数k。要进行分割操作，直到字符串s为空：选择s的最长前缀，该前缀最多包含k个不同字符；删除该前缀，递增分割计数。如果有剩余字符，它们保持原来的顺序。在操作之前，可以修改字符串s中的一个字符为另一个小写英文字母。在最佳情......
  • 个人算法竞赛模板（2024.5.4）
    精简版：#include<algorithm>#include<cmath>#include<cstring>#include<iostream>#include<map>#include<queue>#include<set>#include<stack>#include<string>#include<vector>#include<......
  • P10064 [SNOI2024] 公交线路 题解
    弱化版：CF1827EBusRoutes。对于\(n=2\)的情况可以判掉，剩下的情况取一个度数大于一的点作为根。首先发现如果叶子间满足条件，那么整棵树也满足条件。考虑叶子间什么时候满足条件，记点\(x\)通过最多一条路径可以到达的所有点的集合为\(S_x\)，则需满足\(\forallx,y\in\mathbf......
  • 20240503
    T1NFLSOJP2023050961捉迷藏首先只需要考虑所有叶子，只要每个叶子都连向了另一个距离超过\(2\)的叶子，则符合要求。距离超过\(2\)等价于在不同的父亲下。则问题变为一堆点，每个点有颜色，同色点间没有边，异色点间两两有边，求最大匹配。结论：设点最多的颜色\(c\)有\(x\)个点，若......
  • 2024数据工程开源技术跟踪
    1、已退休、存档和被放弃的项目，例如：ApacheSqoop：ThisrepositoryhasbeenarchivedbytheowneronJul9,2021.Itisnowread-onlyScribe： ThisrepositoryhasbeenarchivedbytheowneronJan13,2022.Itisnowread-only.ApacheApex：Thisrepositoryhasbeen......
  • 2024劳动节北斗课堂总结
    第一天上午讲了数据结构平衡树（Treap）随机的笛卡尔树的期望深度是\(log_{n}\)。合并合并以\(x,y\)为根的\(Treap\)过程若\(x,y\)有一个为空，则返回另一个比较\(x,y\)的随机权值若\(x<y\)则递归合并\(x\)的左儿子和\(y\)。否则返回\(x\)和\(y\)的右儿子......
  • 20240503比赛总结
    T1[CF1279C]StackofPresentshttps://gxyzoj.com/d/hzoj/p/3686数据出锅了，100->40按题意模拟即可，可以发现，最优情况下，一定是将取出的数按后面的拿的顺序排序，O(1)取出，而在取之前未排序的，则需要花2k+1的时间排序并取出代码：#include<cstdio>#definelllonglongusingnamesp......
  • 2024-5-3 假期第三天 杯具ε(┬┬﹏┬┬)3
    昨天和老哥约的今天吃饭，哥和嫂子十点多开车来学校接的我，然后去烤肉店，到店里哥就一直在看手机，然后肉刚烤熟哥就出去了，干啥也没说。我和嫂子都吃完了还没回来，得四十分钟左右吧，然后嫂子有点不高兴了，把剩下的肉打包了，就要直接回去，我趁下去的时候给大姨打个电话问问该怎么办，其实也不能......
  • 2024-5-1 假期第一天 愉快
    假期第一天，中午十点多醒的，经过一番挣扎之后还是下定决心去本部开点二硫化硒，于是坐地铁去本部，到了发现皮肤科不开，遂返回，虽然无功而返吗，但是今天天气是真的好，路上骑行看到的风景很美，回来的时候去物美逛了一圈买了点香蕉，买了点饮料，然后又花30买了两杯喜茶，挺好喝就是有点贵。愉快的一......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99