題目1

題目鏈接
題目大意：
有兩種車分別有4個(gè)輪子和6個(gè)輪子，現(xiàn)在只知道若干個(gè)車的輪子總數(shù)，想知道最少和最多有幾輛車；

輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤1000)
每個(gè)樣例一行 整數(shù) ??，表示 ??個(gè)輪子 (1≤??≤10e18)

輸出：
每個(gè)樣例一行，分別輸出最少和最多有幾輛車，如果沒有則輸出-1；

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

題目解析：
容易知道，如果n為奇數(shù)，則題目無解；
n為偶數(shù)，如果n=2則無解，其他必然有解；
最少的情況，全部用6輪，剩下的有2個(gè)輪子和4個(gè)輪子的情況；如果剩2個(gè)輪子，則總數(shù)+1（將1個(gè)6改成4就好）；如果剩4個(gè)輪子，則總數(shù)+1；
最多的情況，全部用4輪，如果剩2個(gè)輪子，則總數(shù)不變（將1個(gè)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個(gè)整數(shù)的數(shù)組a，現(xiàn)在有兩個(gè)操作：
1、將第i個(gè)數(shù)字替換為x；（x為輸入的整數(shù)）
2、將整個(gè)數(shù)組替換為x；（x為輸入的整數(shù)）
現(xiàn)在想知道經(jīng)歷q次操作，每次操作完數(shù)組的和；

輸入：
第一行，整數(shù) ?? and ?? (1≤??,??≤2?1e5)
第二行n個(gè)整數(shù) ??1,…,???? (1≤????≤1e9)
接下來q行，每行第一個(gè)數(shù)字是t，表示操作1或者操作2；
如果t=1，則接下來輸入數(shù)字i和x (1≤??≤??, 1≤??≤1e9)
如果t=2，則接下來輸入數(shù)字x (1≤??≤1e9)

輸出：
每個(gè)操作一行，輸出操作后的數(shù)字和；

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

題目解析：
樸素的做法，對于數(shù)組a，操作1則修改a[i]，時(shí)間復(fù)雜度O（1）；
操作2則全量修改數(shù)組a，時(shí)間復(fù)雜度O（N）；
計(jì)算數(shù)字和的復(fù)雜度，也是O（N），總的復(fù)雜度是（NQ）；

對于操作2，全量修改沒必要，用變量記住當(dāng)前整個(gè)數(shù)組已經(jīng)修改即可，數(shù)字和也不需要累計(jì)，直接x和n的乘積即可；
但是這個(gè)變量要如何兼容操作1？
不用兼容，單獨(dú)用一個(gè)map來記錄操作1，當(dāng)遇到操作2的時(shí)候再把map清空；正常往map里面添加一個(gè)值的時(shí)候，我們就可以實(shí)時(shí)算出來這個(gè)值帶來的總和diff，O（1）就可以維護(hù)這個(gè)數(shù)組和；
將這個(gè)思路流程化，那么就是記錄一個(gè)當(dāng)前和sum；
然后生成一個(gè)map，記錄每個(gè)位置對應(yīng)的值；
當(dāng)遇到操作1，則訪問當(dāng)前map，拿到當(dāng)前值（如果map沒有就是操作2的值），生成新的值記錄到map，并更新diff到sum；
遇到操作2，則清空map并更新sum；
總的復(fù)雜度是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

題目鏈接
題目大意：
有一個(gè)n x n的國際象棋棋盤，現(xiàn)在有3個(gè)操作：
操作1，往棋盤（x，y）上面放一個(gè)車，車可以攻擊同一行或者同一列；
操作2，移除棋盤（x，y）上面的車；
操作3，詢問區(qū)域(??1,??1)到(??2,??2)內(nèi)所有位置，是否都可以被車攻擊到；
現(xiàn)在有q個(gè)操作，想知道每次操作3 之后的結(jié)果；

輸入：
第一行，整數(shù) ?? and ?? (1≤??,??≤2?1e5)
接下來q行，每行第一個(gè)數(shù)字是t，表示操作1、2、3；
如果t=1或者2，則接下來輸入數(shù)字x和y； (1 ≤ ??,?? ≤ ??)
如果t=3，則接下來輸入數(shù)字x1、y1、x2和y2； (1 ≤ ??1 ≤ ??2 ≤ ??, 1 ≤ ??1 ≤ ??2 ≤ ??)

輸出：
每個(gè)操作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]的變動(dòng)；
操作1和操作2比較簡單，直接操作數(shù)組即可；
操作3，樸素的想法是遍歷所有行、列，看看是否滿足，所有行或者所有列都被車覆蓋；這樣的復(fù)雜度復(fù)雜度是O(N)；
分析這個(gè)遍歷過程，當(dāng)我們想知道row[x1]到row[x2]這個(gè)區(qū)間，是否全部為1，其實(shí)可以轉(zhuǎn)化為前n項(xiàng)和之差：只要sum[x2] - sum[x1] = x2 - x1，就滿足條件；
于是問題轉(zhuǎn)化為，如何快速維護(hù)sum[i]？（row前i個(gè)元素的和）
這里偷個(gè)懶，用樹狀數(shù)組來支持。（就不展開介紹怎么用樹狀數(shù)組了，可以自己百度，有非常詳細(xì)介紹）

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

題目鏈接
題目大意：
有一個(gè)n個(gè)節(jié)點(diǎn)的有向圖，每個(gè)節(jié)點(diǎn)有一個(gè)數(shù)字a[i]；
現(xiàn)在可以選擇某個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開始沿著有向邊走，記錄每個(gè)訪問到的節(jié)點(diǎn)，并將這個(gè)訪問順序記錄下來；
現(xiàn)在想知道，如果需要訪問k個(gè)節(jié)點(diǎn)，訪問順序中的節(jié)點(diǎn)數(shù)字最大值的最小值是多少；

輸入：
整數(shù) ??, ?? and ?? (1≤??≤2?1e5, 0≤??≤2?1e5, 1≤??≤10e18)
接下來n個(gè)整數(shù) ???? (1≤????≤1e9)
接下來是m條行，每行有整數(shù) ?? and ?? ，表示u到v的邊(1≤??≠??≤??)
題目保證沒有指向自己的邊，也沒有多重邊；

輸出：
輸出k個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)字最大值的最小值是多少；
如果無法訪問到k個(gè)節(jié)點(diǎn)，則輸出-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個(gè)節(jié)點(diǎn)，那么就是尋找節(jié)點(diǎn)的最小值；
如果是需要訪問2個(gè)節(jié)點(diǎn)，那么問題就變得復(fù)雜，因?yàn)楣?jié)點(diǎn)2->3的解是比 節(jié)點(diǎn)1->4的解更優(yōu)；那么節(jié)點(diǎn)的最小值就失去了意義；
如果是想遍歷整個(gè)圖，并且在遍歷過程中去保留這個(gè)最大值的最小，無疑是非常復(fù)雜的；

那么換一種思想，假如我用二分來處理這個(gè)最大值，得到mid，如果a[i]<=mid認(rèn)為a[i]可以訪問，如果a[i]>mid則認(rèn)為節(jié)點(diǎn)不可方案；
題目變成在有向圖中，詢問遍歷步數(shù)最多是否能到k；

先不考慮環(huán)的情況，在一個(gè)有向圖中要去判斷遍歷步數(shù)最多情況，可以枚舉所有起點(diǎn)出發(fā)的情況，然后通過深度優(yōu)先搜索來記錄遍歷過程中的步數(shù)；
當(dāng)出現(xiàn)環(huán)的時(shí)候，我們可以把步數(shù)設(shè)置為一個(gè)很大的值，這樣也可以統(tǒng)一邏輯處理。

那么，問題又變成如何在有向圖中判斷環(huán)的存在？
當(dāng)我們在深度優(yōu)先遍歷的過程中，假如當(dāng)前點(diǎn)是u，下一個(gè)節(jié)點(diǎn)是v，此時(shí)有兩種情況，v是已經(jīng)訪問過，v還沒訪問過；
如果v沒有訪問過，那么就訪問v即可；
如果v已經(jīng)訪問過，此時(shí)又有兩種情況，如果v已經(jīng)訪問過，但是還在當(dāng)前的遞歸棧中，則證明v已經(jīng)可以和u構(gòu)成環(huán)；（step[u]=inf，inf表示一個(gè)很大值）
如果是v已經(jīng)訪問過，但是和當(dāng)前遞歸棧中沒有關(guān)系，怎么v只是普通訪問過的節(jié)點(diǎn)；（此時(shí)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個(gè)格子排成一行，每個(gè)格子有一個(gè)燈，燈有兩個(gè)方向：L和R，分別表示朝左和朝右；
當(dāng)一個(gè)燈朝左時(shí)，它能照亮其左邊的格子；（不包括燈所在格子）
當(dāng)一個(gè)燈朝右時(shí)，它能照亮其右邊的格子；（不包括燈所在格子）
現(xiàn)在允許選擇某個(gè)格子，交換該格子和右邊格子的燈，燈的朝向不變；（不能選擇最右邊的格子）
現(xiàn)在想知道，是否能夠讓每個(gè)格子都能被燈照亮；

輸入：
第一行，整數(shù)?? 表示t個(gè)樣例?? (1≤??≤10000)
每個(gè)樣例2行，第一行整數(shù) ?? (2≤??≤100000)
第二行n個(gè)字符'L' 和 'R'

輸出：
每個(gè)樣例一行，如果無解輸出-1，如果不需要交換輸出0，如果需要交換則輸出交換第x個(gè)格子；（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

題目解析：
樣例給了一個(gè)比較關(guān)鍵的數(shù)據(jù)，當(dāng)字符串出現(xiàn)RL，題目就必然存在解；
基于此我們繼續(xù)分析，當(dāng)字符串只有L或者只有R時(shí)，必然無解；
當(dāng)字符串存在L和R時(shí)，必然有解：因?yàn)榭偸悄苷业絃和R相交的位置，如果是R和L，則無需交換；如果是L和R，則進(jìn)行交換；

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;