CF1826E nowcoder55993G - bitset -

CF1826E
这个题比赛的时候基本做出来了，就是不会用 bitset 导致最后寄了。这已经是第三次很有希望做出 E 最后没有做出来了 /ll
好几个月了一直卡在四题，吐了

首先如果对于一个模特，她在 \(i\) 城市的所有分数都分别小于 \(j\) 城市的，那么就 \(i\rightarrow j\) 连一条边，显然这是若干个 DAG，跑 dp 即可

如何判断“分别小于”这个条件？直接判断是 \(O(n^2m)\) 的，显然不行
考虑先固定一个城市，然后按照这个城市的评分对模特排序。考虑对于一个模特，有哪些模特比她小，显然可以用一个 01 串表示。由于小于具有传递性，因此这个 01 串也是可以继承的，每次找到相同的一串人的评分，就更新这一串人的 01 串即可。
可以用 bitset<5002> bit[5002] 维护，其中 bit[i][j] 表示 \(i\rightarrow j\) 是否有边
回到本题，如果 \(i\rightarrow j\) 有边，即 \(i\) 模特比 \(j\) 模特的所有城市的评分都要低，我们可以对每一个城市中 模特 \(i\) 的 01 串取 and（\(bit[i][j]\) 这一位为 1 代表 \(i\) 在某一个城市比 \(j\) 小，取了 & 也就是要求所有的城市都比 \(j\) 小）
复杂度瓶颈在于每次对两个城市 01 串 & 的时候，bitset 优化复杂度 /32
时间复杂度 \(O(n^2m/32)\)

55993G
考虑对于 \(b_i\) 维护有哪些 \(a_j\) 满足 \(a_j\geq b_i\)
例如样例中 \(b_1=2\) 对应的 01 串就是 \(011111\)
问题转化为了有多少个“阶梯型”的 1 ，因为这种才能满足 \(S_i\geq B_i\) 条件
如样例：
011111
010111
010111

发现 \(b_i\) 大的可以由 \(b_i\) 小的继承过来，直接从小到大计算即可，计算阶梯型可以用右移取 &

思考：能用 bitset 是因为这两题都涉及了大小关系，也就是 01 关系，使用 bitset 可以减小 取& 的复杂度

1826E

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 5005;

int m,n;
int p[maxn];
pii a[maxn];
bitset<5005>g[5005];
vector<int>gr[5005];

signed main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)g[i][j] = 1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)scanf("%d",&a[j].first), a[j].second = j;
		sort(a+1,a+n+1);
		bitset<5005>can;
		for(int i=1;i<=n;){
			int j=i;
			while(j<n && a[j+1].first == a[i].first)++ j;
			for(int k=i;k<=j;k++){
				g[a[k].second] &= can;
			}
			for(int k=i;k<=j;k++)
				can[a[k].second] = 1;
			
			i = j+1;
		}
	}
	
	vector<int>de(n+1, 0);
	vector<ll> dp(n+1, 0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j])gr[i].pb(j), ++ de[j];
		}
	}
	
	queue<int>Q;
	for(int i=1;i<=n;i++)if(!de[i])Q.push(i);
	ll ans = 0;
	for(int i=1;i<=n;i++)dp[i] = p[i], ans = max(ans, dp[i]);
	
	while(!Q.empty()){
		int u = Q.front();Q.pop();
		for(int v : gr[u]){
			dp[v] = max(dp[v], dp[u] + p[v]);
			ans = max(ans, dp[v]);
			if(!--de[v])Q.push(v);
		}
	}
	printf("%lld\n",ans);

	return 0;
}

55993G

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n,m;
pii a[maxn], b[maxn];

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].first),a[i].second = i;
	for(int i=1;i<=m;i++)scanf("%d",&b[i].first),b[i].second = i;
	
	sort(a+1,a+n+1,[&](pii a,pii b){return a.first>b.first;});
	sort(b+1,b+m+1,[&](pii a,pii b){return a.first>b.first;});
	
	bitset<150002>now,ans;
	for(int i=1;i<=n;i++)ans[i] = 1;
	for(int i=1,j=0;i<=m;i++){
		int lst = j;
		while(lst < n && a[lst+1].first >= b[i].first){
			now[a[lst+1].second] = 1;
//			printf("! %d\n",a[lst+1].second);
			++ lst;
		}
//		debug();
		ans &= now >> (b[i].second-1);
		j = lst;
	}
	printf("%d\n",ans.count());

	return 0;
}