题解_牛客博客

1.链表直接模拟，注意对长度的特判

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxx 300000
#define  mod 1000000007
#define INF 0x3f3f3f3f
int st;
int ans=0;
int n,a,b,c,m,neww,t,l,r;
int nxt[maxx];
int lst[maxx];
int vis[maxx];
string s;


signed main()
{
   cin>>n>>s;
   l=n;
   for(int i=0;i<n;++i)
   {nxt[i]=(i+1)%n;
   lst[i]=(i-1+n)%n;
   }
   int i=0;
   while(++neww<=3*n)
   {
     if(l==3||l==2)
     {
      if(s[i]==s[nxt[i]]||s[i]==s[lst[i]])
       ans+=2;
       break;
     }
     if(l==1) break;
     if(l==0) break;
     if(s[nxt[i]]==s[i])
     {
       a=lst[i];
       b=nxt[nxt[i]];
       ans+=2;
       nxt[a]=b;
       lst[b]=a;
       i=b;
       l-=2;
     }
     else if(s[lst[i]]==s[i])
     {
       a=lst[lst[i]];
       b=nxt[i];
       ans+=2;
       nxt[a]=b;
       lst[b]=a;
       i=b;
       l-=2;
     }
     else i=nxt[i]; 
   }
   cout<<ans;
}

2.适当公式变换有y/x=5^a/6^b，对y,x进行约分后寻找符合条件的a,b。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxx 1000
#define  mod 1000000007
#define INF 0x3f3f3f3f
int st;
int ans=0;
int n,noww,a,b,c,m,s,neww1,t;
int log5(int x)
{
  int noww=1;
  for(int j=0;j<=17;++j)
  {if(noww==x)
  return j;
  noww*=5;
  }
  return -2;
}

int log6(int x)
{
  int noww=1;
  for(int j=0;j<=17;++j)
  {if(noww==x)
  return j;
  noww*=6;
  }
  return -2;
}



signed main()
{
   cin>>t;
   for(int i=1;i<=t;++i)
   {
    int x,y;
     cin>>x>>y;
     int d=__gcd(x,y);
     x/=d;
     y/=d;
     ans=log5(y)+log6(x);
     if(log5(y)<0||log6(x)<0) cout<<"-1"<<"\n";
     else cout<<ans<<"\n";
   }
}

3.子串连续，记录每一个字母的第一次出现位置，向量维护，每个位置寻找每个元素出现位置，并进行排序，依照出现次数选择适宜位置即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxx 400000
#define  mod 1000000007
#define INF 0x3f3f3f3f
int st;
int ans=0;
int n,a,b,c,m,neww1,t,l,r;
//char all[maxx];
vector<int> M[1000];
vector<int> noww;
string s;


signed main()
{
   cin>>n>>l>>r>>s;
   for(int i=n-1;i>=0;--i)
   M[s[i]].push_back(i);
   for(int i=0;i<n;++i)
   {
     noww.clear();
     for(int j='a';j<='z';++j)
     if(M[j].size()>0)
     noww.push_back(M[j][M[j].size()-1]);
     sort(noww.begin(),noww.end());
     int q1=-1,q2=n-1;
     if(noww.size()>=l)
      q1=noww[l-1];
     if(noww.size()>=r+1)
      q2=noww[r]-1;
     if(q1!=-1) ans+=(q2-q1+1);
     M[s[i]].pop_back();
   }
   cout<<ans;
}

4.数学题，计算(n-2)*26^(n-1),利用动态规划进行推导，示意如下:

dp[n][i][j],代表长度为n,i为n位置的字符,j为n-1位置的字符的子串权值。

dp[n][i][j]=∑dp[n-1][j][k](对k求和)+26^(n-3)

dp[n][i]=∑∑dp[n-1][j][k](对j,k求和)+26^(n-2)

dp[n]=26dp[n-1]+26^(n-1)

求几项可以得出通项公式。

具体计算使用快速幂。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxx 100
#define mod 1000000007
#define INF 0x3f3f3f3f
int ans=0;
int n;
int poww(int i,int j)
{
  if(j<0)  return 0;
  if(j==0) return 1;
  if(j==1) return i%mod;
  int a=poww(i,j/2);
  a=(a*a)%mod;
  if(j%2==0) return a;
  else return (a*(i%mod))%mod;
}

signed main()
{
   cin>>n;
   if(n<3) cout<<0;
    else
    { ans=(poww(26,n-1)*((n-2)%mod))%mod;   
   cout<<ans;}
}