SSY20260131模拟赛题解
T1
题目描述
小明和你正在玩一个游戏。
有一个字符串池，池内只有三种字符串：ABC, BCA, CAB，每种字符串有无数个。
小明首先构造一个字符串。他从字符串池中选取了 N 个字符串，然后把这些字符串拼接成一个字符串，记为 S。显然，S 的长度为 3N，即 S 包含 3N 个字符。
然后小明让你把他构造的字符串清空，即通过若干次删除字符的操作把 S 变成空串。
但小明要求的删除操作非常奇特：每次删除操作，把你准备删除的字符按在 S 中的顺序拼接成一个字符串 T，你必须保证 T 是由两个相同的字符串拼接成的字符串，这次删除操作才可成功执行。
问：你能否将小明构造的字符串 S 清空？
如果不能，请输出一行一个整数 -1；如果能，请你输出你的操作方案，具体输出分两行：
第一行：一个整数 K，表示你删除操作的次数；
第二行：3N 个整数，第 i 个整数表示 S 的第 i 个字符在第几次操作时被删除。当然，你输出的这些整数应该介于 1 和 K 之间。
为了增加游戏难度，小明又给你提了一项要求：他告诉你一个参数 P，并且 P 要么为 0，要么为 1。如果 P = 0, 那么你必须要使用最少的操作次数将字符串清空；如果 P = 1，那么允许你操作的次数可以比最少的操作次数最多多一次。答案可能不唯一，按要求输出满足要求的任意一种可行方案即可。
每个测试点包含多组测试数据，而小明告诉你的参数 P则是该测试点中所有测试数据通用的。
输入格式
第一行：两个整数 T,P，分别表示数据组数和小明给出的参数。
对于每组数据：
第一行：一个整数 N
第二行：一个字符串 S数据保证所有输入的 N 之和 ≤ 10^5
输出格式
每组数据的答案占一行或两行，格式如题所述。
sol
task1:p=1时20分
task2:p=0
所有的字符串都可以在两次以内删除，答案<=2。
如果长度为奇数一定无解
否则从中间劈开，若左边等于右边一次删光。
一次删不完就构造，
ABC BCA CAB，没有BCA、BAC。可循环
每两个长度为3的，一定都有一个最长公共字串/前后缀
例如：ABCCABABCABC
ABCCAB为2（BC)
从中间劈开，因为任何两个要么相同要么就是公共子串2，
相同的可以直接匹配。不同的是公共字串2、1。
不妨将AB作为第一次删除的序列中，C放在第二个。
CAB相当于构造了一个AB，是第一次要删除的序列。ABCAB相当于ABC+AB，后面也有了ABC+AB
第二次删除C就可以了。多试几次就可以看出规律了。
思维题、构造题
思考&改题:如果有ABC BCA CAB CBA 六种？
参考
#include<bits/stdc++.h>
using namespace std;
int T,K,P;
int ans[300005];
int fl[100005];
string s;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>T>>P;
while(T--){
cin>>K>>s;
if(K%2==1){
cout<<"-1\n";
continue;
}
s='#'+s;
for(int i=1;i<=K;++i){
if(s[i*3-2]=='A'&&s[i*3-1]=='B'&&s[i*3]=='C'){
fl[i]=1;
}
else if(s[i*3-2]=='B'&&s[i*3-1]=='C'&&s[i*3]=='A'){
fl[i]=2;
}
else{
fl[i]=3;
}
}
int p=K/2,maxx=-1;
for(int i=1;i<=p;++i){
if(fl[i]==fl[i+p]){
ans[i*3-1]=1;
ans[i*3-2]=1;
ans[i*3]=1;
ans[(i+p)*3-1]=1;
ans[(i+p)*3-2]=1;
ans[(i+p)*3]=1;
maxx=max(maxx,1);
}
else{
if(fl[i]==1){
if(fl[i+p]==2){ //ABC BCA
ans[i*3-2]=2;
ans[i*3-1]=1;
ans[i*3]=1;
ans[(i+p)*3-2]=1;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=2;
}
if(fl[i+p]==3){ //ABC CAB
ans[i*3-2]=1;
ans[i*3-1]=1;
ans[i*3]=2;
ans[(i+p)*3-2]=2;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=1;
}
}
if(fl[i]==2){
if(fl[i+p]==1){ //BCA ABC
ans[i*3-2]=1;
ans[i*3-1]=1;
ans[i*3]=2;
ans[(i+p)*3-2]=2;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=1;
}
if(fl[i+p]==3){ //BCA CAB
ans[i*3-2]=2;
ans[i*3-1]=1;
ans[i*3]=1;
ans[(i+p)*3-2]=1;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=2;
}
}
if(fl[i]==3){
if(fl[i+p]==1){ //CAB ABC
ans[i*3-2]=2;
ans[i*3-1]=1;
ans[i*3]=1;
ans[(i+p)*3-2]=1;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=2;
}
if(fl[i+p]==2){ //CAB BCA
ans[i*3-2]=1;
ans[i*3-1]=1;
ans[i*3]=2;
ans[(i+p)*3-2]=2;
ans[(i+p)*3-1]=1;
ans[(i+p)*3]=1;
}
}
maxx=2;
}
}
if(maxx==1){
cout<<"1\n";
for(int i=1;i<3*K;++i){
cout<<"1 ";
}
cout<<"1\n";
}
else{
cout<<"2\n";
for(int i=1;i<3*K;++i){
cout<<ans[i]<<' ';
}
cout<<ans[3*K]<<'\n';
}
}
return 0;
}
T2
题目描述
有两个长度为 N 的正整数序列：
- A = [A_1, A_2, \dots, A_N]
- B = [B_1, B_2, \dots, B_N]
你可以进行恰好一次操作：选择序列 A 的一个区间 [l, r]（1 \le l \le r \le N），将该区间内的元素整体翻转。
总共有 \frac{(N+1) \times N}{2} 种不同的区间可供选择。
对于第 i 种操作方式（即选择第 i 个区间），翻转后会得到一个新的序列 A'。我们统计该序列中满足 A'_p = B_p 的位置个数，记为 M_i。
最终，我们需要求所有 M_i 的总和：
输入格式
- 第一行：一个整数 N
- 第二行：序列 A 的 N 个元素 A_1, A_2, \dots, A_N
- 第三行：序列 B 的 N 个元素 B_1, B_2, \dots, B_N
输出格式
一个整数，表示所有 M_i 的总和。
输入样例
3
1 2 3
3 2 1
输出样例
6
样例解释
当 N=3 时，总共有 \frac{3 \times 4}{2} = 6 种操作方式：
- 翻转长度为 1 的区间（共 3 个）：翻转后 M_i = 1
- 翻转长度为 2 的区间（共 2 个）：翻转后 M_i = 0
- 翻转长度为 3 的区间（共 1 个）：翻转后 M_i = 3
总和为 1+1+1+0+0+3 = 6
数据范围
- 100% 数据：1 \le N \le 5 \times 10^5，1 \le A_i, B_i \le N
- 10% 数据：N \le 100
- 10% 数据：N \le 5000
- 20% 数据：A_i, B_i 随机生成
- 20% 数据：1 \le A_i, B_i \le 2 且随机生成
sol
拆贡献。
每个axby映射到对答案的贡献上。
123 321中，2与2相等。
反转区间不包含这个2的其他区间反转一定就会有它的贡献。不包含2的区间不管怎么反转，它的贡献始终存在。
对于每一个上下相等的就可以求。
若上下不相等：
a_xxxxxxxxxxxxxx
xxxxxxxxb_y(a_x)
位置不一样，且ax=by。ax可以反转到右侧，当然，by后面可能也有许多相等的。我们要计算出所有ax=by的贡献。
左侧有多少个数，右边就有多少个，这样相对。
参考：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,n,m;
int a[501000],b[501000];
vector<int> posa[501000],posb[501000],sumb[501000];
signed main(){
// freopen("ex.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
posa[a[i]].push_back(i);
posb[i].push_back(0);
}
int ans=0;
for(int i=1;i<=n;i++){
cin>>b[i];
if(a[i]==b[i]) ans++;
posb[b[i]].push_back(i);
}
for(int i=1;i<=n;i++){
sumb[i].push_back(0);
for(int j=1;j<posb[i].size();j++){
sumb[i].push_back(sumb[i][j-1]+posb[i][j]);
}
}
ans*=(n*n+n)/2;
for(int i=1;i<=n;i++){
for(int j=0;j<posa[i].size();j++){
if(posb[i].size()==1) break;
int id=lower_bound(posb[i].begin()+1,posb[i].end(),posa[i][j])-posb[i].begin()-1;
// printf("%d\n",id);
if(id>=1){
int k=upper_bound(posb[i].begin()+1,posb[i].end(),n-posa[i][j]+1)-posb[i].begin()-1;
// printf("%d %d\n",k,id);
if(k>=1){
ans+=sumb[i][min(k,id)];
}
if(k<id){
ans+=(id-k)*(n-posa[i][j]+1);
}
}
id=upper_bound(posb[i].begin()+1,posb[i].end(),posa[i][j])-posb[i].begin();
// printf("%d\n",id);
if(id<posb[i].size()){
int k=lower_bound(posb[i].begin()+1,posb[i].end(),n-posa[i][j]+1)-posb[i].begin();
// printf("%d %d\n",k,id);
if(k<posb[i].size()){
ans+=min(posb[i].size()-k,posb[i].size()-id)*(n+1)-(sumb[i][posb[i].size()-1]-sumb[i][max(k-1,id-1)]);
}
if(k>id){
ans+=(k-id)*(posa[i][j]);
}
}
id=*lower_bound(posb[i].begin()+1,posb[i].end(),posa[i][j]);
if(id==posa[i][j]) ans+=min(id,n-id+1);
// for(int k=0;k<posb[i].size();k++){
// int x=posa[i][j],y=posb[i][k];
// if(x>y) swap(x,y);
// ans+=min(x,n-y+1);
// }
}
}
for(int i=1;i<=n;i++){
if(a[i]==b[i]) ans-=i*(n-i+1);
}
cout<<ans<<'\n';
return 0;
}
T3
题目描述
小明写了一个程序，输入一个整数 N，便可以生成一个 N×N 的矩阵。程序如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cout<<i+j<<' ';
}
cout<<'\n';
}
return 0;
}
第一步：操作了若干次（可以为 0 次），每次操作将矩阵中的某两行进行交换；
第二步：操作了若干次（可以为 0 次），每次操作将矩阵中的某两列进行交换；
第三步：操作了若干次（可以为 0 次），每次操作选取矩阵中的某两个数进行全部互换。即，假设某次操作选取的两个数是 x, y，则将矩阵中所有的 x 替换为 y, 所有的 y 替换为 x。
注意，三步操作是依次进行的，下一步开始后，不能返回上一步进行操作。
全部操作完成后，小明向你展示了最终的矩阵。但是他已经忘了自己是如何操作的。你能帮他还原一下他可能的操作吗？
你只需要输出小明前两步操作结束之后，第三步操作开始之前，矩阵的一种可能状态。答案可能很多，你需要输出字典序最小的那个矩阵。
两个N×N 的矩阵的字典序大小关系，等于它们先按行、再按列依次比较每个元素时，第一次遇到的不同元素的大小关系。
输入格式
第一行：一个整数 N。
接下来是一个 N×N 的矩阵，表示小明三步操作结束后的矩阵。
输出格式
一个 N×N 的矩阵：共 N 行，每行 N 个数，同一行的数之间以一个空格隔开。数据保证有解。
样例
输入
1
2
输出
2
输入
3
3 6 5
6 2 4
5 4 6
输出
2 4 3
4 6 5
3 5 4
样例2解释
该样例中 N=3
--- 初始矩阵 ---
2 3 4
3 4 5
4 5 6
--- 第一步 ---
=== 第二行和第三行交换 ===>
2 3 4
4 5 6
3 4 5
---第二步---
=== 第二列和第三列交换 ===>
2 4 3
4 6 5
3 5 4
---第三步---
=== (1) 交换 2 和 4 ===>
4 2 3
2 6 5
3 5 2
=== (2) 交换 3 和 4 ===>
3 2 4
2 6 5
4 5 2
=== (3) 交换 4 和 5 ===>
3 2 5
2 6 4
5 4 2
=== (4) 交换 2 和 6 ===>
3 6 5
6 2 4
5 4 6
至此得到小明的序列，在第三步开始之前的矩阵为：
2 4 3
4 6 5
3 5 4
是字典序最小的。
下列也是一种可能的操作序列，但在第三步开始之前的矩阵不是字典序最小的。
---初始矩阵---
2 3 4
3 4 5
4 5 6
---第一步---
=== 第一行和第三行交换 ===>
4 5 6
3 4 5
2 3 4
=== 第二行和第三行交换 ===>
4 5 6
2 3 4
3 4 5
---第二步---
=== 第一列和第二列交换 ===>
5 4 6
3 2 4
4 3 5
=== 第一列和第三列交换 ===>
6 4 5
4 2 3
5 3 4
---第三步---
=== (1) 交换 3 和 4 ===>
6 3 5
3 2 4
5 4 3
=== (2) 交换 3 和 6 ===>
3 6 5
6 2 4
5 4 6
至此得到小明的序列，在第三步开始之前的矩阵为：
6 4 5
4 2 3
5 3 4
但它不是字典序最小的。
数据范围
20% 的数据：N≤6
40% 的数据：N≤8。
70% 的数据：N≤100。
100% 的数据：N≤1000
sol
随便生成一个加法表
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10
性质一：2与10只出现过1次。只需要统计次数，找出最大值和最小值，因为这两个只能出现一次。
性质二：行列交换，不管如何变幻都在一行、都在一列。
性质三：对角线上数字出现次数最多。
2和10是最好判断的。那么假如第一个是2，推断后面。假如第一个是10，推断后面。
最后判断两个矩阵的字典序，取小的就可以了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
struct Node{
int r, c;
};
int N;
int F[MAXN][MAXN], ansss[MAXN][MAXN], cans[MAXN][MAXN]; //ansss
int rip[MAXN], cip[MAXN];
map<int, int> counts;
int cnt[MAXN], ccnt = 0;
map<int, Node> vNode;
void solve(int a) {
Node p = vNode[a];
int r0 = p.r;
int c0 = p.c;
for (int j = 1; j <= N; ++j) {
int tmp = F[r0][j];
cip[j] = counts[tmp];
}
for (int i = 1; i <= N; ++i) {
int val = F[i][c0];
rip[i] = counts[val];
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cans[i][j] = rip[i] + cip[j];
}
}
}
bool cmp() {
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
if (cans[i][j] != ansss[i][j]) return cans[i][j] < ansss[i][j];
return false;
}
int main() {
//
cin >> N;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cin >> F[i][j];
counts[F[i][j]]++;
if (vNode.find(F[i][j]) == vNode.end()) {
vNode[F[i][j]] = {i, j};
}
}
}
if (N == 1) {
cout << 2 << endl;
return 0;
}
for (map<int, int>::iterator it = counts.begin(); it != counts.end(); it++) {
if (it->second == 1) {
cnt[ccnt++] = it->first;
}
}
bool first = true;
for (int k = 0; k < ccnt; ++k) {
solve(cnt[k]);
if(first == true){
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
ansss[i][j] = cans[i][j];
}
}
first = false;
}else {
if(cmp()){
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
ansss[i][j] = cans[i][j];
}
}
}
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cout << ansss[i][j] << " ";
}
cout << endl;
}
return 0;
}
总结
平时学的各种算法在这里都用不上，原因何在？
需要训练思维。学的精、学的方式、思维、方法要比模板更有用。