字符串数学专题

粗心的小可

题目描述

小可非常粗心，打字的时候将手放到了比正确位置偏右的一个位置，因此，Q打成了W，E打成了R，H打成了J等等。键盘如下所示

现在给你若干行小可打字的结果，请你还原成正确的文本。

输入描述

若干行字符，每行字符串中可能包含大写字母、字符、数字、空格、或者上面键盘中的标点符号。

带单词标签（比如�������Control、�����Enter、���Tab等）的按键不会出现。同时，最左侧的`QAZ这四种字符也不会出现。

保证不会出现空行，并且字符的总量不超过10510​5​​。

输出描述

如题，将输入的所有文本还原成正确的文本。空格保持不变。保证所有的字母都是大写字母。

样例输入

O S, GOMR YPFSU/

[[-=,.M

样例输出

I AM FINE TODAY.

PP0-M,N

代码

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char c[50]={"`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"};
int main(){string s;while(getline(cin,s)){//循环输入，有空格 int len=s.size(),f;for(int i=0;i<len;i++){//遍历 if(s[i]==' '){continue;}for(int j=0;;j++){if(s[i]==c[j]){f=j;break;}}s[i]=c[f-1];}cout<<s<<"\n";}return 0;}

删除字符

题目描述

小可讨厌单词map，达达讨厌单词pie。现在给你一个长度为n的字符串，请问最少删除多少个字符，使得map和pie都不在这个字符串中出现。

输入描述

第一行给定一个整数T(1≤T≤10​4​​)，表示有T组输入。

对于每组输入，第一行一个正整数n(1≤n≤10​5​​)，表示字符串的长度。

第二行一个长度为n的字符串，只包含小写字母。

保证T组输入的字符串长度的总和不超过10​5​​。

输出描述

对于每组输入，输出一行一个整数，表示最少删除多少个字符，使得map和pie都不在这个字符串中出现。

样例输入

6

9

mmapnapie

9

azabazapi

8

mappppie

18

mapmapmapmapmapmap

1

p

11

pppiepieeee

样例输出

2

0

2

6

0

2 

代码

#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
int t;
int n;
char s[100005];
int cnt;
int main(){cin>>t;while(t--){cin>>n;cin>>s+1;cnt=0;for(int i=1;i<=n-2;i++){if(s[i]=='m'&&s[i+1]=='a'&&s[i+2]=='p'){i+=2;cnt++;}else if(s[i]=='p'&&s[i+1]=='i'&&s[i+2]=='e'){i+=2;cnt++;}}cout<<cnt<<"\n";}return 0;
}

完美序列

题目描述

小可现在有一个时刻自我排序的序列。这个序列时刻保持从小到大的顺序，即使插入一些数字，这个序列也会自动排好序。

一开始这个序列a有n个元素，分别是a​1​​,a​2​​,⋯,a​n​​。小可需要通过做若干次操作，让序列变得完美：

每次操作，小可选定序列中的两个数字x和y，满足x>y并且x−y不在序列a中。然后小可将x−y这个数字插入到序列中。

如果一个序列无法进行上面的操作，那么这个序列就是完美无缺的。小可想知道，这个序列变成完美序列之后，长度最长是多少。题目保证这个长度是有限的。

输入描述

第一行一个正整数T(1≤T≤10∧​4​​)，表示有T组输入。

对于每组输入，第一行一个正整数n(2≤n≤10∧​5​​)，表示序列a一开始的长度。

第二行n个正整数a​1​​,a​2​​,⋯,a​n​​(1≤a​1​​<a​2​​<⋯<a​n​​≤10∧​9​​)，表示序列a一开始的元素。

数据保证，T组输入的n的和不超过2×10∧5

输出描述

对于每组输入，输出一行一个整数，表示序列变成完美序列之后，长度最长是多少。

样例输入

2

2

1 2

3

5 10 25

样例输出

2

5

提示

样例中，第一组输入本身就是完美序列，无法进行操作。

第二组输入，最终的完美序列是5,10,15,20,25

代码

#include<iostream>
using namespace std;
int t;
int n;
int maxx=0;
int a[100005];
int gcd(int a,int b){if(a%b==0){return b;}else{return gcd(b,a%b);}
}
int main(){cin>>t;while(t--){maxx=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];maxx=max(maxx,a[i]);}int x=a[1];for(int i=2;i<=n;i++){x=gcd(x,a[i]);}cout<<maxx/x<<"\n";}return 0;
}

双质数

题目描述

如果一个数字除了11和它自身以外，只有一个正整数因数，那么这个数字就被称为“双质数”。

现在给出n个数，请你判断每个数字是否是双质数。

输入描述

第一行一个正整数n(1≤n≤10​5​​)，代表要询问n个数字。

接下来n个正整数字，每个数字的大小在[1,10​12​​]范围内。

输出描述

对于询问的每个数字，如果是双质数，输出YES，否则输出NO。

样例输入

3

4 5 6

样例输出

YES

NO

NO

代码

#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
const int N=1e6+10;
int n;
bool v[N]; 
void ola(int n){v[1]=1;for(int i=2;i<=n;i++){if(!v[i]){for(int j=i*2;j<=n;j+=i){v[j]=1;}}}
}
int main(){ola(N-1);scanf("%d",&n);ll x;for(int i=1;i<=n;i++){scanf("%lld",&x);ll m=sqrt(x);if(m*m==x&&!v[m]){printf("YES\n");}else{printf("NO\n");}}return 0;
}

因数分解

题目描述

给定一个正整数n，请你把n分解成三个互不相同的大于等于22的整数a,b,c，保a<b<c,a×b×c=n。如果有多解，保证a最小，在a最小的前提下保证b最小。

输入描述

第一行一个正整数T(1≤T≤100)，表示有T组输入。

对于每组输入，输入一个正整数n(2≤n≤10​9​​)，含义如题所示。

输出描述

对于每个n，如果不能按照要求分解，输出NO，否则，输出YES，然后换行输出分解出来的三个正整数。

样例输入

5

64

32

97

2

12345

样例输出

YES

2 4 8

NO

NO

NO

YES

3 5 823

代码

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int N=1e6+10;
int t,n;
int f(int t,int n){for(int i=t;i<=n/i;i++){if(n%i==0){return i;}}return 1;
}
int main(){cin>>t;while(t--){cin>>n;int a=f(2,n);n=n/a;int b=f(a+1,n);n=n/b;if(a!=1&&b!=1&&n!=1&&a!=b&&a!=n&&b!=n){cout<<"YES"<<"\n";cout<<a<<" "<<b<<" "<<n<<"\n";}else{cout<<"NO"<<"\n";}}return 0;
}