牛客周赛 Round 14

A、

小红拿到了一个环形字符串。所谓环形字符串，即首尾相连的字符串。

小红每次可以删除两个相邻的相同字符。小红想知道，最多可以删除多少个字符？

输入描述:

第一行输入一个正整数n，代表环形字符串的长度。
第二行输入一个长度为n，且仅由小写字母组成的字符串。请注意该字符串是首尾相连的。
1≤n≤10^5

输出描述:

最多可以删除的字符数量。

示例1

输入

5
abcba

输出

4

 这个题很经典啊 我感觉以前一直不会

思路：一个一个字符插进去  遇到和前一个一样  消去它们

然后只能是首尾消去了

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s;
int n;
list<char>q; 
signed main()
{
   cin>>n>>s;
   
   int sum=0;
    
   for(int i=0;i<n;i++)
   {
   	 if(!q.empty())
   	 {
   	 	 if(q.back()==s[i])sum+=2,q.pop_back();
   	 	 else q.push_back(s[i]);
	 }
	 else
	 {
	 	 q.push_back(s[i]);
	 }
   }
   
   while(q.size()>1&&q.front()==q.back()){
   	sum+=2;
   	q.pop_back();
   	q.pop_front();
   }
   
   cout<<sum<<"\n";
	return 0;
} 
//x*5n/6m=y
//x*5n=y*6m 
//x/y=6m/5n
 

B、

题目描述

小红拿到了一个正整数 x。她可以对 x 做以下操作：
1. 将 x 乘以5。
2. 若 x 是6的倍数，将 x 除以6。

例如，12经过一次操作可以变成60，也可以变成2。

现在小红想知道，如果要把 x 变成 y，需要操作多少次？一共有 t 组询问。

输入描述:

第一行输入一个正整数 t，代表询问次数。
接下来的 t 行，每行输入两个正整数 x 和 y ，代表一次询问。
数据范围：
1≤t≤1000
1≤x,y≤10^9

输出描述:

输出t行，对于每次询问，如果无论如何都不能把 x 变成 y，输出-1。否则输出操作次数。

示例1

输入

1
6 5

输出

2

说明

x除以6变为1，再乘5变为5，即操作2次可使x变为y

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
signed main()
{
    int t;
    cin>>t;
    while (t--) {
        int X,Y;
        cin>>X>>Y;
        int c5 = 0, c6=0, d5=0, d6=0;
        while (X%5==0) c5++, X/=5;
        while (X%6==0) c6++, X/=6;
        while (Y%5==0) d5++, Y/=5;
        while (Y%6==0) d6++, Y/=6;
        int ans;
        if (c5>d5||c6<d6|| X!=Y) ans=-1;
        else ans = d5-c5+c6-d6;
        cout<<ans<<"\n";
    }
	return 0;
} 
 
 

 

 这个是把x、y都溯源回本质 再进行判断。

D、

定义一个字符串的权值为：长度为3的回文子串的数量。
求长度为n的、仅由小写字母组成的所有字符串的权值之和。答案对10^9+7取模。
提示：共有26^n个字符串。

输入描述:

一个正整数n
1≤n≤10^12

输出描述:

长度为n的所有字符串权值之和，对10^9+7取模的值。

示例1

输入

3

输出

676

说明

长度为3的字符串中，有676个字符串的权值为1：aba、ovo等。

 先放代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int qsm(int x,int n)
{
	int res=1;
	while(n)
	{
		if(n&1)res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	} 
	return res;
}
signed main()
{
    int n;
    
    cin>>n;
    
    if(n<3){
    	cout<<0<<"\n";
		return 0; 
	} 
	
	int sum=(n-2)*26*26%mod*qsm(26,n-3)%mod;
	cout<<sum<<"\n";
	return 0;
} 
 
 

n-2是我有这么多组可以平移 

26*26 是一组的里面的数量

qsm（26，n-3）是这一组3个字符以外 其他可以任选

C我不会 以后有空看看能不能补 看到头疼