(D1T1) 均分纸牌 ((OK))
(D1T2) 字串变换 ((OK))
(D1T3) 自由落体 ((OK))
(D1T4) 矩形覆盖 ((OK))
这年的题其实题目很好,但是数据点又少还水.
(T1)贪心模拟入门题.最终每一堆纸牌的数量是已知的,即(ave=frac{sum}{n}).那么把每一堆纸牌数量减去(ave)后,如果为负数则要从别人那里拿纸牌,如果为正数就要给别人纸牌,如果为(0)就不要动.按照这样从左往右模拟即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=105;
int a[N];
int main(){
int n=read(),sum=0,ans=0;
for(int i=1;i<=n;++i)a[i]=read(),sum+=a[i];
int ave=sum/n;for(int i=1;i<=n;++i)a[i]-=ave;
for(int i=1;i<n;++i){
if(a[i]!=0)++ans,a[i+1]+=a[i];
}
printf("%d
",ans);
return 0;
}
(T2)字符串做到崩溃.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
int num=1;
string st,ed,turna[10],turnb[10];
map<string,int>Map;queue<string>q;
inline bool bfs(){
Map[st]=1;q.push(st);
while(q.size()){
string u=q.front();q.pop();
for(int i=1;i<=num;++i){
string now=u;
while(1){
int pos=now.find(turna[i]);
if(pos==-1)break;
string v=u;now[pos]='|';
v.replace(pos,turna[i].size(),turnb[i]);
if(Map[v])continue;
Map[v]=Map[u]+1;
if(v==ed)return true;
if(Map[v]>=11)return false;
q.push(v);
}
}
}
return false;
}
int main(){
cin>>st>>ed;while(cin>>turna[num]>>turnb[num])num++;num--;
int pd=bfs();if(pd)printf("%d
",Map[ed]-1);else puts("NO ANSWER!");
return 0;
}
(T3)蒟蒻只会中规中矩的一个一个点枚举,然后判断能否被接到.反正应该是数据水的原因,只错了一个点,然后就不会做了.然后题解里面全都是(O(1))的神仙做法,发现反而更好理解:就是说每个小球都是同时下落,同时落地的,那么设小球落到车顶(h-k)的时间为(tmin),落到地上(h)的时间为(tmax),那么根据小车的速度和车长,可以把小车看做是有这么一段区间,小球的下落位置的横坐标如果在区间内就能被接到.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
double h,s,v,l,k;int n;
int main(){
scanf("%lf%lf%lf%lf%lf%d",&h,&s,&v,&l,&k,&n);
double tmin=sqrt((h-k)/5),tmax=sqrt(h/5);
int imin=(int)(s-tmax*v),imax=(int)(s-tmin*v+l);
printf("%d
",min(imax,n)-max(0,imin));
return 0;
}
(T4)这道题我本来觉得很难的,然后随便打了个搜索+剪枝就过了.肯定是数据太水了.我自己是这么想的:把所有点按照横坐标从小到大排序后,最优方案中一个矩形覆盖到的肯定是一段连续的点(这个贪心显然是错的,我虽然造不出(hack)数据,但我就觉得这个贪心是错的,因为如果有两个点横坐标相距很远,但是纵坐标一样,那么用一个矩形覆盖这两个点产生的贡献是(0),很优).
然后就直接搜索枚举每个矩形覆盖哪一段连续的点即可.再加上一个最优性剪枝,跑得飞快.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=51;
int n,k,ans=1<<30;
struct node{int x,y;}a[N];
inline bool cmp(node x,node y){return x.x==y.x?x.y<y.y:x.x<y.x;}
inline void dfs(int now,int cnt,int sum){
if(sum>=ans)return;
if(now>n){ans=sum;return;}
if(cnt>k)return;
for(int i=now;i<=n;++i){
int xmin=1<<30,xmax=0,ymin=1<<30,ymax=0;
for(int j=now;j<=i;++j){
xmin=min(xmin,a[j].x);
xmax=max(xmax,a[j].x);
ymin=min(ymin,a[j].y);
ymax=max(ymax,a[j].y);
}
dfs(i+1,cnt+1,sum+(xmax-xmin)*(ymax-ymin));
}
}
int main(){
n=read();k=read();
for(int i=1;i<=n;++i)a[i].y=read(),a[i].x=read();
sort(a+1,a+n+1,cmp);
dfs(1,1,0);printf("%d
",ans);
return 0;
}