2024.4.1

2024.4.1 【今天为什么是愚人节？因为四月是你的谎言】

Monday 二月二十三

今天愚人节快乐赛（太快乐了

A.项链

题目描述
有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！

在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。

达达要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字 00 至 99 来标示。

一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： 0-1-2-30−1−2−3，它的可能的四种表示是 0123、1230、2301、30120123、1230、2301、3012。

达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。

也就是说给定两个项链的表示，判断他们是否可能是一条项链。

输入格式
输入文件只有两行，每行一个由字符 00 至 99 构成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

输出格式
如果两个对项链的描述不可能代表同一个项链，那么输出 No，否则的话，第一行输出一个 Yes，第二行输出该项链的字典序最小的表示。

数据范围
设项链的长度为 LL，10000001≤L≤1000000

输入样例：

2234342423
2423223434

输出样例：

Yes
2234342423

#include<bits/stdc++.h>
using namespace std;
int len;
string mi(string ls){
	int k = 0, i = 0, j=1;
	while (k < len&& i < len && j < len) {
		if (ls[(i + k) % len] == ls[(j + k) % len]) {
			k++;
		}else{
			if(ls[(i + k) % len] > ls[(j + k) % len]){
				i=i+k+1;
			}else{
				j=j+k+1;
			}
    		if (i == j) i++;
				k = 0;
			}
		}
	i = min(i, j);
	string ret;
	for(int l = 0; l < len; l++){
		ret+=ls[(l+i)%len];
	}
	return ret;
}
int main(){
	string a,b;
	cin>>a>>b;
	len=a.length();
	a=mi(a);
	b=mi(b);
	if(a!=b){
		cout<<"No";
	}else{
		cout<<"Yes\n"<<a;
	}
	return 0; 
}
就求个最小表示法，
然后对比两个字符串就可以了。
最小表示法求解见题解

B. 奶牛矩阵
题目描述
每天早上，农夫约翰的奶牛们被挤奶的时候，都会站成一个 RR 行 CC 列的方阵。

现在在每个奶牛的身上标注表示其品种的大写字母，则所有奶牛共同构成了一个 RR 行 CC 列的字符矩阵。

现在给定由所有奶牛构成的矩阵，求它的最小覆盖子矩阵的面积是多少。

如果一个子矩阵无限复制扩张之后得到的矩阵能包含原来的矩阵，则称该子矩阵为覆盖子矩阵。

输入格式
第 11 行：输入两个用空格隔开的整数，RR 和 CC。

第 2..R+12..R+1 行：描绘由奶牛构成的 RR 行 CC 列的矩阵，每行 CC 个字符，字符之间没有空格。

输出格式
输出最小覆盖子矩阵的面积。（每个字符的面积为 11）

数据范围
100001≤R≤10000, 1≤C≤75

输入样例：

2 5
ABABA
ABABA

输出样例：

2

提示
样例中给出的矩阵的最小覆盖子矩阵为 ABAB，面积为 22。

//错误示例
//2024.4.1
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 10004;

int r,c;
int nxt[oo];
bool che[oo];
char st[oo][100];

int use,ned;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> r >> c;

    for (int i=1;i<=r;i++){
      scanf("%s",st[i]);
      for (int j=1;j<=c;j++){
        bool tag = 1;
          for (int k=j;k<c;k+=j){
            for (int l=0;l<j&&l+k<c;l++){
              if (st[i][l]!=st[i][k+l]){
                tag = 0;break;}
              if (!tag)break;}
            if (!tag)break;}
          if (!tag)che[j]=1;}}
    //哦~宝贝儿~,你不会想看上面这坨*的

    for (int i=1;i<=c;i++)
        if (!che[i]){
            use = i;break;}
        
    for (int i=1;i<=r;i++) st[i][use] = '\0';
                
    int j = 0;

    for (int i=2;i<=r;i++){
        while(j&&strcmp(st[j+1],st[i]))
          j = nxt[j];
        if (!strcmp(st[j+1],st[i]))
        j++;
        nxt[i] = j;
    }
    
    ned = r - nxt[r];
    int out = ned*use;

    cout << out;
    return 0;
}

以下正确。

这是一个二维的kmp算法，直接把字符矩阵看成一不同的行和列，分别求出最小循环节。

对于最小循环节的长度，求出其横向最小长度和纵向最小长度。

就是gcd一下，求最小公倍数。

//2024.4.1
//by white_ice

#include<bits/stdc++.h>
using namespace std;

const int oo=10004;
 
int ne[oo];
bool sp[oo];
char st[oo][100];
int use,ned;

int main(){
    int n, m;
    cin >> n >> m;
    for (int i=1;i<=n;i++){
        scanf("%s", st[i]);
        for (int j=1;j<=m;j++){
            bool a = 1;
            for (int k=j;k<m;k+=j){
                for (int u=0;u<j&&u+k<m;u++){
                    if (st[i][u] != st[i][k + u]){
                        a = 0;
                        break;
                    }
                    if (!a) break;
                }
                if (!a) break;
            }
            
            if (!a) sp[j] = 1;
        }
    }
    
    for (int i=1;i<=m;i++)
        if (!sp[i]){
            use = i;
            break;
        }
        
    for (int i=1;i<=n;i++) st[i][use] = '\0';

    for (int i=2,j=0;i<=n;i++){
        while (j && strcmp(st[j + 1], st[i])) j = ne[j];
        if (!strcmp(st[j + 1], st[i])) j ++ ;
        ne[i] = j;
    }
    
    ned = n - ne[n];
    int out = use*ned;
    cout << out << endl;
    
    return 0;
}

C. 电话列表
题目描述
给出一个电话列表，如果列表中存在其中一个号码是另一个号码的前缀这一情况，那么就称这个电话列表是不兼容的。

假设电话列表如下：

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

在此例中，报警电话号码（911）为 Bob 电话号码（91 12 54 26）的前缀，所以该列表不兼容。

输入格式
第一行输入整数 tt，表示测试用例数量。

对于每个测试用例，第一行输入整数 nn，表示电话号码数量。

接下来 nn 行，每行输入一个电话号码，号码内数字之间无空格，电话号码不超过 1010 位。

输出格式
对于每个测试用例，如果电话列表兼容，则输出 YES。

否则，输出 NO。

数据范围
401≤t≤40, 100001≤n≤10000

输入样例：

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

输出样例：

NO
YES

//2024.4.1
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 100004;

string st;
int trie[oo][10];
int cnt;
bool flag;
bool ids[oo];

int ned;

void insert(string x){
    int use = 0;
    int len = x.size()-1;
    int tag = 0;
    for(int i=0;i<=len;i++){
        ned=x[i]-'0';
        if(trie[use][ned] == 0){
            tag = 1;
            trie[use][ned] = ++cnt;
        }

        use=trie[use][ned];
        if(ids[use] == 1){
            flag=1;
            return ;
        }
    }

    if(tag == 0){
        flag=1;
        return ;
    }
    ids[use] = 1;
    return ;
}

void init(){
    memset(ids,0,sizeof(ids));
    memset(trie,0,sizeof(trie));
    cnt=0;  flag=0;
}

int t,n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> t;
while(t--){
    init();

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> st;
        insert(st);
    }

    if(flag==0)
        puts("YES");    
    else puts("NO");
}
    return 0;
}

字典树裸题。