POI2014解题报告-白红宇

POI2014解题报告

阅读量：5233 次

发布时间：2019-06-14

本文共 25301 字，大约阅读时间需要 84 分钟。

穷酸博主没有bz权限号，也不会去$poi$官网，在某咕刷的$poi$，按照某咕的难度排序刷， poi~

$Luogu3572 PTA-Little Bird$

单调队列，队列内按照步数为第一关键字递增，高度为第二关键字递减

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define R register 6 #define N 1000005 7 using namespace std; 8  9 int n, k, Q;10 int d[N], f[N], q[N];11 12 inline int read() {13     int X = 0, p = 1; char c = getchar();14     for (; c > '9' || c < '0';c = getchar())15         if (c == '-') p = -1;16     for (; c >= '0' && c <= '9'; c = getchar())17         X = X * 10 + c - '0';18     return X * p;19 }20 21 int main()22 {23     n = rd;24     for (R int i = 1; i <= n; ++i) d[i] = rd;25     Q = rd; 26     for (; Q; Q--) {27         k = rd;28         int l = 1, r = 1;29         q[l] = 1;30         for (R int i = 2; i <= n; ++i) {31             while (l <= r && q[l] < i - k) l++;32             f[i] = f[q[l]] + (d[q[l]] <= d[i] ? 1 : 0);33             while (l <= r && (f[q[r]] > f[i] || (f[q[r]] == f[i] && d[q[r]] <= d[i]))) r--;34             q[++r] = i;35         }36         printf("%d\n", f[n]);37     }38 }

View Code

$Luogu3566KLO-Bricks$

贪心，优先用右端点$ed$的颜色的来填，如果$ed$用光了或者上一个颜色是$ed$，则选取剩下来个数最多的去填

个数最多可以用线段树维护

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define N 1000005 6 using namespace std; 7 typedef pair
         
           P; 8  9 int n, m, cnt[N], st, ed, a[N];10 11 int read() {12     int X = 0, p = 1; char c = getchar();13     for (; c > '9' || c < '0'; c = getchar())14         if (c == '-') p = -1;15     for (; c >= '0' && c <= '9'; c = getchar())16         X = X * 10 + c - '0';17     return X * p;18 }19 20 void up(int &A, int B) {21     if (A < B) A = B;22 }23 24 P cmax(P A, P B) {25     return A > B ? A : B;26 }27 28 namespace SegT {29 #define lson nd << 130 #define rson nd << 1 | 131 #define mid ((l + r) >> 1)32     P Max[N << 2];33     34     void pushup(int nd) {35         Max[nd] = cmax(Max[lson], Max[rson]);36     }37 38     void build(int l, int r, int nd) {39         if (l == r) {40             Max[nd] = P(cnt[l], l); return;41         }42         build(l, mid, lson); build(mid + 1, r, rson);43         pushup(nd);44     }45 46     void modify(int c, int l, int r, int nd) {47         if (l == r) {48             Max[nd].first-- ; return;49         }50         if (c <= mid) modify(c, l, mid, lson);51         else modify(c, mid + 1, r, rson);52         pushup(nd);53     }54 55     P query(int L, int R, int l, int r, int nd) {56         if (L > R) return P(0, 0);57         if (L <= l && r <= R) return Max[nd];58         P tmp = P(0, 0);59         if (mid >= L)60             tmp = cmax(tmp, query(L, R, l, mid, lson));61         if (mid < R)62             tmp = cmax(tmp, query(L, R, mid + 1, r, rson));63         return tmp;64     }65 }using namespace SegT;66 67 int main()68 {69     m = rd; st = rd; ed = rd;70     for (int i = 1; i <= m; ++i)71         n += (cnt[i] = rd);72     cnt[st] --; cnt[ed] --;73     a[1] = st; a[n] = ed;74     build(1, m, 1);75     for (int i = 2; i < n; ++i) {76         if (cnt[ed] && a[i - 1] != ed) {77             a[i] = ed;78             cnt[a[i]]--;79             modify(a[i], 1, m, 1);80         } else {81             P tmp = query(1, a[i - 1] - 1, 1, m, 1);82             tmp = cmax(tmp, query(a[i - 1] + 1, m, 1, m, 1));83             if (tmp.first == 0) return printf("0"), 0;84             a[i] = tmp.second;85             cnt[a[i]]--;86             modify(a[i], 1, m, 1);87         }88     }89     if (a[n - 1] == a[n]) 90         return printf("0"), 0;91     printf("%d", a[1]);92     for (int i = 2; i <= n; ++i)93         printf(" %d", a[i]);94     return 0;95 }

View Code

$Luogu3575DOO-Around the world$

双指针扫一遍，找到从 $i$ 往前最多能飞多少格。并记录步数和起始位置。当起始位置和当前位置相距不少于N，则更新答案。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define N 2000005 6 #define R register 7 using namespace std; 8  9 int n, m, f[N], head[N], maxn, a[N];10 11 int read() {12     int X = 0, p = 1; char c = getchar();13     for (; c > '9' || c < '0'; c = getchar())14         if (c == '-') p = -1;15     for (; c >= '0' && c <= '9'; c = getchar())16         X = X * 10 + c - '0';17     return X * p;18 }19 20 void cmax(int &A, int B) {21     if (A < B) A = B;22 }23 24 void cmin(int &A, int B) {25     if (A > B) A = B;26 }27 28 void work(int d) {29     if (d < maxn) {30         puts("NIE"); return;31     }32     int ans = n;33     for (R int i = n + 1, j = 1; i <= 2 * n; ++i) {34         while (a[i] - a[j] > d) j++;35         f[i] = f[j] + 1, head[i] = head[j];36         if (i - head[i] >= n) cmin(ans, f[i]);37     }38     printf("%d\n", ans);39 }40 41 int main()42 {43     n = rd; m = rd;44     for (R int i = 1; i <= n; ++i) 45         a[i] = a[i + n] = rd,46         cmax(maxn, a[i]),47         head[i] = i;48     for (R int i = 1; i <= 2 * n; ++i)49         a[i] += a[i - 1];50     for (R int i = 1; i <= m; ++i) work(rd);51 }

View Code

$Luogu3565Hotels$

枚举根节点为中心，在根的不同儿子的子树中找$3$个相同深度的点的方案数。时间复杂度$O(N^2)$，

不过好像用长链剖分可以做到$O(N)$。。。老年选手也懒得去学了唔

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define N 5005 6 #define ll long long 7 #define R register 8 using namespace std; 9 10 int head[N], tot, dep[N], g[N], n;11 ll ans, f[N][3];12 13 struct edge {14     int nxt, to;15 }e[N << 1];16 17 inline int read() {18     int X = 0, p = 1; char c = getchar();19     for (; c > '9' || c < '0'; c = getchar())20         if (c == '-') p = -1;21     for (; c >= '0' && c <= '9'; c = getchar())22         X = X * 10 + c - '0';23     return X * p;24 }25 26 void add(int u, int v) {27     e[++tot].to = v;28     e[tot].nxt = head[u];29     head[u] = tot;30 }31 32 void cmax(int &A, int B) {33     if (A < B) A = B;34 }35 36 void dfs(int u, int fa) {37     g[dep[u]] ++;38     for (R int i = head[u]; i; i = e[i].nxt) {39         int nt = e[i].to;40         if (nt == fa) continue;41         dep[nt] = dep[u] + 1;42         dfs(nt, u);43     }44 }45 46 int main()47 {48     n = rd; 49     for (int i = 1; i < n; ++i) {50         int u = rd, v = rd;51         add(u, v); add(v, u);52     }53     for (R int rt = 1; rt <= n; ++rt) {54         dep[rt] = 1;55         memset(f, 0, sizeof(f));56         for (R int i = head[rt]; i; i = e[i].nxt) {57             memset(g, 0, sizeof(g));58             dep[e[i].to] = 2;59             dfs(e[i].to, rt);60             for (R int j = 2; j; --j)61                 for (R int k = 1; k <= n; ++k)62                     f[k][j] += f[k][j - 1] * g[k];63             for (R int k = 1; k <= n; ++k)64                 f[k][0] += g[k];65         }66         for (R int i = 1; i <= n; ++i)67             ans += f[i][2];68     }69     printf("%lld\n", ans);70 }

View Code

$Luogu3580Freight$

列车肯定是分批，一批过去再回来，才轮到下一批。

然后就开始$DP$, 设$F[i]$ 为前 $i$ 辆列车回来的最早时间，同时为了防止不同列车同时出发，令$t[i] = max(t[i], t[i-1] + 1)$

有状态转移方程：

　　$f[i] \ = \ min( \ max(f[j] + i -j-1, t[i])+2 \times S + i - j - 1)$

移项得：

　　$f[i] \ = \ 2 \times S + 2 \times i -1 \ + \ min( \ max(f[j] - j - 1, t[i] - i)-j)$

由于 $f[j] - j-1$ 和 $t[i] - i$ 是不下降的，所以用单调队列找到第一个分界点，并且队列除第一位按照 $f[j]-2 \times j - 1$ 递增

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define N 1000005 6 #define R register 7 #define ll long long 8 using namespace std; 9 10 int n, t[N], q[N], S;11 ll f[N];12 13 inline int read() {14     int X = 0, p = 1; char c = getchar();15     for (; c > '9' || c < '0'; c = getchar())16         if (c == '-') p = -1;17     for (; c >= '0' && c <= '9'; c = getchar())18         X = X * 10 + c - '0';19     return X * p;20 }21 22 inline int cmax(int A, int B) {23     return A > B ? A : B;24 }25 26 template
         
          27 inline void down(T &A, T B) {28     if (A > B) A = B;29 }30 31 int main()32 {33     n = rd; S = rd;34     for (R int i = 1; i <= n; ++i) 35         t[i] = cmax(rd, t[i - 1] + 1);36     int l = 1, r = 1;37     for (R int i = 1; i <= n; ++i) {38         while (l < r && f[q[l + 1]] - q[l + 1] - 1<= t[i] - i) l++;39         f[i] = 1LL * t[i] + i - q[l] + 2 * S - 1;40         if (l < r) down(f[i], f[q[l + 1]] - 2 * q[l + 1] - 1 + 2 * S + 2 * i - 1);41         while (l < r && f[q[r]] - 2 * q[r] >= f[i] - 2 * i) r--;42         q[++r] = i;43     }44     printf("%lld\n", f[n]);45 }

View Code

$Luogu3574FarmCraft$

贪心排序+树形DP

我们可以递归求出每颗子树所需要的最大时间，

子节点到父节点的转移方程：

　　$f[u] \ = \ max(2 \times \sum\limits_{k=1}^{i-1}sz[k] + f[i]+1)$ ，父节点 $f[u]$ 初始为 $a[u]$

根据贪心，把子树按照$2 \times sz[i]-f[i]$进行排序（证明挺简单的，邻项交换就可以证出）

由于根节点是要最后安装电脑的， $f[1] = max(f[1], a[1] + 2 \times (sz[1] - 1) )$

最后输出$f[1]$，复杂度$O(NlogN)$

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N 500005 6 #define rd read() 7 using namespace std; 8  9 int head[N], tot, n, f[N], sz[N], a[N];10 vector
          
            v[N];11 12 struct edge {13     int nxt, to;14 }e[N << 1];15 16 inline int read() {17     int X = 0, p = 1; char c = getchar();18     for (; c > '9' || c < '0'; c = getchar())19         if (c == '-') p = -1;20     for (; c >= '0' && c <= '9'; c = getchar())21         X = X * 10 + c - '0';22     return X * p;23 }24 25 void add(int fr, int to) {26     e[++tot].to = to;27     e[tot].nxt = head[fr];28     head[fr] = tot;29 }30 31 int cmp(int A, int B) {32     return 2 * sz[A] - f[A] < 2 * sz[B] - f[B];33 }34 35 void dfs(int u, int fa) {36     for (int i = head[u]; i; i = e[i].nxt) {37         int nt = e[i].to;38         if (nt == fa) continue;39         dfs(nt, u);40         v[u].push_back(nt);41     }42 }43 44 void cmax(int &A, int B) {45     if (A < B) A = B;46 }47 48 void dp(int u) {49     sz[u] = 1;50     f[u] = a[u];51     for (int i = 0, up = v[u].size(); i < up; ++i) {52         int nt = v[u][i];53         dp(nt);54     }55     sort(v[u].begin(), v[u].end(), cmp);56     for (int i = 0, up = v[u].size(); i < up; ++i) {57         int nt = v[u][i];58         cmax(f[u], 2 * sz[u] + f[nt] - 1);59         sz[u] += sz[nt];60     }61 }62 63 int main()64 {65     n = rd;66     for (int i = 1; i <= n; ++i) a[i] = rd;67     for (int i = 1; i < n; ++i) {68         int fr = rd, to = rd;69         add(fr, to); add(to, fr);70     }71     dfs(1, 0); dp(1);72     cmax(f[1], 2 * (n - 1) + a[1]);73     printf("%d\n", f[1]);74 }

View Code

$Luogu3570Criminals$

挺早前就做了的题。。。看不惯当时的毒瘤代码，空格有时有，有时没有。

就是一个链表乱搞，就不贴代码丢脸了（捂脸）

$Luogu3567Couriers$

主席树模板题

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 using namespace std; 6  7 const int N = 1e5; 8  9 int lson[N * 100], rson[N * 100], sum[N * 100];10 int a[N * 10], n, m, root[N * 10], b[N * 10], tot, cnt;11 12 int read() {13     int X = 0, p = 1; char c = getchar();14     for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;15     for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 +  c - '0';16     return X * p;17 }18 19 int fd(int x) {20     return lower_bound(b + 1, b + 1 + tot, x) - b;21 }22 23 void build0(int &o, int l, int r) {24     o = ++cnt;25     if(l == r) return;26     int mid = (l + r) >> 1;27     build0(lson[o], l, mid);28     build0(rson[o], mid + 1, r);29 }30 31 void build(int last, int &o, int pos, int l, int r) {32     o = ++cnt;33     sum[o] = sum[last] + 1;34     lson[o] = lson[last];35     rson[o] = rson[last];36     if(l == r)37         return;38     int mid = (l + r) >> 1;39     if(pos <= mid)40         build(lson[last], lson[o], pos, l, mid);41     else 42         build(rson[last], rson[o], pos, mid + 1, r);43 }44 45 int query(int last, int now, int k, int l, int r) {46     if(l == r)47         return (2 * (sum[now] - sum[last]) > k) ? l : 0;48     int mid = (l + r) >> 1;49     if(2 * (sum[lson[now]] - sum[lson[last]]) > k)50         return query(lson[last], lson[now], k, l, mid);51     else 52         return query(rson[last], rson[now], k, mid + 1, r);53 }54 55 int main()56 {57     n = rd; m = rd;58     for(int i = 1; i <= n; ++i)59         b[i] = a[i] = rd;60     sort(b + 1, b + 1 + n);61     tot = unique(b + 1, b + 1 + n) - b - 1;62     for(int i = 1; i <= n; ++i) 63         build(root[i - 1], root[i], fd(a[i]), 1, tot);64     for(int i = 1; i <= m; ++i) {65         int l = rd, r = rd, ans;66         ans = query(root[l - 1], root[r], r - l + 1, 1, tot);67         printf("%d\n", b[ans]);68     }69 }

View Code

$Luogu3572Ant colony$

倍增LCA+二分查找

$f[i][j]$ 表示 $i$ 的 $2^j$ 级祖先， $g[i][j]$ 表示从i 到 $f[i][j]$ 要分支成几份。另外$g[i][j]$ 可能非常大，最高约是 $3$的几万次方，所以如果$g[i][j] \times k > a[m]$，直接赋为$-1$

然后就可以倍增求要几个分支，设分支数为 $x$，则最后被吃掉的蚂蚁数就是数组a中 $k \times x<= <=(k + 1) \times -1$的个数，二分查找即可。

时间复杂度为$O(NlogN)$， (做POI习惯性卡常数了

1 #include
      
         2 #include
       
          3 #include
        
           4 #define rd read()  5 #define N 1000005  6 #define ll long long  7 #define R register  8 using namespace std;  9  10 const int base = 20; 11  12 int n, m, k, tot, st, ed; 13 int head[N], a[N], f[N][base], d[N], leaf[N], cnt, dep[N]; 14 ll g[N][base], ans; 15 bool in[N]; 16  17 struct edge { 18     int nxt, to; 19 }e[N << 1]; 20  21 inline int read() { 22     int X = 0, p = 1; char c = getchar(); 23     for (; c > '9' || c < '0'; c = getchar()) 24         if (c == '-') p = -1; 25     for (; c >= '0' && c <= '9'; c = getchar()) 26         X = X * 10 + c - '0'; 27     return X * p; 28 } 29  30 inline void add(int u, int v) { 31     e[++tot].to = v; 32     e[tot].nxt = head[u]; 33     head[u] = tot; 34 } 35  36 void dfs(int u, bool flag) { 37     in[u] = flag; 38     for (R int i = head[u]; i; i = e[i].nxt) { 39         R int nt = e[i].to; 40         if (nt == f[u][0]) continue; 41         f[nt][0] = u; 42         g[nt][0] = (d[nt] - 1) ? d[nt] - 1 : 1; 43         dep[nt] = dep[u] + 1; 44         if ((u == e[1].to && nt == e[2].to) || (nt == e[1].to && u == e[2].to)) 45             dfs(nt, true); 46         else dfs(nt, flag); 47     } 48 } 49  50 inline int cal(int x) { 51     int maxn = upper_bound(a + 1, a + 1 + m, 1LL * (k + 1) * x - 1) - a, 52     minn = lower_bound(a + 1, a + 1 + m, k * x) - a; 53     return maxn - minn; 54 } 55  56 int LCA(R int x, R int y) { 57     ll res = 1; 58     if (dep[x] < dep[y]) swap(x, y); 59     for (R int j = base - 1; ~j; --j) 60         if (dep[f[x][j]] >= dep[y]) { 61             res *= g[x][j]; 62             if (res * k > a[m] || res < 0) return -1; 63             x = f[x][j]; 64         } 65     if (x == y) { 66         res *= g[x][0]; 67         if (res * k > a[m] || res < 0) return -1; 68         else return res; 69     } 70     for (R int j = base - 1; ~j; --j) 71         if (f[x][j] != f[y][j]) { 72             res *= g[x][j]; 73             res *= g[y][j]; 74             if (res * k > a[m] || res < 0) return -1; 75             x = f[x][j]; 76             y = f[y][j]; 77         } 78     res *= g[x][1] * g[y][0]; 79     if (res * k > a[m] || res < 0) return -1; 80     return res; 81 } 82  83 void work(int x) { 84     R int tmp = LCA(x, in[x] ? ed : st); 85     if (tmp != -1) ans += 1LL * cal(tmp) * k; 86 } 87  88 int main() 89 { 90     n = rd; m = rd; k = rd; 91     for (R int i = 1; i <= m; ++i) 92         a[i] = rd; 93     for (R int i = 1; i < n; ++i) { 94         int u = rd, v = rd; 95         add(u, v); add(v, u); 96         d[u] ++; d[v] ++; 97     } 98     dep[1] = 1; 99     dfs(1, false);100     g[1][0] = (d[1] - 1) ? d[1] - 1 : 1;101     sort(a + 1, a + 1 + m);102     if (dep[e[1].to] > dep[e[2].to]) st = e[2].to, ed = e[1].to;103     else st = e[1].to, ed = e[2].to;104     for (R int i = 1; i <= n; ++i)105         if (d[i] == 1) leaf[++cnt] = i;106     for (R int j = 1; j < base; ++j)107         for (R int i = 1; i <= n; ++i) {108             f[i][j] = f[f[i][j - 1]][j - 1],109             g[i][j] = g[i][j - 1] * g[f[i][j - 1]][j - 1];110             if (g[i][j] * k > a[m]) g[i][j] = -1;111             else if (g[i][j] < 0) g[i][j] = -1;112         }113     for (R int i = 1; i <= cnt; ++i)114         work(leaf[i]);115     printf("%lld\n", ans);116 }

View Code

$Luogu3564Salad Bar$

树状数组

若$s[i]=='j'$，则赋为 $-1$，若为$'p'$，则赋为 $1$。定义 $sum$为前缀和。

则一个字符串 $[j,i]$ 从前往后的$1$的个数不少于 $-1$的个数，则满足 $sum[j-1] <= sum[k]$ $(j<=k<=i)$ 恒成立。

根据这一点，若要知道最多往后到哪里，只需往后找到第一个 $i$，$sum[i]>sum[j]$。单调栈$O(N)$即可维护。往前同理可得。

我们设从 $i$往后最多到 $R[i]$，往前最多到 $L[i]$。一个字符串 $[j,i]$ 满足条件必须使 $R[j]>=i \& \& L[i]<=j$

我们只需要先把 $i$ 按照 $R[i]$从小往大排序，用树状数组维护即可。

时间复杂度$O(NlogN)$

1 #include
      
         2 #include
       
          3 #include
        
           4 #define rg register  5 #define rd read()  6 #define N 1000005  7 using namespace std;  8   9 int a[N], b[N], n, pre[N], nxt[N]; 10 int st[N], tp, Max[N], ans; 11 char s[N]; 12  13 struct node { 14     int id, L, R; 15     bool operator < (const node &A) const { 16         return R < A.R; 17     } 18 }t[N]; 19  20 int read() { 21     int X = 0, p = 1; char c = getchar(); 22     for (; c > '9' || c < '0'; c = getchar()) 23         if (c == '-') p = -1; 24     for (; c >= '0' && c <= '9'; c = getchar()) 25         X = X * 10 + c - '0'; 26     return X * p; 27 } 28  29 void init() { 30     for (rg int i = 1; i <= n + 1; ++i) { 31         int pr = 0; 32         while (tp) { 33             if (b[st[tp]] >= b[i]) tp--; 34             else { 35                 pr = st[tp]; break; 36             } 37         } 38         pre[i] = pr; 39         st[++tp] = i; 40     } 41     tp = 0; 42     for (rg int i = n; ~i; --i) { 43         int nt = n + 1; 44         while (tp) { 45             if (a[st[tp]] >= a[i]) tp--; 46             else { 47                 nt = st[tp]; break; 48             } 49         } 50         nxt[i] = nt; 51         st[++tp] = i; 52     } 53 } 54  55 inline int cmin(int A, int B) { 56     return A > B ? B : A; 57 } 58  59 inline int cmax(int A, int B) { 60     return A > B ? A : B; 61 } 62  63 inline void up(int &A, int B) { 64     if (A < B) A = B; 65 } 66  67 int lowbit(int x) { 68     return x & -x; 69 } 70  71 void add(int x, int val) { 72     for (; x <= n; x += lowbit(x)) 73         up(Max[x], val); 74 } 75  76 int query(int x) { 77     int res = 0; 78     for (; x; x -= lowbit(x)) 79         up(res, Max[x]); 80     return res; 81 } 82  83 int main() 84 { 85     n = rd; 86     scanf("%s", s + 1); 87     for (rg int i = 1; i <= n; ++i)  88         a[i] = a[i - 1] + (s[i] == 'p' ? 1 : -1); 89     for (rg int i = n; i; --i) 90         b[i] = b[i + 1] + (s[i] == 'p' ? 1 : -1); 91     init(); 92     for (rg int i = 1; i <= n; ++i)  93         pre[i] = pre[i + 1] + 1; 94     for (rg int i = n; i; --i) 95         nxt[i] = nxt[i - 1] - 1; 96     for (rg int i = 1; i <= n; ++i) { 97         t[i].id = i; 98         t[i].L = pre[i]; 99         t[i].R = nxt[i];100     }101     sort(t + 1, t + 1 + n);102     for (rg int i = 1, j = 1; i <= n; ++i) {103         while (j <= n && j <= t[i].R) add(pre[j], j), j++;104         int res = query(t[i].id);105         up(ans, res - t[i].id + 1);106     }107     printf("%d\n", ans);108 }

View Code

$Luogu3579Solar Panels$

整除分块枚举。。。

发现Latex不支持下取整，然后用markdown打的一篇博客→

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define R register 6 using namespace std; 7  8 inline int read() { 9     int X = 0, p = 1; char c = getchar();10     for (; c > '9' || c < '0'; c =  getchar())11         if (c == '-') p = -1;12     for (; c >= '0' && c <= '9'; c = getchar())13         X = X * 10 + c - '0';14     return X * p;15 }16 17 inline void cmax(int &A, int B) {18     if (A < B) A = B;19 }20 21 inline int cmin(int A, int B) {22     return A > B ? B : A;23 }24 25 void work() {26     int ans = 1;27     int a = rd - 1, b = rd, c = rd - 1, d = rd;28     for (R int i = 1, j = 1, up = cmin(b, d); i <= up; i = j + 1) {29         j = cmin(b / (b / i), d / (d / i));30         if (b / j > a / j && d / j > c / j) cmax(ans, j);31     }32     printf("%d\n", ans);33 }34 35 int main()36 {37     int n = rd;38     for (; n; --n) work(); 39 }

View Code

$Luogu3569Cards$

单点改，线段树维护区间信息

对于每段区间，我们分别求出如果第一个位置取大的数和取小的数是否可行，如果可行，则最后一个位置尽量小的数是多少。

这种区间信息可以用线段树合并。最后的答案在区间$[1,N]$。

复杂度$O(MlogN)$，数据比较卡常（我当然是吸了氧气才过去的）

我swap自己写的函数挂了咕咕咕，两个地址相同的时候就会都变成$0$，算是一个教训QAQ

1 #include
      
        2 #include
       
         3 #include
        
          4 #define rd read() 5 #define R register 6 using namespace std; 7  8 const int N = 2e5 + 5; 9 10 int n, m;11 int a[N], b[N];12 13 inline int read() {14     int X = 0, p = 1; char c = getchar();15     for (; c > '9' || c < '0'; c = getchar())16         if (c == '-') p = -1;17     for (; c >= '0' && c <= '9'; c = getchar())18         X = X * 10 + c - '0';19     return X * p;20 }21 22 inline void sw(int &A, int &B) {23     int tmp = A;24     A = B; B = tmp;25 }26 27 namespace SegT {28 #define lson x << 129 #define rson x << 1 | 130 #define mid ((l + r) >> 1)31     int ok[N << 2][3], rmin[N << 2][3], lval[N << 2][3];32 33     inline void up(int x) {34         ok[x][1] = ok[x][2] = 0;35         lval[x][1] = lval[lson][1];36         lval[x][2] = lval[lson][2];37         if (!ok[lson][1] || !ok[rson][1])38             return;39         if (lval[rson][1] >= rmin[lson][1]) {40             ok[x][1] = 1; rmin[x][1] = rmin[rson][1];41         }42         else if (lval[rson][2] >= rmin[lson][1] && ok[rson][2]) {43             ok[x][1] = 1; rmin[x][1] = rmin[rson][2];44         }45         if (!ok[lson][2]) return;46         if (lval[rson][1] >= rmin[lson][2]) {47             ok[x][2] = 1; rmin[x][2] = rmin[rson][1];48         }49         else if (lval[rson][2] >= rmin[lson][2] && ok[rson][2]) {50             ok[x][2] = 1; rmin[x][2] = rmin[rson][2];51         }52     }53 54     void build(int l, int r, int x) {55         if (l == r) {56             ok[x][1] = ok[x][2] = 1;57             rmin[x][1] = lval[x][1] = a[l];58             rmin[x][2] = lval[x][2] = b[l];59             return;60         }61         build(l, mid, lson);62         build(mid + 1, r, rson);63         up(x);64     }65 66     void modify(int c, int val1, int val2, int l, int r, int x) {67         if (l == r) {68             lval[x][1] = rmin[x][1] = val1; 69             lval[x][2] = rmin[x][2] = val2;70             return;71         }72         if (c <= mid) modify(c, val1, val2, l, mid, lson);73         else modify(c, val1, val2, mid + 1, r, rson);74         up(x);75     }76 }using namespace SegT;77 78 int main()79 {80     n = rd;81     for (R int i = 1; i <= n; ++i) {82         a[i] = rd; b[i] = rd;83         if (a[i] > b[i]) sw(a[i], b[i]);84     }85     build(1, n, 1);86     m = rd;87     for (R int i = 1; i <= m; ++i) {88         R int x = rd, y = rd;89         modify(x, a[y], b[y], 1, n, 1);90         modify(y, a[x], b[x], 1, n, 1);91         if (ok[1][1]) puts("TAK");92         else puts("NIE");93         sw(a[x], a[y]); sw(b[x], b[y]);94     }95 }

View Code

$Luogu3573Rally$

不看题解是不可能的，这辈子都不可能的。。。

真的没有想到这种神仙做法QAQ。 Orz

用可重集代替一下堆？

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define rd read() 7 #define rg register 8 using namespace std; 9 10 const int N = 5e5 + 5;11 12 int n, m, f[N][2], st, ed, d[N], ans1, ans2 = N + 1;13 14 vector
           
             to[N], fr[N];15 multiset
            
              S;16 queue
             
               q;17 18 inline int read() {19 int X = 0, p = 1; char c = getchar();20 for (; c > '9' || c < '0'; c = getchar())21 if (c == '-') p = -1;22 for (; c >= '0' && c <= '9'; c = getchar())23 X = X * 10 + c - '0';24 return X * p;25 }26 27 inline void getmax(int &A, int B) {28 if (A < B) A = B;29 }30 31 int dp0(int u) {32 if (u == ed) return 0;33 if (f[u][0]) return f[u][0];34 for (rg int i = 0, up = to[u].size(); i < up; ++i) 35 getmax(f[u][0], dp0(to[u][i]) + 1);36 return f[u][0];37 }38 39 int dp1(int u) {40 if (u == st) return 0;41 if (f[u][1]) return f[u][1];42 for (rg int i = 0, up = fr[u].size(); i < up; ++i) 43 getmax(f[u][1], dp1(fr[u][i]) + 1);44 return f[u][1];45 }46 47 void del(int u) {48 for (rg int i = 0, up = fr[u].size(); i < up; ++i)49 S.erase(S.find(f[u][0] + f[fr[u][i]][1] - 1));50 }51 52 void Topsort() {53 q.push(st);54 for (; !q.empty();) {55 int u = q.front(); q.pop();56 if (u != st && u != ed) {57 del(u); int tmp = *(--S.end());58 if (tmp < ans2) ans2 = tmp, ans1 = u;59 }60 for (rg int i = 0, up = to[u].size(); i < up; ++i) {61 int nt = to[u][i];62 S.insert(f[u][1] + f[nt][0] - 1);63 if (!(--d[nt])) q.push(nt);64 }65 }66 }67 68 int main()69 {70 n = rd; m = rd;71 st = 0; ed = n + 1;72 for (rg int i = 1; i <= m; ++i) {73 int u = rd, v = rd;74 to[u].push_back(v);75 fr[v].push_back(u);76 d[v]++;77 }78 for (rg int i = 1; i <= n; ++i) {79 to[st].push_back(i);80 to[i].push_back(ed);81 fr[ed].push_back(i);82 fr[i].push_back(st);83 d[i]++; d[ed]++;84 }85 dp0(st); dp1(ed);86 Topsort();87 printf("%d %d\n", ans1, ans2);88 }