列个公式推一下就可以了
#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) const int maxn = 100000 + 5; int a[maxn], b[maxn]; int main() { int n; scan(n); for (int i = 1; i <= n; i++) scan(a[i]); for (int i = 1; i <= n - 1; i++) b[i] = a[i] + a[i + 1]; for (int i = 1; i <= n - 1; i++) printf("%d ", b[i]); printf("%d\n", a[n]); return 0; }如果总次数是奇数一定无解。偶数的话分别统计一下UDLR出现的次数，然后相反两个方向的相互转换一定更优。最后单出来的再转换一次
#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) const int maxn = 100000 + 5; char s[maxn]; int main() { scanf("%s", s); int n = strlen(s); if (n & 1) { puts("-1"); return 0; } int u = 0, d = 0, r = 0, l = 0; for (int i = 0; i < n; i++) { if (s[i] == 'U') u++; if (s[i] == 'D') d++; if (s[i] == 'R') r++; if (s[i] == 'L') l++; } int t1 = abs(u - d) / 2; int t2 = abs(r - l) / 2; int ans = t1 + t2; if (abs(u - d) % 2 == 1) ans++; printf("%d\n", ans); return 0; }C题想清楚了超级简单，首先条件就是满足三角形定则 最先考虑的是从x向y转换，每次贪心的去选择（尽可能靠近y），但是第三个样例发现显然不成立 但是如果从y出发， 去倒推x的话发现贪心是成立的
#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) int main() { int x, y, tot = 0; scan2(x, y); int a = y, b = y, c = y; while (a < x) { c = b; b = a; a = b + c - 1; tot++; } printf("%d\n", tot + 2); return 0; }状态表示：d[i][j] 经过i轮，a和b分数相差j（未计入初始值） 转移方程：d[i][j] = d[i - 1][j - 2k] + d[i - 1][j - (2k - 1)] * 2 + … + d[i - 1][j] * (2k + 1) + d[i - 1][j + 1] * 2k + d[i - 1][j + 2] * (2k - 1) + … + d[i - 1][j + 2k] 时间复杂度O(n^2 * k * t)，显然会T 发现右边依次按照1，2，3，4的速度在增长，再考虑d[i][j - 1]，发现两个做差后右边变成了前缀和
将转移的时间复杂度降为了O(1)
#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) const int maxn = 200000 + 200; const int oft = 200000 + 200; const int mod = 1000000007; LL d[2][maxn * 2], sum[maxn * 2]; int a, b, k, t; int main() { scanf("%d%d%d%d", &a, &b, &k, &t); d[0][0 + oft] = 1; int bd = 2 * k * t, o = 0; for (int i = 1; i <= t; i++, o ^= 1) { for (int j = -bd; j <= bd; j++) { sum[j + oft] = sum[j - 1 + oft] + d[o][j + oft]; sum[j + oft] %= mod; } int tbd = 2 * k * i; d[o ^ 1][-tbd + oft] = 1; for (int j = -tbd + 1; j <= tbd; j++) { d[o ^ 1][j + oft] = d[o ^ 1][j - 1 + oft] + (sum[min(j + 2 * k, bd) + oft] - sum[j - 1 + oft]) - (sum[j - 1 + oft] - sum[max(j - 1 - (2 * k + 1), -bd) + oft]); d[o ^ 1][j + oft] += mod; d[o ^ 1][j + oft] %= mod; } } LL ans = 0; for (int i = b - a + 1; i <= bd; i++) { ans += d[o][i + oft]; ans %= mod; } printf("%d\n", ans); return 0; }终于补完了div2一套题了= =看了题解才会 把公式推出来后发现就是线段树的单点修改，区间查询 cf上的题解：
#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) const int maxn = 100000 << 2; double A[maxn], B[maxn]; double pr, ur, a, b; int n, Q; int y1, y2, p, y3, y4; double v; void pushup(int o) { A[o] = A[o << 1] * A[o << 1 | 1]; B[o] = B[o << 1] + B[o << 1 | 1] * A[o << 1]; } void build(int o, int L, int R) { if (L == R) { scanf("%lf%lf", &a, &b); double pr = a / b; A[o] = (1 - pr) / pr; B[o] = A[o]; return; } int M = L + (R - L) / 2; build(o << 1, L, M); build(o << 1 | 1, M + 1, R); pushup(o); } void update(int o, int L, int R) { if (L == R) { A[o] = v; B[o] = v; return; } int M = L + (R - L) / 2; if (p <= M) update(o << 1, L, M); else update(o << 1 | 1, M + 1, R); pushup(o); } pair<double, double> query(int o, int L, int R) { if (y1 <= L && y2 >= R) return mp(A[o], B[o]); int M = L + (R - L) / 2; double tb = 0, ta = 1.0; if (y1 <= M) { pair<double, double> tmp = query(o << 1, L, M); ta *= tmp.first; tb += tmp.second; } if (y2 > M) { pair<double, double> tmp = query(o << 1 | 1, M + 1, R); tb += (tmp.second * ta); ta *= tmp.first; } return mp(ta,tb); } int main() { scan2(n, Q); build(1, 1, n); while (Q--) { int op; double t1, t2; scan(op); if (op == 1) { scanf("%d%lf%lf", &p, &t1, &t2); double tv = t1 / t2; v = (1 - tv) / tv; update(1, 1, n); } else { scan2(y1, y2); printf("%.12lf\n", 1.0/ (1 + query(1, 1, n).second)); } } return 0; }