Codeforces 687 div2

明天来写
最近准备考试，写的不太详细，哪里看不懂直接私信就行。
A：
这个题直接猜了一下就是求4个点到r,c的距离哪个最大

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int n,m,r,c;
        scanf("%d%d%d%d",&n,&m,&r,&c);
        int sum=0;
        sum=max(sum,abs(n-r)+abs(m-c));
        sum=max(sum,abs(r-1)+abs(c-1));
        sum=max(sum,abs(r-1)+abs(m-c));
        sum=max(sum,abs(n-r)+abs(c-1));
        printf("%d\n",sum);
    }
 } 

B:
n=1e5,c=100，这范围直接暴力每个颜色就好了

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int c[N];

void solve()
{
    map<int,int> mp;
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]),mp[c[i]]=1;
    int cnt=1000000;
    for(int i=1;i<=100;i++)
    {
        if(mp[i]==0) continue;
        int cnt1=0;
        for(int j=1;j<=n;)
        {
            if(c[j]!=i) 
            {
                cnt1++;
                j+=k;
                //cout<<j<<" "<<cnt1<<endl;
            }
            else j++;
        }

        cnt=min(cnt1,cnt);
    }
    printf("%d\n",cnt);
}

int main()
{
    int t;    
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        solve();
    }
}

C:
一开始是写的nk复杂度从前面往后算，然后T了,想了想发现只需要从后往前跳，就可以以O(n)的复杂度来解决了。

include<bits/stdc++.h>

typedef long long ll;

const int N= 1e6+10;;
const ll INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;

ll n,m,p;
ll num[N];
char s[N];
ll hz[N];
int a[N];
void solve()
{
        scanf("%lld%lld%lld",&n,&m,&p);
        for(int i=1;i<=n+2*p;i++) hz[i] = 0;

        for(int i=1;i<=n;i++)
        {
            scanf("%1d",&a[i]);
        }
        ll x,y;
        scanf("%lld%lld",&x,&y);
        ll res = INF;
        for(int i=n;i>=1;i--){
            hz[i] = hz[i+p];
            if(a[i] == 0) hz[i] += x;
        }
        for(int i=m;i<=n;i++)
            res = min(res,(i-m)*y+hz[i]);
        printf("%lld\n",res);
}

int main(){
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++)
     solve();
    return 0;
}

D：
如果n>60的话。我们设每个值最高位在第i位，因为长度最多为30，所以n>60时，一定会有连续的3个在一起只需要把两个异或就小于另一个了。n<60的时候就暴力

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10; 
int a[N];
int sum[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]^a[i];
    }
    if(n>60) printf("1\n");
    else {

        int ans=1000000;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                for(int k=i+1;k<=n;k++)
                {
                    if(k-j>2&&(sum[j]^sum[i])>(sum[i]^sum[k]))
                    {
                        ans=min(ans,k-j-2); 
                    }
                }
            }
        }
        if(ans==1e6) ans=-1;
        cout<<ans<<endl;

    }
} 

E：
这个题先从大到小排序，然后从第一个加如果pre<0的话。
这个时候我们就需要对这个当前位置之后的还有当前的pre处理。
因为我们有k个最后一个不需要加，相当于是k+1个，只要把这些分组分到k+1个就好了。第一个是0次贡献，第二个是1次贡献，依次类推

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 5e5+10;
ll c[N];
vector<ll> ve;

bool cmp( int a,int b)
{
    return a>b;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&c[i]);
    } 
    sort(c+1,c+n+1,cmp); 
    ll pre=0;
    ll sum=0;
    int st=n+1;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        //cout<<sum<<endl;
        sum+=pre;
        pre+=c[i];
        //cout<<"pre:"<<pre<<endl;
        if(pre<0)
        {
            ve.push_back(pre);
            st=i+1;
            break;
        }
    }
//    cout<<"st:"<<st<<endl;
    for(int i=st;i<=n;i++)
    {
        ve.push_back(c[i]);

    }
    sort(ve.begin(),ve.end());
    for(int i=0;i<ve.size();i++)
    sum+=(1LL*ve[i]*(i/(k+1)));


    cout<<sum<<endl;


}