题目：张老师和菜哭武的游戏

题目链接：https://ac.nowcoder.com/acm/contest/5477/A

题目大意：

题目转化可变为在寻找在1~n 中寻找x的个数，其中x符合x = y*a + z*b，个数为偶数则后手胜

思路:

由扩展欧几里得算法可知这个 x 可被 gcd(a,b)整除，所以1~n中寻找可被gcd(a,b)整除的个数，也就是 n / gcd(a,b) 。

解题代码:

//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const long long N = 1e10 + 7;
const int maxn = 2e5 + 5;
const long long INF = 8e18;
typedef long long ll;
#define for0(i,n) for(int i = 0;i < n;i++)
#define for1(i,n) for(int i = 1;i <= n;i++)
using namespace std;
int gcd(int x,int y)
{
    if(x%y==0)
        return y;
    return gcd(y,x%y);
}
int main()
{
    int t;
    cin>>t;
    while(t--){

        int n,a,b;
        cin >> n >> a >> b;
        int num = gcd(a,b);
        if(n/num % 2 == 0)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
}

题目：排列计算

题目链接：https://ac.nowcoder.com/acm/contest/5477/F

题目大意：

排列长度为n的数列（包含1~n不重复），给出m个询问区间，求解如何最优安排数列，使得所有询问区间内的和最大。

思路:

本题关键寻找1~n每个位置被区间询问的次数，将询问次数最多的位置尽量放大数。所以可利用一维差分进行记录各位置询问次数。

一维差分：如果要在一个区间[ l,r ]内都加上一个数a，就可以弄一个差分数组,在x[l]处+a，在x [ r+1 ]处-a，这样像前缀和一样扫过l到r这个区间时,在l处开始有+a，+a对 [ l,r ]区间产生影响，在r+1处-a变回原来的值，对r+1后面的区间没有了影响。

解题代码:

//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const long long N = 1e10 + 7;
const int maxn = 2e5 + 5;
const long long INF = 8e18;
typedef long long ll;
#define for0(i,n) for(int i = 0;i < n;i++)
#define for1(i,n) for(int i = 1;i <= n;i++)
ll x[maxn];
int main()
{
    int n,m;
    cin >> n >> m;
    while(m--){
        int a,b;
        cin >> a >> b;
        x[a]++;
        x[b+1]--;

    }
    for(int i = 1;i <= n;i++){
        x[i] += x[i-1];
    }
    sort(x+1,x+1+n);
    ll sum = 0;
    for(int i = n ;i > 0;i--){  
        sum += x[i] * i;
    }
    cout << sum << endl;
    return 0;
}