A - Water Station
题目大意
给定一个0~100之间的数, 输出离它最近的5的倍数
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10,mod= 998244353;
int n, m;
signed main() {
cin >> n;
m = n % 5;
if (m > 2) n = n + (5 - m);
else n = n - m;
cout << n;
return 0;
}
B - ABCDEFG
题目大意
给出A~G七个字母, 以及每个字母之间的权值, 输入两个字母, 输出两个字母之间的权重总和;
解题思路
前缀和签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 10;
int n, m, k;
int d[] = { 0,3,1,4,1,5,9 };
int s[N];
signed main() {
for (int i = 1; i <= 6; i++) s[i] = s[i - 1] + d[i];
char a, b;
cin >> a >> b;
n = min(a - 'A', b - 'A');
m = max(a - 'A', b - 'A');
cout << s[m] - s[n];
return 0;
}
C - Snuke the Cookie Picker
题目大意
给定一个由' . '组成的矩阵, 这个矩阵内部有个由'#'组成的小矩阵, 但是这个小矩阵有一个位置仍是' . ', 找出这个位置;
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
int n, m, k;
char g[N][N];
signed main() {
cin >> n >> m;
int l=N, r=0, u=N, d=0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
if (g[i][j] == '#') {
l = min(l, i);
r = max(r, i);
u = min(u, j);
d = max(d, j);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '.') {
if (i >= l && i <= r && j >= u && j <= d) {
cout << i << ' ' << j;
return 0;
}
}
}
}
return 0;
}
D - Sleep Log
题目大意
小莫展示了他一天的作息时间, 给出了n个时间点, 第1个时间点为0, 都2i个时间点和第(2i+1)个时间点之间是小莫的睡眠时间, 其余时间为清醒时间, 给出m组询问, 每组询问是输入两个时间点, 问这个时间段内小莫的睡眠时间;
解题思路
这个题看着简单, 实际做起来其实还是有许多需要思考的点; 因为时间最多到1e9级别, 而n只有1e5级别, 所以我们可以对时间段进行处理; 对于n个时间点就有(n-1)个时间段, 我们对每个时间段进行编号, 睡眠时间段的值就是时间差, 而清醒时间段为0, 然后求时间段的前缀和; 此外我们可以让两个时间点中较大的那个代表整个时间段 (这个可以用map进行映射), 从而判断询问给出的时间点位于哪个时间段内; 然后在询问中, 对于两个时间点, 我们可以先用二分找到第一个大于等于它的时间点, 这样就可以找到包围询问时间段的两个时间段, 用前缀和得到大致答案后, 再对首尾的两个时间段进行具体的减补;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k,z;
vector<int>v;
map<int, int> mp;
int g[N];
bool st[N];
signed main() {
cin >> n;
int maxn = 0;
cin >> z;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (i % 2 == 0) {
g[i] = x - z;
st[i] = true;
}
else st[i] = false;
z = x;
v.push_back(x);
mp[x] = i;
}
for (int i = 1; i < n; i++) g[i] += g[i - 1];
cin >> m;
for (int i = 1; i <= m; i++) {
int res = 0;
int a, b;
cin >> a >> b;
auto l = lower_bound(v.begin(), v.end(), a) - v.begin();
auto r = lower_bound(v.begin(), v.end(), b) - v.begin();
int l1 = mp[v[l]];
int r1 = mp[v[r]];
res += g[r1] - g[l1];
if (st[l1]) res += v[l] - a;
if (st[r1]) res -= v[r] - b;
cout << res << endl;
}
return 0;
}
E - Art Gallery on Graph
题目大意
给定一个图, 有n个点和m条边, 每条边的权值为1; 然后又给出k个保安, 每个保安都位于不同的点上, 我们乘这些点为监视点, 每个保安都有一个视野范围h, 凡是与监视点距离小于等于h的点都会被监视, 问都有哪些点被监视了(包括监视点), 升序输出;
解题思路
因为n, m, k, 都是1e5级别的, 所以不能用bfs, 所以我想着只能从边入手, 但是一直没有思路; 然后看了看佬的题解, 发现了一个炒鸡牛逼的做法; 我们先找出所有视野范围h中的最大值max, 我们可以另外创建一个点x, 让x连接所有监视点, 然后最牛逼的来了, 我们让x到监视点之间的权值为max-hi (hi为各自的视野范围); 这样我们从x点出发, 找到所有与x距离小于等于max的点就是被监视的点了; 于是这个题就变成了最短路问题;(真的太强了 Orz); 为了防止监视点通过x到达其他点, 我们可以让监视点到x的权值为无穷;
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k, ini, idx;
int h[N], w[N], e[N], ne[N], d[N];
bool st[N];
set<int> s;
vector<PII> v;
void add(int a, int b,int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c; h[a] = idx++;
}
void dijkstra() {
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({ 0,ini });
memset(d, 0x3f, sizeof d);
d[ini] = 0;
while (q.size()) {
auto t = q.top();
q.pop();
int x = t.second;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[x] + w[i]) {
d[j] = d[x] + w[i];
q.push({ d[j],j });
}
}
}
}
signed main() {
memset(h, -1,sizeof h);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b,1);
add(b, a,1);
}
ini = n + 1;
int maxn = 0;
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
maxn = max(maxn, b);
v.push_back({ a,b });
s.insert(a);
}
for (auto t : v) {
int a = t.first;
int b = t.second;
add(ini, a, maxn - b);
add(a, ini, 0x3f3f3f3f);
}
dijkstra();
for (int i = 1; i <= n; i++) {
if (d[i] <= maxn) s.insert(i);
}
cout << s.size() << endl;
for (int x : s) {
cout << x << ' ';
}
return 0;
}
F - Art Gallery on Graph
题目大意
小莫和安姐在同一家便利店打工, 给定一个长度为n的字符串代表小莫有一个n天的日程表, 第i个字符为'#'表示小莫第i天要值班, 如果是' . '则是休息; 而安姐也要指定一个日程表, 有如下要求
一是小莫休息的日期, 安姐必须要去值班;
二是安姐会取n的一个因数m(不包括n), 并且让这n天的日程表是以m为周期循环的;
问安姐的日程表一共有多少种可能, 结果对998244353取模;
解题思路
一开始我们可以先把n的所有因数m存起来作为循环节的长度; 然后把字符串里所有' . '的位置p也存起来, 这是已经固定的安排, 在后续操作中我们可以把所有的p通过对m取余来聚集到同一个循环节里进行操作; 在一个长度为a的循环节里, 如果已经有b个' . '; 那么对于剩下的(a-b)个日期里我们有2的(a-b)次方个选择方案;
注意, 对于我们选择的循环节长度a, 它的所有方案中也包括了a的因数作为循环节长度时的方案; 比如a=6时的方案里面就存在a=1, a=2和a=3的所有方案, 所以为了避免重复必须要减去所有a的因数的方案; 对此我们可以用map来存储所有长度的方案;
二是注意对减法运算进行取模时记得要+mod之后再取模, 防止有负数; 因为这个debug了好久...
后来才知道这其实是容斥原理的思想: 求满足s1, s2, s3三个条件其中一个的方案数, 那么就可以求s1 + s2 + s3 - s1∩s2 - s1∩s3 - s2∩s3 + s1∪s2∪s3;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10,mod= 998244353;
int n, m;
vector<int> v1;
vector<int> v2;
set<int> s1;
map<int, int>mp;
char str[N];
int qmid(int a, int b, int c) {
int res = 1;
while (b) {
if (b & 1) res = res * a % c;
a = a * a %c;
b >>= 1;
}
return res;
}
void ini() {
for (int i = 1; i <= n / i; i++) {
if (n % i == 0) {
v2.push_back(i);
if (i == 1) continue;
if (i * i != n) v2.push_back(n / i);
}
}
}
int check(int x,int y) {
int a = (qmid(2, x, mod)+mod)%mod;
for (int i = 1; i <= y / i; i++) {
if (y % i == 0) {
a = (a - mp[i]+mod) % mod;
if (i == 1) continue;
if (i * i != y) a = (a - mp[y/i]+mod) % mod;
}
}
return a;
}
signed main() {
cin >> n >> str+1;
for (int i = 1; i <= n; i++) {
if (str[i] == '.') v1.push_back(i);
}
ini();
sort(v2.begin(), v2.end());
int res = 0;
for (int i = 0; i < v2.size(); i++) {
int x = v2[i];
s1.clear();
for (int j = 0; j < v1.size(); j++) {
int y = v1[j];
if (y > x) {
if (y % x == 0) y = x;
else y = y % x;
}
s1.insert(y);
}
int idx = (x - s1.size())%mod;
mp[x] = check(idx,x);
res = (res +mp[x]) % mod;
}
cout << res;
return 0;
}