题解 | #小红的环形字符串#

小红的环形字符串

https://ac.nowcoder.com/acm/contest/65821/A

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;
}

B.<小红的乘除变换>

两种操作使x变成y
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;
}