A.<小红的环形字符串>
简单的链表模拟题
每次删除前都进行判断(判断头尾是否相同或相邻的两个元素是否相同),相同的便删除掉,并记录删除的个数
#include<bits/stdc++.h>
using namespace std;
vector<char>k;//这里我用的vector容器来模拟
int t,ans;//用t记录一下是否满足判断,不满足时直接break结束循环
int main()
{
int n;
cin>>n;
char a;
for(int i=0;i<n;i++)
{
cin>>a;
k.push_back(a);
}
while(k.size()>1)
{
t=0;
if(k[0]==k[k.size()-1])
{
t=1;
k.erase(k.begin());
k.pop_back();
ans+=2;
}
else for(int i=1;i<k.size();i++)
{
if(k[i]==k[i-1])
{
t=1;
k.erase(k.begin()+i);
k.erase(k.begin()+i-1);
ans+=2;
break;
}
}
if(t==0) break;
}
cout<<ans;
return 0;
}
两种操作使x变成y
1. 将 x 乘以5。
2. 若 x 是6的倍数,将 x 除以6。
1. 将 x 乘以5。
2. 若 x 是6的倍数,将 x 除以6。
则:假设x需要乘以a个5,除以b个6可以得到y,那么x与y之间就有y/x=5^a/6^b;
那么可以用map记录每一个5^a/6^b的值,并存为a+b,后续,每次询问就直接在map中查找
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<double,int>k;
for(int i=0;i<=100;i++)
for(int j=0;j<=100;j++)
{
k[double(pow(5,i)/(pow(6,j)*1.0))]=i+j;
}
int n;cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
if(a==b) cout<<"0"<<endl;
else
{
double c;
c=double(b/(a*1.0));
if(k[c]) cout<<k[c]<<endl;
else cout<<"-1"<<endl;
}
}
}
D.回文权值和
经典的快速幂数论问题
一个字符串的权值为:长度为3的回文子串的数量
求长度为n的、仅由小写字母组成的所有字符串的权值之和。答案对10^9+7取模
从中不难看出所求结果res=(n-2)*26^(n-1)%(1e9+7) ----(模拟几组情况便能看出来)
由于数据n的范围最大是10^12,用暴力的方法一定会超时,所以要采用快速幂算法进行幂运算
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e9+7;
void solve(LL n)
{ LL a=26;
LL res=1;
LL k=n-1;
while(k)
{
if(k&1) res=(res*a)%N;
k>>=1;
a=(a*a)%N;
}
res=res%N;
cout<<((n-2)%N*res)%N<<endl;
}
int main()
{
LL n;cin>>n;
if(n<3)
{
cout<<"0"<<endl;
return 0;
}
solve(n);
return 0;
}



京公网安备 11010502036488号