更新至E,D…
开学了,只水了签到。
题E:
题意:给定一个 n∗m 的矩形, 求是否能分成若干个不连续的正方形。
解:欧几里得的几何解释。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #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(){ int n; cin >> n; while(n--) solve(); return 0; }
|
题D:
题意:长度的序列 a,问有多少子区间 [l,r],满足区间中的每一个数(原序列第 i 个数,l≤i≤r)都不是区间中第 i−l+1 小的数(n≤5000)。
解:数据量比较小,直接枚举 dp[i][j], 第二维表示差分前缀和,我们用来表示一个第 i 个数是否在某个区间内不满足题目要求。首先我们右移 r 使得 a[i] 是区间最小,此时 dp[i][l]++,dp[i][r+1]−−。随后移动左边间 j(1≤j≤i−1), 倘若 a[j]>a[i], 那么我们就可以将 a[r+1] 加入到区间这时候 i 就是区间第二大,以此类推…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #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; }
|