A. Most Unstable Array
题意： (t) 组数据 ((1 leq t leq 10^4)) ，每组数据给出整数 (n) 和 (m~(1 leq n,m leq 10^9)) ，现要求把 (m) 划分成 (n) 个大于等于 (0) 的数之和，设这 (n) 个数构成数组 (a)，求
的最大值
分析： 因为要求划分的数都大于等于 (0) ，所以最好的划分就是一个大于 (0) 的数左右两边都是 (0) ，这样的划分就等价于 (0,m,0,...,0) ，所以
- (n=1,ans=0)
- (n=2,ans=m)
- (n>2,ans=2m)
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
if(n==1) cout<<0<<endl;
else if(n==2) cout<<m<<endl;
else cout<<2*m<<endl;
}
}
B. Two Arrays And Swaps
题意： (t~(1 leq t leq 200)) 组测试数据，每组数据先有整数 (n) 和 (k~(1 leq n leq 30;0 leq k leq n)) ，然后给出大小为 (n) 的整数数组 (a) 和 (b~(1 leq a_i,b_i leq 30))，现在最多有 (k) 次机会互换 数组 (a) 和 (b) 内的任意元素，使得最后 (a) 的元素和最大，求这个最大元素和
分析： 模拟
代码：
#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
const int N = 100;
P s[N];
bool cmp(P a,P b)
{
if(a.first==b.first) return a.second<b.second;
return a.first>b.first;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n,k;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1,x;i<=n;i++) cin>>x,s[i]=P(x,1);
for(int i=n+1,x;i<=n+n;i++) cin>>x,s[i]=P(x,2);
sort(s+1,s+n+n+1,cmp);
int sum=0,cnt=1;
for(int i=1;i<=n;i++)
{
if(s[cnt].second==1) sum+=s[cnt].first,cnt++;
else if(k){
sum+=s[cnt].first,cnt++,k--;
}
else{
while(s[cnt].second==2) cnt++;
sum+=s[cnt].first,cnt++;
}
}
cout<<sum<<endl;
}
}
C. Board Moves
题意： 给定一个 (n imes n~(n in odd;1 leq n leq 5 imes 10^5)) 的矩阵，每个点上有个数字，求把所有数字集中到一个点上的最小花费，一个点上的数字移动到相邻的点上的花费为 (1) (相邻的定义为周围八个位置)
分析： (n) 是奇数，显然把所有点移到矩阵的中心花费是最小的，根据相邻的定义，从中心点周围第一圈花费为 (1) ，第二圈花费为 (2) ，... 打个表就可以了
代码：
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 5E5+10;
ull a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
a[1]=0;
ull cnt=1;
for(int i=3;i<N;i+=2) a[i]=a[i-2]+((i-2)*4+4)*cnt,cnt++;
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<a[n]<<endl;
}
}
D. Constructing the Array
题意： 给定大小为 (n~(1 leq n leq 2 cdot 10^5)) 的数组 s ，初始全为 (0) ，现在要求填 (n) 次数字，第 (i) 填 (i) ，每一次都需要在数组中找到最长的 (0) 段(如果有多个取最左边的)，设它的长度为 (m)，区间为 ([l,r]) 若
- (m in odd，则s[frac{l+r}{2}]=i;)
- (m in even，则s[frac{l+r-1}{2}]=i;)
输出最后的数组
分析： 根据题目的优先级建立优先队列模拟填写过程
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
int a[N];
struct node{
int l,r;
bool operator<(const node& a)const{
if(r-l!=a.r-a.l) return r-l<a.r-a.l;
else return l>a.l;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
priority_queue<node>q;
q.push((node){1,n});
int cnt=1;
while(!q.empty())
{
node top=q.top();q.pop();
int l=top.l,r=top.r;
if((r-l+1)%2==1)
{
int m=(r+l)/2;
a[m]=cnt;
if(r-l>1)
q.push((node){l,m-1}),
q.push((node){m+1,r});
}
else
{
int m=(r+l-1)/2;
a[m]=cnt;
if(l<m) q.push((node){l,m-1});
if(m<r) q.push((node){m+1,r});
}
cnt++;
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<endl;
}
}
E. K-periodic Garland
题意： (t~(1 leq t leq 25000)) 组测试数据，每组数据先给出 (n) 和 (k~(1 leq n leq 10^6;1 leq k leq n))，然后给出长度为 (n) 的 (01) 序列代表 (n) 盏灯，(0) 表示关，(1) 表示开，每次可以选择一盏灯改变它的状态，问最少需要操作多少次使得所有 (1) 之间的间距为 k
分析： 设 (dp[i]) 表示第 (i) 位为 (1)，([1,i]) 满足条件的情况下需要最少的操作步数，则转移方程不难给出，设 (sum[i]) 为前 (i) 盏灯原状态为 (1) 的数量
if(第i盏灯原状态为1){
if(i<=k) dp[i]=sum[i-1]; //前面不足k盏灯，所以必须全为0
else{
dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]);
//否则，第i-k盏灯必须为1，且开区间(i-k,i)之间的状态必须都为0
dp[i]=min(dp[i],sum[i-1]);
//或者前i-1个都为0，取较小代价
}
}
else{ //下述同理，唯一区别就是第i盏灯原状态为0，代价+1
if(i<=k) dp[i]=sum[i-1]+1;
else{
dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]+1);
dp[i]=min(dp[i],sum[i-1]+1);
}
}
但是这样还不够，我们从前往后求的 (dp[i]) 是基于第 (i) 点状态为 (1) 的情况下区间 ([1,i]) 的最优解，后面的怎么管?——其实可以在 dp 的时候顺便枚举以当前点为最后一个状态 (1) 时的最小代价，即
f=min(f,dp[i]+sum[n]-sum[i]); //第i个点之后的状态1全部置为0
上面考虑的是至少有一个状态 (1) 的情况，所以最后再与全部置 (0)，代价即 (sum[n]) 作比较取最小值即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1E6+10;
int dp[N],sum[N];
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n,k;
cin>>t;
while(t--)
{
cin>>n>>k>>s;
for(int i=1;i<=n;i++)
if(s[i-1]=='1') sum[i]=1;
else sum[i]=0;
for(int i=2;i<=n;i++) sum[i]+=sum[i-1];
for(int i=0;i<=n;i++) dp[i]=0;
int f=1000000;
for(int i=1;i<=n;i++)
{
if(s[i-1]=='1')
{
if(i-k>0){
dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]);
dp[i]=min(dp[i],sum[i-1]);
}
else{
dp[i]=sum[i-1];
}
}
else
{
if(i-k>0){
dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]+1);
dp[i]=min(dp[i],sum[i-1]+1);
}
else{
dp[i]=sum[i-1]+1;
}
}
f=min(f,dp[i]+sum[n]-sum[i]);
}
cout<<min(dp[n],min(f,sum[n]))<<endl;
}
}
F. Decreasing Heights
题意： (t~(1 leq t leq 100)) 组测试数据，每组数据先给出 (n) 和 (m~(1 leq n,m leq 100))，然后给出 (n imes m) 的整数矩阵，花费一次代价你可以把矩阵内任意点上的元素减 (1)，现在要求从点 ((1,1)) 开始走，只能往下或者往右，且下一步的点上的元素要比上一步的点上的元素恰好大 (1)，走到 ((n,m)) 的最小代价(保证有解)
分析： 最小代价，所以本着尽量少改变的原则，至少有一个点上的元素是不变的，那么我们枚举这个点然后递推一遍求代价就可以了
代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 100+10;
#define ll long long
#define INF 1E18
ll dp[N][N],ans;
ll s[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
rep(i,1,n)rep(j,1,m)
{
cin>>s[i][j];
}
ans=INF;
rep(i,1,n)rep(j,1,m)
{
if(s[1][1]<s[i][j]-(i-1)-(j-1)) continue;
//这个点与起点距离通过操作无法满足1的等差条件
rep(x,0,n)rep(y,0,m) dp[x][y]=INF;
dp[1][1]=s[1][1]-(s[i][j]-(i-1)-(j-1));
rep(x,1,n)rep(y,1,m)
{
if(x==1&&y==1) continue;
ll res=s[i][j]+(x-i)+(y-j);
if(s[x][y]<res) continue;
dp[x][y]=min(dp[x-1][y],dp[x][y-1])+s[x][y]-res;
}
ans=min(ans,dp[n][m]);
}
cout<<ans<<endl;
}
}