本期封面原图 画师礼島れいあ
太魔幻了，四场比赛，从晋级赛打成晋级赛了，一路掉到绿啊，真给我干emo了
A. Rectangle Arrangement
题意
就是说有n个章，长宽知道，随意位置在纸上各盖一次，求黑色部分最小周长
思路
一开始看错成面积了，所以就写了个叠起来，事实上这么写也是周长最小的方案
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n;
scanf("%d",&n);
vector<pii> a(n);
int G[114][514];
memset(G,0,sizeof(G));
for (int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
for(int j=1;j<=x;j++)
{
for(int k=1;k<=y;k++)
{
G[j][k]++;
}
}
}
int ans=0;
for(int i=1;i<=100;i++)
{
for(int j=1;j<=500;j++)
{
if(G[i][j]>0)
{
if(G[i-1][j]==0)
{
ans++;
}
if(G[i+1][j]==0)
{
ans++;
}
if(G[i][j-1]==0)
{
ans++;
}
if(G[i][j+1]==0)
{
ans++;
}
}
}
}
printf("%d\n",ans);
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
B. Stalin Sort
题意
定义一种排列，只要一个数比前面的数小就直接强行删掉。
再定义一种脆弱数组，就是说对任意子序列任意使用这种排列可以使整个数组递减。
最小删掉几个数可以使原数组变为脆弱数组。
思路
题意很长，看起来很难受，但是贪心起来还是很简单
以为数据范围不大，所以我们可以找以每一个数为开头需要删掉多少个，然后加上自己的位置去比较就行
他说他叫Stalin排序，那我们也Stalin起来，都杀掉，最后只要剩下两个，是递减就行了对吧，那么我在前期处理的时候，假设以第i个数为开头，只要他是最大的，那我一定可以通过从他到倒数第二个用一次Stalin排序变成递减序列，所以他后面比他大的我要全部提前删掉
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//numbers: 3 6 4 9 2 5 2
//i-th big: 3 6 4 7 1 5 1
//org_posi: 1 2 3 4 5 6 7
void solve()
{
int n;
scanf("%d",&n);
int a[n+1];
a[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
ll ans=1e9;
for(int i=1;i<=n;i++)
{
ll sum=i-1;
for(int j=i+1;j<=n;j++)
{
if(a[j]>a[i]) sum++;
}
ans=min(ans,sum);
}
printf("%lld\n",ans);
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
C. Add Zeros
题意
给你一个最初包含 n n n 个整数的数组 a a a 。在一次操作中，您必须执行以下操作：
- 选择一个位置 i i i ，要求 1 < i ≤ ∣ a ∣ 1 < i \le |a| 1<i≤∣a∣ 且 a i = ∣ a ∣ + 1 − i a_i = |a| + 1 - i ai=∣a∣+1−i ，其中 ∣ a ∣ |a| ∣a∣ 是数组的当前大小。
- 在 a a a 的末尾添加 i − 1 i - 1 i−1 个零。
在多次执行此操作后，数组 a a a 的最大可能长度是多少？
思路
开个map存一下每个点都要求什么长度才可以变，然后直接dfs就行
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=3e5+5;
ll a[N];
ll n;
map<ll,bool> visited;
map<ll,vector<ll>> mp;
ll ans=0;
void dfs(ll p)
{
visited[p]=1;
// printf("%lld\n",p);
ans=max(ans,p);
for(auto x:mp[p-n])
{
if(!visited[p+x-1])
{
dfs(p+x-1);
}
}
}
void solve()
{
mp.clear();
visited.clear();
ans=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld", &a[i]);
a[i]-=(n-i+1);
if(i>1)
{
mp[a[i]].push_back(i);
}
}
dfs(n);
printf("%lld\n",ans);
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
D1. The Endspeaker (Easy Version)
题意
给你一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b （ b i > b i + 1 b_i > b_{i+1} bi>bi+1 对于所有 1 ≤ i < m 1 \le i < m 1≤i<m ）。最初， k k k 的值是 1 1 1 。您的目标是通过重复执行这两种操作中的一种，使数组 a a a 为空：
- 类型 1 1 1 - 如果 k k k 的值小于 m m m ，并且数组 a a a 不为空，则可以将 k k k 的值增加 1 1 1 。这不会产生任何费用。
- 类型 2 2 2 - 从数组 a a a 中移除一个非空的前缀，使得其总和不超过 b k b_k bk 。此操作需要花费 m − k m - k m−k 。
你需要最小化操作的总成本，使数组 a a a 为空。如果无法通过任何操作序列实现，则输出 − 1 -1 −1 。否则，输出操作的最小总成本。
思路
考虑dp，
d
p
i
,
j
dp_{i,j}
dpi,j表示指针指向b中的第j个数时删掉a前面i个数的最小总成本，有点像一个完全背包，因为一个b可以用好几次，那就是dp[i][j]=min(dp[i][j],dp[比i大的所有值][j]+m-j)
但是现在这个比i大的所有值有个要求，就是你能删对吧，所以需要前缀和维护区间和，然后二分查找第一个能删的
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
vector<int> a(n+1),b(m+1);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
if(maxOf(a)>maxOf(b))
{
puts("-1");
return;
}
ll sum[n+1];
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
vector dp(n+1,vector<ll>(m+1,1e18));
vector mn(n+1,vector<ll>(m+1,1e18));
fill(dp[0].begin(),dp[0].end(),0);
fill(mn[0].begin(),mn[0].end(),0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]>b[j])
continue;
int l=1,r=i;
while(l<r)
{
int mid=(l+r)/2;
if(sum[i]-sum[mid-1]<=b[j])
r=mid;
else
l=mid+1;
}
dp[i][j]=min(dp[i][j],mn[l-1][j]+m-j);
}
for(int j=1;j<=m;j++)
mn[i][j]=min(mn[i][j-1],dp[i][j]);
}
ll ans=1e18;
for(int i=1;i<=m;i++)
ans=min(ans,dp[n][i]);
printf("%lld\n",ans==1e18?-1:ans);
}
int main()
{
int T=1;