codeforces round 687 div.2 题解
反思之前，确实太水了，不想再水下去了，菜鸡不能永远是菜鸡，以后cf坚持写题解，加油干呗
A:给你一个n*m大的矩阵，对于矩阵中任何一点，每一步，可以向上下左右走或者停在原地，问所有点要走到给定的(r,c)最少多少步？
题解：就画一个图，我们先走x方向然后走y方向，然后在x方向上，取max(r-1,n-r),表示x方向上最多走多少步，在y方向上，取max(c-1,m-c),然后两个max相加即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,r,c;
cin>>n>>m>>r>>c;
cout<<max(r-1,n-r)+max(c-1,m-c)<<endl;
}
return 0;
}B:给你n个数ci(1<=ci<=100)，每次可以把其中k个数变成同一个数，问最少多少次能够把所有数变成一样的。
题解：ci取值非常小，直接枚举把所有数变成某个ci（从1到100），再从头开始枚举数组，需要多少步能把所有数变成一样的，10^7可以过的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int c[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
int ans=(int)1e9;
int res;
for(int i=1;i<=100;i++)
{
res=0;
for(int j=1;j<=n;)
{
if(c[j]!=i)
{
res++;
j+=k;
}
else
{
j++;
}
}
ans=min(ans,res);
}
cout<<ans<<endl;
}
return 0;
}C:给你长度为n（10^5）的字符串a1-an（ai为0或1,1表示该位置有柱子，0没有）,给你一个p，一个k,代表从第p个开始跳，每次跳到该位置的下k个位置,即第p+k,p+2k...,再给你一个x,y代表删掉最开头那个字符的花费，x代表把某个位置的0改变成1的花费，问要跳出最后一个位置最少需要多少步。
题解：我们用类似dp的思想，如果a[i]=='0',i位置开始总比i+k开始要多变一次,dp[i]=dp[i+k]+(a[i]=='0').
现在我们求出了从每个位置跳到末尾要变多少次。然后遍历所有a[i]，求从a[i]开始的花费，同时更新最小值。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
ll dp[N];
char a[N];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
int n,p,k;
cin>>n>>p>>k;
cin>>a+1;
ll x,y;
cin>>x>>y;
for(int i=n;i>=p;i--)
{
dp[i]=dp[i+k]+(a[i]=='0');
}
ll ans=0x7f7f7f7f7f7f7f7f;
for(int i=p;i<=n;i++)
{
ans=min(ans,(i-p)*y+dp[i]*x);
}
cout<<ans<<endl;
}
return 0;
}D:给你n个数，每次操作可以选择其中连续的两个数，把他们变成一个数-它们的异或和，为最少多少次操作，才能使这个序列不再是非严格单调增序列
题解：异或和，就去想二进制表达嘛，然后变成不再是非严格单调增序列，就是从第二个数到最后一个数，存在一个数大于其左边或者小于其右边，考虑一下最高位，因为是非严格单增的，所以前面的数的最高位不可能比后面大，每个ai<10^9，约32位，那么当n>=96时，必然存在连续三个最高位相同，三个数中的后两个异或和比前面小，这时答案必定是1，n<96时直接暴力，枚举起点，终点，从起点到终点遍历一遍，更新答案。（我是憨批，为什么写代码的时候只考虑一段区间的左右两点，而不是左右两段，好好去反思反思*-*）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
ll dp[N];
ll a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(n>=96) cout<<1<<endl;
else{
int f=0;
ll ans=0x7f7f7f7f7f7f7f7f;
for(ll i=1;i<=n-1;i++)
{
for(ll j=i+1;j<=n;j++)
{
ll temp=0;
for(ll k=i;k<=j;k++)
{
temp^=a[k];
}
ll temp1=0;
for(ll k=i-1;k>=1;k--)
{
temp1^=a[k];
if(temp<temp1)
{
f=1;
ans=min(ans,j-i+i-1-k);
}
}
ll temp2=0;
for(ll k=j+1;k<=n;k++)
{
temp2^=a[k];
if(temp>temp2)
{
f=1;
ans=min(ans,j-i+k-j-1);
}
}
//cout<<i<<' '<<j<<' '<<temp1<<' '<<temp2<<endl;
}
}
if(f)
cout<<ans<<endl;
else cout<<-1<<endl;
}
//ll fin1=11^22,fin2=71^92;
//cout<<fin1<<' '<<fin2<<endl;
return 0;
}E:题意就是给你n个数ci,和一个k，开始基金为0，设为res,设所要求的为sum,每次res加一个ci,sum+=res;如果res小于0的时候,可以重置res为0，并且这次加的ci不算，最多重置k次，问把所有ci加完，sum最大值是多少。
题解：我做这题的时候又去***了...明显，要使sum最大，肯定是把正数全部加上，而且正数越大的，贡献越大，此时也不使用重置，所以首先从大到小排个序，然后res和sum一直加，当res加到负之前，sum还是一直加res,res<0时，就把它和后面没加的负的ci放在一起考虑，一群负数，我们现在有k次机会把res置0，首先想的是负的越多的贡献让它尽可能小（我当时想的是把最小的就用置0，其他的按数从大到小贡献也越来越小，这样子就是从小到大排序，然后后面几个全部用0，后面也发现了bug,想错了，因为我还是没有做到让越小的所有数的贡献尽可能小），但是自己当时也没有平均分这个思想，还是太菜了。。。我们有k次置0机会，但是最后一个数咱们不算啊，就可以想想分成k+1组，把最小的那k+1个放到每一组的最后一个，其次小的k+1个放在每一组的倒数第二个...想想是不是最优的做法呢,答案是肯定的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5;
ll c[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
sort(c+1,c+1+n,greater<ll>());
ll sum=0,res=0;
int i;
for(i=1;i<=n;i++)
{
sum+=res;
res+=c[i];
if(res<0) break;
}
vector<ll>q;
q.push_back(res);
for(i++;i<=n;i++)
{
q.push_back(c[i]);
}
sort(q.begin(),q.end());
for(int j=0;j<q.size();j++)
{
sum+=(ll)q[j]*(j/(k+1));
}
cout<<sum<<endl;
return 0;
}