T1
>传送门<
记忆化搜索，听说有更简单的方法(但博主比较菜)
#include <cstdio> #include <cstdlib> #define ll long long ll read(){ ll x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf; } int a[105], n; int vis[105]; void DFS(int pos, int floor){ if (vis[pos]) return ; vis[pos] = 1; for (int i = ((n - pos) & 1) ? (n - 1) : n; i >= pos; i -= 2){ if (i == n){ if (a[i] & 1){ if (floor & 1){ printf("Yes"); exit(0); } } } else{ if ((a[i] & 1) && (a[i + 1] & 1)){ if (i + 1 == n){ if (!(floor & 1)){ printf("Yes"); exit(0); } } DFS(i + 1, floor + 1); } } } } int main(){ n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); if (!(a[1] & 1) || !(a[n] & 1)){ printf("No"); return 0; } DFS(1, 1); printf("No"); return 0; }
T2
>传送门<
第1个点肯定要选的，暴力枚举第一条线段的第二个点在哪里，然后暴力模拟，注意第二个点可能为空
#include <cstdio> #include <cmath> #define ll long long const double DEL = 1e-14; ll read(){ ll x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf; } double myAbs(double a){ return (a > 0) ? a : -a; } double equal(double a, double b){ if (myAbs(a - b) <= DEL) return 1; else return 0; } double y[1005]; int main(){ int n = read(); if (n <= 2){ printf("Yes "); return 0; } for (int i = 0; i < n; ++i) y[i] = read(); double lineA, lineB; int b1 = -1, b2 = -1; for (int i = 1; i < n; ++i){ lineA = (y[i] - y[0]) / (double)(i); b1 = b2 = -1; int j; for (j = 1; j < n; ++j){ if (j == i) continue; if (!equal((y[j] - y[0]) / (double)(j), lineA)){ if (b1 == -1){ b1 = j; }else if (b2 == -1){ b2 = j; lineB = (y[b2] - y[b1]) / (double)(b2 - b1); if (!equal(lineA, lineB)) break; }else{ if (!equal((y[j] - y[b1]) / (double)(j - b1), lineB)) break; } } } if (j == n){ if (b1 != -1){ printf("Yes "); return 0; } } } double line1 = y[2] - y[1]; int i; for (i = 3; i < n; ++i){ if (!equal((y[i] - y[1]) / (double)(i - 1), line1)) break; } if (i == n && (!equal((y[1] - y[0]), line1))) printf("Yes "); else printf("No "); return 0; }
T3
>传送门<
发现不管怎么合并，结果都一样，于是等差数列求和公式用一用AC
#include <cstdio> #define ll long long ll read(){ ll x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf; } ll getNum(ll a){ return (((1 + a) * a) >> 1); } int main(){ int k = read(); if (k == 0){ printf("ab"); return 0; } char ch = 'a'; while (k > 0){ int l = 0, r = 100000, mid, ans = 0; while (l <= r){ mid = (l + r) >> 1; if (getNum(mid) > k){ r = mid - 1; }else{ l = mid + 1; ans = mid; } } k -= getNum(ans); for (int i = 0; i <= ans; ++i) printf("%c", ch); ++ch; } return 0; }
T4
>传送门<
欧拉筛，二分AC
#include <cstdio> #include <map> #include <cmath> #include <algorithm> #define ll long long using namespace std; int a[10000005], qzh[1000005]; int primes[10000005]; int prime_num = 1; bool is_not_primes[10000005] = {false}; map<int, int> mp; ll read(){ ll x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf; } void getPrime(int n){ is_not_primes[0] = true; is_not_primes[1] = true; for (int i = 2; i <= n; i++){ if (is_not_primes[i] == false) primes[prime_num++] = i; for (int j = 1; (j < prime_num) && (primes[j] * i <= n); j++){ is_not_primes[primes[j] * i] = true; if ((i % primes[j]) == 0) break; } } } int main(){ getPrime(10000000); int n = read(); for(int i = 1; i <= n; ++i){ int x = read(); ++a[x]; } for(int i = 1; i < prime_num; ++i) for(int j = primes[i]; j <= 10000000; j += primes[i]) qzh[i] += a[j]; for(int i = 1; i < prime_num; ++i) qzh[i] += qzh[i - 1]; int m = read(), l, r; for(int i = 1; i <= m; ++i){ l = read(), r = read(); ll ans_r = qzh[lower_bound(primes + 1, primes + prime_num, r + 1) - primes - 1]; ll ans_l = qzh[lower_bound(primes + 1, primes + prime_num, l) - primes - 1]; printf("%lld ", ans_r - ans_l); } }
T5
>传送门<
真正难的题目(目测实测洛谷黑题)，因为我比较菜，不会分块cdq分治，差分乱搞的算法，只能打一发树套树，
如何使用树套树呢？
我们把一维问题转换成二维问题，一个点的横坐标就是这个点的位置，纵坐标是这个点前一个与它颜色相同的点的位置，权值是横坐标减纵坐标。
这里查询[l,r]区间的答案，就是二维平面上(l,l)点和(r,r)点组成的矩阵内的权值之和。
原理？占坑代填
然后预处理再上树套树板子就行了
#include <cstdio> #include <vector> #include <set> #define ll long long using namespace std; ll read(){ ll x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf; } //SegmentTree long long s[12000000]; int lc[12000000], rc[12000000]; int node_cnt = 0; void Add(int &pos, int l, int r, int k, ll val){ if (!pos) pos = ++node_cnt; s[pos] += val; if (l == r) return; int mid = (l + r) >> 1; if (k <= mid) Add(lc[pos], l, mid, k, val); else Add(rc[pos], mid + 1, r, k, val); } long long Query(int pos, int l, int r, int k){ if (!pos) return 0; if (l == r) return s[pos]; int mid = (l + r) >> 1; if (k <= mid) return Query(lc[pos], l, mid, k) + s[rc[pos]]; else return Query(rc[pos], mid + 1, r, k); } int rt[100005], fst[100005]; //fentree struct fenTree{ #define lowbit(x) (x & -x) void add(int k, int pos, ll val, int n){ for (int i = k; i <= n; i += lowbit(i)) Add(rt[i], 1, n, pos, val); } ll qry(int k, int pos, int n) { ll res = 0; for (int i = pos; i; i -= lowbit(i)) res += Query(rt[i], 1, n, k); return res; } #undef lowbit } bit; void update(int x, int y, int n){ if(fst[x]) bit.add(x, fst[x], fst[x] - x, n); if(y) bit.add(x, y, x - y, n); fst[x] = y; } int aa[100005]; set<int> st[100005]; inline set<int>::iterator nxt_it(set<int>::iterator it){ return (++it); } inline set<int>::iterator pre_it(set<int>::iterator it){ return (--it); } int main(){ int n = read(), m = read(); for (int i = 1; i <= n; ++i) aa[i] = read(); for (int i = 1; i <= n; i ++) { if (!st[aa[i]].empty()){ fst[i] = *st[aa[i]].rbegin(); bit.add(i, fst[i], i - fst[i], n); } st[aa[i]].insert(i); } int op, x, y; for (int I = 0; I < m; ++I){ op = read(), x = read(), y = read(); if (op == 1){ set<int>::iterator it = st[aa[x]].find(x); if (nxt_it(it) != st[aa[x]].end()) update(*nxt_it(it), (it == st[aa[x]].begin() ? 0 : *pre_it(it)), n); st[aa[x]].erase(x); aa[x] = y; it = st[y].insert(x).first; update(x, (it == st[y].begin() ? 0 : *pre_it(it)), n); if(nxt_it(it) != st[y].end()) update(*nxt_it(it), x, n); } else printf("%lld ", bit.qry(x, y, n)); } return 0; }