[关闭]
@2368860385 2020-11-07T03:05:15.000000Z 字数 9985 阅读 182

day4

正睿提高

2018.9.15

放假回家，然后没做。。。
回来看了题之后，发现一个都不会做。。。

T1

每个点只能买或者卖。
第一档：3^n枚举每个点是买/卖/不操作

第二档：状压前面没有买的点。

第三档：dp，f[i][j]表示到第i个位置，买了j个的获益。然后判断i是买/卖/不操作。个人理解：第二维在转移时好像并没有用，因为这j个也不知道是哪些，获得的收益也不知道从哪里买的。但是去掉这一维发现不能转移了（转移时不会买，因为一旦买就成了负数了），转移时i只有三种情况买/卖/不操作，为了可以转移，必须要满足三种情况可以转移（从哪转移，贡献怎么算），发现转移会影响当前买的个数，于是加上这个限制条件就可以转移了。

第四档：直接判断第i个位置是否可以卖出。然后从前面所有没有买的找最小的，从所有卖出的位置替换（表示在i这个位置卖），如果都不能获得收益，则只能在i这里买了。注意：为了让操作次数更少，于是先考虑在i卖出，可能代替某些位置。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<queue>
  7. using namespace std;
  8. typedef long long LL;
  10. inline int read() {
  11.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  12.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  13. }
  15. const int N = 50010;
  17. int a[N];
  18. int n;
  20. priority_queue< int, vector<int>, greater<int> > q1, q2;
  22. void init() {
  23.     n = read();
  24.     for (int i=1; i<=n; ++i) a[i] = read();
  25.     while (!q1.empty()) q1.pop();
  26.     while (!q2.empty()) q2.pop();
  27. }
  29. void solve() {
  30.     LL Ans = 0;
  31.     for (int i=1; i<=n; ++i) {
  32.         int opt = 0, mx = 0;
  33.         if (!q2.empty()) { // 卖出的，优先考虑，减少购买次数 
  34.             if (mx < a[i] - q2.top()) 
  35.                 mx = a[i] - q2.top(), opt = 1; 
  36.         }
  37.         if (!q1.empty()) { // 未买入的 
  38.             if (mx < a[i] - q1.top()) 
  39.                 mx = a[i] - q1.top(), opt = 2;
  40.         }
  41.         Ans += mx;
  42.         if (opt == 0) q1.push(a[i]);
  43.         else if (opt == 1) q1.push(q2.top()), q2.pop(), q2.push(a[i]);
  44.         else q1.pop(), q2.push(a[i]);
  45.     }
  46.     cout << Ans << " " << (int)(q2.size()) * 2 << "\n"; 
  47. }
  49. int main() {
  50.     int T = read();
  51.     while (T--) {
  52.         init();
  53.         solve();
  54.     }
  55.     return 0;
  56. }

T2

二分一个直径d，判断能否穿过。
判断是否穿过有点难，正难则反，判断是否不能穿过。
假设L上方有一个点为S，x轴下方有一个点为T，如果两点之间的距离小于d，那么连一条边，如果S与T联通了，那么说明直径为d的球无法穿过。复杂度

也就是求最小瓶颈生成树。

瓶颈生成树 ：无向图G的一颗瓶颈生成树是这样的一颗生成树，它最大的边权值在G的所有生成树中是最小的。瓶颈生成树的值为T中最大权值边的权。
无向图的最小生成树一定是瓶颈生成树。瓶颈生成树不一定是最小生成树。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<map>
  11. #define fi(s) freopen(s,"r",stdin);
  12. #define fo(s) freopen(s,"w",stdout);
  13. using namespace std;
  14. typedef long long LL;
  16. const double eps = 1e-8;
  17. const int N = 505;
  19. int fa[N];
  20. int n, S, T;
  21. double x[N], y[N], L;
  23. int find(int x) {
  24.     return x == fa[x] ? x : fa[x] = find(fa[x]);
  25. }
  26. void Merge(int x,int y) {
  27.     x = find(x), y = find(y);
  28.     fa[x] = y;
  29. }
  30. double Calc(int i,int j) {
  31.     return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
  32. }
  33. bool check(double d) {
  34.     for (int i=1; i<=n+2; ++i) fa[i] = i;
  36.     for (int i=1; i<=n; ++i) {
  37.         if (d > y[i]) Merge(T, i); // 居然写成了x[i]
  38.         if (d > L - y[i]) Merge(S, i);
  39.         for (int j=i+1; j<=n; ++j) 
  40.             if (d > Calc(i, j)) Merge(i, j);
  41.     }
  43.     if (find(S) == find(T)) return false;
  44.     return true;    
  45. }
  47. int main() {
  48.     scanf("%d%lf",&n,&L);
  49.     S = n + 1, T = n + 2;
  50.     for (int i=1; i<=n; ++i) 
  51.         scanf("%lf%lf",&x[i],&y[i]);
  53.     double l = 0, r = L, ans = 0;
  54.     while (r - l > eps) {
  55.         double mid = (l + r) / 2.0;
  56.         if (check(mid)) ans = mid, l = mid;
  57.         else r = mid;
  58.     }
  59.     printf("%.3lf",ans);
  60.     return 0;
  61. }

T3

题意：一个长度为N的01序列。
现在有Q次询问，每次询问一个区间[L,R]，问在这个区间中最少需要删掉多少个数，使得这个区间剩下的每个非空前缀以及每个非空后缀中，0的个数都不小于1的个数。
（老是想成将1变成0。。。）

两种做法。
首先都是将字符串中的0变成1,1变成-1。不合法=>区间和为负
1、线段树求最小的“前缀+后缀”
结论：答案就是在查询区间内，选一个前缀,一个后缀（要求不重复），然后加起来，取最小值。
就是
证明？（测试一下小于1000的数据？）

于是就可以线段树维护了。
首先让每个节点的值直接是前缀和，和后缀和，最后答案=ans-pre[l-1]-suf[r+1]就行了。
每个节点维护三个值：vl,vr,val，表示在此区间内的前缀最大值，后缀最大值，前缀和后缀都在此区间的答案的最大值（l,r都在此区间的，才更新）。
查询的时候是这样的：
_ | _ _ | _ _ _ _
l,r都在左边的线段树维护了，都在右边的也维护了。还有一个在左边一个在右边，这样没有更新到。由于每次更新一段区间一定是从左往右更新的，那么记录一个值表示当前区间的左边的所有区间内的前缀最大值（比如上图中到第三个区间的时候，更新出了前两个区间的前缀最大值，即123），然后可以直接和这个区间的后缀最大值合并了。

2、倍增

每次询问：从左忘右扫一遍，删除必须要删除的1，（为了是所有非空前缀满足条件），然后为了让所有非空后缀满足条件，然后在删掉1后的序列上，求一个最小后缀和，ans=删掉的1的个数+（-最小后缀和）

题解：
考虑用倍增加速删除的过程。
每个点记录右边第一个删除的位置，显然是一个树结构。
然后删除这个点后，剩下很多段，然后合并这些段求出最小后缀值。

011100111
0走到第3个位置，剩下的段是01，然后在走到第4个位置，没有剩下的，然后再走到最后一个1的位置，剩下的是0011，合起来就是010011，求出最小后缀和。
两段合并的过程是可以倍增加速的。就是一次走2^j步。最后一个段不一定走完，特判。

线段树维护前缀最小 + 后缀最小

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<map>
  11. #define fi(s) freopen(s,"r",stdin);
  12. #define fo(s) freopen(s,"w",stdout);
  13. using namespace std;
  14. typedef long long LL;
  16. inline int read() {
  17.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  18.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  19. }
  21. const int N = 200005;
  22. const int INF = 1e9;
  24. char s[N];
  25. int a[N], val[N << 2], vl[N << 2], vr[N << 2], pre[N], suf[N];
  26. int Ans, VL;
  28. void solve1(int n, int Q) {     
  29.     while (Q--) {
  30.         int l = read(), r = read(), ans = INF, minL = INF;
  31.         for (int sum=0,i=l-1; i<=r; ++i) {
  32.             minL = min(minL, pre[i] - pre[l - 1]);
  33.             ans = min(ans, minL + (suf[i + 1] - suf[r + 1]));
  34.         }
  35.         printf("%d\n",-ans);
  36.     }   
  37. }
  39. #define Root 0, n + 1, 1
  40. #define lson l, mid, rt << 1
  41. #define rson mid + 1, r, rt << 1 | 1
  43. void pushup(int rt) {
  44.     vl[rt] = min(vl[rt << 1], vl[rt << 1 | 1]);
  45.     vr[rt] = min(vr[rt << 1], vr[rt << 1 | 1]);
  46.     val[rt] = min(vl[rt << 1] + vr[rt << 1 | 1], min(val[rt << 1], val[rt << 1 | 1]));
  47. }
  48. void build(int l,int r,int rt) {
  49.     if (l == r) {
  50.         vl[rt] = pre[l], vr[rt] = suf[l], val[rt] = INF;
  51.         return ;
  52.     }
  53.     int mid = (l + r) >> 1;
  54.     build(lson);build(rson);
  55.     pushup(rt);
  56. }
  57. void query(int l,int r,int rt,int L,int R) {
  58.     if (L <= l && r <= R) {
  59.         if (VL == INF) Ans = val[rt], VL = vl[rt];
  60.         else {
  61.             Ans = min(Ans, val[rt]);
  62.             Ans = min(Ans, VL + vr[rt]);
  63.             VL = min(VL, vl[rt]);
  64.         }
  65.         return ;
  66.     }
  67.     int mid = (l + r) >> 1;
  68.     if (L <= mid) query(lson, L, R);
  69.     if (R > mid) query(rson, L, R);
  70. }
  72. int main() {
  73.     int n = read(), Q = read();
  74.     scanf("%s",s + 1);
  75.     for (int i=1; i<=n; ++i) 
  76.         a[i] = s[i] == '0' ? 1 : - 1;
  78.     for (int i=1; i<=n; ++i) pre[i] = pre[i - 1] + a[i];
  79.     for (int i=n; i>=1; --i) suf[i] = suf[i + 1] + a[i];
  81.     if (n <= 1000) { solve1(n, Q); return 0; }
  83.     build(Root);
  84.     while (Q --) {
  85.         int l = read(), r = read();
  86.         l --, r ++;
  87.         VL = Ans = INF;
  88.         query(Root, l, r);
  89.         Ans = Ans - pre[l] - suf[r];
  90.         printf("%d\n",-Ans);
  91.     }
  92.     return 0;
  93. }

倍增。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<map>
  11. #define fi(s) freopen(s,"r",stdin);
  12. #define fo(s) freopen(s,"w",stdout);
  13. using namespace std;
  14. typedef long long LL;
  16. inline int read() {
  17.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  18.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  19. }
  21. const int N = 200005;
  22. const int INF = 1e9;
  24. char s[N];
  25. int a[N], pre[N], suf[N], sk[N], st[N][20];
  27. struct Node{
  28.     int pos, sum, val, cnt; // 分别表示位置，和，最小后缀和，要删掉个数。 
  29. }f[N][20];
  31. Node operator + (Node A, Node B) {
  32.     Node C;
  33.     C.pos = B.pos;
  34.     C.sum = A.sum + B.sum;
  35.     C.val = min(B.val, B.sum + A.val);
  36.     C.cnt = A.cnt + B.cnt;
  37.     return C;
  38. }
  39. int getsum(int l,int r) {
  40.     if (l > r) return 0;
  41.     return suf[l] - suf[r + 1];
  42. }
  43. int getmin(int l,int r) {
  44.     if (l > r) return INF;
  45.     int t = log2(r - l + 1);
  46.     return min(st[l][t], st[r - (1<<t) + 1][t]);
  47. }
  48. void work() {
  49.     int l = read(), r = read();
  50.     if (l == r) {
  51.         if (s[l] == '1') puts("1");
  52.         else puts("0");
  53.         return ;
  54.     }
  55.     Node ans;
  56.     ans.pos = l; ans.val = INF; ans.sum = 0; ans.cnt = 0;
  57.     for (int j=19; j>=0; --j) 
  58.         if (f[ans.pos][j].pos <= r) 
  59.             ans = ans + f[ans.pos][j];
  60.     if (ans.pos < r) {
  61.         int sum = getsum(ans.pos + 1, r);
  62.         int mn = getmin(ans.pos + 1, r) - suf[r + 1];
  63.         ans.val = min(0, min(ans.val + sum, mn));
  64.     }
  65.     if (a[l] == -1) ans.cnt ++;
  66.     if (ans.cnt == (r-l+1)) ans.val = 0;
  67.     printf("%d\n", ans.cnt + (-ans.val));
  68. }
  69. int main() {
  70.     int n = read(), Q = read();
  71.     scanf("%s",s + 1);
  72.     for (int i=1; i<=n; ++i) 
  73.         a[i] = s[i] == '0' ? 1 : - 1;
  75.     memset(st, 0x3f, sizeof(st));
  76.     for (int i=n; i>=1; --i) suf[i] = suf[i + 1] + a[i], st[i][0] = suf[i];
  77.     for (int j=1; j<=19; ++j) 
  78.         for (int i=1; (i+(1<<(j-1)))<=n; ++i) {
  79.             st[i][j] = min(st[i][j - 1], st[i + (1<<(j-1))][j - 1]);
  80.         }
  82.     int top = 1;sk[top] = n + 1;
  83.     for (int p,i=n; i>=1; --i) {
  84.         if (s[i] == '0') {
  85.             if (top > 1) top --;
  86.         }
  87.         p = sk[top];
  88.         f[i][0].pos = p, f[i][0].sum = getsum(i + 1, p - 1), f[i][0].val = getmin(i + 1, p - 1) - suf[p];
  89.         f[i][0].cnt = 1;        
  90.         if (s[i] == '1') sk[++top] = i;
  91.     }
  93.     for (int j=0; j<=19; ++j) f[n+1][j].pos = n + 1;
  94.     for (int j=1; j<=19; ++j) 
  95.         for (int i=1; i<=n; ++i) 
  96.             f[i][j] = f[i][j - 1] + f[f[i][j-1].pos][j - 1];
  97.     while (Q--) work();
  98.     return 0;
  99. }

调试代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<map>
  11. #define fi(s) freopen(s,"r",stdin);
  12. #define fo(s) freopen(s,"w",stdout);
  13. using namespace std;
  14. typedef long long LL;
  16. inline int read() {
  17.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  18.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  19. }
  21. const int N = 200005;
  22. const int INF = 1e9;
  24. char s[N];
  25. int a[N], pre[N], suf[N], sk[N], st[N][20];
  27. struct Node{
  28.     int pos, sum, val, cnt;
  29. }f[N][20];
  31. Node operator + (Node A, Node B) {
  32.     Node C;
  33.     C.pos = B.pos;
  34.     C.sum = A.sum + B.sum;
  35.     C.val = min(B.val, B.sum + A.val);
  36.     C.cnt = A.cnt + B.cnt;
  37.     return C;
  38. }
  40. void solve1(int n, int Q) {     
  41.     while (Q--) {
  42.         int l = read(), r = read(), ans = 0;
  44.         for (int sum=0,i=l; i<=r; ++i) {
  45.             sum += a[i];
  46.             if (sum < 0) sum = 0, ans ++, a[i] = 0;
  47.         }
  48.         for (int sum=0,i=r; i>=l; --i) {
  49.             sum += a[i];
  50.             if (sum < 0) sum = 0, ans ++, a[i] = 0;
  51.         }
  52.         for (int i=l; i<=r; ++i) 
  53.             if (!a[i]) a[i] = -1;
  55.         printf("%d\n",ans);
  56.     }   
  57. }
  58. int getsum(int l,int r) {
  59.     if (l > r) return 0;
  60.     return suf[l] - suf[r + 1];
  61. }
  62. int getmin(int l,int r) {
  63.     if (l > r) return INF;
  64.     int t = log2(r - l + 1);
  65.     return min(st[l][t], st[r - (1<<t) + 1][t]);
  66. }
  67. void work() {
  68.     int l = read(), r = read();
  69.     if (l == r) {
  70.         if (s[l] == '1') puts("1");
  71.         else puts("0");
  72.         return ;
  73.     }
  74.     Node ans;
  75.     ans.pos = l; ans.val = INF; ans.sum = 0; ans.cnt = 0;
  76.     for (int j=19; j>=0; --j) {
  77. //      cout << f[ans.pos][j].pos << "\n";
  78.         if (f[ans.pos][j].pos <= r) {
  79.             ans = ans + f[ans.pos][j];
  80. //          cout << ans.pos << " "<< ans.sum << " " << ans.cnt << " " << ans.val << "\n";
  81.         }
  82.     }
  83. //  cout << ans.sum << " " << ans.cnt << " " << ans.val << "\n";
  84.     if (ans.pos < r) {
  85.         int sum = getsum(ans.pos + 1, r);
  86.         int mn = getmin(ans.pos + 1, r) - suf[r + 1];
  87.         ans.val = min(0, min(ans.val + sum, mn));
  88.     }
  89.     if (a[l] == -1) ans.cnt ++;
  90.     if (ans.cnt == (r-l+1)) ans.val = 0;
  91.     printf("%d\n", ans.cnt + (-ans.val));
  92. }
  93. //#define bd
  94. int main() {
  95. #ifdef bd
  96.     fi("2.txt");
  97. #endif
  98.     int n = read(), Q = read();
  99.     scanf("%s",s + 1);
  100.     for (int i=1; i<=n; ++i) 
  101.         a[i] = s[i] == '0' ? 1 : - 1;
  103. //  if (n <= 1000) { solve1(n, Q); return 0; }
  105.     memset(st, 0x3f, sizeof(st));
  107.     for (int i=n; i>=1; --i) suf[i] = suf[i + 1] + a[i], st[i][0] = suf[i];
  109.     for (int j=1; j<=19; ++j) 
  110.         for (int i=1; (i+(1<<(j-1)))<=n; ++i) {
  111.             st[i][j] = min(st[i][j - 1], st[i + (1<<(j-1))][j - 1]);
  112.         }
  114.     int top = 1;sk[top] = n + 1;
  115.     for (int p,i=n; i>=1; --i) {
  116.         if (s[i] == '0') {
  117.             if (top > 1) top --;
  118.         }
  120.         p = sk[top];
  121.         f[i][0].pos = p, f[i][0].sum = getsum(i + 1, p - 1), f[i][0].val = getmin(i + 1, p - 1) - suf[p];
  122.         f[i][0].cnt = 1;
  123. //      cout << p << " " << f[i][0].sum << " " << f[i][0].val  << " \n";
  125.         if (s[i] == '1') sk[++top] = i;
  126.     }
  128.     for (int j=0; j<=19; ++j) f[n+1][j].pos = n + 1;
  129.     for (int j=1; j<=19; ++j) 
  130.         for (int i=1; i<=n; ++i) {
  131.             f[i][j] = f[i][j - 1] + f[f[i][j-1].pos][j - 1];
  132. //          cout << i << " " << f[i][j].pos << "\n";
  133. //          cout << f[i][j].val << " " << f[i][j].sum << "\n";
  134.         }
  135.     while (Q--) work();
  137.     return 0;
  138. }
  139. /*
  140. 11 1
  141. 01110100111
  143. */

对拍数据生成器

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<map>
  11. #define fi(s) freopen(s,"r",stdin);
  12. #define fo(s) freopen(s,"w",stdout);
  13. #include<ctime>
  14. using namespace std;
  15. typedef long long LL;
  17. inline int read() {
  18.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  19.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  20. }
  22. int a[200005];
  24. int main() {
  25.     srand(time(0));
  26.     int n = 997, q = 1000;
  27.     cout << n << " " << q << "\n";
  28.     int t = rand() % n + 1;
  29.     for (int i=1; i<=t; ++i) a[i] = 1;
  30.     random_shuffle(a + 1, a + n + 1);
  31.     for (int i=1; i<=n; ++i) cout << a[i];
  32.     puts("");
  33.     for (int i=1; i<=q; ++i) {
  34.         int l = rand() % n + 1;
  35.         int r = rand() % (n - l + 1) + l;
  36.         cout << l << " " << r << "\n";
  37.     }
  38.     return 0;
  39. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注