第一题：水题
#include <iostream> #include <cstdio> #include <cstring> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == ‘-‘) ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 1005; char s1[MAXN], s2[MAXN]; inline int ord(char c){ if(c >= ‘a‘ && c <= ‘z‘) return c - ‘a‘; return c - ‘A‘; } int main(){ scanf("%s%s", s1, s2); int len1 = strlen(s1), len2 = strlen(s2); for(int i=0, j=0; i<len2; i++, j=(j+1)%len1) putchar((26 + ord(s2[i]) - ord(s1[j])) % 26 + ((s2[i] >= ‘a‘) ? ‘a‘ : ‘A‘)); return 0; }
第二题：贪心提前处理出最后的序列（以$a*b$为关键字排序），最后高精度模拟即可
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == ‘-‘) ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 1005; struct Node{ int a, b; const bool operator < (const Node &x) const{ return a * b < x.a * x.b; } }a[MAXN]; const int BITLEN = 10000, BIGSIZE = 900; struct Big{ int val[BIGSIZE+1]; void operator = (int x){ memset(val, 0, sizeof(val)); val[0] = x; } Big(int x = 0){this->operator = (x);} Big operator + (Big x){ Big ans; for(int i=0; i<BIGSIZE; i++){ ans.val[i] += val[i] + x.val[i]; ans.val[i + 1] += ans.val[i] / BITLEN; ans.val[i] %= BITLEN; } return ans; } Big operator * (int x){ Big ans; for(int i=0; i<BIGSIZE; i++) ans.val[i] = x * val[i]; for(int i=0; i<BIGSIZE-1; i++) ans.val[i+1] += ans.val[i] / BITLEN, ans.val[i] %= BITLEN; return ans; } Big operator / (int x){ Big ans; for(int i=BIGSIZE-1, rest=0; i>=0; i--){ rest = rest * BITLEN + val[i]; ans.val[i] = rest / x; rest = rest % x; } return ans; } const bool operator < (const Big &x)const{ for(int i=BIGSIZE-1; i>=0; i--) if(val[i] != x.val[i]) return val[i] < x.val[i]; return false; } void print(){ int len = BIGSIZE - 1; while(!val[len]) len--; for(int i=len; i>=0; i--){ if(i != len) for(int j=BITLEN/10; j>1; j/=10) if(val[i] < j) putchar(‘0‘); printf("%d", val[i]); } } }; int main(){ int n = read(); for(int i=0; i<=n; i++) a[i].a = read(), a[i].b = read(); sort(a+1, a+1+n); Big ans = 0, sum = a[0].a; for(int i=1; i<=n; i++){ Big temp = sum / a[i].b; if(ans < temp) ans = temp; sum = sum * a[i].a; } ans.print(); return 0; }
第三题：倍增Dp提前预处理出一个点走$2^i$后的情况，对于寻找第一近和第二近的房子可以用map进行维护，每次找到最近的几个点，最后直接模拟即可
#include <iostream> #include <cstdio> #include <cstring> #include <map> #include <cmath> #include <queue> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == ‘-‘) ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 100001, LOGN = 18; int h[MAXN], next1[MAXN], next2[MAXN]; long long Dp[MAXN][LOGN+1][2], last[MAXN][LOGN+1]; map<int,int> hash; struct Tuple{ int dis, h, id; const bool operator < (const Tuple &x) const{ if(dis != x.dis) return dis > x.dis; return h > x.h; } }; priority_queue<Tuple> Q; int main(){ int n = read(); for(int i=1; i<=n; i++) h[i] = read(); hash[h[n]] = n, hash[h[n-1]] = n - 1; next1[n] = next2[n] = n, next1[n-1] = n, next2[n-1] = n-1; for(int i=n-2; i>=1; i--){ map<int,int>::iterator it = hash.upper_bound(h[i]), it2 = it; for(int j=1; j<=2; j++, it++) if(it != hash.end()) Q.push((Tuple){abs(h[i]-it->first), it->first, it->second}); if(it2 != hash.begin()){ it2--; for(int j=1; j<=2; j++, it2--){ Q.push((Tuple){abs(h[i]-it2->first), it2->first, it2->second}); if(it2 == hash.begin()) break; } } next1[i] = Q.top().id; Q.pop(); next2[i] = Q.top().id; hash[h[i]] = i; while(!Q.empty()) Q.pop(); } for(int i=1; i<=n; i++) Dp[i][0][0] = abs(h[next2[i]] - h[i]), Dp[i][0][1] = abs(h[next1[i]] - h[i]); for(int i=1; i<=n; i++) Dp[i][1][0] = Dp[i][0][0], Dp[i][1][1] = (next2[i] == i) ? 0 : Dp[next2[i]][0][1], last[i][1] = (next2[i] == i) ? next2[i] : next1[next2[i]]; for(int i=2; i<=LOGN; i++) for(int j=1; j<=n; j++){ Dp[j][i][0] = Dp[last[j][i-1]][i-1][0] + Dp[j][i-1][0], Dp[j][i][1] = Dp[last[j][i-1]][i-1][1] + Dp[j][i-1][1]; last[j][i] = last[last[j][i-1]][i-1]; } int x0 = read(), s0 = 0; double maxNum = 1e18; for(int i=1; i<=n; i++){ long long disA = 0, disB = 0, u = i, x = x0; for(int j=LOGN; j>=1; j--) if(Dp[u][j][0] + Dp[u][j][1] <= x) disA += Dp[u][j][0], disB += Dp[u][j][1], x -= Dp[u][j][0] + Dp[u][j][1], u = last[u][j]; if(Dp[u][0][0] <= x) disA += Dp[u][0][0]; if((double)disA / disB < maxNum) maxNum = (double)disA / disB, s0 = i; } printf("%d\n", s0); int m = read(); for(int i=1; i<=m; i++){ long long disA = 0, disB = 0, u = read(), x = read(); for(int j=LOGN; j>=1; j--) if(Dp[u][j][0] + Dp[u][j][1] <= x) disA += Dp[u][j][0], disB += Dp[u][j][1], x -= Dp[u][j][0] + Dp[u][j][1], u = last[u][j]; if(Dp[u][0][0] <= x) disA += Dp[u][0][0]; printf("%lld %lld\n", disA, disB); } return 0; }
第四题：对于$n<=1000$，暴力即可，对于$n<=10^6，z=0$，使用树状数组优化即可，对于数据加强的$11,12$点，可以考虑用树套树，但也可以用CDQ
因为CDQ的前提必须是更新过的节点不再更新，所以先分治，后计算左对右贡献的做法显然不行，但是可以先分治左，再计算左对右，再计算右，需要时刻牢记自己定义的CDQ是什么
这道题CDQ函数定义：将L到R的已经对X排序的数组计算贡献，并最后按照Y进行排序。
这样如果数组顺序不对需要重新排序（用sort排序），当然因为sort是在第一层CDQ里面的所以总时间复杂度还是$O(nlog^2n)$，和树套树的时间复杂度一样（虽然常数大了一点）
普通代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == ‘-‘) ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 1000001; struct Tuple{ int x, y, z, val; bool const operator < (const Tuple &temp) const{ if(x != temp.x) return x < temp.x; if(y != temp.y) return y < temp.y; return z < temp.z; } }tup[MAXN]; struct BIT{ int val[MAXN]; void add(int pos,int x){ for(int i=pos; i<MAXN; i+=i&(-i)) val[i] = max(val[i], x); } int query(int pos){ int ans = 0; for(int i=pos; i; i-=i&(-i)) ans = max(ans, val[i]); return ans; } }bit; int main(){ int n = read(); for(int i=1; i<=n; i++) tup[i].x = read(), tup[i].y = read(), tup[i].z = read(), tup[i].val = 1; sort(tup+1, tup+1+n); if(n > 10001){ for(int i=1; i<=n; i++){ tup[i].val = bit.query(tup[i].y) + 1; bit.add(tup[i].y, tup[i].val); } } else{ for(int i=1; i<=n; i++) for(int j=1; j<i; j++) if(tup[j].y <= tup[i].y && tup[j].z <= tup[i].z) tup[i].val = max(tup[i].val, tup[j].val + 1); } int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, tup[i].val); printf("%d", ans); return 0; }
数据加强版代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == ‘-‘) ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 1000005; struct Tuple{ int x, y, z, val; bool const operator < (const Tuple &temp) const{ if(x != temp.x) return x < temp.x; if(y != temp.y) return y < temp.y; return z < temp.z; } }tup[MAXN], temp[MAXN]; struct BIT{ int val[MAXN]; void add(int pos,int x){ for(int i=pos; i<MAXN; i+=i&(-i)) val[i] = max(val[i], x); } int query(int pos){ int ans = 0; for(int i=pos; i; i-=i&(-i)) ans = max(ans, val[i]); return ans; } void clear(int pos){ for(int i=pos; i<MAXN; i+=i&(-i)) val[i] = 0; } }bit; const bool cmp(const Tuple &a,const Tuple &b){ if(a.y != b.y) return a.y < b.y; return a.z < b.z; } void CDQ(int l,int r){ int mid = (l + r) >> 1; if(l == r) return; CDQ(l, mid); sort(tup+mid+1, tup+r+1, cmp); for(int i=l, j=mid+1, k=l; k<=r; k++){ if(j > r || (i <= mid && tup[i].y <= tup[j].y)) bit.add(tup[i].z, tup[i].val), i++; else tup[j].val = max(tup[j].val, bit.query(tup[j].z) + 1), j++; } for(int i=l; i<=mid; i++) bit.clear(tup[i].z); sort(tup+mid+1, tup+r+1); CDQ(mid+1, r); for(int i=l, j=mid+1, k=l; k<=r; k++){ if(j > r || (i <= mid && tup[i].y <= tup[j].y)) temp[k] = tup[i++]; else temp[k] = tup[j++]; } for(int i=l; i<=r; i++) tup[i] = temp[i]; } int main(){ int n = read(); for(int i=1; i<=n; i++) tup[i].x = read() + 1, tup[i].y = read() + 1, tup[i].z = read() + 1, tup[i].val = 1; sort(tup+1, tup+1+n); CDQ(1, n); int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, tup[i].val); printf("%d", ans); return 0; }
原文：https://www.cnblogs.com/PHDHD/p/12637616.html
