T1
给一个环，每个点有一个权值，把环分成三段，求最小的那段的最大值
sol：暴力
二分答案，chk就是把环搞成三倍链，每次枚举起点，后面三个切割点都可以二分找
然后就Rua过去了
//yyc wenle #include<bits/stdc++.h> #define LL long long using namespace std; const int maxn = 100010; inline LL read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } int n; LL s[3 * maxn],a[2 * maxn]; LL l,r; inline LL findnx(int pos,LL x){return upper_bound(s,s + 3 * n + 1,s[pos] + x - 1) - s;} inline int chk(LL x) { int pos; for(int i=0;i<n;i++) { pos = i; pos = findnx(pos,x);if(pos > i + n)continue; pos = findnx(pos,x);if(pos > i + n)continue; pos = findnx(pos,x);if(pos > i + n)continue; return 1; } return 0; } int main() { n = read(); for(int i=1;i<=n;i++){a[i] = read();a[n + i] = a[i];a[2 * n + i] = a[i];} for(int i=1;i<=3 * n;i++)s[i] = s[i - 1] + a[i]; l = 0,r = s[n] / 3;LL ans; while(l <= r) { LL mid = (l + r) >> 1; if(chk(mid))l = mid + 1,ans = mid; else r = mid - 1; } printf("%lld ",ans); } /* 30 1 34 44 13 30 1 9 3 7 7 20 12 2 44 6 9 44 31 17 20 33 18 48 23 19 31 24 50 43 15 */
T2
树上选出k个点，如果选一个点，也要选他的祖先，默认选0，每个人有一个战斗力和一个花费
求选出的最大战斗力除以最大花费
sol：
分数规划，每个点权变成了zdl - mid * hf
然后就是“树上选出若干点点权大于0”
然后，我们就想歪了
考虑选出的肯定是很多条链，树上选出很多链？那岂不是...
九省联考_林可卡特树
然后想了半天带权二分...咳咳
然后就去想T3了
写完T3才发现这tm不是个树背包吗
然后算算复杂度
小数点后3位，最大10000，那就是1e8
log1e8 * O(n^2)显然挂了
所以需要一个常数小的写法
考虑dfs序，我们选一个点，可以转移到他dfs序后一个点
不选一个点，就转出这棵子树
然后常数非常的优秀，不需要“证明复杂度”和size写法
（学弟预处理size然后T了
//yyc wenle #include<bits/stdc++.h> #define LL long long #define DB long double using namespace std; const int maxn = 100010; const double inf = 1e9; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } int n,k; double s[maxn],p[maxn]; int first[maxn],to[maxn],nx[maxn],cnt; int dfin[maxn],pos[maxn],dfout[maxn],dfn; double f[2510][2510];int ccnt = 0; inline void add(int u,int v) { to[++cnt] = v; nx[cnt] = first[u]; first[u] = cnt; } inline void dfs(int x) { dfin[x] = ++dfn; pos[dfn] = x; for(int i=first[x];i;i=nx[i])dfs(to[i]); dfout[dfin[x]] = dfn; } inline int chk(double x) { for(int i=1;i<=n + 2;i++) for(int j=0;j<=k + 1;j++) f[i][j] = -inf; f[1][0] = 0; for(int i=1;i<=n+1;i++) for(int j=0;j<=k+1;j++) { if(f[i][j] == -inf)continue; double cur = p[pos[i]] - x * (s[pos[i]]); f[dfout[i] + 1][j] = max(f[dfout[i] + 1][j],f[i][j]); f[dfout[i] + 1][j + 1] = max(f[dfout[i] + 1][j + 1],f[i][j] + cur); for(int xx=first[pos[i]];xx;xx = nx[xx]) { int targ = to[xx]; f[dfin[targ]][j + 1] = max(f[dfin[targ]][j + 1],f[i][j] + cur); //ccnt++; } } return f[n + 2][k + 1] >= 0.0; } const double eps = 1e-5; int main() { //freopen("rantree.in","r",stdin); //freopen("1.txt","r",stdin); //freopen("gen.out","w",stdout); //freopen("mactree.in","r",stdin); //freopen("chain.in","r",stdin); //freopen("juhua.in","r",stdin); k = read(),n = read(); if(!k){puts("0.000");return 0;} for(int i=1;i<=n;i++) { scanf("%lf%lf",&s[i],&p[i]);int py = read(); add(py,i); } dfs(0); //cout<<pos[1]; double l = 0,r = 10000.0; for(int tms = 1;tms <= 50;tms++) { if(r - l <= eps)break; double mid = (l + r) / 2.0; if(chk(mid))l = mid + eps; else r = mid - eps; } //cout<<ccnt<<endl; printf("%.3lf",(l + r) / 2.0); }
T3
给n个门，每个门是一个位运算和一个数，经过这个门就对这个数操作
求1~m经过这些门之后最大的数
sol：
贪心
1.如果这位选0，改了之后变成1，血赚
2.如果这位选1，改了之后变成0，血亏
3.剩下的，选0肯定比选1更小于m
//yyc wenle #include<bits/stdc++.h> #define LL long long using namespace std; const int maxn = 100010; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } int n,m; char opt[50]; int num; int main() { n = read(),m = read(); int x = (1 << 30) - 1,y = 0; for(int i=1;i<=n;i++) { scanf("%s",opt);num = read(); if(opt[0] == 'A')x &= num,y &= num; if(opt[0] == 'X')x ^= num,y ^= num; if(opt[0] == 'O')x |= num,y |= num; } int a = 0,b = 0; for(int i = (1 << 30);i;i >>= 1) { if((a | i) <= m && (x & i) > (y & i))b |= (x & i),a |= i; else b |= (y & i); } printf("%d ",b); }
AK了