Kyooma's Blog

2023牛客多校04

  • ~8.32K 字

题目来自: 2023牛客暑期多校训练营4

Solved Rank A B C D E F G H I J K L
5 / 12 109 / 1469 O - - - - O - O - O - O
  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

A - Bobo String Construction

SOLUTION

思维题，串 $s$ 为全 $0$ 或者全 $1$ 必定有一个是合法的，用 $kmp$ 判断合法性即可。

CODE
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
#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
const int N = 3000 + 10;

int nxt[N];
string a, b;

bool jud(int n, int m){
	int i, j;
	for(nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j){
		while(~j && a[j + 1] != a[i]) j = nxt[j];
		if(a[j + 1] == a[i]) j++;
	}
	int cnt = 0;
	for(j = -1, i = 0; i < m; i++){
		while(~j && a[j + 1] != b[i]) j = nxt[j];
		if(a[j + 1] == b[i]) j++;
		if(j == n - 1){
			cnt++;
			j = nxt[j];
		}
	}
	return cnt <= 2;
}

void solve(){
	int n;
	cin >> n >> a;
	string zero(n, '0'), one(n, '1');
	b = a + zero + a;
	if(jud((int)a.size(), (int)b.size())){
		cout << zero << '\n';
		return;
	}
	b = a + one + a;
	if(jud((int)a.size(), (int)b.size())){
		cout << one << '\n';
		return;
	}
	cout << "-1\n";
}
signed main(void){
	int T=1;
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		solve();
	}
}

F - Election of the King

SOLUTION

签到题，每回合淘汰的必定是最小值或者是最大值，模拟一下即可。

CODE
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e6+10;
struct node{
	int id,x;
}a[N];
bool cmp(node x,node y){
	return x.x<y.x;
}
void solve(){
	int n,m,i,j,x,y,q,op,f;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	int l=1,r=n;
	for(i=1;i<n;i++){
		if((r-l-1)&1){
			x=a[(l+r)/2].x;
			if(x-a[l].x==a[r].x-x){
				if(a[l].x>a[r].x) l++;//
				else r--;
			}
			else if(x-a[l].x>a[r].x-x) l++;
			else r--;
		}
		else{
			x=a[(l+r)/2].x;
			y=a[(l+r)/2+1].x;
			int f1=0,f2=0;
			if(x-a[l].x==a[r].x-x){
				if(a[l].x>a[r].x) f1++;//
				else f2++;
			}
			else if(x-a[l].x>a[r].x-x) f1++;
			else f2++;
			if(y-a[l].x==a[r].x-y){
				if(a[l].x>a[r].x) f1++;//
				else f2++;
			}
			else if(y-a[l].x>a[r].x-y) f1++;
			else f2++;
			
			if(f1>f2) l++;
			else if(f1<f2) r--;
			else{
				if(a[l].x>a[r].x) l++;//
				else r--;
			}
			//cout<<f1<<" "<<f2<<'\n';
		}
		//cout<<l<<" "<<r<<'\n';
	}
	cout<<a[l].id;
}
int main(void){
	int T=1;
	ios::sync_with_stdio(0);
//	cin>>T;
	while(T--){
		solve();
	}
}

H - Merge the squares!

SOLUTION

由于只能是小正方形合并为大正方形，可以反过来考虑如何把 $n \times n$ 的正方形拆分。

可以将大正方形左上角拆出一个 $a \times a$ 的正方形，右下角拆出一个 $b \times b$ 的正方形，那么会剩下两个 $a \times b$ 的矩形，接下来考虑这个矩形是长方形的情况，那么我们需要尽可能少的将这个长方形拆成正方形（因为一次最多只能合并 $50$ 个正方形），可以用类似辗转相除的方法进行拆分，打表发现最多只会拆成 $32$ 个正方形。那么预处理出每个 $n$ 的最优选择的 $a、b$ 即可。

CODE
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
#include<bits/stdc++.h>
using namespace std;

const int N = 3000 + 10;

void dfs(int x, int y, int n);
void gao(int x, int y, int n, int m);

struct node{
	int x, y, w;
};

vector<node> ans;

int dp[N];

void gao(int x, int y, int n, int m){
	if(!n || !m) return;
	if(n == m){
		dfs(x, y, n);
		return;
	}
	if(n < m){
		dfs(x, y, n);
		gao(x, y + n, n, m - n);
	}else{
		dfs(x, y, m);
		gao(x + m, y, n - m, m);
	}
}

void dfs(int x, int y, int n){
	if(n == 1) return;
	if(n * n <= 50){
		ans.push_back({x, y, n});
		return;
	}
	int a = dp[n], b = n - a;
	dfs(x, y, a);
	dfs(x + a, y + a, b);
	int dx, dy;
	for(dx = x + a, dy = y + a - b; dy >= y; dy -= b){
		dfs(dx, dy, b);
	}
	dy += b;
	gao(dx, y, b, dy - y);
	for(dx = x + a - b, dy = y + a; dx >= x; dx -= b){
		dfs(dx, dy, b);
	}
	dx += b;
	gao(x, dy, dx - x, b);
	ans.push_back({x, y, n});
}

int find(int n, int m){
	if(n > m) swap(n, m);
	if(n == 0) return 0;
	return m / n + find(n, m % n);
}

void solve(){
	int n;
	cin >> n;
	dfs(1, 1, n);
	cout << ans.size() << '\n';
	for(auto i : ans){
		cout << i.x << ' ' << i.y << ' ' << i.w << '\n';
	}
}

int main(){
	int T = 1;
	for(int i = 2; i <= 1000; i++){
		int res = 1e6, ans;
		for(int a = 1; a < i; a++){
			int b = i - a;
			int cnt = 2 + 2 * find(a, b);
			if(cnt < res){
				res = cnt;
				ans = a;
			}
		}
		dp[i] = ans;
	}
	ios::sync_with_stdio(0);
	while(T--){
		solve();
	}
}

J - Qu’est-ce Que C’est?

SOLUTION

dp，队友秒了

CODE
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
#include<bits/stdc++.h>

#define int long long
#define endl '\n'
using namespace std;
const int p = 998244353;
int dp[2][10004][3], aa[2][10004][3], n, m, pp[2][10004];

void solve() {
    cin >> n >> m;
    for (int i = m; i >= 0; --i) {
        dp[1][i + m][0] = 1;
        aa[1][i + m][0] = (dp[1][i + m][0] + aa[1][i + m + 1][0]) % p;
    }
    for (int i = -1; i >= -m; --i) {
        dp[1][i + m][1] = 1;
        aa[1][i + m][1] = (dp[1][i + m][1] + aa[1][i + m + 1][1]) % p;
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = -1; j >= -m; --j) {
            dp[i & 1][m + j][1] = (aa[i - 1 & 1][m - j][0] + aa[i - 1 & 1][m - j][2]) % p;
            pp[i & 1][m + m + j] = dp[i - 1 & 1][m + j][1];
            aa[i & 1][m + j][1] = (aa[i & 1][m + j + 1][1] + dp[i & 1][m + j][1]) % p;
        }
        for (int j = m; j >= 0; --j) {
            dp[i & 1][m + j][0] = (aa[i - 1 & 1][m][0] + aa[i - 1 & 1][m][2]) % p;
            aa[i & 1][m + j][0] = (aa[i & 1][m + j + 1][0] + dp[i & 1][m + j][0]) % p;
            dp[i & 1][m + j][2] = (dp[i & 1][m + j + 1][2] + pp[i & 1][m + j]) % p;
            aa[i & 1][m + j][2] = (aa[i & 1][m + j + 1][2] + dp[i & 1][m + j][2]) % p;
        }
    }
    cout << (aa[n & 1][m][0] + aa[n & 1][0][1] + aa[n & 1][m][2]) % p << endl;
}

signed main(void) {
    int T = 1;
    ios::sync_with_stdio(0);
    while (T--) {
        solve();
    }
}

L - We are the Lights

SOLUTION

签到

CODE
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e6+10;
struct node{
	int op,f,x;
}a[N];
int l,r,v1[N],v2[N];
void solve(){
	int n,m,i,j,x,y,q,op,f;
	ll ans=0;
	string s,t;
	cin>>n>>m>>q;
	for(i=1;i<=q;i++){
		cin>>s>>a[i].x>>t;
		if(t=="on") a[i].f=1;
		else a[i].f=0;
		if(s[0]=='r') a[i].op=1;
		else a[i].op=2;
	}
	for(i=q;i;i--){
		op=a[i].op;
		x=a[i].x;
		f=a[i].x;
		if(op==1){
			if(v1[x]) continue;
			v1[x]++;
			ans+=(m-r)*a[i].f;
			l++;
		}
		else{
			if(v2[x]) continue;
			v2[x]++;
			ans+=(n-l)*a[i].f;
			r++;
		}
	}
	cout<<ans;
}
int main(void){
	int T=1;
	ios::sync_with_stdio(0);
//	cin>>T;
	while(T--){
		solve();
	}
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可