牛客暑期多校训练营9

更新至E,D…
开学了,只水了签到。

题E：

题意：给定一个 $n*m$ 的矩形， 求是否能分成若干个不连续的正方形。

解：欧几里得的几何解释。

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
struct P{
    int xx, yy, l;
}ans[N];
void solve(){
    int n, m, t = 0; cin >> n >> m;
    int x = 0, y = 0;
    while(x < n && y < m){
        int a = n - x, b = m - y;
        if(a == b) {ans[++ t] = {x, y, a}; break;}
        if(a < b){
            ans[++ t] = {x, y, a};
            y += a; 
        }else {
            ans[++ t] = {x, y, b};
            x += b;
        }
    }
    cout << "YES\n";
    cout << t << '\n';
    for(int i = 1; i <= t; ++ i) 
        cout << ans[i].xx << ' ' << ans[i].yy << ' ' << ans[i].l << '\n';
}
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}

题D:

题意：长度的序列 $a$，问有多少子区间 $[l,r]$，满足区间中的每一个数(原序列第 $i$ 个数，$l\le i\le r$)都不是区间中第 $i-l+1$ 小的数$(n \le 5000)$。

解：数据量比较小，直接枚举 $dp[i][j]$, 第二维表示差分前缀和，我们用来表示一个第 $i$ 个数是否在某个区间内不满足题目要求。首先我们右移 $r$ 使得 $a[i]$ 是区间最小，此时 $dp[i][l]++, dp[i][r+1]–$。随后移动左边间 $j(1\le j \le i - 1)$, 倘若 $a[j] > a[i]$, 那么我们就可以将 $a[r+1]$ 加入到区间这时候 $i$ 就是区间第二大，以此类推…

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], dp[N][N];
void solve(){
    int n, ans = 0; cin >> n;
    for(int i = 1; i <= n; ++ i) for(int j = 1; j <= n; ++ j) dp[i][j] = 0;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    for(int i = 1; i <= n; ++ i){
        int l = i, r = i;
        while(r < n && a[r + 1] > a[i]) r ++;
        dp[i][l] ++, dp[i][r + 1] --;
        for(int j = i - 1; j; -- j){
            if(a[j] > a[i]){
                l = r = r + 1;
                while(r < n && a[r + 1] > a[i]) r ++;
            }
            if(l <= n) dp[j][l] ++, dp[j][r + 1] --;
        }
    }
    for(int i = 1; i <= n; ++ i){
        int s = 0;
        for(int j = i; j <= n; ++ j){
            s += dp[i][j];
            if(s == 0) ans ++;
        }
    }
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}