【】
A - 添加逗号
注意是从后往前三个三个加逗号，最前面不允许有逗号
#includeusing namespace std; const int maxn = 1e5 + 10;char s[maxn];char ans[maxn];int sz; int main() { scanf("%s", s); int len = strlen(s); sz = 0; int t = 0; for(int i = len - 1; i >= 0; i --) { ans[sz ++] = s[i]; ans[sz] = 0; t ++; if(t % 3 == 0 && i != 0) ans[sz ++] = ',', ans[sz] = 0; } len = strlen(ans); for(int i = len - 1; i >= 0; i --) { printf("%c", ans[i]); } printf("\n"); return 0;}
B - 对称
可以递归求解。
#includeusing namespace std; long long n, m; long long work(long long r, long long c) { if(r % 2 == 0 || c % 2 == 0) return 0LL; return 4 * work(r / 2, c / 2) + 1LL;} int main() { scanf("%lld%lld", &n, &m); printf("%lld\n", work(n, m)); return 0;}
C - 竞赛技巧
排序。
#includeusing namespace std; const int maxn = 1e5 + 10;struct X{ int h, m, s; void out() { printf("%d %d %d\n", h, m, s); }}s[maxn];int n; bool cmp(const X&a, const X&b) { if(a.h != b.h) return a.h < b.h; if(a.m != b.m) return a.m < b.m; return a.s < b.s;} int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d%d%d", &s[i].h, &s[i].m, &s[i].s); } sort(s + 1, s + 1 + n, cmp); for(int i = 1; i <= n; i ++) { s[i].out(); } return 0;}
D - 训练技巧
设$dp[0][i]$表示以$i$为结尾的最大价值，$dp[1][i]$表示$j(j < i)$为结尾的最大价值。可见，该$dp$为$O(n^2)$效率的。
显然，$dp[0][i] = \mathop {\max }\limits_{j = i - k}^{i - 1} (dp[1][j] + i - j) = i + \mathop {\max }\limits_{j = i - k}^{i - 1} (dp[1][j] - j)$。
只要维护$dp[1][j] - j$的最大值即可，用单调队列 or 线段树就可以了。
#includeusing namespace std; const int maxn = 1e5 + 10;int n, k;long long a[maxn];long long dp[2][maxn];long long sum[maxn]; int q[5 * maxn];int first, last; bool check2(int a, int b) { if(dp[1][b] - dp[1][a] > sum[b] - sum[a]) return 1; return 0;} int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; i ++) { scanf("%lld", &a[i]); sum[i] = sum[i - 1] + a[i]; } /* dp[0][i] // 以i结尾 dp[1][i] // 不以i结尾 */ first = 0, last = -1; for(int i = 1; i <= k; i ++) { dp[0][i] = sum[i]; dp[1][i + 1] = max(dp[0][i], dp[1][i]); while(1) { if(last - first + 1 == 0) break; if(check2(q[last], i)) last --; else break; } last ++; q[last] = i; } for(int i = k + 1; i <= n; i ++) { while(1) { if(last < first) break; if(i - q[first] > k) first ++; else break; } /* printf("debug %d: ", i); for(int i = first; i <= last; i ++) { printf("%d ", q[i]); } printf("\n"); */ dp[0][i] = dp[1][q[first]] + sum[i] - sum[q[first]]; dp[1][i + 1] = max(dp[0][i], dp[1][i]); while(1) { if(last - first + 1 == 0) break; if(check2(q[last], i)) last --; else break; } last ++; q[last] = i; /* printf("debug %d: ", i); for(int i = first; i <= last; i ++) { printf("%d ", q[i]); } printf("\n"); */ } for(int i = 1; i <= n; i ++) { // printf("%d %lld %lld\n", i, dp[0][i], dp[1][i]); } long long ans = 0; for(int i = 1; i <= n; i ++) { ans = max(ans, dp[0][i]); ans = max(ans, dp[1][i]); } printf("%lld\n", ans); return 0;}
E - 这是一个数学题
化简之后可以发现$A_i = A_0*\frac{n-i}{n} + A_n*\frac{i}{n}$，这样就很容易求解了。
import java.math.BigDecimal;import java.math.BigInteger;import java.util.*; public class Main { static Scanner cin = new Scanner(System.in); public static void main(String[] args) { int n = cin.nextInt(); long a0 = cin.nextLong(); long an = cin.nextLong(); int Q = cin.nextInt(); while(Q -- > 0) { long L = cin.nextLong(); long R = cin.nextLong(); long len = R - L + 1; BigInteger ans = BigInteger.ZERO; BigInteger A = BigInteger.ZERO;; BigInteger B = BigInteger.ZERO;; long x = len * n; long y = (L + R) * len / 2; A = BigInteger.valueOf(x).subtract(BigInteger.valueOf(y)); A = A.multiply(BigInteger.valueOf(a0)); A = A.divide(BigInteger.valueOf(n)); B = BigInteger.valueOf(an).multiply(BigInteger.valueOf(y)).divide(BigInteger.valueOf(n)); ans = A.add(B); System.out.println(ans); } }}
F - 大佬的生日大礼包
如果$x$个人能满足，那么$[0,x]$个人都能满足，依据这个性质，我们可以对答案进行二分。
接下来就是验证$x$个人能否满足：
首先观察到，无论是哪一种大礼包，都会用掉一个U盘和一个鼠标，除此之外，每种礼包再外加一个物品。
因此U盘或者鼠标数量不足$x$个，则无解。
将U盘和鼠标数量都减去$x$个后，问题就变成了：三种物品分别有$p_0$，$p_1$，$p_2$个，问是否存在排列方案使得相邻两个物品种类不同。
只要验证$\sum_{i=0}^2min(p_i, \frac{x+1}{2})$和$x$的大小关系即可。
#includeusing namespace std; int T, a, b ,c; int check(int x) { int p[3]; p[0] = a - x; p[1] = b - x; p[2] = c; if(p[0] < 0 || p[1] < 0) return 0; for(int i = 0; i < 3; i ++) { p[i] = min(p[i], (x + 1) / 2); } if(p[0] + p[1] + p[2] >= x) return 1; return 0;} int main() { scanf("%d", &T); while(T --) { scanf("%d%d%d", &a, &b, &c); int L = 0, R = a + b + c, ans = 0; while(L <= R) { int mid = (L + R) / 2; if(check(mid)) ans = mid, L = mid + 1; else R = mid - 1; } printf("%d\n", ans); } return 0;}
G - 零下e度
公式1：$\frac{1}{e}= \sum_{i = 0}^{\infty} (-1)^i\frac{1}{i!}$
公式2：$e= \sum_{i = 0}^{\infty} \frac{1}{i!}$
知道上面这个公式就会做了。这题卡常数，$mod$如果不是const定义的话容易超时。
#includeusing namespace std; const int mod = 998244353LL;long long ans;int n; int main() { scanf("%d", &n); long long u = 1; int p = (n % 2) ? -1 : 1; for(int i = n; i >= 1; i --) { ans = (ans + p * u + mod) % mod; u = (u * i) % mod; p = p * -1; } ans = (ans + u) % mod; printf("%lld\n", ans); return 0;}
H - 酸碱滴定
模拟题。
#includeusing namespace std;double eps = 1e-8;double work(double x) { int a = x * 10000; int b = a / 10 % 10; if(b < 5) return (int)(a / 100) / 100.0; else if(b > 5) return ((int)(a / 100) + 1) / 100.0; else { if (x * 10000 - a > eps) return ((int)(a / 100) + 1) / 100.0; else { if (a / 100 % 10 % 2) return ((int)(a / 100) + 1) / 100.0; else return (int)(a / 100) / 100.0; } }}int main() { int T; scanf("%d", &T); while(T --) { double a, b, c; scanf("%lf%lf%lf", &a, &b, &c); printf("%.2lf\n", work(a * c / b)); } return 0;}
I - 合成反应
暴力，每次判断那些还不能执行的方程式，直到不能增加元素为止。
#includeusing namespace std; const int maxn = 1e5 + 10;int f[maxn];int a[maxn], b[maxn], c[maxn];int q, n, k, m;set st; int main() { scanf("%d%d%d%d", &k, &n, &m, &q); for(int i = 1; i <= n; i ++) { scanf("%d%d%d", &a[i], &b[i], &c[i]); st.insert(i); } for(int i = 1; i <= m; i ++) { int x; scanf("%d", &x); f[x] = 1; } vector vec; while(!st.empty()) { set ::iterator it; vec.clear(); for(it = st.begin(); it != st.end(); it ++) { int id = *it; if((f[a[id]] && f[b[id]]) || f[c[id]]) { f[a[id]] = 1; f[b[id]] = 1; f[c[id]] = 1; vec.push_back(id); } } if(vec.size() == 0) break; for(int i = 0; i < vec.size(); i ++) { st.erase(vec[i]); } } while(q --) { int x; scanf("%d", &x); printf("%s\n", f[x] ? "Yes" : "No"); } return 0;}
J - 同分异构体
手算 or OEIS
#includeusing namespace std; int ans[] = {1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159}; int main() { int n; scanf("%d", &n); printf("%d\n", ans[n]); return 0;}