目录

cf1199解题报告 ABCDEF

cf1199解题报告

发一波水题。

A

模拟

#include <bits/stdc++.h> #define ll long long using namespace std; const int _=1e6+7; int n,x,y,a[_]; int main() { scanf("%d%d%d",&n,&x,&y); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int d=1;d<=n;++d) { int flag=0; for(int j=max(1,d-x);j<d;++j) if(a[d]>=a[j]) flag=1; for(int j=d+1;j<=min(n,d+y);++j) if(a[d]>=a[j]) flag=1; if(!flag) return printf("%d\n",d),0; } return 0; }

B

小学几何题。输出lf格式不对错了几发、、、

#include <bits/stdc++.h> #define ll long long using namespace std; const int _=1e6+7; double H,L,x; int main() { cin>>H>>L; double x=(H*H+L*L)/(2*H); printf("%.13lf\n",x-H); return 0; }

C

最多能保留几个不同的数，然后删就行了。 我以为是\(map\)的\(log\)太大了T了。 其实是暴利统计最多保留几个没加范围。

#include <bits/stdc++.h> using namespace std; const int _=4e5+7; int n,m,k,a[_],ans=0x3f3f3f3f; int Hash[_],lsh[_]; vector<pair<int,int> > tmp; int sum[_]; int read() { int x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f; } int main() { n=read(),m=read()*8; for(int i=1;i<=n;++i) lsh[i]=a[i]=read(); sort(lsh+1,lsh+1+n); int len=unique(lsh+1,lsh+1+n)-lsh-1; for(int i=1;i<=n;++i) a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh; for(int i=1;i<=n;++i) Hash[a[i]]++; while((int)ceil(log2(k+1))*n<=m&&k<=n) k++; for(int i=1;i<=n;++i) if(Hash[i]) tmp.push_back(make_pair(i,Hash[i])); int Siz=tmp.size(); for(int i=0;i<Siz;++i) { if(i) sum[i]=sum[i-1]; sum[i]+=tmp[i].second; if(i<k) ans=min(ans,n-sum[i]); else ans=min(ans,n-sum[i]+sum[i-k]); } printf("%d\n",ans); return 0; }

D

每个数最后的值=max(上一次更改的值，这段时间内政府补贴的最大值)。 由于都是后缀，\(O(n)\)统计一遍就行了。 当然也可以学傻了写线段树或者BIT。

#include <bits/stdc++.h> using namespace std; const int _=4e5+7; namespace seg { #define ls rt<<1 #define rs rt<<1|1 int a[_],ma[_<<2]; void build(int l,int r,int rt) { if(l==r) {ma[rt]=a[l];return;} int mid=(l+r)>>1; build(l,mid,ls); build(mid+1,r,rs); ma[rt]=max(ma[ls],ma[rs]); } int modify(int L,int R,int l,int r,int rt) { if(L>R) return 0; if(L<=l&&r<=R) return ma[rt]; int mid=(l+r)>>1,ma=0; if(L<=mid) ma=max(ma,modify(L,R,l,mid,ls)); if(R>mid) ma=max(ma,modify(L,R,mid+1,r,rs)); return ma; } } int n,a[_],las[_],q,dsr[_]; int main() { // freopen("a.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); scanf("%d",&q); for(int i=1,opt,p,x;i<=q;++i) { scanf("%d",&opt); if(opt==1) scanf("%d%d",&p,&x),las[p]=i,dsr[i]=x; else scanf("%d",&x),seg::a[i]=x; } seg::build(1,q,1); for(int i=1,val;i<=n;++i) { if(!las[i]) val=a[i]; else val=dsr[las[i]]; val=max(val,seg::modify(max(las[i],1),q,1,q,1)); printf("%d ",val); } return 0; }

E

\(matching\)和\(indset\)至少存在一个。 每次遇到符合\(matching\)的边就加上。 做完后，剩下的点就是\(indset\)的。 反证：没在\(matching\)的两个点，而且有边相连，显然矛盾。 因为是\(3n\)个点，所以做完后一定有一个满足条件。

#include <bits/stdc++.h> using namespace std; const int _=5e5+7; int T,n,m,vis[_]; std::vector<int> dsr; int main() { scanf("%d",&T); while(T --> 0) { scanf("%d%d",&n,&m); dsr.clear(); for(int i=1;i<=3*n;++i) vis[i]=0; for(int i=1,u,v;i<=m;++i) { scanf("%d%d",&u,&v); if(!vis[u]&&!vis[v]) { vis[u]=vis[v]=1; dsr.push_back(i); } } if((int)dsr.size()>=n) { printf("Matching\n"); for(int i=0;i<n;++i) printf("%d ",dsr[i]); printf("\n"); } else { printf("IndSet\n"); for(int i=1,js=1;js<=n;++i) if(!vis[i]) printf("%d ",i),++js; printf("\n"); } } return 0; }

F

大爆搜\(f[x][y][X][Y]\)表示左上角\((x,y)\)，右下角\((X,Y)\)的矩阵变为白色的最小代价。 每次转移\(O(n)\)，有\(O(n^4)\)个转态。复杂度\(O(n^5)\)

#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int _=51; int n,s[_][_],num[_][_],f[_][_][_][_]; char S[_][_]; int calc(int x,int y,int X,int Y) { return s[X][Y]-s[x-1][Y]-s[X][y-1]+s[x-1][y-1]; } int dfs(int x,int y,int X,int Y) { if(!calc(x,y,X,Y)||f[x][y][X][Y]) return f[x][y][X][Y]; if(x==X&&y==Y) {f[x][y][X][Y]=1;return 1;} f[x][y][X][Y]=max(X-x+1,Y-y+1); for(int i=x;i<X;++i) f[x][y][X][Y]=min(f[x][y][X][Y],dfs(x,y,i,Y)+dfs(i+1,y,X,Y)); for(int i=y;i<Y;++i) f[x][y][X][Y]=min(f[x][y][X][Y],dfs(x,y,X,i)+dfs(x,i+1,X,Y)); return f[x][y][X][Y]; } int main() { freopen("a.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",S[i]+1); for(int j=1,tot=0;j<=n;++j) { tot+=(S[i][j]=='#'); s[i][j]=s[i-1][j]+tot; } } printf("%d\n",dfs(1,1,n,n)); return 0; }

转载于:https://www.cnblogs.com/dsrdsr/p/11372863.html

相关资源：JAVA上百实例源码以及开源项目