Codeforces Round #243 (Div. 一)-A,B,C
Codeforces Round #243 (Div. 1)-A,B,C
B题：
这场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 __int64
int 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;
}
C 题：
这次的题意真是。。。。不好懂。。
dp[i][j]:在a数组里选到第i个数共选出了j次，对应b数组下标的最小位置。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 110000
#define INF 99999999
int dp[maxn][330];
vector<int>vec[maxn];
int a[maxn];
int b[maxn];
int sea(int x,int y)
{
int l=0;
int r=vec[y].size();
int mid=(l+r)/2;
while(l<r)
{
if(vec[y][mid]<=x)l=mid+1;
else r=mid;
mid=(l+r)/2;
}
if(mid==vec[y].size())return INF;
else return vec[y][mid];
}
int main()
{
int n,m,s,e;
int k;
int i,j;
while(~scanf("%d%d%d%d",&n,&m,&s,&e))
{
k=s/e;
for(i=0;i<=n;i++)
{
vec[i].clear();
for(j=0;j<=k;j++)dp[i][j]=INF;
}
//cout<<"--"<<endl;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d",&b[i]);
for(i=1;i<=m;i++)
{
vec[b[i]].push_back(i);
}
int ans=0;
dp[0][0]=0;
for(i=1;i<=n;i++)
{
dp[i][0]=0;
for(j=1;j<=k&&j<=i;j++)
{
int x=dp[i-1][j-1];
int ps=sea(x,a[i]);
dp[i][j]=min(dp[i-1][j],ps);
if(j>ans)
{
if(i+dp[i][j]+j*e<=s)
{
ans=j;
}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=k&&j<=i;j++)
{
// cout<<dp[i][j]<<" ";
}
// cout<<endl;
}
cout<<ans<<endl;
}
return 0;
}