Codeforces Round #243 (Div. 1)_html/css_WEB-ITnose-HTML Tutorial-php.cn

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

WBOY

Release： 2016-06-24 12:05:29

Original

1129 people have browsed it

This CF is really funny. . .

Because I got up at 7 o'clock in the morning, I had not rested for 17 hours by the time I did CF, plus the 5-hour game at noon.

My mind is very unclear. When I was doing the first question, I almost read it as finding the maximum sum of fields. Then I discovered it was a body of water and quickly jumped out.

Then I started reading question B. I didn’t understand it the first time, and my brain couldn’t stand it anymore. Then suddenly a certain group said that D is a water question.

I took a look at D. Go ahead, the question meaning of D is so simple. . . . So, I was thinking hard. . . . . Until almost 1 o'clock

, there was still no result. . . At this point I felt like I couldn't do it anymore. . I wanted to give up on D, so I went to see B again. After reading the question carefully,

I discovered that question B is the real water question. . Feeling depressed for a while. .

Question A:

You can violently enumerate the intervals, and then remove a few numbers by enumeration.

When counting, you must first remove the smallest number, and then bring in the largest number.

#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;}

Copy after login

Question B:

If you study this question carefully, you will find that if you want to become legal, then any two lines or Both columns are the same or opposite states.

Then if m is less than 10, we will enumerate the status of the first row.

If m is greater than 10, we enumerate which columns have not been changed.

#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;}

Copy after login