Kyooma's Blog

2023牛客多校08

  • ~11.76K 字

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

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

A - Alive Fossils

DESCRIPTION

给 $n$ 个字符串集合，求这 $n$ 个集合的交集。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int>mp;
void kaibai(){
	int n,i,x,j,k,ans=0;
	cin>>n;
	string s;
	for(i=1;i<=n;i++){
		cin>>k;
		while(k--){
			cin>>s;
			mp[s]++;
		}
	}
	vector<string>v;
	for(auto i:mp){
		if(i.second==n) v.push_back(i.first);
	}
	cout<<v.size()<<'\n';
	for(auto i:v) cout<<i<<'\n';
} 
int main(void){
	int T=1;
	ios::sync_with_stdio(0);
//	cin>>T;
	while(T--){
		kaibai();
	}
}

H - Insert 1, Insert 2, Insert 3, …

DESCRIPTION

有一个初始为空的序列，对于每次操作，你可以选择一个数 $x$，然后往序列中插入 $1, 2, …, x$ 这 $x$ 个数，要求满足插入 $i$ 的位置在插入 $i + 1$ 的位置之前（ $1 \le i < x$ ）。

现在给你 $a_1, a_2, …, a_n$ 问 $a$ 中有几个子区间可以被上述操作生成出来。

SOLUTION

雷伤杯秒了。

显然每个大于 $1$ 的数都需要 $1$ 去生成，所以可以处理出每个数对应的最近的 $1$ 位置，然后可以变成一个二分+区间min能解决的问题。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+6;
int n,a[N],b[N],logx[N],st[N][25];
vector<int> g[N];
void init() {
	logx[0]=-1;
	for (int i=1;i<=n;++i) logx[i]=logx[i>>1]+1;
	for (int i=1;i<=n;++i) st[i][0]=b[i];
	for (int j=1;(1<<j)<=n;++j) {
		for (int i=1;i+(1<<j)-1<=n;++i) {
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r){
	int k=logx[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int l,int r) {
	return query(l,r)>=l;
}
void kaibai(){
	cin>>n;
	for (int i=1;i<=n;++i) cin >> a[i];
	for (int i=1;i<=n;++i) b[i]=i;
	for (int i=1,x;i<=n;++i) {
		x=a[i];
		if (a[i]==1) {
			g[x].push_back(i);
		}else {
			if (g[x-1].size()) {
				g[x].push_back(i);
				b[i]=b[g[x-1].back()];
				g[x-1].pop_back();
			}else {
				b[i]=-1;
			}
		}
	}
	init();
	int ans=0;
	for (int i=1;i<=n;++i) {
		int l=i,r=n,mid,tmp=i-1;
		while (l<=r) {
			mid=(l+r)/2;
			if (check(i,mid)) {
				l=mid+1;
				tmp=mid;
			}else{
				r=mid-1;
			}
		}
		tmp=tmp-i+1;
		ans+=tmp;
	}
	cout << ans;
} 
signed main(void){
	int T=1;
	ios::sync_with_stdio(0);
	while(T--){
		kaibai();
	}
}

I - Make It Square

DESCRIPTION

给出字符串 $s$ 和 $t$，求有多少种字符串 $p$ 和 $q$ 满足 $|p| = |q| = i\ (1 \le i \le m)$ ，字符串 $p + s + q + t$ 的长度为偶数，且它的前一半字符串与后一半字符串完全相等（如 $abcdabcd$）。

SOLUTION

枚举 $p, q$ 串的长度，然后按中点位置分类讨论一下，再用哈希判断相等即可。

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
90
91
92
93
94
#include<bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 1e6 + 5, P = 998244353;
const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251};

pll pw[N], f[N], g[N];
int p26[N];

pll operator * (const pll &p1, const pll &p2) {
	return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second};
}

pll operator + (const pll &p1, const pll &p2){
	return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second};
}

pll operator - (const pll &p1, const pll &p2){
	return {(p1.first - p2.first + mod.first) % mod.first, (p1.second - p2.second + mod.second) % mod.second};
}

pll getf(int l, int r){
	return f[r] - f[l - 1] * pw[r - l + 1];
}

pll getg(int l, int r){
	return g[r] - g[l - 1] * pw[r - l + 1];
}

void kaibai(){
	int m;
	string s, t;
	cin >> m >> s >> t;
	int l1 = (int)s.size(), l2 = (int)t.size();
	for(int i = 1; i <= l1; i++){
		f[i] = f[i - 1] * base + pll{s[i - 1], s[i - 1]};
	}
	for(int i = 1; i <= l2; i++){
		g[i] = g[i - 1] * base + pll{t[i - 1], t[i - 1]};
	}
	for(int i = 1; i <= m; i++){
		ll ans = 0;
		int len = l1 + l2 + i * 2;
		if(len & 1){
			cout << "0 ";
			continue;
		}
		int mid = len / 2, res = 0, ok = 1;
		if(mid <= l1 + i){// s
			int lp = mid + 1, rp = mid + i;
			if(rp >= l1 + i){
				res = rp - l1 - i;
				int lens = mid - i;
				if(getf(lens - l2 + 1, lens) != getg(1, l2)) ok = 0;
			}else{
				int lens = mid - i;
				if(getf(lens - l2 + 1, lens) != getg(1, l2)) ok = 0;
				lens = i + l1 - rp;
				if(getf(1, lens) != getf(l1 - lens + 1 , l1)) ok = 0;
			}
		}else if(mid <= l1 + i * 2){// q
			res = l1 + i * 2 - mid;
			int lt = mid + i - l1 - i * 2 + 1;
			if(getf(1, l1) != getg(lt, lt + l1 - 1)) ok = 0;
		}else{// t
			int lt = mid + i - l1 - i * 2 + 1;
			if(getf(1, l1) != getg(lt, lt + l1 - 1)) ok = 0;
			int lent = mid - l1 - i * 2;
			if(getg(1, lent) != getg(l2 - lent + 1, l2)) ok = 0;
		}
		ans = ok * p26[res];
		cout << ans << " ";
	}
} 


int main(void){
	int T=1;
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	pw[0] = {1, 1};
	p26[0] = 1;
	for(int i = 1; i < N; i++){
		pw[i] = pw[i - 1] * base;
		p26[i] = 1ll * p26[i - 1] * 26 % P;
	}
//	cin>>T;
	while(T--){
		kaibai();
	}
}

J - Permutation and Primes

DESCRIPTION

求一个 $1,2,3,…,n$ 的排列满足相邻元素的和或者差的绝对值是个奇质数。

SOLUTION

打表，按 $\bmod 8$ 的余数分类，打出 $1$ 到 $15$ 的表即可。

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

int num[8][8] = {{}, 
				{1}, // 1
				{1, 2}, // 2
				{1, 2, 3}, // 3
				{1, 2, 3, 4}, // 4
				{1, 4, 3, 2, 5}, // 5
				{1, 2, 5, 6, 3, 4}, // 6
				{3, 6, 1, 4, 7, 2, 5}}; // 7

int table[8][20] = {{1, 6, 3, 8, 5, 2, 7, 4}, // 0
					{1, 6, 3, 8, 5, 2, 7, 4, 9}, // 1
					{1, 4, 7, 2, 9, 6, 3, 8, 5, 10}, // 2
					{1, 4, 7, 2, 5, 10, 3, 8, 11, 6, 9}, // 3
					{1, 4, 7, 2, 5, 10, 3, 8, 11, 6, 9, 12}, // 4
					{1, 4, 7, 2, 5, 12, 9, 6, 3, 10, 13, 8, 11}, // 5
					{1, 4, 7, 2, 5, 8, 3, 10, 13, 6, 11, 14, 9, 12}, // 6
					{1, 4, 7, 2, 5, 8, 3, 6, 11, 14, 9, 12, 15, 10, 13}}; // 7



void kaibai(){
	int n;
	cin >> n;
	if(n < 8){
		for(int i = 0; i < n; i++){
			cout << num[n][i] << " \n"[i == n - 1];
		}
		return;
	}
	// n >= 8
	int m = n % 8, p = 0;
	n -= m;
	for(int i = 1; i < n / 8; i++, p += 8){
		for(int j = 0; j < 8; j++){
			cout << table[0][j] + p << " ";
		}
	}
	for(int i = 0; i < 8 + m; i++){
		cout << table[m][i] + p << " \n"[i == m + 7];
	}
} 


int main(void){
	int T=1;
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		kaibai();
	}
}

K - Scheming Furry

DESCRIPTION

博弈，给出一个 $n * m$ 的矩阵，且矩阵元素互不相同，先手可以选两个不同行交换，后手可以选两个不同列交换，若某人操作后矩阵变为有序（从上到下，从左到右遍历）则它获胜。若能无限操作下去，则为平局。

SOLUTION

分类讨论。

首先，如果本身就无法换成有序状态肯定是平局，以下讨论能变换为有序的情况。

若 $n > 2$ 且 $m > 2$ 时，先手如果不能一步就获胜，那么肯定可以将局面拖入平局，因为先手可以将本该在最后一行的元素换到第一行，然后一直交换最后两行。

若 $n = 2 $ 且 $ m = 2$ 时，模拟操作四次即可，因为两人都是固定操作。

若 $n = 2$ 且 $m > 2$ 时，先手无法获胜，可以通过手玩或者仔细分析发现答案和排列的奇偶性有关（把行和列看成长度为 $n$ 和 $m$ 的两个排列），当先手的奇偶性和后手相同时后手获胜，否则平局。

若 $n > 2$ 且 $m = 2$ 时，类似的，后手无法获胜，当先手的奇偶性和后手不同时先手获胜，否则平局。

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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=1e6+6;
int n,m,a[202][202],r,b[202][202];
string s[3];
bool check() {
	int x=0;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			if (a[i][j]<x) return false;
			x=a[i][j];
		}
	}
	return true;
}
void swap1(int i1,int i2) {
	for (int j=1;j<=m;++j) swap(a[i1][j],a[i2][j]);
}
void swap2(int j1,int j2) {
	for (int i=1;i<=n;++i) swap(a[i][j1],a[i][j2]);
}
void findtonumber(int &u,int &v) {
	for (int i=1;i<=n;++i) {
		if (a[i][1]!=b[i][1]) {
			if (u==0) u=i;
			else      v=i;
		}
	}
}
void kaibai(){
	cin >> n >> m;r=0;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			cin >> a[i][j];
			b[i][j]=++r;
		}
	}
	if (n==2&&m==2) {
		for (int i=0;i<4;++i) {
			if (i&1) swap2(1,2);
			else     swap1(1,2);
			if (check()) {
				cout << s[i&1] << endl;
				return;
			}
		}
		cout << s[2] << endl;
		return;
	}
	if (n==2) {
		swap1(1,2);
		if (check()) {
			cout << s[0] << endl;
			return;
		}
		swap1(1,2);
		bool ff=false,fff=true;
		fff=true;
		for (int j=1;j<=m;++j) {
			if (a[1][j]-a[2][j]!=m) fff=false;
		}
		ff|=fff;
		fff=true;
		for (int j=1;j<=m;++j) {
			if (a[1][j]-a[2][j]!=-m) fff=false;
		}
		ff|=fff;
		
		if (ff) {
			int cnt=0;
			if (a[1][1]>m) cnt++;
			for (int i=1;i<=m;++i) {
				for (int j=i+1;j<=m;++j) {
					if (a[1][i]>a[1][j]) cnt++;
				}
			}
			if (cnt%2==0) cout << s[1] << endl;
			else          cout << s[2] << endl;
		}else {
			cout << s[2] << endl;
		}
		return;
	}
	if (m==2) {
		bool ff=false,fff=true;
		fff=true;
		for (int i=1;i<=n;++i) {
			if (a[i][1]-a[i][2]!=1) fff=false;
		}
		ff|=fff;
		fff=true;
		for (int i=1;i<=n;++i) {
			if (a[i][1]-a[i][2]!=-1) fff=false;
		}
		ff|=fff;
		if (ff) {
			int cnt=0;
			if (a[1][1]&1) cnt++;
			for (int i=1;i<=n;++i) {
				for (int j=i+1;j<=n;++j) {
					if (a[i][1]>a[j][1]) cnt++;
				}
			}
			if (cnt%2==0) cout << s[0] << endl;
			else          cout << s[2] << endl;
		}else {
			cout << s[2] << endl;
		}
		return;
	}
	
	
	
	
	int u=0,v=0;
	findtonumber(u,v);
	if (v==0) {
		cout << "NSFW" << endl;
		return;
	}
	swap1(u,v);
	if (check()) {
		cout << "FOX" << endl;
	}else {
		cout << "NSFW" << endl;
	}
} 
signed main(void){
	int T=1;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	s[0]="FOX",s[1]="CAT",s[2]="NSFW";
	while(T--){
		kaibai();
	}
	
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可