Preface
回归
Content
[luogu P4310]绝世好题
给定序列 \(a_{1\sim n}\)，求子序列 \(b\) 的最长长度 \(k\)，使得 \(\forall i \in [2,k],b_i\mathsf{\&}b_{i-1}\gt 0\)。
\(1\le n\le 10^5,1\le a_i \le 10^9\)。
跟二进制有关，考虑位运算。
发现 \(b_i \mathsf{\&}b_{i-1}\gt 0\) 的必要条件是 \(b_i,b_{i-1}\) 的某个二进制位 \(j\) 均为 \(1\)。
这启发我们对于每个二进制位开一个 dp 数组。
具体而言，令 \(dp(i,j)\) 表示前 \(i\) 个数的最长子序列的长度，且 \(b_{dp(i,j)}\) 的第 \(j\) 为 \(1\)。
直接更新即可。并且可以用滚动数组优化。时间复杂度 \(O(n\log a)\)。
Code
// Problem: P4310 绝世好题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4310
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,a[maxn],dp[32];
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
for(int k = 30;~ k;-- k)
if(a[1] >> k & 1)dp[k] = 1;
for(int i = 2;i <= n;++ i) {
int ans = 0;
for(int k = 30;~ k;-- k) {
if(a[i] >> k & 1)ans = max(ans , dp[k] + 1);
}
for(int k = 30;~ k;-- k) {
if(a[i] >> k & 1)dp[k] = max(dp[k] , ans);
}
}
int ans = 0;
for(int k = 30;~ k;-- k)ans = max(ans , dp[k]);
printf("%d\n",ans);
return 0;
}
[BJOI2019]排兵布阵
\(n\) 座城堡，\(s\) 名玩家，已知第 \(i\) 名玩家在第 \(j\) 座城堡布置了 \(b(i,j)\) 个士兵。
你可以在第 \(i\) 座城堡布置 \(a_i\) 个士兵，使得 \(\sum_{i=1}^n a_i\le m\)。
对于玩家 \(i\)，如果有 \(a_j \gt 2\times b(i,j)\)，那么你可以获得 \(j\) 的收益。
求怎样布置士兵才能使收益最大。
\(1\le n,s\le 100,1\le m\le 2\times 10^4\)。
不难想到朴素 DP：
设 \(f(i,j)\) 表示在前 \(i\) 个城堡总共布置 \(j\) 个士兵的最大收益。
状态转移方程：\(f(i,j)=\max\limits_{k=0}^j \{f(i-1,j-k)+calc(i,k) \}\)。
其中 \(calc(i,k)\) 表示在第 \(i\) 个城堡放 \(k\) 个士兵产生的收益。
时间复杂度 \(O(nm^2+nms)\)。其中 \(O(nms)\) 是预处理 \(calc(i,k)\)。
仔细想一想，发现其实 \(k\) 的枚举并没有这么复杂。
\(k\) 真正有效的取值，只有 \(0,2\times b(1,i)+1,2\times b(2,i)+1\ldots 2\times b(s,i)+1\)。
如果 \(b(1\sim s,i)\) 升序，那么这些取值对答案的贡献分别是 \(0,1\times i,2\times i,\ldots s\times i\)。
所以直接排个序跑分组背包即可。时间复杂度 \(O(nms)\)。感觉 \(1s\) 的时限不太可过，结果一看题解正解还真是这个 /jk
Code
// Problem: P5322 [BJOI2019] 排兵布阵
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5322
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int maxm = 2e4 + 5;
int n,m,s;
int f[maxm];
int a[maxn][maxn],c[maxn][maxn];
int main() {
scanf("%d %d %d",&s,&n,&m);
for(int i = 1;i <= s;++ i) {
for(int k = 1;k <= n;++ k) {
scanf("%d",&a[i][k]);
c[k][i] = a[i][k];
}
}
for(int i = 1;i <= n;++ i) {
sort(c[i] + 1 , c[i] + 1 + s);
for(int k = 1;k <= s;++ k)
c[i][k] = (c[i][k] << 1) + 1;
}
for(int i = 1;i <= n;++ i) {
for(int j = m;~ j;-- j) {
for(int k = 1;k <= s;++ k) {
if(j >= c[i][k])f[j] = max(f[j - c[i][k]] + k * i , f[j]);
else break ;
}
}
}
printf("%d\n",f[m]);
return 0;
}
[CF1092D2]Great Vova Wall (Version 2)
给定 \(a_{1\sim n}\)，你可以进行无数次操作，每次找到一个整数 \(i(i\in [1,n-1])\) 使得 \(a_i=a_i+1\)，然后 \(a_i\gets a_i+1,a_{i+1}\gets a_{i+1}+1\)。
询问可否通过若干次操作使得 \(a_1=a_2=\ldots =a_n\)。
\(1\le n\le 2\times 10^5,1\le a_i \le 10^9\)。
可以用栈，但我不会，感觉栈的思路并不自然。
已经看出来了结论，就是不知道怎么做，看了 7kByte 大佬的题解醍醐灌顶。
显然操作要从小到大进行。
不难观察到一个结论，对于每个数 \(x\)，所有不超过 \(x\) 的 \(a_i\) 形成的连通块大小均为偶数。
将 \(a_i\) 排序后从小到大加点，用并查集维护连通块即可。时间复杂度 \(O(n\log n)\)。
Code
// Problem: CF1092D2 Great Vova Wall (Version 2)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1092D2
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn],n,pre[maxn],sz[maxn],sum[2],rk[maxn];
bool flag = false;
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void merge(int x,int y) {
x = find(x);
y = find(y);
-- sum[sz[x] & 1];
-- sum[sz[y] & 1];
sz[x] += sz[y];
pre[y] = x;
++ sum[sz[x] & 1];
return ;
}
void solve(int l,int r) {
for(int i = l;i <= r;++ i) {
pre[rk[i]] = rk[i];
++ sum[sz[rk[i]] = 1];
if(pre[rk[i] - 1])merge(rk[i] - 1 , rk[i]);
if(pre[rk[i] + 1])merge(rk[i] + 1 , rk[i]);
}
if(sum[1])flag = true;
return ;
}
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),rk[i] = i;
sort(rk + 1 , rk + 1 + n , [&](const int& p,const int& q) {
return a[p] < a[q];
});
int lst = 1;
for(int i = 2;i <= n;++ i) {
if(a[rk[i]] != a[rk[i - 1]]) {
solve(lst , i - 1);
lst = i;
}
}
if(!flag)puts("YES");
else puts("NO");
return 0;
}