凯撒密码

题意：根据偏移量求出偏移后的字符串。
思路：因为题目限制了只有大小写字符和数字，那么我们就先将它们的相对位置关系存放在一个temp数组里面，然后根据偏移量进行映射即可。
代码：

class Solution {
public:
    /**
     * 解密密文
     * @param str string字符串 密文
     * @param d int整型 偏移量
     * @return string字符串
     */
     string temp="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    string decode(string str, int d) {
        // write code here
        int len=str.size();
        int l=temp.size();
        for(int i=0;i<len;i++){
            int id;
            if(str[i]<='9'&&str[i]>='0')  id=str[i]-'0';
            else if(str[i]<='Z'&&str[i]>='A')  id=str[i]-'A'+10;
            else  id=str[i]-'a'+36;
            if(id>=d)  str[i]=temp[id-d];
            else  str[i]=temp[l-d+id];
        }
        return str;
    }
};

完全平方数的尾巴

思路：打表。我们通过打表，我们可以发现满足题目条件的只有159个数，那么先打表，然后一个一个判断即可。
代码：

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
     int a[159]={0,1,4,9,16,24,25,36,41,44,49,56,64,76,81,84,89,96,100,104,116,121,124,129,136,144,156,161,164,169,176,184,196,201,204,209,216,224,225,236,241,244,249,256,264,276,281,284,289,296,304,316,321,324,329,336,344,356,361,364,369,376,384,396,400,401,404,409,416,424,436,441,444,449,456,464,476,481,484,489,496,500,504,516,521,524,529,536,544,556,561,564,569,576,584,596,600,601,604,609,616,624,625,636,641,644,649,656,664,676,681,684,689,696,704,716,721,724,729,736,744,756,761,764,769,776,784,796,801,804,809,816,824,836,841,844,849,856,864,876,881,884,889,896,900,904,916,921,924,929,936,944,956,961,964,969,976,984,996};
    bool solve(int x) {
        // write code here
        for(int i=0;i<159;i++){
            if(a[i]==x)  return true;
        }
        return false;
    }
};

排队

题意：n个人，m个窗口，给出求出每个人完成办理之后的时间的逆序对。
思路：既然是排队，我们很自然就想到要用队列来进行模拟，先求出每个人的办理时长。这里由于m个窗口都的人会变动的，我们就用一个有限队列来进行存储，我们先把m个0放进去，然后遍历n个人的时间，每次取出队首的元素，对应这个人的就是队首时间加上他的办理时间。求出tim数组之后，题目就转化为求逆序对的个数的一个题目了，板子题，用归并排序求得即可。
代码：

class Solution {
public:
    /**
     * 求解合法的(i,j)对的数量
     * @param n int整型 n个人
     * @param m int整型 m个窗口
     * @param a int整型vector 长度为n的vector,顺序表示1-n号客人的办理业务所需时间
     * @return long长整型
     */
     typedef long long ll;
     priority_queue<ll,vector<ll>,greater<ll> > q;
     ll tim[100010];
     ll temp[100010];
     ll sum=0;
     void merge(int L,int R){
         int mid=(L+R)>>1;
         int k=1,l=L,r=mid+1;
         while(l<=mid&&r<=R){
             if(tim[l]<=tim[r]){
                 temp[k++]=tim[l++];
             }
             else{
                 sum+=mid+1-l;
                 temp[k++]=tim[r++];
             }
         }
         while(l<=mid) temp[k++]=tim[l++];
         while(r<=R)  temp[k++]=tim[r++];
         k=1;
         for(int i=L;i<=R;i++,k++){
             tim[i]=temp[k];
         }
     }
     void mergesort(int l,int r){
         if(l<r){
             int mid=(l+r)>>1;
             mergesort(l,mid);
             mergesort(mid+1,r);
             merge(l,r);
         }
     }
    ll getNumValidPairs(int n, int m, vector<int>& a) {
        // write code here
        for(int i=0;i<m;i++){
            q.push(0);
        }
        for(int i=0;i<n;i++){
            ll t=q.top()+a[i];
            tim[i]=t;
            q.pop();
            q.push(t);
        }
        mergesort(0,n-1);
        return sum;
    }
};