Codeforces Round #243 (Div. 1)_html/css_WEB-ITnose-html教程-PHP中文网

Codeforces Round #243 (Div. 1)_html/css_WEB-ITnose

php中文网

发布： 2016-06-24 12:05:29

原创

1172人浏览过

这场cf真是逗了。。。

因为早上7点起的，所以到做CF的时候已经17个小时没有休息了，再加上中午5小时的比赛。

头脑很不清晰。做第一个题的时候差点读成求最大字段和了。然后发现是水体，迅速A掉。

然后开始看了B题，第一遍没有看懂，此时大脑已经看不下去了。然后突然某个群说D是水题。

我去看了一下D，我去，D的题意好简单啊。。。。于是，冥思苦想中。。。。。一直到快要1点

立即学习“前端免费学习笔记（深入）”；

的时候，还是没有结果。。。此时我感觉不行了。。要放弃D，于是，又去看B。仔细读了读题目，

才发现，B题才是真正的水题。。一阵郁闷啊。。

A题：

可以暴力枚举区间，然后枚举去掉几个数。

去数的时候肯定是优先去掉最小的数，然后拿进来最大的。

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>using namespace std;#define maxn 220000#define mem(a,b) memset(a,b,sizeof(a))int a[222];vector<int>vec;vector<int>vecc;int main(){    int n,m,ans,i,j,k;    while(~scanf("%d%d",&n,&m))    {        for(i=1;i<=n;i++)scanf("%d",&a[i]);        ans=a[1];        for(i=1;i<=n;i++)        {            int p=0;            for(j=i;j<=n;j++)            {                vec.clear();                vecc.clear();                p=0;                for(k=i;k<=j;k++)                {                    vec.push_back(a[k]);                    p+=a[k];                }                for(k=1;k<=n;k++)                {                    if(k<i||k>j)vecc.push_back(a[k]);                }                sort(vec.begin(),vec.end());                sort(vecc.begin(),vecc.end());                int len=vec.size();                ans=max(ans,p);                for(k=1;k<=m&&k<=len&&k<=vecc.size();k++)                {                    p-=vec[k-1];                    p+=vecc[vecc.size()-k];                    ans=max(ans,p);                }            }        }        cout<<ans<<endl;    }    return 0;}

登录后复制

B题：

这道题目仔细研究下你就会发现，如果想变成合法的，那么任意两行或者两列都是相同或者相反的状态。

那么如果m小与10的话，咱们就枚举第一行的状态。

如果m大于10的话，咱们就枚举哪一列没有被改变。

#include <cmath>#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <cstring>#include<map>using namespace std;#define N 251000#define maxn 110000#define LL __int64int maps[220][220];int c[220];int r[220];int dp[220];int num[220][2];int number_1(int x){    x=(x& 0x55555555)+((x>>1)& 0x55555555);    x=(x& 0x33333333)+((x>>2)& 0x33333333);    x=(x& 0x0F0F0F0F)+((x>>4)& 0x0F0F0F0F);    x=(x& 0x00FF00FF)+((x>>8)& 0x00FF00FF);    x=(x& 0x0000FFFF)+((x>>16)& 0x0000FFFF);    return x;}void dos(int n,int m,int ks){    int ans=99999;    int i,j,k;    for(k=0;k<(1<<m);k++)    {        int ps=0;        for(i=1;i<=n;i++)        {            int p=0;            for(j=1;j<=m;j++)            {                if(maps[i][j]&&(k&(1<<(j-1))))                {                    p++;                }                else if(!maps[i][j]&&((k&(1<<(j-1)))==0))                {                    p++;                }            }            ps+=min(p,m-p);        }        ans=min(ans,ps);    }    if(ans<=ks)cout<<ans<<endl;    else cout<<"-1"<<endl;}int have[110][110];void dos2(int n,int m,int ks){    int i,j,k;    for(i=1;i<=m;i++)    {        for(j=1;j<=m;j++)        {            for(k=1;k<=n;k++)            {                if(maps[k][i]==maps[k][j])have[i][j]++;            }        }    }    int ans=999;    for(i=1;i<=m;i++)    {        int p=0;        for(j=1;j<=m;j++)        {            p+=min(have[i][j],n-have[i][j]);        }        ans=min(ans,p);    }    if(ans<=ks)cout<<ans<<endl;    else cout<<"-1"<<endl;}int main(){    int n,m,k,i,j;    while(~scanf("%d%d%d",&n,&m,&k))    {        memset(c,0,sizeof(c));        memset(r,0,sizeof(r));        memset(dp,0,sizeof(dp));        memset(maps,0,sizeof(maps));        memset(num,0,sizeof(num));        for(i=1;i<=n;i++)        {            for(j=1;j<=m;j++)            {                scanf("%d",&maps[i][j]);            }        }        if(m<=10)        {            dos(n,m,k);        }        else        {            dos2(n,m,k);        }    }    return 0;}

登录后复制