A. Most Unstable Array
题意：给出n，m。 n表示有n个数，m表示这n个数的总和。每个数都是正整数。 现在你可以随便把m拆成n个数，要保证拆完后的序列，相邻差的绝对值和要最大。
解：
首先特判 n=1 ，答案一定为0，只有一个数嘛。n=2 的时候，2个数，答案要最大，一定是[m,0].这样绝对值差是m，即最大值。
当n>=3时 ，我们可以发现， [0,m,0]这样去构造，答案是2*m ，即最大值。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
ll t;
ll n,m;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
if(n<=2)
{
if(n==1)
{
printf("0\n");
}
else
{
printf("%lld\n",m);
}
}
else
{
printf("%lld\n",m*2ll);
}
}
return 0;
}
B. Two Arrays And Swaps
题意：给出2个数组a，b。每次你可以任意选择2个值i，j。可以交换a[i],b[j]的值，最多交换次数为k，问你交换结束要使得a数组的和尽可能大。
解：
既然可以随便选来交换，我们可以把b数组从大到小排序，a数组从小到大排序，用b大的值去把a小的值换掉，这样最贪。但是要注意一点，如果b数组小于a数组的值，就不要去交换了，不然就亏了。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
const int N=100;
int t;
int n,k;
int a[N];
int b[N];
bool cmp(int _,int __)
{
return _>__;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
sort(a,a+n);
sort(b,b+n,cmp);
for(int i=0;i<k;i++)
{
if(b[i]>a[i])
{
a[i]=b[i];
}
}
int ans=0;
for(int i=0;i<n;i++)
{
ans+=a[i];
}
printf("%d\n",ans);
}
return 0;
}
C. Board Moves
题意：给出一个n*n的矩阵，n保证是奇数。矩阵每个位置都有一个数，从1开始到n×n。 现在一个数可以移动到另一个格子里，移动的方向有8个。问你最小移动次数，是的所有数字在同一个格子里。
解：
由于n是奇数，我们可以发现，中心点可以确定的，我们最外圈的每一个数字，到中心点的距离都是一样的，次外圈也是一个道理。所以我们只要算出外圈的个数，还有距离中心点距离，乘起来就是这一圈所有数字移动次数，次外圈也同理，一圈一圈缩小，直到就剩一个中心点。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
ll t;
ll n;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
ll zhi=n/2;
ll k=n/2;//总共有多少圈
ll ans=0;
for(ll i=0;i<zhi;i++)
{
ll wai=n*4-4;//算一圈有几个，四条边*4，4个点重复算-4
//cout<<wai<<endl;
ans+=wai*k;
n-=2;//没缩小一圈，边长-2
k--;//圈数--
}
printf("%lld\n",ans);
}
return 0;
}
D. Constructing the Array
题意：给出一个长度是n的全0数组，每次有一个区间，这个区间是由这个数组最长连续0的序列的左右边界（从左往右的顺序，相当于如果左边和右边有相同长度的，我们先选着左边的区间）。例如第一次，最长连续全0序列就是1-n，即 L=1，R=n。 具体看样例解释。
解：
这题主要是 如何找最长连续0的序列，如果你能很快找到，那么就很简单了。 如果暴力找，复杂度是不行的，TLE。 由于每次加入一个数，区间就会被拆分，我们要保存这个区间信息，但是又要最长。我们就想到优先队列，优先队列里存放区间。优先队列的排序规则就是，先按照区间长度排序，再按照L小的来。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
const int N=2e5+100;
int t;
int n;
int a[N];
struct cmp
{
template <typename T,typename U>
bool operator()(T const &left,U const &right)
{
if(left.second-left.first!=right.second-right.first)
{
return (left.second-left.first)<(right.second-right.first);
}
else
{
return left.first>right.first;
}
}
};
priority_queue<pair<int,int>, vector<pair<int,int>> ,cmp>pq;
int main()
{
scanf("%d",&t);
while(t--)
{
while(!pq.empty())pq.pop();
scanf("%d",&n);
int c=0;
int l=1;
int r=n;
int mid=(l+r)>>1;
a[mid]=1;
pq.push(make_pair(l,mid-1));
pq.push(make_pair(mid+1,r));
for(int i=2;i<=n;i++)
{
pair<int,int> k;
k=pq.top();
pq.pop();
l=k.first;
r=k.second;
int mid=(l+r)>>1;
a[mid]=i;
pq.push(make_pair(l,mid-1));
pq.push(make_pair(mid+1,r));
}
for(int i=1;i<=n;i++)
{
printf("%d%c",a[i]," \n"[i==n]);
}
}
return 0;
}
E题没时间看了，只好赛后补了
E. K-periodic Garland
题意：给出一个01串，每个1之间的距离为k，你有一个操作，可以把0变成1，1变成0.现在问你最少改变次数，使得每个1之间的距离都为k。
解：
dp的思路，设 sum[i]为前i个数1的个数（前缀和）
dp[i][0]表示第i个位置是0，前i个数的改变次数
dp[i][1]表示第i个位置是1，前i个数的改变次数
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+(a[i]==1)
这个位置是0的话，就前一个的2个状态取min就好了，如果这个位置是1，说明要改变一次，就+1.
dp[i][1]=min(dp[i-k][1],sum[i-1]-sum[i-k],sum[i-1])+(a[i]==0)
由于相差k，我们要看dp[i-k][1]的值是多少，并且i-k到i-1中间不有1，如果有1，就要变成0，所以我们sum数组就要用了，把区间1的个数算出来，有几个1就改几次。 sum[i-1]的意思就是，前面可能会出现全1的情况。
AC代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
const int N=1e6+100;
int t;
int n,k;
int a[N];
int dp[N][2]; //dp[i][0]表示第i位置是0前面合法的数量
//dp[i][1]表示第i位置是1前面合法的数量
int sum[N];//sum[i]表示 统计前缀1的个数
int main()
{
scanf("%d",&t);
while(t--)
{
//memset(dp,0,sizeof(dp));
//memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%1d",&a[i]);
}
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+(a[i]==1);
}
for(int i=1;i<=n;i++)
{
int p=max(0,i-k);
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+(a[i]==1);
dp[i][1]=min(dp[p][1]+sum[i-1]-sum[p],sum[i-1])+(a[i]==0);
}
// for(int i=1;i<=n;i++)
// {
// printf("dp[%d][0]: %d dp[%d][1]: %d\n",i,dp[i][0],i,dp[i][1]);
// }
printf("%d\n",min(dp[n][1],dp[n][0]));
}
return 0;
}
版权声明：本文为weixin_43913594原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。