s赛5 青白黄砖全题解
A 凯撒密码
定义一个字符串由全部的合法字符按顺序组成 在复制一遍形成一个环
使用字符串的rfind（优先位于后面的相同字符）函数找到现在字符的位置在进行变换
class Solution {
public:
/**
* 解密密文
* @param str string字符串 密文
* @param d int整型 偏移量
* @return string字符串
*/
string decode(string str, int d) {
string t="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
t+=t;
string s;
for(int i=0;i<str.size();i++) s+=t[t.rfind(str[i])-d];
return s;
};
};B 完全平方数
大于一千的数在取模后与小于一千的某个数的数值是一样的 所以我们只需要遍历1-999就行
class Solution {
public:
/**
*
* @param x int整型
* @return bool布尔型
*/
bool solve(int x) {
for(int i=1;i<=999;++i)
{
if((i*i)%1000==x) return true;
}
return false;
}
};C 排队
用一个优先队列存储排队的时间顺序 在用归并排序统计逆序对的个数即为答案
class Solution {
public:
#define ll long long
priority_queue<ll,vector<ll>, greater<ll>>b;
ll s[111111];
void Union(int L,int R,int mid,ll &sum)
{
ll q[111111];
int k=1,l=L,r=mid+1;
while(l<=mid&&r<=R)
{
if(s[l]<=s[r])
{
q[k++]=s[l++];
}
else
{
sum+=mid+1-l;
q[k++]=s[r++];
}
}
while(l<=mid)q[k++]=s[l++];
while(r<=R)q[k++]=s[r++];
for(int i=L,j=1;i<=R;i++,j++)s[i]=q[j];
return;
}
void merge(int l,int r,ll &sum)
{
if(l==r)return;
int mid=(l+r)/2;
merge(l,mid,sum);
merge(mid+1,r,sum);
Union(l,r,mid,sum);
}
ll getNumValidPairs(int n, int m, vector<int>& a) {
// write code here
for(int i=0;i<m;++i)b.push(0);
for(int i=1;i<=n;++i)
{
ll k=b.top()+a[i-1];
s[i]=k;
b.pop();
b.push(k);
}
ll ans=0;
merge(1,n,ans);
return ans;
}
};D 牛牛的字符串
用标记数组存储是否到过 没到过的字符进行+K的比较并标记
在比较过程中用一个数组统计字符的个数和大小 每一个新的字符都能与前面比他小的字符进行交换 这样答案就出来了
class Solution {
public:
/**
*
* @param s string字符串 s.size() <= 1e5
* @param k int整型 k <= s.size()
* @return int整型
*/
int turn(string s, int k) {
// write code here
int ans=0,v[100005]={0};
int len=s.length();
for(int i=0;i<len;++i)
{
if(v[i]) continue;
int q[30]={0};
for(int j=i;j<len;j+=k)
{
v[j]=1;
int tmp=s[j]-'a'+1;
for(int kk=1;kk<tmp;++kk)
ans+=q[kk];
q[tmp]++;
}
}
return ans;
}
};E 下棋
先将棋盘存入数组 在二维前缀和统计大小 在由题目所给式子来进行累加得到答案
class Solution {
public:
/**
* 求每一步后的总分数，所有分数都对1,000,000,007取模
* @param n int整型 棋盘大小
* @param query int整型vector 每次掷出的点数的列表
* @return int整型vector
*/
#define ll long long
int mod=1000000007;
ll a[2005][2005],sum[2005][2005];
int x[2005*2005],y[2005*2005];
vector<int> getScores(int n, vector<int>& q)
{
// write code here
vector<int> res;
int cnt=1,i=1,j=1;
while(cnt<=n*n)///将棋盘存入数组
{
for(;j<=n;++j)
{
if(j>n||a[i][j]) break;
x[cnt]=i;
y[cnt]=j;
a[i][j]=cnt++;
}
j--,i++;
for(;i<=n;++i)
{
if(i>n||a[i][j]) break;
x[cnt]=i;
y[cnt]=j;
a[i][j]=cnt++;
}
i--,j--;
for(;j>=1;--j)
{
if(j<1||a[i][j]) break;
x[cnt]=i;
y[cnt]=j;
a[i][j]=cnt++;
}
j++,i--;
for(;i>=1;--i)
{
if(i<1||a[i][j]) break;
x[cnt]=i;
y[cnt]=j;
a[i][j]=cnt++;
}
i++,j++;
}
for(int i=1;i<=n;++i)///二维前缀和统计
{
for(int j=1;j<=n;++j)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
int idx=1;
ll ans=0;
for(int i=0;i<q.size();++i)///由题目的式子来累加
{
idx=(idx+q[i]-1)%(n*n)+1;
for(int j=max(x[idx]-q[i]+1,1);j<=min(x[idx]+q[i]-1,n);++j)
{
ans=(ans+sum[j][n]-sum[j-1][n])%mod;
}
for(int j=max(y[idx]-q[i]+1,1);j<=min(y[idx]+q[i]-1,n);++j)
{
ans=(ans+sum[n][j]-sum[n][j-1])%mod;
}
for(int j=max(x[idx]-q[i]+1,1);j<=min(x[idx]+q[i]-1,n);++j)
{
for(int k=max(y[idx]-q[i]+1,1);k<=min(y[idx]+q[i]-1,n);++k)
{
ans=((ans-a[j][k])%mod+mod)%mod;
}
}
res.push_back((int)ans);
}
return res;
}
};具体的解法在程序中体现qwq
