记录下9.4字节笔试

第一题：简单dp 100%

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> v(n + 2, vector<int>(m + 2, 0));
	for(int i = 0; i < n; i++){
		for(int j = 1; j <= m; j++)
			cin >> v[i][j];
	}
	int ans = 0;
	vector<vector<int>> dp(n + 2, vector<int>(m + 2, -1));
	for(int i = 1; i <= m; i++)
		dp[0][i] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 1; j <= m; j++){
			if(dp[i][j] == -1) continue;
			if(v[i][j] != -1) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + v[i][j]);
			else{
				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 0);
				dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + 0);
			}
		}
	}
	for(int i = 1; i <= m; i++)
		ans = max(ans, dp[n][i]);
	cout << ans << endl;
	return 0;
}

第二题：不知道怎么搞出来的，试了排序100%

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int t, n;
	cin >> t;
	while(t--){
		cin >> n;
		int a[n];
		map<int, int>mp;
		for(int i = 0; i < n; i++){
			cin >> a[i];
			mp[a[i]]++;
		}
		sort(a, a + n);
		int flag = 1;
		for(int i = 2; i < n; i++){
			if(mp[a[i] + a[i - 1] + a[i - 2]] == 0){
				flag = 0;
				break;
			}
		}
		puts(flag ? "YES" : "NO");
	}
	return 0;
}

第三题：字符串操作，用来滑动窗口40%，没调出来，不知道是不是思路有问题

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int t, n, m;
	cin >> t;
	while(t--){
		cin >> n >> m;
		string s1, s2;
		cin >> s1 >> s2;
		int s[n];
		for(int i = 0; i < n; i++)
			s[i] = (int)(s1[i] - 'a');
		int ans = 1;
		if(m == 0){
			int oo = 1;
			for(int i = 1; i < n; i++){
				if(s[i] == s[i - 1]) oo++;
				else oo = 1;
				ans = max(ans, oo);
			}
			cout << ans << endl;
			continue;
		}
		for(int k = 0; k < 26; k++){
			vector<vector<int>> cnt(26, vector<int>(2, 0));
			for(int i = 0; i < 26; i++){
				cnt[i][0] = 0;
				cnt[i][0] = -1;
			}
			int mark = 0, pos = 0;
			for(int i = 0; i < n; i++){
				if(s2[i] == '1' && s[i] != k) mark++;
				if(mark <= m){
					int x = s2[i] == '1' ? k : s[i];
					if(cnt[x][1] == (i - 1)){
						cnt[x][1] = i;
						ans = max(ans, cnt[x][1] - cnt[x][0] + 1);
					}else{
						cnt[x][0] = i;
						cnt[x][1] = i;
						ans = max(ans, cnt[x][1] - cnt[x][0] + 1);
					}
					//cout 
				}
				if(mark >= m){
					int ok = 0;
					while(1 && pos < n){
						if(s2[pos] == '1' && s[pos] != k) ok = 1;
						int x = s2[pos] == '1' ? k : s[pos];
						if(cnt[x][0] == pos){
							cnt[x][0]++;
						}
						pos++;
						if(ok) break;
					}
					mark --;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

第四题：AB故障命中 100%

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	const int N = n;
	bitset<100000> a[m + 1];
	bitset<100000> b[m + 1];
	vector<int> vis(m + 1, 0);
	for(int i = 0; i < n; i++){
		int c;
		scanf("%d", &c);
		for(int j = 0, x; j < c; j++){
			cin >> x;
			vis[x] = 1;
			a[x].set(i);
		}
		for(int j = 1; j <= m; j++){
			if(vis[j] == 1){
				vis[j] = 0;
				continue;
			}
			b[j].set(i);
		}
	}
	while(q--){
		bitset<100000> ans;
		ans.set();
		int x, y;
		scanf("%d", &x);
		while(x--){
			scanf("%d", &y);
			if(y > 0) ans &= a[y];
			else ans &= b[abs(y)];
		}
		cout << (int)ans.count() << endl;
	}
	return 0;
}