B - Christmas Trees
难度: ⭐⭐
题目大意
小莫从坐标轴的某个位置n种了一棵树, 并且每隔m米就再种一棵树, 注意是双向的, 两边都种; 给定一个区间, 问这个区间中有多少棵树;
解题思路
我们可以让区间的边界都减去n, 这样区间中的树都位于坐标km上; 然后我们把边界都平移到正数区间, 设f(x)是从0到x有多少棵树, 则f(r) - f(l - 1)即为所求;
本题有坑点, f(x) = x / m 下取整, 如果x为负数则不符合, 所以需要先变成正数;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
signed main() {
int a, b, res = 0;
cin >> n >> m >> a >> b;
a -= n, b -= n;
if(a < 0){
int x = -a / m + 1;
a += x * m;
b += x * m;
}
res = b / m - (a - 1) / m;
cout << res;
return 0;
}
C - Socks 2
难度: ⭐⭐
题目大意
小莫有n双不同颜色的袜子, 某天小莫丢失了m只不同颜色的袜子, 也就是说有m种颜色的袜子只剩一只了; 小莫现在想把剩下的所有袜子两两组合, 设颜色a和b的袜子组合, 则差异值为|a - b|, 问总的差异值最小为多少;
解题思路
很容易可以证得没有缺失的袜子还是和自己组合就好, 只需要考虑如何把落单的袜子组合; 先把这m只袜子按照颜色从小到大排序; 如果m为偶数, 那么也很容易证得就是让相邻的两个袜子组合, 即Xi和Xi+1; 如果为奇数则需要丢弃一只, 这个我们只需要遍历求解即可; 我们可以先按偶数情况求解, 减去奇数位置的颜色, 加上偶数位置的颜色; 如果丢弃第x个袜子, 那么保留前x - 1的值, 然后把x往后的值取反, 因为去掉x后, 后面袜子位置的奇偶性就都变了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res, sum;
int p[N];
signed main() {
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> p[i];
if(i % 2) res -= p[i];
else res += p[i];
}
if(m % 2) {
sum = res;
res += p[m];
int x = 0, y;
for(int i = 1; i <= m; i++ ){
if(i % 2) y = -p[i];
else y = p[i];
res = min(res, x - (sum - y - x));
x += y;
}
}
cout << res;
return 0;
}
D - Reindeer and Sleigh
难度: ⭐⭐
题目大意
给定n个雪橇, 其中第i个雪橇需要pi个驯鹿来拉; 给出m个询问, 每个询问给定现有驯鹿数量, 问最多可以拉多少个雪橇;
解题思路
一道直接的二分; 先把雪橇按照pi从小到大排序然后求出前缀和; 对于每个询问用二分查找最合适的前缀和即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int p[N], s[N];
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> p[i];
}
sort(p + 1, p + 1 + n);
for(int i = 1; i <= n; i ++ ){
s[i] = s[i - 1] + p[i];
}
while(m--){
int x;
cin >> x;
int l = 0, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(s[mid] > x) r = mid - 1;
else l = mid;
}
cout << l << endl;
}
return 0;
}
E - Christmas Color Grid 1
难度: ⭐⭐⭐
题目大意
给定一个n * m的网格, 每个格子被染成红色或者绿色; 我们可以任意选择一个红色格子将其染为绿色, 然后会得到当前绿色格子连通块的数量, 问绿色格子连通块的数量期望是多少, 对mod取模;
解题思路
也是比较直接的一道题, 我们可以先得到未处理前网格中绿色格子连通块的数量; 对于某个红色格子, 将其染色后, 新的绿色格子连通块的数量就是 原数量减去与该格子相邻的不同连通块的数量后加一; 期望数量的分母就是原网格中红色格子的数量;
需要注意的时候, 我一开始用map<PII, PII>来存连通块的父节点, 结果会超时, 改为二维数组后就没事了, 应该是占内存太大了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
char g[N][N];
PII p[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int qmi(int a, int b){
int res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
PII find(int x, int y){
if(p[x][y] != make_pair(x, y)){
p[x][y] = find(p[x][y].first, p[x][y].second);
}
return p[x][y];
}
signed main() {
IOS;
cin >> n >> m;
int num = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> g[i][j];
p[i][j] = {i, j};
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(g[i][j] == '#'){
bool f = false;
for(int k = 0; k < 2; k++){
int x = i + dx[k], y = j + dy[k];
if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '#'){
PII pa = find(i, j);
p[pa.first][pa.second] = find(x, y);
}
}
}
else num++;
}
}
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
if (g[i][j] == '#' && find(i, j) == make_pair(i, j)) idx++;
}
}
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(g[i][j] != '#'){
set<PII> s;
for(int k = 0; k < 4; k++){
int x = i + dx[k], y = j + dy[k];
if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '#'){
s.insert(find(x, y));
}
}
int a = idx - s.size() + 1;
res += a;
}
}
}
cout << res % mod * qmi(num, mod - 2) % mod;
return 0;
}
F - Christmas Present 2
难度: ⭐⭐⭐⭐
- Beginner AtCoder Contest 334beginner atcoder contest 334 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 327 beginner atcoder contest 332