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