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;
}