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