Codeforces

Berland 年有 $m$ 月，每月 $d$ 天。一周有 $w$ 天。 若第 $x$ 月的第 $y$ 天和第 $y$ 月的第 $x$ 天是同一个星期，则称 $(x,y)$ 是一对。 求一年有几对。 $$ xd+y \equiv yd+x \pmod w $$ 即 $$ (x-y)(d-1) \equiv 0 \Rightarrow (x-y)(d-1) \in w\mathbb{Z} $$ 于是有 $$ y-x = \frac{wk}{\gcd(w,d-1)} $$ 又 $x < y \leqslant \min(m,d)$​， int main() { ll ttt = rr(); while (ttt--) { ll m = rr(), d = rr(), w = rr(); ll g = w / gcd(w, d - 1); ll max_y = min(m, d) - 1; ll div = (max_y + 1) / g, mod = (max_y + 1) % g; ll sum = (div - 1) * div / 2 * g + mod * div; printf("%lld\n", sum); } return 0; }

题目链接：Link 。 A. ABC String 这么水的题竟然 wa 了 4 发。。 题目大意 给定一个长 $n$ 的字符串 $a$，仅由 A，B，C 组成，$n$ 为偶数。 对于仅含 ( 和 ) 的括号序列，当我们能够在其中添加 1 使得其为合法的表达式，则序列合法。 构造合法的长为 $n$ 的括号序列 $b$，要求在 $a$ 同为 A 的，在 $b$ 中也要相同；B，C 也是如此。 分析 序列合法的定义即对任意位置，其左侧的 ) 总比 ( 少，且整体左右括号数相等。 首个字母必为左括号，末尾字母必为右括号。剩下的那个讨论一下即可。 char ss[60]; int main() { ll ttt = rr(); while (ttt--) { scanf("%s", ss + 1); ll len = strlen(ss + 1); if (ss[1] == ss[len]) { printf("NO\n"); continue; } ll sa[3] = {0, 0, 0}; for (ll i = 1; i <= len; i++) sa[ss[i] - 'A']++; ll sl = ss[1] - 'A', sr = ss[len] - 'A'; ll sm = 3ll - sl - sr; bool flag = false; sa[0] = sa[1] = sa[2] = 0; if (sa[sl] + sa[sm] == sa[sr]) { for (ll i = 1; i <= len; i++) { sa[ss[i] - 'A']++; flag = flag || sa[sl] + sa[sm] < sa[sr]; } } else if (sa[sl] == sa[sm] + sa[sr]) { for (ll i = 1; i <= len; i++) { sa[ss[i] - 'A']++; flag = flag || sa[sl] < sa[sm] + sa[sr]; } } else { printf("NO\n"); continue; } if (flag) printf("NO\n"); else printf("YES\n"); } return 0; } B....

题目大意 海里每一个位置都有一个深度，而且水里随着时间有锯齿状周期为 $2k$ 的潮汐。 当潮汐与深度之和大于给定值 $l$ 时 Koa 会溺水，游泳、海岸、岛上永远是安全的。 在任意时间 Koa 可以选择游到 $x+1$ 或停留在 $x$，试问 Koa 是否能够安全的从海岸 $0$ 到达岛上 $n+1$。 分析 开始的想法是随着时间 DP，更好的解法是贪心。 若一个位置在水位最高时仍不会溺水，则称这个位置是安全的，并且可以任意选择出发时机。 即安全位置之间是相互独立的，我们只需判断可达性，尽量到达每一个安全位置。若之后 $2k$ 个位置没有安全位置，必死。 Koa 的最优决策是在刚退潮时出发，如果能走就尽量往前走，不能走就等，等到涨潮就说明不存在通过方法。 int main() { int ttt = rr(); while (ttt--) { int n = rr(), k = rr(), l = rr(); int flag = 0; int last = k; for (ll i = 1; i <= n; i++) { int d = rr(); flag += l < d; if (l - d >= k) last = k; else last = min(last - 1, l - d); flag += abs(last) > l - d; } if (flag) printf("No\n"); else printf("Yes\n"); } return 0; }