题目1

题目链接
题目大意：
有两种车分别有4个轮子和6个轮子，现在只知道若干个车的轮子总数，想知道最少和最多有几辆车；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例一行 整数 𝑛，表示 𝑛个轮子 (1≤𝑛≤10e18)

输出：
每个样例一行，分别输出最少和最多有几辆车，如果没有则输出-1；

Examples
input
4
4
7
24
998244353998244352
output
1 1
-1
4 6
166374058999707392 249561088499561088

题目解析：
容易知道，如果n为奇数，则题目无解；
n为偶数，如果n=2则无解，其他必然有解；
最少的情况，全部用6轮，剩下的有2个轮子和4个轮子的情况；如果剩2个轮子，则总数+1（将1个6改成4就好）；如果剩4个轮子，则总数+1；
最多的情况，全部用4轮，如果剩2个轮子，则总数不变（将1个4改成6就好）；

class Solution {
    static const int N = 201010;
    int a[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            lld n;
            cin >> n;
            if (n < 4 || n % 2) {
                cout << -1 << endl;
            }
            else {
                lld ansMin = (n / 6) + (n % 6 != 0);
                lld ansMax = (n / 4);
                cout << ansMin << " " << ansMax << endl;
            }
        }
    }
}
ac;

题目2

题目链接
题目大意：
给出n个整数的数组a，现在有两个操作：
1、将第i个数字替换为x；（x为输入的整数）
2、将整个数组替换为x；（x为输入的整数）
现在想知道经历q次操作，每次操作完数组的和；

输入：
第一行，整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5)
第二行n个整数 𝑎1,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
接下来q行，每行第一个数字是t，表示操作1或者操作2；
如果t=1，则接下来输入数字i和x (1≤𝑖≤𝑛, 1≤𝑥≤1e9)
如果t=2，则接下来输入数字x (1≤𝑥≤1e9)

输出：
每个操作一行，输出操作后的数字和；

Examples
input
5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1

output
19
50
51
42
5

题目解析：
朴素的做法，对于数组a，操作1则修改a[i]，时间复杂度O（1）；
操作2则全量修改数组a，时间复杂度O（N）；
计算数字和的复杂度，也是O（N），总的复杂度是（NQ）；

对于操作2，全量修改没必要，用变量记住当前整个数组已经修改即可，数字和也不需要累计，直接x和n的乘积即可；
但是这个变量要如何兼容操作1？
不用兼容，单独用一个map来记录操作1，当遇到操作2的时候再把map清空；正常往map里面添加一个值的时候，我们就可以实时算出来这个值带来的总和diff，O（1）就可以维护这个数组和；
将这个思路流程化，那么就是记录一个当前和sum；
然后生成一个map，记录每个位置对应的值；
当遇到操作1，则访问当前map，拿到当前值（如果map没有就是操作2的值），生成新的值记录到map，并更新diff到sum；
遇到操作2，则清空map并更新sum；
总的复杂度是O(NlogN)；

class Solution {
    static const int N = 201010;
    lld a[N];

public:
    void solve() {
        lld n, q;
        cin >> n >> q;
        map<lld, lld> h;
        lld cur = 0, sum = 0;
        for (int i = 1; i <= n; ++i) {
            lld x;
            cin >> x;
            h[i] = x;
            sum += x;
        }
        while (q--) {
            int k;
            cin >> k;
            if (k == 1) {
                int i, x;
                cin >> i >> x;
                if (h[i]) {
                    sum += x - h[i];
                    h[i] = x;
                }
                else {
                    sum += x - cur;
                    h[i] = x;
                }
            }
            else {
                int x;
                cin >> x;
                cur = x;
                sum = cur * n;
                h.clear();
            }
            cout << sum << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
有一个n x n的国际象棋棋盘，现在有3个操作：
操作1，往棋盘（x，y）上面放一个车，车可以攻击同一行或者同一列；
操作2，移除棋盘（x，y）上面的车；
操作3，询问区域(𝑥1,𝑦1)到(𝑥2,𝑦2)内所有位置，是否都可以被车攻击到；
现在有q个操作，想知道每次操作3 之后的结果；

输入：
第一行，整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5)
接下来q行，每行第一个数字是t，表示操作1、2、3；
如果t=1或者2，则接下来输入数字x和y； (1 ≤ 𝑥,𝑦 ≤ 𝑛)
如果t=3，则接下来输入数字x1、y1、x2和y2； (1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛, 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑛)

输出：
每个操作3一行，输出YES或者NO；

Examples
input
8 10
1 2 4
3 6 2 7 2
1 3 2
3 6 2 7 2
1 4 3
3 2 6 4 8
2 4 3
3 2 6 4 8
1 4 8
3 2 6 4 8

output
No
Yes
Yes
No
Yes

题目解析：
我们用row[N]和column[N]来表示行和列，那么添加(x, y)就可以拆分为row[x]和column[y]的变动；
操作1和操作2比较简单，直接操作数组即可；
操作3，朴素的想法是遍历所有行、列，看看是否满足，所有行或者所有列都被车覆盖；这样的复杂度复杂度是O(N)；
分析这个遍历过程，当我们想知道row[x1]到row[x2]这个区间，是否全部为1，其实可以转化为前n项和之差：只要sum[x2] - sum[x1] = x2 - x1，就满足条件；
于是问题转化为，如何快速维护sum[i]？（row前i个元素的和）
这里偷个懒，用树状数组来支持。（就不展开介绍怎么用树状数组了，可以自己百度，有非常详细介绍）

class TreeArray {
    static const int N = 201001;
    int tree[N];
    
    int low_bit(int x)
    {
        return x&-x;
    }
    public:
    void tree_add(int x,int v, int n)
    {
        while(x<=n)
        {
            tree[x] += v;
            x+=low_bit(x);
        }
    }
    int tree_sum(int x)
    {
        int sum=0;
        while(x)
        {
            sum += tree[x];
            x-=low_bit(x);
        }
        return sum;
    }
};

class Solution {
    static const int N = 201001;
    TreeArray rowArr, columnArr;
    int rowCnt[N], columnCnt[N];

public:
    void solve() {
        int n, q;
        cin >> n >> q;
        while (q--) {
            int k;
            cin >> k;
            
            if (k == 1) {
                int x, y;
                scanf("%d%d", &x, &y);
                int add = 1;
                rowCnt[x] += add;
                if (rowCnt[x] == 1) {
                    rowArr.tree_add(x, add, n);
                }
                columnCnt[y] += add;
                if (columnCnt[y] == 1) {
                    columnArr.tree_add(y, add, n);
                }
            }
            else if (k == 2) {
                int x, y;
                scanf("%d%d", &x, &y);
                int add = -1;
                rowCnt[x] += add;
                if (rowCnt[x] == 0) {
                    rowArr.tree_add(x, add, n);
                }
                columnCnt[y] += add;
                if (columnCnt[y] == 0) {
                    columnArr.tree_add(y, add, n);
                }
            }
            else {
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                int rowSum = rowArr.tree_sum(x2) - rowArr.tree_sum(x1 - 1);
                int columnSum = columnArr.tree_sum(y2) - columnArr.tree_sum(y1 - 1);
                if (rowSum == (x2 - x1 + 1) || columnSum == (y2 - y1 + 1)) {
                    cout << "Yes" << endl;
                }
                else {
                    cout << "No" << endl;
                }
            }

        }
    }
}
ac;

题目4

题目链接
题目大意：
有一个n个节点的有向图，每个节点有一个数字a[i]；
现在可以选择某个节点，从这个节点开始沿着有向边走，记录每个访问到的节点，并将这个访问顺序记录下来；
现在想知道，如果需要访问k个节点，访问顺序中的节点数字最大值的最小值是多少；

输入：
整数 𝑛, 𝑚 and 𝑘 (1≤𝑛≤2⋅1e5, 0≤𝑚≤2⋅1e5, 1≤𝑘≤10e18)
接下来n个整数 𝑎𝑖 (1≤𝑎𝑖≤1e9)
接下来是m条行，每行有整数 𝑢 and 𝑣 ，表示u到v的边(1≤𝑢≠𝑣≤𝑛)
题目保证没有指向自己的边，也没有多重边；

输出：
输出k个节点，节点数字最大值的最小值是多少；
如果无法访问到k个节点，则输出-1；

Examples
input
6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

output
4

题目解析：
先用朴素的思维来分析，假如我们需要访问1个节点，那么就是寻找节点的最小值；
如果是需要访问2个节点，那么问题就变得复杂，因为节点2->3的解是比 节点1->4的解更优；那么节点的最小值就失去了意义；
如果是想遍历整个图，并且在遍历过程中去保留这个最大值的最小，无疑是非常复杂的；

那么换一种思想，假如我用二分来处理这个最大值，得到mid，如果a[i]<=mid认为a[i]可以访问，如果a[i]>mid则认为节点不可方案；
题目变成在有向图中，询问遍历步数最多是否能到k；

先不考虑环的情况，在一个有向图中要去判断遍历步数最多情况，可以枚举所有起点出发的情况，然后通过深度优先搜索来记录遍历过程中的步数；
当出现环的时候，我们可以把步数设置为一个很大的值，这样也可以统一逻辑处理。

那么，问题又变成如何在有向图中判断环的存在？
当我们在深度优先遍历的过程中，假如当前点是u，下一个节点是v，此时有两种情况，v是已经访问过，v还没访问过；
如果v没有访问过，那么就访问v即可；
如果v已经访问过，此时又有两种情况，如果v已经访问过，但是还在当前的递归栈中，则证明v已经可以和u构成环；（step[u]=inf，inf表示一个很大值）
如果是v已经访问过，但是和当前递归栈中没有关系，怎么v只是普通访问过的节点；（此时step[u]=max(step[u], step[v]+1);

class Solution {
    static const lld N = 201001;
    static const lld inf = 0x7fff7fff3fff7fff;
    lld a[N];
    int vis[N]; // 0表示没访问，1表示访问中，2表示访问后
    lld step[N], n;
    vector<lld> g[N];
    
    void dfs(lld u, lld cur, lld mid) {
        vis[u] = 1;
        step[u] = 1;
        for (lld i = 0; i < g[u].size(); ++i) {
            lld v = g[u][i];
            if (a[v] > mid) {
                continue;
            }
            if (!vis[v]) {
                dfs(v, cur + 1, mid);
                step[u] = max(step[u], step[v] + 1);
            }
            else {
                if (vis[v] == 1) {
                    step[u] = inf;
                }
                else {
                    step[u] = max(step[u], step[v] + 1);
                }
            }
        }
        vis[u] = 2;
    }
    
    bool check(lld mid, lld k) {
        memset(vis, 0, sizeof(vis));
        memset(step, 0, sizeof(step));
        dfs(0, 0, mid);
        for (lld i = 1; i <= n; ++i) {
            if (a[i] > mid) {
                continue;;
            }
            if (step[i] >= k) {
                return true;
            }
        }
        return false;
    }

public:
    void solve() {
        lld m, k;
        cin >> n >> m >> k;
        lld l = 0, r = 0x7fffffff;
        for (lld i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            r = max(r, a[i]);
        }
        for (lld i = 0; i < m; ++i) {
            lld u, v;
            scanf("%lld%lld", &u, &v);
            g[u].push_back(v);
        }
        for (int i = 1; i <= n; ++i) {
            g[0].push_back(i);
        }
        lld ans = -1;
        while (l <= r) {
            lld mid = (l + r) / 2;
            if (check(mid, k)) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        cout << ans << endl;
    }
}
ac;

题目5

题目链接
题目大意：
有n个格子排成一行，每个格子有一个灯，灯有两个方向：L和R，分别表示朝左和朝右；
当一个灯朝左时，它能照亮其左边的格子；（不包括灯所在格子）
当一个灯朝右时，它能照亮其右边的格子；（不包括灯所在格子）
现在允许选择某个格子，交换该格子和右边格子的灯，灯的朝向不变；（不能选择最右边的格子）
现在想知道，是否能够让每个格子都能被灯照亮；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤10000)
每个样例2行，第一行整数 𝑛 (2≤𝑛≤100000)
第二行n个字符'L' 和 'R'

输出：
每个样例一行，如果无解输出-1，如果不需要交换输出0，如果需要交换则输出交换第x个格子；（1 <= x < n）

Examples
input
6
2
LL
2
LR
2
RL
2
RR
7
LLRLLLR
7
RRLRRRL
output
-1
1
0
-1
3
6

题目解析：
样例给了一个比较关键的数据，当字符串出现RL，题目就必然存在解；
基于此我们继续分析，当字符串只有L或者只有R时，必然无解；
当字符串存在L和R时，必然有解：因为总是能找到L和R相交的位置，如果是R和L，则无需交换；如果是L和R，则进行交换；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            string str;
            cin >> str;
            int index = -1;
            for (int i = 0; i + 1 < n; ++i) {
                if (str[i] != str[i + 1]) {
                    index = str[i] == 'R' ? 0 : (i + 1);
                    break;
                }
            }
            cout << index << endl;
        }
    }
}
ac;