T1
先来一张图(代表我在考场做此题的心境, 暴躁的Aliemo):
solution:
我们可以发现1582.10.5是第2299161, 然后呢我们可以以这个来处理
在这个日期之前的, 我们计算有几个4年,1年, 1月, 再加上天数
在这个日期之后, 我们先判断判断到1583年, 然后继续400年, 一年, 一月的减
Code:
/**
* Author: Aliemo
* Data:
* Problem:
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define rr register
#define inf 1e9
#define MAXN 100010
using namespace std;
inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int r, d, m, y;
int D[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool judge(int y) {
if (y <= 1582) return (y % 4 == 0);
return (y % 400 == 0) || (y % 4 == 0 && y % 100 != 0);
}
inline void solve1() {
d = 1, m = 1, y = -4712;
int cnt = (r / (3 * 365 + 366));
y += 4 * cnt, r -= cnt * (3 * 365 + 366);
for (rr int i = 1; i <= 3; i++) {
int delta = 365 + judge(y);
if (delta > r) break;
y++, r -= delta;
}
for (rr int i = 1; i <= 12; i++) {
int delta = D[i] + (i == 2 && judge(y));
// cout << r << "
";
if (delta > r) break;
m++, r -= delta;
}
d += r;
}
inline void solve2() {
r -= 2299161;
d = 15, m = 10, y = 1582;
if (r <= 16) {
d += r;
return ;
}
d = 1, m++, r -= 17;
if (r < 30) {
d += r;
return ;
}
m++, r -= 30;
if (r < 31) {
d += r;
return ;
}
m = 1, y++, r -= 31;
int cnt = r / (97 * 366 + 303 * 365);
y += 400 * cnt, r -= cnt * (97 * 366 + 303 * 365);
for (rr int i = 1; i <= 400; i++) {
int delta = 365 + judge(y);
if (delta > r) break;
y++, r -= delta;
}
for (rr int i = 1; i <= 12; i++) {
int delta = D[i] + 1 * (i == 2 && judge(y));
if (delta > r) break;
m++, r -= delta;
}
d += r;
}
signed main() {
int T = read();
while (T--) {
r = read();
if (r < 2299161) solve1();
else solve2();
if (y <= 0) cout << d << " " << m << " " << -y + 1 << " " << "BC" << "
";
else cout << d << " " << m << " " << y << "
";
}
}
T2
这题爆掉了unsigned long long(妈的绝了)
solution
我们发现, 对于每一位来说, 只要当前这位没有在已知饲料中出现过, 那么总的种数就处于 (2)
然后在减去 (n) 就好了
我们先看一共有(2^k) 种, 正好爆掉了unsigned long long, 我们可以先求(2^{k - 1}) 然后最后的乘以2即可
然后呢, 对于最后的答案为 (2^{64}) 的时候, 我们直接特判一下就好了啊
Code:
// Author:Aliemo
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define MAXN 100010
#define inf 1e9
using namespace std;
const int mod = 1e9 + 7;
int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(unsigned long long x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int n, m, c, k;
unsigned long long ans;
int kin1[70], kin2[70];
unsigned long long p[70];
signed main() {
// freopen("zoo.in", "r", stdin);
// freopen("zoo.out", "w", stdout);
n = read(), m = read(), c = read(), k = read();
p[0] = 1;
for (int i = 1; i <= k; i++) p[i] = p[i - 1] + p[i - 1];
ans = p[k - 1];
for (int i = 1; i <= n; i++) {
unsigned long long q;
cin >> q;
for (int i = k - 1; i >= 0; i--) {
if (q >= p[i]) {
q -= p[i];
kin1[i] = 1;
}
}
}
while (m--) {
int p = read(), q = read();
if (!kin1[p] && !kin2[p]) {
kin2[p] = 1;
ans /= 2ll;
}
}
if (n == 0 && ans == p[k - 1]) cout << "18446744073709551616";
else cout << ans * 2ll - n;
fclose(stdin);
fclose(stdout);
return 0;
}
T3
solution
一看, 好像可以用线段树做, 建一个DAG, 然后遍历的的时候用线段树处理, 好像可以做诶, 然后就那道了30分暴力分
那怎么做呢, 可以来一次拓扑排序, 然后跑个DP
可以参考: CSP 2020-S 题解
Code:
/**
* Author: Aliemo
* Data:
* Problem:
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
#define rr register
#define inf 1e9
#define MAXN 100010
using namespace std;
const int mod = 998244353;
inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)0) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int n, m, q_num;
int t[MAXN], pos[MAXN], c[MAXN], into[MAXN], q[MAXN], a[MAXN], val[MAXN], cnt[MAXN], mul[MAXN];
vector<int> v[MAXN];
int dfs(int x) {
if (mul[x] != -1) return mul[x];
if (t[x] != 3) {
mul[x] = (t[x] == 1) ? 1 : val[x];
return mul[x];
}
mul[x] = 1;
for (rr int i = c[x] - 1; i >= 0; i--) {
int v_ = v[x][i];
mul[x] = mul[x] * dfs(v_) % mod;
}
return mul[x];
}
inline void Topsort() {
queue<int> q;
for (rr int i = 1; i <= m; i++) if (!into[i]) q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
int prod = 1;
for (rr int i = c[x] - 1; i >= 0; i--) {
int v_ = v[x][i];
cnt[v_] = (cnt[v_] + prod * cnt[x] % mod) % mod;
into[v_]--;
if (!into[v_]) q.push(v_);
prod = prod * mul[v_] % mod;
}
}
for (rr int i = 1; i <= m; i++)
if (t[i] == 1)
a[pos[i]] = (a[pos[i]] + val[i] * cnt[i] % mod) % mod;
}
signed main() {
n = read();
for (rr int i = 1; i <= n; i++) a[i] = read();
m = read();
for (rr int i = 1; i <= m; i++) {
t[i] = read();
if (t[i] == 1) pos[i] = read(), val[i] = read();
else if (t[i] == 2) val[i] = read();
else if (t[i] == 3) {
c[i] = read();
for (rr int j = 1; j <= c[i]; j++) {
int v_ = read();
v[i].push_back(v_);
into[v_]++;
}
}
}
memset(mul, -1, sizeof mul);
for (rr int i = 1; i <= m; i++)
if (!into[i])
mul[i] = dfs(i);
q_num = read();
for (rr int i = 1; i <= q_num; i++) q[i] = read();
int prod = 1;
for (rr int i = q_num; i; i--) {
cnt[q[i]] = (prod + cnt[q[i]]) % mod;
prod = prod * mul[q[i]] % mod;
}
for (rr int i = 1; i <= n; i++) a[i] = a[i] * prod % mod;
Topsort();
for (rr int i = 1; i <= n; i++) cout << a[i] << " ";
}
T4
solution
对于 (20\%) , 当蛇能吃就必须一直吃 否则就不吃, 然后呢, 能吃的时候答案就是 (1) , 否则答案就是 (3)
对于 (70\%),
具体如何操作呢, 尝试直接模拟, 发现需要一个能够查询最大值, 最小值, 和删除修改得数据结构, 这不是平衡树么?
那我们如何具体维护呢?
请见LB
考虑如何求得第一个操作不进行的回合, 考虑现在正在操作着的蛇, 只有它在吃掉体力最小的蛇后的所有回合中都不会被吃掉, 操作才会进行.
所有回合指该回合后, 知道第一个一定不会进行操作的回合, 考虑倒序枚举操作序列, 标记所有蛇是否被消除, 枚举到被删除蛇时判读即可,
答案为第一个不会进行的回合时, 剩下的蛇的数量.
那么这个回合怎么找呢?
先找出操作序列, 然后倒序操作
对于 (100\%), 这太难了, 我要知难而退 放个链接: 题解 贪吃蛇 - fight for dream - 洛谷博客
Code:
/**
* Author: Aliemo
* Data:
* Problem:
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <deque>
#define int long long
#define rr register
#define inf 1e9
#define MAXN 1000010
using namespace std;
inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int T, n;
struct Deque {
int b[MAXN * 20], *a = b + MAXN * 10;
int qian = 1, hou = 0;
Deque () {}
inline void push_back(int x) { a[++hou] = x;}
inline void push_front(int x) {a[--qian] = x;}
inline bool empty() { return (qian > hou);}
inline int size() {return hou - qian + 1;}
inline int front() { return a[qian];}
inline int back() { return a[hou];}
inline void pop_back() { hou--;}
inline void pop_front() { qian++;}
}q1, q2;
// deque<int> q1, q2;
int val[MAXN], a[MAXN];
inline void build() {
while (!q1.empty()) q1.pop_front();
while (!q2.empty()) q2.pop_front();
q1.push_back(n);
val[n] = a[n];
for (rr int i = 1; i < n; i++) q2.push_back(i), val[i] = a[i];
}
inline int ncmp(int x, int y) {
if (x == y) return 0;
else if (val[x] > val[y]) return 1;
else if (val[x] < val[y]) return -1;
else if (x < y) return -1;
else return 1;
}
bool check() {
if (q1.size() == 1) return 0;
if (q1.size() == 2) return 1;
int x = q1.front();
q1.pop_front();
int y = q1.back();
q1.pop_back();
val[y] -= val[x];
if (ncmp(y, q1.front()) < 0) {
q1.push_front(y);
return !check();
}
return 1;
}
inline bool calc() {
if (q2.empty()) return 0;
int x = q1.back();
q1.pop_back();
int y = q2.front();
q2.pop_front();
val[x] -= val[y];
while (!q2.empty() && ncmp(x, q2.back()) < 0) {
q1.push_front(q2.back());
q2.pop_back();
}
q1.push_front(x);
if (!q2.empty()) return 1;
if (!check()) return 1;
return 0;
}
inline int solve() {
build();
int ans = n;
while (calc()) ans--;
return ans;
}
signed main() {
T = read() - 1;
n = read();
for (rr int i = 1; i <= n; i++) a[i] = read();
cout << solve() << "
";
while (T--) {
int k = read();
for (rr int i = 1; i <= k; i++) {
int x = read(), y = read();
a[x] = y;
}
cout << solve() << "
";
}
}