• 欢迎光临~
> > 2022.8.21 摆烂记录

2022.8.21 摆烂记录

开发技术 开发技术 2022-08-21 次浏览

Preface

回归

Content

[luogu P4310]绝世好题

给定序列 (a_{1sim n})，求子序列 (b) 的最长长度 (k)，使得 (forall i in [2,k],b_imathsf{&}b_{i-1}gt 0)。

(1le nle 10^5,1le 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(nlog 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("%dn",ans);
    return 0;
}

[BJOI2019]排兵布阵

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

你可以在第 (i) 座城堡布置 (a_i) 个士兵，使得 (sum_{i=1}^n a_ile m)。

对于玩家 (i)，如果有 (a_j gt 2times b(i,j))，那么你可以获得 (j) 的收益。

求怎样布置士兵才能使收益最大。

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

不难想到朴素 DP：

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

状态转移方程：(f(i,j)=maxlimits_{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,2times b(1,i)+1,2times b(2,i)+1ldots 2times b(s,i)+1)。

如果 (b(1sim s,i)) 升序，那么这些取值对答案的贡献分别是 (0,1times i,2times i,ldots stimes 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("%dn",f[m]);
    return 0;
}

[CF1092D2]Great Vova Wall (Version 2)

给定 (a_{1sim n})，你可以进行无数次操作，每次找到一个整数 (i(iin [1,n-1])) 使得 (a_i=a_i+1)，然后 (a_igets a_i+1,a_{i+1}gets a_{i+1}+1)。

询问可否通过若干次操作使得 (a_1=a_2=ldots =a_n)。

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

可以用栈，但我不会，感觉栈的思路并不自然。

已经看出来了结论，就是不知道怎么做，看了 7kByte 大佬的题解醍醐灌顶。

显然操作要从小到大进行。

不难观察到一个结论，对于每个数 (x)，所有不超过 (x) 的 (a_i) 形成的连通块大小均为偶数。

将 (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
// 
// 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;
}

[JOISC2014 Day1 T3]歴史の研究

回滚莫队入门

程序员灯塔
转载请注明原文链接：2022.8.21 摆烂记录
喜欢 (0)