A 汽水瓶
思路：
模拟，其实也可以考虑贡献，每次都相当于少了两个汽水瓶，所以(res=n/2)
代码：
int main(){
int n;
while(cin>>n){
if(!n) break;
int res=0;
while(n>=2){
if(n==2){
res++;break;
}
int t1=n/3,t2=n%3;
res+=t1;n=t2+t1;
}
cout<<res<<endl;
}
return 0;
}
B 弟弟的作业
思路：
利用(atoi)函数来将结果转化成数字，其余模拟。
代码：
int main(){
int a,b,res=0;
char ch;
char s[100];
while(scanf("%d%c%d=%s",&a,&ch,&b,s)!=EOF){
//cout<<a<<ch<<b<<"="<<s<<endl;
int c=atoi(s);
//cout<<c<<endl;
if(ch=='+'&&s[0]!='?'){
if(a+b==c) res++;
}
if(ch=='-'&&s[0]!='?'){
if(a-b==c) res++;
}
}
cout<<res<<endl;
return 0;
}
C 数字整除
思路：
从高位向低位转化，每次取余(17)，若最后结果为(0)，则可以整除。
代码：
int main(){
string s;//17
while(cin>>s){
if(s[0]=='0') break;
ll sum=0;
rep(i,0,s.size()-1){
sum=sum*10+s[i]-'0';
sum%=17;
}
if(sum) puts("0");
else puts("1");
}
return 0;
}
D 台球碰撞
思路：
(1.)由于球是不规则的，所以球的运动范围一定在一个小框内，右上角的点为((l-r,w-r))，所以第一步要将长宽更改一下。
(2.)将速度分解为水平速度和竖直速度，分别考虑两个坐标轴的变化。
(3.)模拟每一秒的变化过程，由于碰撞后速度不会发生变化，所以每秒对于每个坐标轴的变化都是一样的，可以根据这点确定下一秒的位置。
比如，当(y>w)时，说明已经超出边界，假设变化前的坐标为(y_{1})，则在到达上界限的距离为(w-y_{1}),一共变化的距离为(y-y_{1}),所以碰撞后还需要再变化的距离为(w-y_{1}-(y-y_{1})),这次的变化距离是相对于上界限要移动的距离，所以碰撞后的坐标为(2*w-y)。其他的也类似。
(4.)注意，有可能一次碰撞后还会接触边界，所以要用(while)循环。
代码:
#define PI acos(-1)
const double eps=1e-6;
int main(){
double l,w,x,y,r,a,v,s;
while(cin>>l>>w>>x>>y>>r>>a>>v>>s){
if(!l&&!w&&!x&&!y&&!r&&!a&&!v&&!s) break;
l=l-r,w=w-r;
double vx=v*1.0*cos(a/180.0*PI);
double vy=v*1.0*sin(a/180.0*PI);
while(s--){
x+=vx,y+=vy;
while(y>w||x>l||y<r||x<r){
if(y>w) y=2.0*w-y,vy=-vy;
if(x>l) x=2.0*l-x,vx=-vx;
if(y<r) y=2.0*r-y,vy=-vy;
if(x<r) x=2.0*r-x,vx=-vx;
}
}
printf("%.2f %.2f
",x,y);
}
return 0;
}
E 内部收益率
思路：
浮点数二分，也可以不将式子变成乘法，直接用除法的式子进行二分。
看网上其他题解说没有"Too many"和“No"的情况
代码：
const double eps=1e-6;
int n,cf[maxn];
double check(double irr){
double sum=0.0;
double tmp=1.0;
for(int i=n;i>=0;i--){
sum+=cf[i]*1.0*tmp;
tmp=tmp*(1+irr);
}
return sum;
}
int main(){
while(cin>>n){
if(!n) break;
rep(i,0,n) cf[i]=read;
double l=-1.0,r=1000000.0,res=0;
int cnt=0,idx=0;
double t=1000000000.0;
while(r-l>=eps&&idx<=1e7&&cnt<=1){
idx++;
double mid=(l+r)/2.0;
//cout<<mid<<endl;
t=check(mid);
if(t>0) l=mid;
else if(t<0) r=mid;
else if(fabs(t)<eps){
cnt++,res=mid,r=mid;
}
// cout<<l<<" "<<r<<" "<<t<<"
";
}
//cout<<res<<"***"<<cnt<<"***"<<idx<<"
";
if(idx>=1e7&&cnt<=1) puts("No");
else if(cnt>1) puts("Too many");
else printf("%.2lf
",l);
}
return 0;
}
F Biggest Number
思路：
bfs估价剪枝。
首先想到的思路是dfs，显然过不了，考虑剪枝。
对于每个搜到的点，先用bfs进行估价，找到他能到达的所有点：
如果目前的数的长度加上能够到达的点的个数大于答案的长度，说明是可以继续搜下去的。
如果等于并且数值大于的话，也是可以继续搜下去的。
代码:
char a[110][110];
int n,m;
bool vis[110][110],st[110][110];
string ans,tmps;
int nx[]={0,0,1,-1};
int ny[]={1,-1,0,0};
int bfs(int x,int y){
memset(st,0,sizeof st);
int cnt=0;
tmps="";
queue<PII>q;
q.push({x,y});
st[x][y]=1;
while(!q.empty()){
int tx=q.front().first,ty=q.front().second;
q.pop();
tmps+=a[tx][ty];
for(int i=0;i<4;i++){
int xx=tx+nx[i],yy=ty+ny[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]!='#'&&!vis[xx][yy]&&!st[xx][yy]){
st[xx][yy]=1;
q.push({xx,yy});
}
}
}
sort(tmps.begin(),tmps.end());
reverse(tmps.begin(),tmps.end());
return tmps.size();
}
void dfs(int x,int y,string s){
s+=a[x][y];
vis[x][y]=1;
if(s.size()>ans.size()||(s.size()==ans.size()&&s>ans)) ans=s;
for(int k=0;k<4;k++){
int xx=x+nx[k],yy=y+ny[k];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]!='#'&&!vis[xx][yy]){
int maxl=bfs(xx,yy);
if(s.size()+maxl>ans.size()||(s.size()+maxl==ans.size()&&s+tmps>ans)){
dfs(xx,yy,s);
}
}
}
vis[x][y]=0;
}
int main(){
while(cin>>n>>m){
if(!n&&!m) break;
for(int i=0;i<n;i++) cin>>a[i];
memset(vis,0,sizeof vis);
ans="";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]!='#') dfs(i,j,"");
cout<<ans<<"
";
}
return 0;
}
G Repairing a Road
思路：
边数很少，考虑枚举每一条边。
对于每一条边，修建道路后的代价为(dis(1,x)+t-dis(1,x)+v*a_{-t}+dis(y,n))
求导数得：(1-ln(a)*v*a_{-t})，当导数为(0)时，取得最小值，二分查找。
对于(dis),考虑用(floyd)
代码：
int n,m;
double g[110][110];
struct node{
int x,y;
double v,a;
}edge[510];
inline int sgn(double x) {
if(fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
double check(double v,double a,double l,double r){
double res,tmpl=l;
while(r-l>eps){
double mid=(l+r)/2;
if(1-log(a)*v*pow(a,-mid)>0) r=mid;
else l=mid;
}
return l;
}
int main(){
while(cin>>n>>m){
if(!n&&!m) break;
rep(i,1,n) rep(j,1,n)
if(i==j) g[i][j]=0;
else g[i][j]=1000000.0;
rep(i,1,m){
cin>>edge[i].x>>edge[i].y>>edge[i].v>>edge[i].a;
int x=edge[i].x,y=edge[i].y;
g[x][y]=min(g[x][y],edge[i].v);
g[y][x]=min(g[y][x],edge[i].v);
}
rep(k,1,n) rep(i,1,n) rep(j,1,n)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
double res=g[1][n];
rep(i,1,m){
int x=edge[i].x,y=edge[i].y;
double v=edge[i].v,a=edge[i].a;
double t=check(v,a,g[1][x],res);
res=min(res,t+g[y][n]+v*pow(a,-t));
t=check(v,a,g[1][y],res);
res=min(res,t+g[x][n]+v*pow(a,-t));
}
printf("%.3f
",res);
}
return 0;
}