儒略日
模拟题，放一个好实现的代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
typedef long long ll;
typedef pair<int, int> pii;
int T, n, ans[N][3];
int d1, d2, d3 = 3000000;
int getDay(int y, int m) {if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) return 31;if (m == 4 || m == 6 || m == 9 || m == 11) return 30;if (y < 0) y++;if (y <= 1582) return y % 4 == 0 ? 29 : 28;else return ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) ? 29 : 28;
}
void nextDay(int &y, int &m, int &d) {if (y == 1582 && m == 10 && d == 4) {d = 15;return ;}if (d < getDay(y, m)) d++;else {d = 1;if (m == 12) {m = 1;if (y == -1) y = 1;else y++;} else m++;}
}
int main() {int y = -4713, m = 1, d = 1;for (int i = 0; i <= d3; i++) {ans[i][0] = y, ans[i][1] = m, ans[i][2] = d;if (y == 1600 && m == 1 && d == 1) d1 = i;if (y == 2000 && m == 1 && d == 1) d2 = i - d1; //周期nextDay(y, m, d);}scanf("%d", &T);while (T--) {ll x;scanf("%lld", &x);if (x <= d3) {if (ans[x][0] < 0) printf("%d %d %d BC\n", ans[x][2], ans[x][1], -ans[x][0]);else printf("%d %d %d\n", ans[x][2], ans[x][1], ans[x][0]);} else {ll t = (x - d1) / d2, y = x - t * d2;printf("%d %d %lld\n", ans[y][2], ans[y][1], ans[y][0] + 400 * t);}}return 0;
}
动物园
贪心宝宝题。注意边界。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int n, m, k, c, b[64], d[N];
ll a[N];
map<int, int>mp;
vector<pii>l;
int main() {scanf("%d%d%d%d", &n, &m, &c, &k);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]); for (int j = 0; j < 64; j++)if (a[i] & (1ll << j)) b[j] = 1;}for (int i = 1; i <= m; i++) {int p, q;scanf("%d%d", &p, &q);if (b[p]) mp[q] = 1;else l.push_back({p, q});}for (auto [p, q] : l) if (!mp[q]) d[p] = 1;int s = 0;for (int i = 0; i < 64; i++) if (d[i]) s++;if (k == 64 && s == 0) {if (n == 0) puts("18446744073709551616");else printf("%llu\n", -(ull)n);} else printf("%lld\n", (1ll << (k - s)) - n);return 0;
}
函数调用
首先类似线段树模板 2，如果我们直接模拟一个函数，就可以得到一个长度为 \(n\) 的数组表示加法标记，以及一个数表示乘法标记。
正着做是困难的，我们考虑倒过来，假设一个函数后面的函数的乘法标记是 \(mul\), 那么这个函数得到的所有加法标记都会 \(\times mul\), 这个东西等价于函数被调用了 \(mul\) 次，如果这个函数是会调用其它函数的，那么它调用的函数的调用次数要加上它的调用次数 \(\times mul\), 根据这个，先记忆化求出每个点的乘法标记，再拓扑排序即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {#ifdef ONLINE_JUDGEreturn ;#endifcout << arg << ' ';dbg(args...);
}
int n, m, Q, typ[N], in[N], f[N];
ll a[N], p[N], val[N], vis[N], t[N], mul[N], add[N];
vector<int>e[N];
inline ll dfs(int u) {if (mul[u] != -1) return mul[u];if (typ[u] == 1) return mul[u] = 1;if (typ[u] == 2) return mul[u] = val[u];mul[u] = 1;for (auto v : e[u]) mul[u] = mul[u] * dfs(v) % mod;return mul[u];
}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}memset(mul, 255, sizeof mul);cin >> m;for (int i = 1; i <= m; i++) {cin >> typ[i];if (typ[i] == 1) {cin >> p[i] >> val[i];} else if (typ[i] == 2) {cin >> val[i];} else {int k;cin >> k;while (k--) {int x;cin >> x;++in[x];e[i].push_back(x);}reverse(e[i].begin(), e[i].end());}}cin >> Q;for (int i = 1; i <= Q; i++) cin >> f[i], e[0].push_back(f[i]), ++in[f[i]];reverse(e[0].begin(), e[0].end());for (int i = 0; i <= m; i++) if (mul[i] == -1) dfs(i);queue<int>q;q.push(0);t[0] = 1;for (int i = 1; i <= m; i++) if (!in[i]) q.push(i);while (!q.empty()) {int u = q.front(); q.pop();ll fac = 1;for (auto v : e[u]) {t[v] = (t[v] + t[u] * fac) % mod;// dbg("###", u, v, fac, t[v]);fac = fac * mul[v] % mod;if (!--in[v]) q.push(v);}}for (int i = 1; i <= n; i++) {a[i] = a[i] * mul[0] % mod;}for (int i = 1; i <= m; i++) {if (typ[i] == 1) a[p[i]] = (a[p[i]] + val[i] * t[i]) % mod;}for (int i = 1; i <= n; i++) {cout << a[i] << " \n"[i == n]; }return 0;
}
贪吃蛇
首先是一个观察：由于蛇很智慧，所以如果能轮到它决策，它就绝对不会死，因为如果它预料到它会死它就会直接选择结束。
分讨一条蛇吃完后的情况：
- 如果这条蛇吃完之后还是最强的，那么肯定会吃
- 如果不是最强的也不是最弱的，那么下一轮是次强的决策，且这时候最弱的变为了原先次弱的，所以如果次强蛇吃了，次强蛇就会比最强蛇小，如果最强蛇死了，那么次强蛇必定先死，由于次强蛇能够决策，所以它肯定不会死，所以最强蛇也不会死。
- 是最弱的。那么假设现在开始每条决策的蛇是 \(1, 2, 3, \cdots, k\), 如果 \(1\) 吃了之后变成了最弱的，由 \(2\) 决策，如果 \(2\) 吃了 \(1\) 不是最弱的，那根据第二点，\(1\) 会死，\(1\) 知道这点，不会吃。否则，\(2\) 需要看 \(3\) 来决定吃不吃，如果 \(2\) 会吃 \(1\)，\(1\) 就会选择结束，否则 \(1\) 会吃，对于 \(2\) 也同理，同时 \(3\) 需要依赖 \(4\), 以此类推，如果只剩两条蛇了，那么当前决策的蛇肯定不敢吃，不然会被最后一条吃掉，所以我们发现如果 \(k\) 是奇数就会吃。并且吃了之后 \(2\) 也不会吃了，因为 \(2\) 变成了新的 \(1\), \(k\) 变成了偶数，所以一旦出现这种情况，最多再吃一次了。
这样可以直接 set 维护最大值和最小值，时间复杂度 \(\mathcal{O}(Tn \log n)\)。
考虑经典 trick 把队列当优先队列做，需要满足每次入队的点有单调性，首先一开始的蛇本身有单调性，其次根据第二点的观察，如果一条蛇吃了，那肯定会比上一条吃了的蛇弱，所以再开一个队列维护吃过的蛇，每次入队即可。
时间复杂度 \(\mathcal{O}(Tn)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 1e6 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
int T, n, a[N];
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> T >> n;for (int tc = 1; tc <= T; tc++) {if (tc == 1) for (int i = 1; i <= n; i++) cin >> a[i];else {int k, x, y; cin >> k;while (k--) { cin >> x >> y; a[x] = y; }}deque<pii>q1, q2;for (int i = 1; i <= n; i++) q1.push_back({a[i], i});int ans;while (1) {if (q1.size() + q2.size() == 2) {ans = 1;break;}int x, y, id; y = q1.front().first; q1.pop_front();if (q2.empty() || (!q1.empty() && q1.back() > q2.back())) { tie(x, id) = q1.back(); q1.pop_back(); } else { tie(x, id) = q2.back(); q2.pop_back(); }pii now = {x - y, id};if (q1.empty() || q1.front() > now) {ans = q1.size() + q2.size() + 2; int cnt = 0;while (1) {cnt ^= 1;if (q1.size() + q2.size() == 1) { if (!cnt) ans--; break; }if (q2.empty() || (!q1.empty() && q1.back() > q2.back())) { tie(x, id) = q1.back(); q1.pop_back(); } else { tie(x, id) = q2.back(); q2.pop_back(); }now = {x - now.first, id};if ((q1.empty() || now < q1.front()) && (q2.empty() || now < q2.front())) continue;if (!cnt) ans--;break;}break;} else q2.push_front(now);}cout << ans << '\n';}return 0;
}