Programming training 1

Before the order

     I feel that programming is a basic threshold for entering a large factory , Early in winter vacation , I have studied programming for one month , I will do some questions every Saturday , It should be done now , After that, I may do it irregularly , It seems that the problems of big factories come from leetcode Upper hard, Then I'll just brush it leetcode Of hard It's a question . Actually, I want to improve my python Language , So I used it python, But I still feel that I will use c++, I still prefer c++ Develop similar positions .

greedy

1、Circle of Monsters
http://codeforces.com/contest/1334/problem/C
A strange , The best result is that all explosion effects are used , Just enumerate where to start

from sys import stdin

t = int(stdin.buffer.readline())
for _ in range(t):
    n = int(stdin.buffer.readline())
    a = list()
    b = list()
    for _ in range(n):
        x, y = map(int, stdin.buffer.readline().split())
        a.append(x)
        b.append(y)
    Sum = 0
    res = float("inf")
    for i in range(n):
        d = (a[i] - b[(i - 1 + n) % n]) if a[i] >= b[(i - 1 + n) % n] else 0
        Sum += d

        res = min(res, a[i] - d)
        
    print(Sum + res)

2、 Standard Free2play
http://codeforces.com/problemset/problem/1238/C
It can be simulated directly , Every time I stand x At height , At this time, hide the platform at your height , take x-1 The status of the altitude platform changes

from sys import stdin

q = int(stdin.buffer.readline())
for _ in range(q):
    h, n = map(int, stdin.buffer.readline().split())
    a = list(map(int, stdin.buffer.readline().split()))
    a.append(0)
    ans = 0

    i = 1
    while i < n:
        if a[i] == a[i + 1] + 1: # Here, it is assumed to stand on the front height platform of the current coordinate each time 
            i = i + 2
        else:
            ans += 1
            i = i + 1
    print(ans)

3、School Marks
http://codeforces.com/problemset/problem/540/B
Left complement 1, The right to repair y

from sys import stdin
 
n, k, p, x, y = map(int, stdin.buffer.readline().split())
a = list(map(int, stdin.buffer.readline().split()))
a.sort()
 
Sum = 0
id = k
flag = False
for i in range(len(a)):
    Sum += a[i]
    if a[i] >= y and not flag:
        flag = True 
        id = i
 
if Sum + n - k > x or id > (n // 2):
    print(-1)
    exit()
 
res = list()
for i in range(min(n // 2 - id, n - k)):
    res.append(1)
    Sum += 1
 
for i in range(min(n // 2 - k + id + 1, n - k)):
    res.append(y)
    Sum += y
 
if Sum > x:
    print(-1)
else:
    print(*res)

Training 1

1、They Are Everywhere
https://codeforces.com/gym/312363/problem/E
Method ： Ruler method

from sys import stdin

n = int(stdin.readline())
s = stdin.readline().strip('\n')

flag = [0] * 256
num = len(set(s))

l, r = 0, -1
cnt = 0
MIN = float("inf")

while r < n:
    while cnt < num:
        r += 1
        if r >= n:
            break
        if flag[ord(s[r])] == 0:
            cnt += 1
            flag[ord(s[r])] = 1
        else:
            flag[ord(s[r])] += 1
    
    while cnt == num and l <= r:
        if flag[ord(s[l])] > 1:
            flag[ord(s[l])] -= 1
        else:
            cnt -= 1
            flag[ord(s[l])] = 0
        l += 1
    if cnt == num - 1:
        MIN = min(MIN, r - l + 2)
print(MIN)

2、As Fast As Possible
https://codeforces.com/gym/312363/problem/F

from sys import stdin
n, l, v1, v2, k = map(int, stdin.readline().split())
eps = 1e-6
def check(t):
    global n, l, v1, v2, k
    cnt = (n + k - 1) // k
    t1 = (l - v1 * t * 1.0) / (v2 - v1)
    return t1 * cnt + (v2 - v1) * t1 * (cnt - 1) / (v1 + v2) - t <= eps
L = l / v2
R = l / v1
while True:
    mid = (L + R) / 2.0
    if abs(R - L) <= eps:
        break
    if check(mid):
        R = mid
    else:
        L = mid
    
print('{:.10f}'.format(R))

3、White Lines
https://codeforces.com/gym/312363/problem/G


Reverse thinking , According to Haig , Find the rectangle that turns the black line white , Here is the two-dimensional difference , Two-dimensional prefix and can be done
One dimensional difference
Two dimensional difference

from sys import stdin

n, k = map(int, stdin.readline().split())
s = list()
for _ in range(n):
    s.append(stdin.readline().strip('\n'))

diff = [[0 for j in range(n + 2)] for i in range(n + 2)]
res = 0

for i in range(n):
    cnt, l, r = 0, 0, 0
    for j in range(n):
        if s[i][j] == 'B':
            cnt += 1
            if cnt == 1:
                l, r = j, j
            else:
                r = j
    if cnt == 0:
        res += 1
    else:
        if r - l + 1 > k:
            continue
        x1, y1 = max(0,i - k + 1), max(0, r - k + 1)
        x2, y2 = i, l
        diff[x1][y1] += 1
        diff[x1][y2+1] -= 1
        diff[x2+1][y1] -= 1
        diff[x2+1][y2+1] += 1

for i in range(n):
    cnt, l, r = 0, 0, 0
    for j in range(n):
        if s[j][i] == 'B':
            cnt += 1
            if cnt == 1:
                l, r = j, j
            else:
                r = j
    if cnt == 0:
        res += 1
    else:
        if r - l + 1 > k:
            continue
        x1, y1 = max(0,r - k + 1), max(0, i - k + 1)
        x2, y2 = l, i
        diff[x1][y1] += 1
        diff[x1][y2+1] -= 1
        diff[x2+1][y1] -= 1
        diff[x2+1][y2+1] += 1

MAX = -1
for i in range(n):
    for j in range(n):
        if i - 1 >= 0:
            diff[i][j] += diff[i - 1][j]
        if j - 1 >= 0:
            diff[i][j] += diff[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            diff[i][j] -= diff[i - 1][j - 1]
        MAX = max(MAX, diff[i][j])

print(MAX + res)

4、 Explain
• The prefix and （ Find the sum of intervals , Ask many times ）
• st surface （ Find the maximum of the interval , Ask many times ）,O(nlog(n))
• Line segment tree （ Find the maximum of the interval , Interval and , Modifiable value , Interval modification value ）
• Chairman tree （ Find the maximum of the interval , The maximum value of the historical modification process interval ）

Training 2

This time mainly focuses on the training of ruler taking method
1、Subsequence
A very common rule taking method , You need to pay attention to something when writing , A good way to write an algorithm is to get twice the result with half the effort

```cpp
//
//  main.cpp
//  test
//
//  Created by  Zhangjiangyu  on 2021/1/23.
//
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
const int inf = 0x3f3f3f3f;
LL a[N];
int main()
{
    
    int t;
    cin >> t;
    while(t--){
    
        int n;
        LL s;
        cin >> n >> s;
        for(int i = 0;i < n;++i){
    
            cin >> a[i];
        }
        int l = 0,r = 0;
        LL sum = 0;
        int ans = inf;
        while(true){
    
            while(r < n && sum < s){
    
                sum += a[r++];
            }
            if(sum < s)
                break;
            ans = min(ans, r - l);
            sum -= a[l++];
        }
        if(ans == inf){
    
            cout << 0 << endl;
            continue;
        }
        cout << ans << endl;
    }
    return 0;
}

2、Jessica’s Reading Problem
Very much like training 1 Of codeforce The topic , Here we should learn to use map mapping

//
// main.cpp
// test
//
// Created by  Zhangjiangyu  on 2021/1/23.
//
#include<iostream>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[N];
map<int,int>mp;
set<int>se;
int main()
{
    
    int p;
    cin >> p;
    for(int i = 0;i < p;++i){
    
        cin >> a[i];
        se.insert(a[i]);
    }
    int num = se.size();
    int l = 0,r = 0;
    int sum = 0;
    int ans = inf;
    while(true){
    
        while(r < p && sum < num){
    
            if(mp[a[r++]]++ == 0){
    
                sum++;
            }
        }
        if(sum < num)
            break;
        ans = min(ans, r - l);
        if(--mp[a[l++]] == 0){
    
            sum--;
        }
    }
    cout << ans << endl;
    return 0;
}

3、Bound Found
There are negative numbers here , Therefore, if the ruler takes the right hand and the pointer moves to the right, it will not guarantee a better answer
When prefix and post sort are used here , The right pointer will keep increasing when it turns right , The left pointer to the right will narrow the answer
notes ： Be sure to add a subscript as 0 Of , Otherwise, it would be wrong , Because in some cases, it is impossible to traverse

//
// main.cpp
// test
//
// Created by  Zhangjiangyu  on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
const LL inf = 0x3f3f3f3f3f3f3f3f;
typedef struct Node{
    
    LL sum;
    int id;
    friend bool operator < (const Node &a,const Node &b){
    
        return a.sum < b.sum;
    }
}Node;
Node node[N];
LL a[N];
int n,k;
LL t;
LL ABS(LL x){
    
    return x > 0? x:-x;
}
int main()
{
    
    while(cin >> n >> k){
    
        if(n == 0 && k == 0){
    
            break;
        }
        memset(node,0,sizeof(node));
        node[0].sum = 0;
        node[0].id = 0;
        for(int i = 1;i <= n;++i){
    
            cin >> a[i];
            node[i].sum = node[i - 1].sum + a[i];
            node[i].id = i;
        }
        sort(node,node + n + 1);
// for(int i = 0;i <= n;++i){
    
// cout << node[i].sum << " " << node[i].id << endl;
// }
        while(k--){
    
            cin >> t;
            int l = 0, r = 1;
            LL MIN = inf;
            int ansL = 0, ansR = 0;
            LL ans = 0;
            while(r <= n){
    
                LL sum = node[r].sum - node[l].sum;
                if(ABS(sum - t) < MIN){
    
                    MIN = ABS(sum - t);
                    ansL = node[l].id;
                    ans = sum;
                    ansR = node[r].id;
                }
                if(sum > t) l++;
                else if(sum < t) r++;
                else break;
                if(l == r){
    
                    r++;
                }
            }
            if(ansR < ansL){
    
                int tmp = ansR;
                ansR = ansL;
                ansL = tmp;
            }
            cout << ans << " " << ansL + 1 << " " << ansR << endl;
        }
        
    }
    return 0;
}

4、Sum of Consecutive Prime Numbers
Simply add a prime number to the sieve

//
// main.cpp
// test
//
// Created by  Zhangjiangyu  on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int MAXN=10010;
int prime[MAXN];
void getprime()
{
    
    memset(prime,0,sizeof(prime));
    //prime[0] Store <=MAXN The prime number of 
    int i,j;
    for(i=2;i<MAXN;++i)
    {
    
        if(!prime[i]) prime[++prime[0]]=i;
        for(j=1;j<=prime[0]&&prime[j]*i<=MAXN;++j)
        {
    
            prime[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int n;
int main()
{
    
    getprime();
    while(cin >> n){
    
        if(n == 0)
            break;
        int cnt = 0;
        int l = 1,r = 1;
        int sum = 0;
        while(true){
    
            while(r < prime[0] && sum < n){
    
                sum += prime[r++];
            }
            if(sum < n)
                break;
            if(sum == n){
    
                cnt++;
            }
            sum -= prime[l++];
        }
        cout << cnt << endl;
    }
    return 0;
}

5、Graveyard Design
This is also simple

//
// main.cpp
// test
//
// Created by  Zhangjiangyu  on 2021/1/23.
//
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
LL n;
typedef struct Node{
    
    int num;
    int base;
    friend bool operator < (const Node &a,const Node &b){
    
        return a.num > b.num;
    }
}Node;
Node node[100010];
int main()
{
    
    cin >> n;
    int l = 1, r = 1;
    int ansL = 0, ansR = 0;
    LL sum = 0;
    int num = 0;
    while(true){
    
        while(r <= (int)sqrt((double)n) && sum < n){
    
            sum += 1LL * r * r;
            r++;
        }
        if(sum < n)
            break;
        if(sum == n){
    
            node[num].num = r - l;
            node[num++].base = l;
        }
        sum -= 1LL * l * l;
        l++;
    }
    sort(node,node + num);
    cout << num << endl;
    for(int i = 0;i < num;++i){
    
        cout << node[i].num;
        for(int j = 0;j < node[i].num;++j){
    
            cout << " " << node[i].base + j;
        }
        cout << endl;
    }
    return 0;
}

Training 3

1、pearls in a Row
https://codeforces.com/problemset/problem/620/C
It can be simulated directly

from sys import stdin
n = int(stdin.buffer.readline())
a = list(map(int, stdin.buffer.readline().split()))
mp = dict()
l = 0
res = list()
for i in range(n):
    if a[i] in mp:
        res.append((l + 1, i + 1))
        mp.clear()
        l = i + 1
    else:
        mp[a[i]] = 1
if len(res) == 0:
    print(-1)
    exit()
print(len(res))
for i in range(len(res)):
    if i == len(res) - 1:
        print(res[i][0],n)
    else:
        print(res[i][0],res[i][1])

2、 Producing Snow
https://codeforces.com/problemset/problem/948/C
Simple use of one-dimensional difference , The dichotomy skill is too difficult

from sys import stdin
def binary_search(l, r, val):
    global prefix
    i, j = l, r
    while i < j:
        mid = (i + j) // 2
        ptr = prefix[mid]
        if ptr <= val:
            i = mid + 1
        else:
            j = mid
    return i
n = int(stdin.buffer.readline())
V = list(map(int, stdin.buffer.readline().split()))
T = list(map(int, stdin.buffer.readline().split()))
cnt = [0] * (n + 1)
res = [0] * (n + 1)
prefix = [0] * (n + 1)
for i in range(n):
    if i == 0:
        prefix[i] = T[i]
    else:
        prefix[i] = prefix[i - 1] + T[i]
for i in range(n):
    id = None
    if i == 0:
        id = binary_search(i, n - 1, V[i])
    else:
        id = binary_search(i, n - 1, V[i] + prefix[i - 1])
    if id == n - 1 and V[i] + prefix[i - 1] > prefix[id]:
        id += 1
    cnt[i] += 1
    cnt[id] -= 1
    if id == n:
        continue
    if i == 0:
        res[id] += (T[id] - prefix[id] + V[i])
    else:
        res[id] += (T[id] - prefix[id] + V[i] + prefix[i - 1])
for i in range(n):
    if i > 0:
        cnt[i] += cnt[i - 1]
    res[i] += cnt[i] * T[i]
for i in range(n):
    if i == n - 1:
        print(res[i])
    else:
        print(res[i], end = ' ')

3、 Salary Changing
https://codeforces.com/problemset/problem/1251/D

from sys import stdin
from operator import itemgetter, attrgetter
def check(salary, mid, s):
    cnt = 0
    for i in range(len(salary)):
        if salary[i][0] > mid:
            s -= salary[i][0]
            cnt += 1
        elif salary[i][0] <= mid and salary[i][1] >= mid:
            if cnt < (len(salary) + 1) // 2:
                s -= mid
                cnt += 1
            else:
                s -= salary[i][0]
        elif salary[i][1] < mid:
            s -= salary[i][0]
    if cnt >= (len(salary) + 1) // 2 and s >= 0:
        return True
    else:
        return False
t = int(stdin.buffer.readline())
for _ in range(t):
    salary = list()
    n, s = map(int, stdin.buffer.readline().split())
    ansL, ansR = 0x3f3f3f3f3f3f3f3f, -1
    for i in range(n):
        l, r = map(int, stdin.buffer.readline().split())
        ansL = min(ansL, l)
        ansR = max(ansR, r)
        salary.append((l, r))
    salary = sorted(salary, key=itemgetter(0), reverse=True)
    
    l = ansL
    r = ansR
    ans = None
    while l <= r:    
        mid = (l + r) // 2  
        if check(salary, mid, s):
            ans = mid        
            l = mid + 1    
        else:        
            r = mid - 1
    print(ans)

4、 Divide and conquer Two points The segment tree can also http://codeforces.com/contest/768/problem/B

from sys import stdin
import math
# From here calnum Make a table to judge num[n] = n
# def calnum(n):
# if n == 0 or n == 1:
# return n
# return 2 * calnum(n // 2) + calnum(n % 2)
#python Of math.log The function is imprecise ...
def Log(n):
    for i in range(52):
        num = int(math.pow(2, i))
        if n < num:
            return i - 1
def dfs(n, nl, nr, l, r):
    if l <= nl and r >= nr:
        return n
    mid = (nl + nr) // 2
    num = 0
    if mid >= l and mid <= r:
        num += n % 2
    if l < mid:
        num += dfs(n // 2, nl, mid - 1, l, r)
    if r > mid:
        num += dfs(n // 2, mid + 1, nr, l, r)
    return num
n, l, r = map(int, stdin.buffer.readline().split())
if n == 0:
    print(0)
    exit()
num = Log(n)
nl, nr = 1, int(math.pow(2, num + 1)) - 1
ans = dfs(n, nl, nr, l, r)
print(ans)

5、 A good problem of line segment tree http://codeforces.com/problemset/problem/914/D
Pay special attention to pruning here

//
//  main.cpp
//  test
//
//  Created by  Zhangjiangyu  on 2021/2/6.
//
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 5 * 1e5 + 5;
int n, q;
LL a[N];
LL tree[N << 2];
LL gcd(LL a, LL b){
    
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
void build(int root, int l, int r){
    
    if(l == r){
    
        tree[root] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(root * 2, l, mid);
    build(root * 2 + 1, mid + 1, r);
    tree[root] = gcd(tree[root * 2], tree[root * 2 + 1]);
    return ;
}
void update(int root, int l, int r, int id, LL val){
    
    if(l == r){
    
        tree[root] = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if(id <= mid)
        update(root * 2, l, mid, id, val);
    if(id > mid)
        update(root * 2 + 1, mid + 1, r, id, val);
    tree[root] = gcd(tree[root * 2], tree[root * 2 + 1]);
    return ;
}
int cnt = 0;
void query(int root, int l,int r, int ql, int qr, LL val){
    
    if(cnt > 1) return ;
    int mid = (l + r) >> 1;
    if(l >= ql && r <= qr){
    
        if(tree[root] % val == 0){
    
            return ;
        }else{
    
            if(l == r){
    
                cnt += 1;
                return ;
            }
            LL lt = tree[root * 2];
            LL rt = tree[root * 2 + 1];
            if(((lt % val) && (rt % val)) || cnt){
    
                cnt = 2;
                return ;
            }
            // Here's the key 
            if(lt % val)
                query(root * 2, l, mid, ql, qr, val);
            if(rt % val)
                query(root * 2 + 1, mid + 1, r, ql, qr, val);
            return ;
        }
    }
    if(ql <= mid)
        query(root * 2, l, mid, ql, qr, val);
    if(qr > mid)
        query(root * 2 + 1, mid + 1, r, ql, qr, val);
    return ;
}
int main()
{
    
    scanf("%d",&n);
    for(int i = 1;i <= n;++i){
    
        scanf("%lld", &a[i]);
    }
    build(1,1,n);
    scanf("%d",&q);
    for(int i = 0;i < q;++i){
    
        int num;
        scanf("%d",&num);
        if(num == 2){
    
            int x;
            LL y;
            scanf("%d %lld",&x, &y);
            update(1, 1, n, x, y);
        }else{
    
            int x,y;
            LL z;
            scanf("%d %d %lld", &x, &y, &z);
            cnt = 0;
            query(1, 1, n, x, y, z);
            if(cnt <= 1){
    
                cout << "YES" << endl;
            }else{
    
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

The first question of Ali's spring moves

Now divide the collocation of each line into ABA and ABC Two cases
When the type of each line is determined , The situation in the second line is determined , One layer at a time
When the first act ABA when , On the next line, there are three kinds of ABA Situation and two ABC situation
When the first act ABC when , The next line is that there are two kinds of ABA Situation and two ABC situation
for example ：
121 The next line corresponds to 212,313,232,231,312
123 The next line corresponds to 212,232,231,312
therefore ：
When the first i Behavior ABA when , Number of all cases : x[i] = 3 * x[i - 1] + 2 * y[i - 1]
When the first i Behavior ABC when , Number of all cases : y[i] = 2 * x[i - 1] + 2 * y[i - 1]

class Solution {
    
public: 
    typedef long long LL;
    const LL mod = 1e9 + 7;
    LL x[5005];
    LL y[5005];
    int numOfWays(int n) {
    
        x[1] = 6;
        y[1] = 6;
        for(int i = 2;i <= n;++i){
    
            x[i] = (3LL * x[i - 1] % mod + 2LL * y[i - 1] % mod) % mod;
            y[i] = (2LL * x[i - 1] % mod + 2LL * y[i - 1] % mod) % mod;
        }
        return (x[n] + y[n]) % mod;
    }
};