• 欢迎光临~

# Content

## [luogu P4310]绝世好题

(1le nle 10^5,1le a_i le 10^9)

### Code

``````// Problem: P4310 绝世好题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4310
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//

#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("%dn",ans);
return 0;
}
``````

## [BJOI2019]排兵布阵

(n) 座城堡，(s) 名玩家，已知第 (i) 名玩家在第 (j) 座城堡布置了 (b(i,j)) 个士兵。

(1le n,sle 100,1le mle 2times 10^4)

(f(i,j)) 表示在前 (i) 个城堡总共布置 (j) 个士兵的最大收益。

(k) 真正有效的取值，只有 (0,2times b(1,i)+1,2times b(2,i)+1ldots 2times b(s,i)+1)

### Code

``````// Problem: P5322 [BJOI2019] 排兵布阵
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5322
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//

#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("%dn",f[m]);
return 0;
}
``````

## [CF1092D2]Great Vova Wall (Version 2)

(1le nle 2times 10^5,1le a_i le 10^9)

(a_i) 排序后从小到大加点，用并查集维护连通块即可。时间复杂度 (O(nlog 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
//

#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;
}
``````