牛客暑期多校训练营9
发表于:2023-08-27 | 分类: 思维
字数统计: 720 | 阅读时长: 3分钟 | 阅读量:

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

题E:

题意:给定一个 nmn*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(){
//ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
while(n--) solve();
return 0;
}

题D:

题意:长度的序列 aa,问有多少子区间 [l,r][l,r],满足区间中的每一个数(原序列第 ii 个数,lirl\le i\le r)都不是区间中第 il+1i-l+1 小的数(n5000)(n \le 5000)

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

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;
}
上一篇:
快速傅里叶变换
下一篇:
牛客暑期多校训练营10