浙江理工大学2023淘汰赛部分题目的理解
这里仅提供代码及思路，网站链接如下：
链接>http://47.96.116.66/contest.php?cid=5372<
难度梯度：A B C L D E F K I G H——/) /)
有错误的话请联系我，我也想知道 ฅ(• - •)ฅ
痛！请勿在比赛中使用endl(虽然我不会)
问题 A: ACMer猫猫
题面：
你说的对，但是ICPC是由ACM自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作PTA的幻想世界，在这里，你将扮演一位名为ACMer的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们， 和他们一起击败强敌，找回失散的亲人——同时，逐步发掘PTA的真相。
刚刚成为成为ACMer的猫猫获得了一个由 A, C, M三个字符组成的字符串，它想知道有多少个长度为3的 ACM子串。
思想：枚举
代码：
点击查看代码
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#pragma GCC optimize(2)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,maxn = 1e6 + 10;
char a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int res=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i>=3&&a[i-2]=='A'&&a[i-1]=='C'&&a[i]=='M')
{
res++;
}
}
cout<<res;
}
问题 B: 猫猫本
题面：
猫猫在《猫猫本》上写了n个由2个小写字母组成的字符串。现在猫猫想知道每写一个新的字符串后，《猫猫本》上有多少字符串和新添加的字符串是相似的。猫猫认为，当且仅当只有一个位置相同两个字符串是相似的。例如aa和ab，ab和cb是相似的；但是aa和aa，aa和cc是不相似的。
思想：容斥\哈希\map
点击查看代码
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#pragma GCC optimize(2)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,maxn = 1e6 + 10;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 1;i <= n; i++){
string s;
cin>>s;
int t1=s[0]-'a'+1;
int t2=s[1]-'a'+1;
cout<<a[t1]+b[t2]-2*b[t1*131+t2]<<"\n";
a[t1]++;
b[t2]++;
b[t1*131+t2]++;
}
return 0;
}
问题 C: 猫猫game
题面：
猫猫一个人在实验室玩游戏。
游戏规则是这样的：每轮游戏会给猫猫两个整数 n,m，猫猫在区间 [1,n] 内，随机取m个整数。该操作进行\(2023^{2023}\)次。如果每次这m个数中，一定存在一个整数是另一个整数的倍数，则猫猫回答Yes，否则回答No。请你告诉猫猫每轮游戏的结果。
思想：鸽巢原理，真的不是找质数（赛时我在干这个蠢事）
样本大至正无穷，相当于取遍样本。下面解释为什么找质数是错误的，注意到《每个》，若n=10，取56789；这时候质数是2357，显然前面的数字更多更符合题意。其次，当n比较大时，一个数的质数个数是\(\frac{X}{lnX}\)级别的,而一个数的一半是\(\frac{X}{2}\)。显然前者小于后者。
下面证正确思想：m>(n+1)/2。每次取一半的时候都是满足题意的，n为偶数时是不影响的，n为奇数时变成n+1（自己理解下吧）
代码:
点击查看代码
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#pragma GCC optimize(2)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,maxn = 1e6 + 10;
void solve(){
int n,m;
cin>>n>>m;
if(m>(n+1)/2){
puts("Yes");
} else {
puts("No");
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while( t-- ){
solve();
}
return 0;
}