5.2cf

2023-09-25 12 0

5.2

vp了一场Global Round 没有做完就去吃饭了,出了三题

Codeforces Global Round 4

A题 签到

but我下午状态不是很好,是最后再做的

因为A题的题面有太多我不认识的名词,虽然我知道这个是名词例如prime minister是总理,but我总想去查,然后,就不想看了

B题 模拟

我一个变量名码错了,白wa

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1Akb81bj-1620024804958)(C:\Users\lili\AppData\Roaming\Typora\typora-user-images\image-20210503144731603.png)]

D题 构造

同样一个变量名码错了,白wa
在这里插入图片描述

题意

给一个n,能不能构造一个无环无重复边的无向图是的,有n个点,总的有素数个边,每个点有素数的度

题解

如果n是素数,那么相邻两个点连边, 对于每个点度都是2

如果不是,我大胆猜想(毛估估素数的密度)觉得n到3n/2一定有一个素数,

这样的话,相当于增加连线 i 和 i + n/2 点的边

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e3 + 10;
const int INF = 1e9 + 7;
const int MOD = 998244353;bool is_pri[MAX];
int pri[MAX];
int cnt = 0;void prime() {is_pri[0] = is_pri[1] = 1;for(int i = 2; i <= MAX; i++) {if(!is_pri[i]) pri[cnt++] = i;for(int j = 0; j < cnt && pri[j] * i <= MAX; j++) {is_pri[pri[j] * i] = 1;if(i % pri[j] == 0) break;}}
}
int main() {int n;scanf("%d", &n);prime();if(is_pri[n] == 0) {printf("%d\n", n);for(int i = 1; i < n; i++) {printf("%d %d\n", i, i + 1);}printf("%d 1\n", n);}else {int tmp = 0;for(int i = n; i <= n + n / 2; i++) {if(is_pri[i] == 0) {tmp = i;break;}}printf("%d\n", tmp);for(int i = 1; i < n; i++) {printf("%d %d\n", i, i + 1);}printf("%d 1\n", n);tmp -= n;int i = 1, j = i + n / 2;while(tmp--) {printf("%d %d\n", i, j);i++; j++;}}
}

C题

我果然理解错题目了,我一开始以为是黑的不能碰在一起,实际上是相同颜色的不能碰在一起

题解

请注意,对于固定的一对瓦片(i-1,j)和(i,j-1),存在一种将瓦片放置在(i,j)上满足条件的确切方法。
结果,当放置所有图块(1,i)和(j,1)时,其余图块将唯一确定。
我们只需要计算平铺第一行和第一列的方法数

很神奇的是

凭借我的乱猜大法,是猜到了,but由于我快速幂n = n * n的地方忘记写MOD,wa4了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e6 + 10;
const int INF = 1e9 + 7;
const int MOD = 998244353;
ll qpow(ll n, ll k) {ll res = 1;while(k) {if(k & 1) res = res * (n % MOD) % MOD;k >>= 1;n = n * n % MOD;}return res;
}
int main() {int n, m;scanf("%d%d", &n, &m);ll ans = qpow(2, m + n) % MOD;printf("%lld\n", ans);
}
代码编程
赞赏

相关文章

ubuntu18.04交叉编译linux3.6内核
786. K-th Smallest Prime Fraction
668. Kth Smallest Number in Multiplication Table
构建嵌入式系统软件开发环境-建立交叉编译环境
7-8 File Transfer (25 分)
改善睡眠的东西有哪些?能够帮助睡眠的好物推荐