AtCoder Beginner Contest 226（A-G）

2023-10-17 16:43:34

AtCoder Beginner Contest 226（A-G）

@TOC

知识点整理：

题号 知识点 备注
A 无
B 无
C BFS
D 简单模拟、数学
E 图论 好题，需要记住思路
F DP 较为复杂的DP
G 贪心 ARC的一道类似题
H 概率期望，DP

签到题、简单题

A - Round decimals

求浮点数的四舍五入

#include <bits/stdc++.h>

using namespace std;

int main() {
  double x;
  cin >> x;
  cout << (int)(x+0.5) << endl;
  return 0;
}

B - Counting Arrays

给你很多数组，判断有几种不同的数组

直接用set模拟即可

#include <bits/stdc++.h>

using namespace std;

set<vector<int>> s;

int n, l, a;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        vector<int> arr;
        cin >> l;
        for (int i = 0; i < l; i++) {
            cin >> a;
            arr.push_back(a);
        }
        s.insert(arr);
    }
    cout << s.size() << endl;
    return 0;
}

C - Martial artist

给你 n n n 个技能，点亮某个技能需要一些前置技能，还需要花费 t [ i ] t[i] t[i]的时间，初始技能树是空的，问把技能 N N N点亮至少花费多少时间？

一开始用拓扑排序做错了，后来发现构图然后从N点开始直接bfs即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
int t[N];
int k[N];
vector<int> a[N];
int T[N];

int vis[N];
ll res;
int main() {
    queue<int> q;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &t[i], &k[i]);
        for (int j = 1; j <= k[i]; j++) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
        }
    }
    q.push(n);
    vis[n] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();
        int j;
        for (int i = 0; i < a[t].size(); i++) {
            j = a[t][i];
            if (vis[j])
                continue;
            else {
                vis[j] = 1;
                q.push(j);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        //cout << vis[i] << endl;
        if (vis[i] == 1) {
            res += t[i];
        }
    }
    cout << res << endl;
}

中等题

D - Teleportation

有一种咒语记为 ( a , b ) (a,b) (a,b)，可以从地图上的 ( x , y ) (x,y) (x,y)点瞬移到 ( x + a , y + b ) (x+a, y+b) (x+a,y+b)点。现在在笛卡尔系上有 N N N个点，问至少需要多少种咒语，才可以在这 N N N个点之间任意行走？

这道题出乎意料的简单，看到 N ≤ 500 N \le 500 N≤500, 说明 O ( n 2 ) O(n^2) O(n2)肯定是可行的。N个点两两做得到 N 2 N^2 N2个差值，每个差值对应两个咒语（可以往返），但是这样不是最优的，因为可以取最大公约数达到最大的复用性，因此再取一个gcd就可以了，注意有0的情况。用set维护，最后答案是set大小再乘2，总的时间复杂度是 O ( n 2 l o g n ) O(n^2logn) O(n2logn)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 510;

int n;
ll x[N], y[N];

set<pii> s;

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    
    for (int i = 1; i <= n ; i++) {
        for (int j = i+1; j <= n; j++) {
            ll dx = x[i] - x[j], dy = y[i] - y[j];
            ll g = gcd(dx, dy);

            if (g != 0) {
                dx /= g, dy /= g;
            }

            s.insert({dx, dy});
        }
    }

    cout << s.size() * 2 << endl;
    return 0;
}

E - Just one

题意：

给你 n n n点 m m m边的无向图，问有多少种加边的方案，使得每个点的出度都是1？

题解：

一开始我考虑的是跟判环有关系，但是会TLE。

其实看了答案，实现过程并不难：对每个连通分量，只要点数==边数，这个连通分量对答案就有2的贡献，否则就无解。

证明如下：

要想实现 将无向图定向，使得每个点出度均为 1
那么就需要每个点都有一条出边
对于一个连通图来说 如果点数>边数，要么是不连通图，要么就是一颗树，无法实现每个点都有出边,因为点数的边数不对

如果点数<边数的连通图，由于要实现每个点都有一条出边，那么可以先使每个点都出去一条边，此时用了一些边，但是还有一些边没有定方向，由于所有点的定了一个出去的方向，再给摸
个点定一个出边的话，就与题意矛盾

所以只能点数=边数

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200100;
const int MOD = 998244353;

struct Edge {
    int to, next;
} e[N << 1];

int n, m, head[N], vis[N], idx = 1;

int vert, edge; // 表示点数和边数

void add_edge(int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx++;
}
void clear_graph() {
    memset(head, -1, sizeof(head));
    memset(e, 0, sizeof(e));
    idx = 1;
}

void dfs(int u) {
	vis[u] = true;
	vert++;
	for (int i = head[u]; ~i; i = e[i].next) {
		edge++;
		int j = e[i].to;
		if (!vis[j]) dfs(j);
	}
}
int main() {
    cin >> n >> m;
	int u, v;
	clear_graph();
    for (int i = 1; i <= m; i++) {
        cin >>u>>v;
		add_edge(u, v), add_edge(v, u);
    }
    
	ll res = 1;
    for (int i = 1; i <= n ; i++) {
        if (!vis[i]) {
			vert = edge = 0;
			dfs(i);
			if (vert*2 == edge) res = res * 2 % MOD;
			else res = 0;
		}
    }

    cout << res << endl;
    return 0;
}

F - Score of Permutations

题意：

定义一个 1 − n 1-n 1−n的排列 P P P的分数 S ( P ) S(P) S(P)为：

有 N N N个人，初始的时候按 1 , 2 , . . . n 1,2,...n 1,2,...n站着，每轮让 i i i走到 p i p_i pi​的位置，直到每个人都走回初始位置，走的轮数记为排列 P P P的分数 S ( P ) S(P) S(P)。

给出 N , K N,K N,K，求 ∑ P ∈ S N S ( P ) K \sum_{P\in S_N}S(P)^K ∑P∈SN​​S(P)K .答案对998244353取模。

题解

这道题可以用DP来做，对于这种排列来回换座位的题，通常用图论的思想来考虑，把 i → p i , p i → p [ p i ] . . . . i \to p_i, p_i \to p[p_i].... i→pi​,pi​→p[pi​]....连边，则构成若干个闭环，每个环走它的长度的时候，回到初始点。

故对于每种排列，其分数为该排列对应所有环大小的LCM，因此可以设计一种DP的关系：

设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前i个人，环的LCM为j的方案数，则有

d p [ i + x ] [ l c m ( j , x ) ] = d p [ i ] [ j ] ∗ C n − i − 1 x − 1 ∗ ( x − 1 ) ! dp[i+x][lcm(j, x)]=dp[i][j]*C_{n-i-1}^{x-1}*(x-1)! dp[i+x][lcm(j,x)]=dp[i][j]∗Cn−i−1x−1​∗(x−1)!

对 d p [ i ] [ j ] dp[i][j] dp[i][j]这个状态，考虑下一个环的大小为x，那么下一个环要从剩下的 n − i n-i n−i个数里先固定选一个下标最小的，使得每次转移时，每个环内的最小值一定是单调递增的，而长度为 x x x的环的排列数是 ( x − 1 ) ! (x-1)! (x−1)!,因此得到上述转移关系。

实现的时候，因为 j j j状态非常大，还可能爆int，而且绝大多数是0，故可以用map<ll, ll>优化,总的时间复杂度应该是 O ( n 2 l o g n ) O(n^2logn) O(n2logn)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 55, mod = 998244353;
ll n, k;
ll fact[N], infact[N];
map<ll, ll> dp[N];

ll qmi(ll a, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = (ll)res * a % mod;
        k >>= 1;
        a = a * a%mod;
    }
    return res;
}

void init() {
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++) 
    {
        fact[i]=(ll)fact[i-1]*i%mod; 
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2)%mod; 
    }
}

ll C(ll a, ll b) {
    if (a < b) return 0;
    return fact[a] * infact[b] % mod * infact[a - b] % mod;
}

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }



int main() {
    init();
    cin >> n >> k;
    dp[0][1] = 1;
    for (int i = 0; i < n; i++) {
        for (auto it : dp[i]) {
            for (int j = 1; i + j <= n; j++) {
                dp[i + j][lcm(j, it.first)] = (dp[i + j][lcm(j, it.first)] + it.second * C(n - i - 1, j - 1) %mod * fact[j - 1] % mod) % mod;
            }
        }
    }
    ll res = 0;
    for (auto it : dp[n]) {
        res = (res + it.second * qmi(it.first, k)) % mod;
    }
    cout << res << endl;
}

高级题

G - The baggage

题意：

给你五种物品，质量分别是1,2,3,4,5,个数分别是 A 1 , A 2 , A 3 , A 4 , A 5 A_1,A_2,A_3,A_4,A_5 A1​,A2​,A3​,A4​,A5​

现有五种工人，负重分别是1,2,3,4,5,个数分别是 B 1 , B 2 , B 3 , B 4 , B 5 B_1,B_2,B_3,B_4,B_5 B1​,B2​,B3​,B4​,B5​

问这些工人能否带走这些物品？

题解

跟这道题A - Make 10很像，看数据范围就知道没法遍历，只能设计一种贪心思路。

从最重的物品开始贪心：

  • 负重5的工人搬质量5
  • 负重4的工人搬质量4
  • 负重5的工人搬质量4
  • 负重3的工人搬质量3
  • 负重5的工人搬质量3
  • 负重4的工人搬质量3
  • 负重2的工人搬质量2
  • 负重5,4,3的工人搬质量2
  • 。。。

这个策略的证明就不说了，实现上述过程即可，如果还剩物品没搬走，则输出No

每个样例都是 O ( 1 ) O(1) O(1)的

#include <bits/stdc++.h>
using namespace std;

#define N 200010
#define MOD (ll)998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

ll a[6];
ll b[6];

void pack(ll x, ll y) {
	ll c = min(a[x], b[y]);
	a[x] -= c;
	b[y] -= c;
	b[y - x] += c; // c个工人的负重还剩下y-x
	return;
}

int main(void) {
	ll t;
	bool ans;
	cin >> t;
	rep(tt, t) {
		rep(i, 5)cin >> a[i + 1];
		rep(i, 5)cin >> b[i + 1];
		a[0] = 0;
		b[0] = 0;

		pack(5, 5);
		pack(4, 4);
		pack(4, 5);
		pack(3, 3);
		pack(3, 5);
		pack(3, 4);
		rep(i, 4)pack(2, 5 - i);
		rep(i, 5)pack(1, 5 - i);

		ans = true;
		rep(i, 5)if (a[i + 1] > 0)ans = false;
		if (ans)cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

H - Security Camera 2

题意：

给你 N N N个连续随机变量 X 1 , X 2 . . . X n X_1,X_2...X_n X1​,X2​...Xn​.

其中 X i X_i Xi​ 在区间 [ L i , R i ] [L_i,R_i] [Li​,Ri​]内均匀分布，求第 K K K大数的期望。

这题大约相当于CF 2600的水平，不会

上一篇：226反转二叉树


下一篇：AtCoder Beginner Contest 226 （A～E)