B 水平考试

======

等价于两个集合 S,TS, T 判断 SS 中是否存在 TT 中所不包含的元素。

  • 若存在则输出 0；
  • 否则输出 10。

时间复杂度：O(T)O(T)

C题：区间查询当前区间可以被分为多少段，要求每段只有一种数字。

做法1：提前对所有段编号，查询时直接左右边界编号相减，注意边界需要特别处理
做法2：标记第i段与第i+1段之间的分界点，然后求前缀和，本质上和做法1一样

D题：给定网格，0表示障碍，1表示道路。问有多少块长方形道路？（正方形也是长方形）

对此我们首先用过bfs找到连通块，对于每个连通块我们需要维护这个连通块最大x，y坐标，
最小x，y坐标，以及连通块大小。当连通块是矩形的时候通过
统计矩形的(minX, minY) -> (maxX, maxY)

然后判断 (maxY - minY + 1) * (maxX - minX + 1) == 连通图的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Problem: 剪纸游戏
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/73450/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 1e3 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
bool st[N][N];
int  a[N][N];
int dx[5]={0,1,-1,0};
int dy[5]={1,0,0,-1};
vector<pii>mx(N*N,{-1,-1});
vector<pii>mn(N*N,{2000,2000});
vector<int>sz(N*N,0);
queue<pii>q;
int cnt=0;
void bfs(int x,int y){
	//cerr<<x<<" "<<y<<endl;
	q.push({x,y});
	st[x][y]=true;
	sz[cnt]++;
	mx[cnt].first=max(mx[cnt].first,x);
	mx[cnt].second=max(mx[cnt].second,y);
	// mx[cnt]=max(mx[cnt],{x,y});
	// mn[cnt]=min(mn[cnt],{x,y});
	
	mn[cnt].first=min(mn[cnt].first,x);
	mn[cnt].second=min(mn[cnt].second,y);
	while(q.size()){
		auto t=q.front();q.pop();
		
		for(int i=0;i<4;i++){
			int tx=t.first+dx[i];
			int ty=t.second+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]&&!st[tx][ty]){
				q.push({tx,ty});st[tx][ty]=true;
				sz[cnt]++;
				mx[cnt].first=max(mx[cnt].first,tx);
	mx[cnt].second=max(mx[cnt].second,ty);
	
	mn[cnt].first=min(mn[cnt].first,tx);
	mn[cnt].second=min(mn[cnt].second,ty);
	//mx[cnt]=max(mx[cnt],{tx,ty});
	//mn[cnt]=min(mn[cnt],{tx,ty});
			}
		}
	}
	// cerr<<sz[cnt]<<endl;
	// cerr<<mx[cnt].first<<" "<<mx[cnt].second<<endl;
	// cerr<<mn[cnt].first<<" "<<mn[cnt].second<<endl;
	// cerr<<"***************************"<<endl;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;cin>>c;
			if(c=='.')a[i][j]=1;
			else a[i][j]=0;
			//cerr<<a[i][j]<<" ";
		}
		//cerr<<endl;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==0||st[i][j])continue;
			bfs(i,j);
		cnt++;
			
			
			
			
		}
	}
	int res=0;
	//cerr<<cnt<<endl;
	for(int i=0;i<cnt;i++){
		int l=mx[i].first-mn[i].first+1;
		int r=mx[i].second-mn[i].second+1;
		if(l*r==sz[i]){
			res++;
		//cerr<<l<<" "<<r<<' '<<sz[cnt]<<endl;
		}
	}	
	cout<<res<<endl;
}
signed main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}

E题：带容量下限的最大连续子数组和

简单无脑做法：

  • 枚举每个起点，他的终点是j到n的任意一点。j是从左到右第一个满足当前区间容量大于W的坐标，对于这一过程我们显然需要维护容量的前缀和然后二分。我们希望价值最大，在终点到n中，我们需要找到最大的前缀和，因为起点被我们枚举从而固定，对此我们提前预处理后缀最大前缀和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Problem: 可口蛋糕
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/73450/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 1e6+5;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int w[N],v[N];
int sw[N],sv[N];
int mx[N];
//v是体积，w是价值
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i];
	for(int i=1;i<=n;i++)sv[i]=sv[i-1]+v[i];
	//for(int i=1;i<=n;i++)cerr<<sv[i]<<" ";
	//cerr<<endl;
	
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++)sw[i]=sw[i-1]+w[i];
	//for(int i=1;i<=n;i++)cerr<<sw[i]<<" ";
	//cerr<<endl;
	
	
	for(int i=n;i>=1;i--){
		if(i==n)mx[i]=sw[i];
		else mx[i]=max(mx[i+1],sw[i]);
		
	}
	//for(int i=1;i<=n;i++)cerr<<mx[i]<<" ";
	//cerr<<endl;
	int ans=-1e18;
	for(int i=1;i<=n;i++){
		int l=i;
		int val=sv[i-1]+m;
		int r=lower_bound(sv+1,sv+n+1,val)-sv;
		if(sv[r]-sv[l-1]<m)continue;
	//	cerr<<l<<" "<<r<<endl;
		int res=mx[r]-sw[l-1];
		//cerr<<l<<" "<<r<<" "<<res<<endl;
		ans=max(ans,res);
	}
	
	cout<<ans<<endl;
	
	
	}
signed main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}

标程做法：首先枚举左端点，然后根据 WW 的限制求解出右端点的最小值（双指针递推），记为 rr。

那么此时问题转变为：以 rr 为左端点的最大子段和（通过倒序 dp 预处理即可）。

时间复杂度：O(n)O(n)