首页 > 代码库 > Codeforces Round #243 (Div. 1)-A,B,C-D
Codeforces Round #243 (Div. 1)-A,B,C-D
这场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; }
D题:
这道题目分两种情况讨论。
枚举x轴.
1,如果x轴上的点大于sqrt(n);
如果当前枚举到的x轴上的点大于sqrt(n)的话,那么就枚举其它轴上的所有的点,看能不能跟x轴形成一个正方形。
这种点的个数为n^0.5次方个,每一个的时间复杂度n,总时间复杂度为n^1.5
2,如果x轴上的点小与sqrt(n);
枚举这个轴上的任意两个点能不能形成正方行。
这种点的个数为n^0.5次方个,每一个的时间复杂度为(sqrt(n))^2;
综合时间复杂度为O(n^1.5)
#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> #include<vector> #include<math.h> #include<map> using namespace std; #define maxn 110000 #define INF 99999999 vector<int>vec[maxn]; bool find(int x,int y) { if(x>=maxn)return false; return binary_search(vec[x].begin(),vec[x].end(),y); } int main() { int n,i,j,k,x,y; while(~scanf("%d",&n)) { for(i=0;i<maxn;i++)vec[i].clear(); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); } for(i=0;i<maxn;i++)sort(vec[i].begin(),vec[i].end()); int sq=sqrt(n); int ans=0; for(i=0;i<maxn;i++) { int p=vec[i].size(); if(vec[i].size()==0)continue; if(p<sq) { for(j=0;j<p;j++) { for(k=j+1;k<p;k++) { int d=vec[i][k]-vec[i][j]; //cout<<"-"<<vec[i][k]<<" "<<vec[i][j]<<endl; if(find(i+d,vec[i][j])&&find(i+d,vec[i][k])) { // cout<<i<<" "<<vec[i][k]<<" "<<vec[i][j]<<endl; ans++; } } } } else { for(j=i+1;j<maxn;j++) { for(k=0;k<vec[j].size();k++) { int d=j-i; // cout<<"-"<<i<<" "<<j<<" "<<vec[j][k]<<endl; if(find(i,vec[j][k])&&find(j,vec[j][k]+d)&&find(i,vec[j][k]+d)) { // cout<<i<<" "<<j<<" "<<vec[j][k]<<endl; ans++; } } } } } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。