A. Rectangle Arrangement
最长和最高相加乘二即为答案
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e2+7, mod=1e9+7;
void solve(){
int n;
cin>>n;
int mx,my;
mx=my=-1;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
mx=max(mx,x);
my=max(my,y);
}
cout<<(mx+my)*2<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Stalin Sort
$n\leq2000$ 直接 $O(n^2)$ 查找当前位后有几个比他大的，都删去
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>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
int a[N];
void solve(){
int ans=INT_MAX;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int tmp=i-1;
for(int j=i+1;j<=n;j++){
if(a[j]>a[i])tmp++;
}
ans=min(tmp,ans);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Add Zeros
观察题目发现 $a_i = |a| + 1 - i$ 中的 $|a|$ 并不会改变，那么只需要考虑当前数组长度即可，将所有 $i$ 对应的 $|a|$ 找到，相同的存入同一数组，用 $dfs$ 暴力查找即可
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
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;
ll n;
ll a[N];
ll ans;
map<ll,vector<ll>>vis;
set<ll> visited;
void dfs(ll now){
if (visited.count(now)) return;
visited.insert(now);
ans=max(ans,now);
if(vis.find(now) != vis.end()){
for(ll x:vis[now]){
dfs(now+x-1);
}
}
}
void solve(){
ans=-1;
vis.clear();
visited.clear();
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
vis[a[i] + i - 1].push_back(i);
}
dfs(n);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D1. The Endspeaker (Easy Version)
多种操作完成某个目标的最小代价，可以考虑 DP
设 $dp_{i,j}$ 为对于前 $i$ 个数组，使用第 $j$ 总操作的最小代价
易得转移方程 $dp[i][j]= \text{min}{dp[p][k]}+m-j,\text{sum}[p,i]\le b[j],1\le k\le j,1\le p\le i$
显然可以将第一维优化掉，我们只需要通过当前操作能到达 $n$ 即可，可以用后面的操作覆盖前面的
现在的优化难点在于 $p$ 如何确定
其实转移过程就是通过一个滑动窗口来进行实时更新，我们可以用双指针来完成这个操作
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
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;
const int inf=1e9;
int n,m;
ll a[N],b[N],s[N],mx;
void solve(){
cin>>n>>m;
mx=-1;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
mx=max(mx,a[i]);
}
for(int i=1;i<=m;i++)cin>>b[i];
if(mx>b[1]){
cout<<"-1\n";
return;
}
vector<int> dp(n+10,inf);
dp[0]=0;
for(int i=1;i<=m;i++){
int l=0,r=1;
while(r<=n){
while(l<r&&s[r]-s[l]>b[i])l++;
if(l<r)dp[r]=min(dp[r],dp[l]+m-i);
r++;
}
}
cout<<dp[n]<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|