题解：
第一题：
或者ＤＰ，先按ｘ排序，ｄｐ［ｉ］表示选择ｉ作为结尾的最大团size;
发现i向前连边的条件是xi - wi >= xj + wj; (这个式子我推出来，但并没有深入探究）
简单探索一番可以发现如果i可以和前面的j连边，j可以和前面p连边，则i就可以和p连边；
dp[i] = max(dp[j]) + 1, 这个可以用树状数组维护；
#include<bits/stdc++.h> using namespace std; const int M = 200005; int c[M<<1], dis[M<<1], q; struct node{int u, v, x;}p[M]; bool cmp(node A, node B){ return A.x < B.x; } void add(int x, int u){ for(; x <= q; x += x&(-x)) c[x] = max(c[x], u); } int query(int x){ int ret = 0; for(; x; x -= x&(-x)) ret = max(ret, c[x]); return ret; } int read(){ int x = 0; int f = 1; char c = getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} return x*=f; } int main(){ freopen("clique.in","r",stdin); freopen("clique.out","w",stdout); int n = read(), tot = 0; for(int i = 1; i <= n; i++){ int x = read(), w = read(); p[i].x = x; p[i].u = x - w; p[i].v = x + w; dis[++tot] = p[i].u, dis[++tot] = p[i].v; } sort(dis + 1, dis + 1 + tot); q = unique(dis + 1, dis + 1 + tot) - dis - 1; for(int i = 1; i <= n; i++){ p[i].u = lower_bound(dis + 1, dis + 1 + q, p[i].u) - dis; p[i].v = lower_bound(dis + 1, dis + 1 + q, p[i].v) - dis; } sort(p + 1, p + 1 + n, cmp); add(p[1].v, 1); int ans = 1; for(int i = 2; i <= n; i++){ int t = query(p[i].u); add(p[i].v, t+1); ans = max(ans, t+1); } printf("%d ", ans); }
第二题：正确解法基于一个重要的结论，a % b <= a/2，这就意味着，任何一个数loga[i]次取模以内就能变为0。同时还注意到，a % b = a (a < b)。这两点便可以极大的降低时间复杂度。
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 1e5+5; int a[M], n, m; #define Ls nd->ls, lf, mid #define Rs nd->rs, mid+1, rg struct Node{ int v; ll sum; Node *ls, *rs; void up(){ v = max(ls->v, rs->v); sum = ls->sum + rs->sum; } }pool[M << 2], *root, *tail = pool; Node *build(int lf = 1, int rg = n){ Node *nd = ++tail; if(lf == rg)nd->v = nd->sum = a[lf]; else { int mid = (lf + rg) >> 1; nd->ls = build(lf, mid); nd->rs = build(mid+1, rg); nd->up(); } return nd; } void add(int pos, int x, Node *nd = root, int lf = 1, int rg = n){ if(lf == rg){ nd->v = nd->sum = x; } else { int mid = (lf + rg) >> 1; if(pos <= mid)add(pos, x, Ls); else add(pos, x, Rs); nd->up(); } } ll query(int L, int R, Node *nd = root, int lf = 1, int rg = n){ if(L <= lf && rg <= R)return nd->sum; else { int mid = (lf + rg) >> 1; ll ret = 0; if(L <= mid)ret += query(L, R, Ls); if(R > mid) ret += query(L, R, Rs); return ret; } } void modify(int L, int R, ll x, Node *nd = root, int lf = 1, int rg = n){ if(nd->v < x) return ; if(lf == rg)nd->v %= x, nd->sum%= x; else { int mid = (lf + rg) >> 1; int ret = 0; if(L <= mid)modify(L, R, x, Ls); if(R > mid) modify(L, R, x, Rs); nd->up(); } } int read(){ int x = 0; int f = 1; char c = getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} return x*=f; } int main(){ freopen("mod.in","r",stdin); freopen("mod.out","w",stdout); n = read(), m = read(); for(int i = 1; i <= n; i++) a[i] = read(); root = build(); int opt, l, r, x; while(m--){ opt = read(); if(opt == 1){ l = read(), r = read(); printf("%lld ", query(l, r)); } else if(opt == 2){ l = read(), r = read(), x = read(); modify(l, r, x); } else { l = read(), x = read(); add(l, x); } } }
第三题：令S(i)={i+1,i+2,…,2i}，f(i,k)表示S(i)中二进制下恰好有k个1的数的个数（i>0，k>=0）。
发现f(i, k) <= f(i+1, k), 这个满足二分性质， 就二分i, f可以用数位DP解决，但是是Log^2的，我们可以直接用组合数解决；
没有顶上界， 有C(位数，要的1)， 代替数位DP的过程，顶上界只有一次，是logN的；
#include<bits/stdc++.h> using namespace std; #define ull unsigned long long const ull INF = 2e18; ull C[67][67]; int digit[67]; ull dfs(int dep, int res, int sum){ int now = sum - res; if(now > dep)return 0; if(!now)return 1; if(dep == 1) return digit[dep] == sum - res; if(!digit[dep])return dfs(dep-1, res, sum); ull tmp = C[dep-1][now]; if(tmp == INF) return INF + 1; ull nw = dfs(dep-1, res+1, sum); return min(INF + 1, tmp + nw); } ull check(ull xz, ull k){ ull up = xz<<1; int cnt = 0; while(xz){ digit[++cnt] = xz&1; xz >>= 1; } ull ans1 = dfs(cnt, 0, k); cnt = 0; while(up){ digit[++cnt] = up&1; up >>= 1; } ull ans2 = dfs(cnt, 0, k); return ans2 - ans1; } int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); for(int i = 0; i <= 65; i++) for(int j = 0; j <= i; j++) if(j == 0 || i == j) C[i][j] = 1; else C[i][j] = min(C[i-1][j-1] + C[i-1][j], INF); int T; scanf("%d", &T); ull m, k; while(T--){ scanf("%llu%llu", &m, &k); if(m == 1 && k == 1){puts("1 -1");continue;} ull lf = 1, rg = 1e18, p1 = -1, p2 = -1; while(lf <= rg){ ull mid = (lf + rg) / 2; ull now = check(mid, k); if(now == m){ p1 = mid; rg = mid - 1; } else if(now > m)rg = mid - 1; else lf = mid + 1; } lf = 1, rg = 2e18; while(lf <= rg){ ull mid = (lf + rg) / 2; ull now = check(mid, k); if(now == m){ p2 = mid; lf = mid + 1; } else if(now > m)rg = mid - 1; else lf = mid + 1; } printf("%llu %llu ", p1, p2 - p1 + 1); } }