20220927(平)
t1 [SCOI2009]生日快乐
思路
题目还是挺具有迷惑性的，至少我第一眼就以为是二分。然后就写了个二分，然而最后写出来是在二分里二分，又发现只有边长除以所分边长为整数的才可行，那这其实就是个暴力搜索。把一个大蛋糕一刀分成两个蛋糕，然后再继续分下去，求最小的比值即可。
点击查看代码
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
double n,x,y;
inline double dfs(double xx,double yy,double nn){
double ans=1e9,ans1,ans2;
if(nn==1){
if(xx<yy)swap(xx,yy);
return xx/yy;
}
double minx=xx/nn,miny=yy/nn;
fo(i,1,nn/2){
ans1=max(dfs(minx*i,yy,i),dfs(xx-minx*i,yy,nn-i));
ans2=max(dfs(xx,miny*i,i),dfs(xx,yy-miny*i,nn-i));
ans=min(ans,min(ans1,ans2));
}
return ans;
}
int main(){
scanf("%lf%lf%lf",&x,&y,&n);
printf("%.6lf",dfs(x,y,n));
return 0;
}
t2 windy数
[传送门]([P2657 SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
思路
显而易见的数位dp。\(f[i][j]\)表示长度为i，最高位为j的满足条件的数的个数。然后将该数组预处理出来。最后求答案时统计即可。
点击查看代码
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
double n,x,y;
inline double dfs(double xx,double yy,double nn){
double ans=1e9,ans1,ans2;
if(nn==1){
if(xx<yy)swap(xx,yy);
return xx/yy;
}
double minx=xx/nn,miny=yy/nn;
fo(i,1,nn/2){
ans1=max(dfs(minx*i,yy,i),dfs(xx-minx*i,yy,nn-i));
ans2=max(dfs(xx,miny*i,i),dfs(xx,yy-miny*i,nn-i));
ans=min(ans,min(ans1,ans2));
}
return ans;
}
int main(){
scanf("%lf%lf%lf",&x,&y,&n);
printf("%.6lf",dfs(x,y,n));
return 0;
}
t3 [SCOI2009]最长距离
[传送门]([P4162 SCOI2009]最长距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
思路
其实就是个最短路，求从各个点到其他点所需移除的障碍数，如果小于t说明可以到达，此时就统计答案。
点击查看代码
#include<iostream>
#include<cmath>
#include<queue>
#include<utility>
#include<cstring>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
int n,m,t;
int mp[35][35],dis[35][35];
ll ans;
queue<pair<int,int> > q;
int fx[]={0,0,1,-1},fy[]={1,-1,0,0};
bool vis[35][35];
inline bool check(int x,int y){
if(x<=0||y<=0||x>n||y>m)return 0;
return 1;
}
void spfa(int x,int y){
memset(dis,127,sizeof(dis));
dis[x][y]=mp[x][y];
q.push(make_pair(x,y));
while(!q.empty()){
int x=q.front().first,y=q.front().second;
vis[x][y]=0;
q.pop();
fo(i,0,3){
int x1=x+fx[i],y1=y+fy[i];
if(!check(x1,y1))continue;
if(dis[x1][y1]>dis[x][y]+mp[x1][y1]){
dis[x1][y1]=dis[x][y]+mp[x1][y1];
if(!vis[x1][y1]){
q.push(make_pair(x1,y1));
vis[x1][y1]=1;
}
}
}
}
}
inline ll get(int x,int y,int xx,int yy){
return pow(x-xx,2)+pow(y-yy,2);
}
int main(){
in(n),in(m),in(t);
fo(i,1,n){
char c[35];
scanf("%s",c);
fo(j,0,m-1){
mp[i][j+1]=c[j]-'0';
}
}
fo(i,1,n){
fo(j,1,m){
spfa(i,j);
fo(ii,1,n)
fo(jj,1,m){
if(dis[ii][jj]<=t)
ans=max(ans,get(i,j,ii,jj));
}
}
}
printf("%.6lf",sqrt(ans));
return 0;
}
t4 [HNOI2008]GT考试
[传送门]([P3193 HNOI2008]GT考试 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))