A Beta Go

B Build Roads(最小生成树Kruskal)

image.png

  1. 如果在边权中存在质数，那么他与所有数的最大公约数都是1，则答案一定是n - 1
  2. return xorshift64() % (R - L + 1) + L;
    //这个式子决定了a[i]的值，若R - L == 0 || R - L + 1 == 1那么取模之后一定是 0， 则返回值为 L, 这种情况下所有边权都是 L
  3. a[i] 的 取值一定在 L ~ (R - L + 1) + L 之间，当n比较小时使用Kruskal计算最小生成树即可，若n较大，则a[i]中一定存在素数

    **//
    // Created by SYSZY on 2022/5/14.
    //

#include
#include
#include
#include
#include
#include _

_using namespace std;
typedef unsigned long long ull;
const int N = 200001;
int n, L, R, a[N];
_ull _seed;
bool **_prime[N];

**_void getprime() {
memset(prime, 1, sizeof(prime));
prime[1] = 1;
for (int i = 2; i <= 200000; ++i) {
if (prime[i]) {
for (int **_j = i + i; j <= 200000; j += i)prime[j] = 0;
}
}
}

ull _xorshift64() {
_ull _x = seed;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return _seed = x;
}

**_int gen() {
return xorshift64() % (R - L + 1) + L;
//这个式子决定了a[i]的值，若R - L == 0 || R - L + 1 == 1那么取模之后一定是 0， 则返回值为 L, 这种情况下所有边权都是 L
**_}

**_struct Edge {
int **x, y, w_;
};

**_void solve1() {
_vector<_Edge_> edge;
_for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
edge.push_back({i, j, __gcd(a[i], a[j])});
}
}
_vector<_int> pre(n + 1);
for (int i = 1; i <= n; ++i)pre[i] = i;
sort(edge.begin(), edge.end(), [](const Edge _&_a, const Edge &_b) -> _bool {
return **a.w < _b.w;
});

  1. _function_<_**_int_**_(_**_int_**_)> Find = [&](_**_int _**x_) -> _**_int _**_{<br />        _**_return _**_pre[_x_] == _x _? _x _: pre[_x_] = Find(pre[_x_]);<br />    };
  3. _**_int _**_ans = 0;<br />    _**_for _**_(_**_auto _**_&x:edge) {<br />        _**_int _**_fx = Find(x_.x_);<br />        _**_int _**_fy = Find(x_.y_);<br />        _**_if _**_(fx != fy) {<br />            pre[fx] = fy;<br />            ans += x_.w_;<br />        }<br />    }<br />    printf(_**_"%d_\n_"_**, _ans);<br />}

**_int main() {
getprime();//欧拉筛找到所有质数
scanf(“%d%d%d%llu”, &n, &L, &R, &seed);
for (int i = 1; i <= n; i++) {
a[i] = gen();
}//题目中的代码模板，生成边权
for (int i = 1; i <= n; ++i) {//如果在边权中存在质数，那么他与所有数的最大公约数都是1，则答案一定是n - 1
if (prime[a[i]]) {
printf(“%d\n“, n - 1);
return **_0;
}
}

  1. _**_if _**_(n <= 30000)<br />        solve1();<br />    _**_else if _**_(L != R)<br />        printf(_**_"%d_\n_"_**, _n - 1);<br />     _**_else<br />__        _**_printf(_**_"%lld_\n_"_**, _1ll * R * (n - 1));<br />    _**_return _**_0;<br />}_

Kruskal算法

基本思想 ：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
方法：找到所有边中未纳入最小生成树且边权最小的边，使用并查集检查该边的两端点是否存在未纳入最小生成树的点，有则纳入最小生成树，若全被纳入最小生成树则放弃该边，继续遍历，知道纳入了n - 1条边。

**//
// Created by SYSZY on 2022/5/14.
//

#include
#include
#include
#include _

_using namespace std;
const int N = 1e3 + 10;
int n, m, k;
int **_f[N];

**_struct Edge {
int **x, y, v_;

  1. Edge(_**_int _**x, **_int _**y, **_int _**v_) : _x_(_x_)_, y_(_y_)_, v_(_v_) {}<br />};

vector<_Edge_> edge;

**_int find(int x) {
return **f[_x] == x ? x : f[x] = find(f[x]);
}

**_int Kruskal() {
int sum = 0;
int cnt = 0;
for (int i = 0; i < edge.size(); i++) {
int u = edge[i].x, v = edge[i].y, w = edge[i].v;
int fx = find(u), fy = find(v);
if (fx != fy) {
f[fx] = fy;
sum += w;
cnt++;
}
if (cnt == n - 1) break;
}
return **_sum;

}

**_int main() {
scanf(“%d%d%d”, &n, &m);
for (int i = 1; i <= n; i++) {
f[i] = i;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf(“%d%d%d”**, &u, &v, &w);
edge.push_back({u, v, _w});
}

  1. sort(edge_._begin()_, _edge_._end()_, _[](_Edge _&_a, Edge _&_b_) {<br />        _**_return _**a.v _< _b.v_;<br />    });
  3. _**_int _**_ans = Kruskal();<br />    _**_if _**_(ans != -1)<br />        printf(_**_"%d"_**, _ans);<br />    _**_else<br />__        _**_printf(_**_"No Answer"_**_);<br />    _**_return _**_0;<br />}_

C Cat virus

D Dyson Box

模拟题，记录每次垂直掉落和水平掉落对原状态的影响并输出每次影响的结果即可。

include

using namespace std;

int n, x, y; int row[200005] = {0}, col[200005] = {0};

int main() { scanf(“%d”, &n); long long sumrow = 0, sumcol = 0; for (int i = 1; i <= n; i++) {

  1.     scanf("%d%d", &x, &y);
  2.     int num = 4;
  3.     if (col[x] != 0) num -= 2;
  4.     col[x]++;//Vertical
  5.     if (col[x - 1] >= col[x]) num -= 2;
  6.     if (col[x + 1] >= col[x]) num -= 2;
  7.     sumcol += num;
  8.     int num2 = 4;
  9.     if (row[y] != 0) num2 -= 2;
  10.     row[y]++;//Horizontal
  11.     if (row[y - 1] >= row[y]) num2 -= 2;
  12.     if (row[y + 1] >= row[y]) num2 -= 2;
  14.     sumrow += num2;
  15.     printf("%lld %lld\n", sumcol, sumrow);
  16. }
  19. return 0;

}

E Evaluate Expression

F Birthday Cake

G Grade Point Average

高精度模拟除法

include

include

include

include

using namespace std; typedef long long ll;

int main() { int n,k; scanf(“%d%d”,&n,&k); int a,sum=0; for(int i=1;i<=n;i++) { scanf(“%d”,&a); sum+=a; } printf(“%d.”,sum/n); int b; for(int i=1;i<=k;i++) //模拟手算除法 { b=sum%n; b*=10; sum=b; b/=n; printf(“%d”,b); } puts(“”); //PAUSE; return 0; }

H Adventurer’s Guild

二维费用背包问题
Yuna有 H 生命值和 S护甲值，当生命值下降到0时死亡。
每个怪物会对Yuna造成 h 点真实伤害（直接减血）和 s 点物理伤害（有护甲减护甲，无护甲则减血）。
击杀怪物会掉落金币
求 Yuna 最多能获得多少金币。

**//
// Created by SYSZY on 2022/5/14.
//

#include
#include _

_using namespace std;
typedef long long **ll_;

**_const int N = 1005;
int H, S, n;
int **h[N], s[N], _v[N];
_ll _dp[N][N];

**_int main() {
scanf(“%d%d%d”, &n, &H, &S);
for (int i = 1; i <= n; i++) {
scanf(“%d%d%d”, &h[i], &s[i], &v[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = H; j >= 0; j—) {
for (int k = S; k >= 0; k—) {
if (j > h[i] && k >= s[i]) {//血量和护甲都够扣
dp[j][k] = max(dp[j - h[i]][k - s[i]] + v[i], dp[j][k]);
} else if (j > h[i] && j + k > h[i] + s[i]) {//护甲不够扣，但是血量够
dp[j][k] = max(dp[j][k], dp[j - h[i] - (s[i] - k)][0] + v[i]);
}
}
}
}
printf(“%lld”, dp[H][S]);
return **0;
}

I Chemical Code

J Tuition Agent

K Piggy Calculator

L Construction of 5G Base Stations

M Matrix

构造矩阵

**//
// Created by SYSZY on 2022/5/19.
//

#include_

_using namespace **std_;

**_typedef unsigned long long ull;
typedef long long **ll_;

**_const int *_N = 2 1e5 + 100;

**_int **n, _m;

_string _s[501];

**_int **_main() {
cin >> n >> m;

  1. _**_for _**_(_**_int _**_i = 1; i <= n; i++) {<br />        cin >> s[i];<br />    }<br />    _**//A矩阵<br />    **_printf(_**_"1"_**_);<br />    _**_for _**_(_**_int _**_i = 2; i <= m; i++) printf(_**_"0"_**_);<br />    printf(_**_"_\n_"_**_);_**//A第一行
  3. _for _**_(_**_int _**_i = 2; i <= n - 1; i++) {<br />        printf(_**_"1"_**_);<br />        _**_for _**_(_**_int _**_j = 1; j < s[i]_._size() - 1; j++) {<br />            _**_if _**_(s[i][j] == _**_'1'_**_) printf(_**_"1"_**_);<br />            _**_if _**_(s[i][j] == _**_'0'_**_) {<br />                _**_if _**_(i % 2 != 0)<br />                    printf(_**_"1"_**_);<br />                _**_else<br />                    _**_printf(_**_"0"_**_);<br />            }<br />        }<br />        printf(_**_"0_\n_"_**_);<br />    }_**//A中间行
  5. **_printf(_**_"1"_**_);<br />    _**_for _**_(_**_int _**_i = 2; i <= m; i++) printf(_**_"0"_**_);<br />    printf(_**_"_\n_"_**_);_**//A末行
  7. _for _**_(_**_int _**_i = 1; i < m; i++) printf(_**_"0"_**_);<br />    printf(_**_"1"_**_);<br />    printf(_**_"_\n_"_**_);_**//B第一行
  9. _for _**_(_**_int _**_i = 2; i <= n - 1; i++) {<br />        printf(_**_"0"_**_);<br />        _**_for _**_(_**_int _**_j = 1; j < s[i]_._size() - 1; j++) {<br />            _**_if _**_(s[i][j] == _**_'1'_**_) printf(_**_"1"_**_);<br />            _**_if _**_(s[i][j] == _**_'0'_**_) {<br />                _**_if _**_(i % 2 == 0)<br />                    printf(_**_"1"_**_);<br />                _**_else<br />                    _**_printf(_**_"0"_**_);<br />            }<br />        }<br />        printf(_**_"1_\n_"_**_);<br />    }_**//B中间行
  11. _for _**_(_**_int _**_i = 1; i < m; i++) printf(_**_"0"_**_);<br />    printf(_**_"1"_**_);<br />    printf(_**_"_\n_"_**_);_**//B末行

**_}

_