A. 儒略日
根据题意直接模拟。我的方法是依次以400, 100, 4, 1为周期计算年份然后再算月日。
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int p4 = 365 * 4 + 1, p100 = 365 * 100 + 25 - 1, p400 = 365 * 400 + 100 - 3;
constexpr int days[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int main() {
int t; readInt(t);
while (t--) {
LL r; readInt(r);
int year = -4712;
auto checkYear = [&]() {
if (year <= 1582) return year % 4 == 0;
return year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
};
auto print = [&]() {
assert(0 <= r && r <= 365);
if (checkYear() && r >= 31 + 28) {
if (r == 31 + 28) {
printf("29 2 ");
if (year <= 0)
printf("%d BC
", -year + 1);
else
printf("%d
", year);
return;
}
r--;
}
int m = 0;
while (r >= days[m]) r -= days[m++];
m++, r++;
if (year <= 0)
printf("%lld %d %d BC
", r, m, -year + 1);
else
printf("%lld %d %d
", r, m, year);
};
auto extend = [&](int pt) {
while (year < pt) {
int span = checkYear() ? 366 : 365;
if (r < span) break;
r -= span, year++;
}
};
int pt = year + r / p4 * 4;
if (pt <= 1582) {
r %= p4, year = pt;
} else {
year = 1580, r -= (1580 + 4712) / 4 * p4;
}
extend(1582);
if (year == 1582) {
if (r >= 277) r += 10;
extend(1600);
}
if (year == 1600) {
year += r / p400 * 400, r %= p400;
if (r >= p100 + 1) {
r--;
year += r / p100 * 100, r %= p100;
}
if (!checkYear() && r >= p4 - 1) r++;
year += r / p4 * 4, r %= p4;
extend(1e9);
}
print();
}
return 0;
}
B. 动物园
处理出已有哪些饲料，这些饲料可以养二进制哪些位为1的动物，答案是可以养的数量减去已有的数量。
注意 (k=64, n = 0) 时会爆 uint64，这里直接用 long double。
实际上，因为所有的 (q_i) 互不相同，所以饲料的需求信息其实没啥用，只要统计哪些位在要求中出现即可。
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
constexpr int N(1e6 + 5);
int n, m, c, k;
using ULL = unsigned long long;
int main() {
readInt(n, m, c, k);
ULL s = 0, ok = 0;
for (int i = 1; i <= n; i++) {
ULL x;
readInt(x);
s |= x;
}
for (int i = 1, x, y; i <= m; i++) {
readInt(x, y);
if (s >> x & 1 ^ 1) ok |= 1ULL << x;
}
long double ans = 1;
for (int i = 0; i < k; i++)
if (ok >> i & 1 ^ 1) ans *= 2;
printf("%.0Lf", ans - n);
return 0;
}
C. 函数调用
题意：有长度为 (n) 的序列 ({a_n}) 和 (m) 个函数。函数只有三种：单点加一个数，序列整体乘一个数，依次调用若干函数（不会出现递归）。求依次调用一些函数后的序列 (a_n)。
考虑每个加操作被之后的乘操作影响了多少，即，求 (delta_i imes num_i) 的系数 (num_i)
数据范围中的树提示我们建图。
如果函数 (f) 调用了函数 (g)，那么连有向边 (f ightarrow g)。因为没有递归，所以是DAG，下面在这个DAG上求解。
设 (multi_i) 表示调用函数 (i) 执行的所有乘法系数之积。
若函数 (f) 依次调用了函数 (g_0, g_1, g_2,dots g_k)，那么 (g_i) 内部的某个加法操作所受的影响可以分为三个部分：
- 内部乘法的影响
- (prod_{j = i + 1}^k multi_j)
- 调用(f)的函数 (F) 的影响。
将第3条 (F) 对其子函数的 影响 也记为 (num_F)。
如果 (F) 只是一个加法操作，那么这个 (num) 就是加法的系数。
转移时，调用 (f) 的函数有 (F_0, F_1, dots, F_K)，则 (num_f=sum left(num_{F_i} imesprod multi_j ight))。
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(1e5 + 5), P(998244353);
inline void inc(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int n, m, a[N], p[N], v[N], d[N];
std::vector<int> g[N];
int multi[N], now[N];
bool vis[N];
void dfs(int x) {
if (vis[x]) return;
vis[x] = 1;
multi[x] = !p[x] && v[x] >= 0 ? v[x] : 1;
for (int y: g[x]) {
dfs(y);
d[y]++;
multi[x] = 1LL * multi[x] * multi[y] % P;
}
}
int main() {
readInt(n);
for (int i = 1; i <= n; i++) readInt(a[i]);
readInt(m);
for (int i = 1; i <= m; i++) {
int opt; readInt(opt);
if (opt == 1)
readInt(p[i], v[i]);
else if (opt == 2)
readInt(v[i]);
else {
readInt(v[i]);
while (v[i]--) {
int x; readInt(x);
g[i].push_back(x);
}
std::reverse(g[i].begin(), g[i].end());
}
}
readInt(v[++m]);
while (v[m]--) {
int x; readInt(x);
g[m].push_back(x);
}
std::reverse(g[m].begin(), g[m].end());
dfs(m);
for (int i = 1; i <= n; i++)
a[i] = 1LL * a[i] * multi[m] % P;
std::queue<int> q;
q.push(m);
now[m] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
if (p[x]) a[p[x]] = (a[p[x]] + 1LL * now[x] * v[x]) % P;
for (int y: g[x]) {
inc(now[y], now[x]);
now[x] = 1LL * now[x] * multi[y] % P;
if (--d[y] == 0) q.push(y);
}
}
for (int i = 1; i <= n; i++)
printf("%d%c", a[i], "
"[i == n]);
return 0;
}
D. 贪吃蛇
题意：给定长度为 (n) 的序列 (a_n) 表示 (n) 条蛇的长度，蛇 (i) 强于 (j) 当且仅当 ((a_i, i)>(a_j, j))。然后从第一轮开始，每轮最强的蛇可以吃掉最菜的蛇并开启下一轮。当某一轮选择不吃则不会开启下一轮。(i) 吃 (j) 会使 (a_i = a_i - a_j)。每条蛇想在不被吃的情况下吃尽可能多的蛇，问每条蛇都采取最优策略时最后会剩多少条蛇。
最优策略一直都挺劝退的。
如果不会选择不吃，那么会进行 (n-1) 轮，最后剩下一条。显然最优策略是这 $n-1 $轮的某个前缀。
第 (i) 轮的决策取决于后面的情况而与已经进行的轮无关，
设 (f(i)) 表示进行完前 (i) 轮（前面的蛇都选择吃）的情况下，总共最多会进行 (f(i)) 轮（在第 (f(i)+1) 轮选择了不吃）。
设第 (i) 轮的最强蛇会在第 (t_i) 轮被吃掉，那么 (f(i)<t_i) 就表示可以吃，否则不可以吃。
那么 (f(i) = min_{j=i+1}^{n-1} j [f(j)ge t_j])。
如果知道这 (n-1) 轮的具体情况， (f) 就可以在线性时间内处理出来，答案就是 (n - f(0))。
用 std::set 维护每轮的蛇，(O(nlog n))，可以得到70分。
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(1e6 + 5);
int n, a[N];
void solve() {
std::set<PII> s;
for (int i = 1; i <= n; i++) s.insert({a[i], i});
static int idx[N], t[N];
for (int i = 1; i <= n; i++) t[i] = 0;
int ans = 1;
for (int i = n; i > 1; i--) {
idx[i] = s.rbegin()->second;
t[s.begin()->second] = i;
PII v = *s.rbegin();
v.first -= s.begin()->first;
s.erase(--s.end());
s.erase(s.begin());
s.insert(v);
}
for (int i = 2; i <= n; i++)
if (t[idx[i]] > ans) ans = i;
printf("%d
", ans);
}
int main() {
int t;
readInt(t, n);
for (int i = 1; i <= n; i++) readInt(a[i]);
for (solve(); t > 1; t--) {
int k, x, y;
readInt(k);
while (k--) {
readInt(x, y);
a[x] = y;
}
solve();
}
return 0;
}
100分的暂时不会，丢个链接，咕咕咕。