A - An Easy Physics Problem

Not Easy 啊。
给个射线，和一个圆柱体，射线撞到圆柱体会弹射。判断能否经过给定的点。

折射的时候不能用三角函数旋转，会被卡精度。

$(x,y)$关于直线$ax+by+c=0$的对称点坐标$nx=x-2a\frac{ax+by+c}{a^2+b^2}$，$ny=y-2b\frac{ax+by+c}{a^2+b^2}$。

#include <bits/stdc++.h>using namespace std; typedef long long ll; typedef long double db; const db eps = 1e-12; const db pi = 4.0 * atan(1.0);int sgn(db x) {if (x > eps) return 1;if (x < -eps) return -1;return 0; } struct vec {db x, y;vec() {}vec(db _x, db _y): x(_x), y(_y) {}vec rotate(db c) {return vec(x * cos(c) - y * sin(c), x * sin(c) + y * cos(c));} };struct line {vec p, q;line() {}line(vec _x, vec _y): p(_x), q(_y) {} };db ox, oy, r, sx, sy, vx, vy, ex, ey; bool ok;vec solve() {db dx = sx - ox;db dy = sy - oy;db a = vx * vx + vy * vy;db b = 2.0 * (vx * dx + vy * dy);db c = dx * dx + dy * dy - r * r;db delta = b * b - 4.0 * a * c;if (delta > eps && b < -eps) {delta = sqrt(delta);db t2 = (-b - delta) / (2.0 * a);if (t2 < -eps) {ok = 0;return vec(0, 0);} else if (t2 > -eps) {ok = 1;return vec(t2, t2);} else {ok = 1;return vec(0, 0);}}ok = 0;return vec(0, 0); }bool ison1(db sx, db sy, db vx, db vy, db ex, db ey) {//if (sgn(sx - ex) == 0 && sgn(sy - ey) == 0) return 1;db lx = ex - sx;db ly = ey - sy;db dl = lx * vy - vx * ly;if (sgn(dl) == 0) {if (sgn(vx) != 0) {db sg = lx / vx;if (sgn(sg) > 0) return 1;return 0;} else if (sgn(vy) != 0) {db sg = ly / vy;if (sgn(sg) > 0) return 1;return 0;}}return 0; }bool ison2(db sx, db sy, db vx, db vy, db ex, db ey, db t) {//if (sgn(sx - ex) == 0 && sgn(sy - ey) == 0) return 1;db lx = ex - sx;db ly = ey - sy;db dl = lx * vy - vx * ly;if (sgn(dl) == 0) {if (sgn(vx) != 0) {db sg = lx / vx;if (sgn(sg) > 0 && sgn(sg - t) <= 0) return 1;return 0;} else if (sgn(vy) != 0) {db sg = ly / vy;if (sgn(sg) > 0 && sgn(sg - t) <= 0) return 1;return 0;}}return 0; }db get(db sx, db sy, db xx, db yy, db ox, db oy) {db l1 = (sx - xx) * (sx - xx) + (sy - yy) * (sy - yy);l1 = sqrt(l1);db l2 = r;db l3 = (sx - ox) * (sx - ox) + (sy - oy) * (sy - oy);l3 = sqrt(l3);db COS = l1 * l1 + l2 * l2 - l3 * l3;COS /= (2.0 * l1 * l2);db alp = acos(COS);return alp; }vec get2(db sx,db sy,db ox,db oy,db xx,db yy){db A,B,C;A=oy-yy;B=xx-ox;C=ox*yy-xx*oy;db rx=sx-2.0*A*(A*sx+B*sy+C)/(A*A+B*B);db ry=sy-2.0*B*(A*sx+B*sy+C)/(A*A+B*B);return vec(rx,ry); }int main() {//freopen("in.txt", "r", stdin);//printf("%.17Lf\n",pi);//cout<<pi<<endl;int T, cas = 1;cin >> T;while (T--) {cin >> ox >> oy >> r;cin >> sx >> sy >> vx >> vy;cin >> ex >> ey;vec pt = solve();bool flg = 0;//cout<<"#"<<ok<<endl;if (!ok) {if (ison1(sx, sy, vx, vy, ex, ey)) {flg = 1;}} else {if (ison2(sx, sy, vx, vy, ex, ey, pt.x)) {flg = 1;}db xx = sx + vx * pt.x;db yy = sy + vy * pt.x;// db angle = get(sx, sy, xx, yy, ox, oy);// angle = 2.0 * angle - pi;// vec np = vec(vx, vy);// db fx1,fy1,fx2,fy2;// fx1=xx-sx;fy1=yy-sy;// fx2=ox-sx;fy2=oy-sy;// if(sgn(fx1*fy2-fx2*fy1)<0)// np = np.rotate(angle);// else np = np.rotate(-angle);// if (ison1(xx, yy, np.x, np.y, ex, ey)) {// flg = 1;// }vec dxd=get2(sx,sy,ox,oy,xx,yy);//cout<<dxd.x<<" "<<dxd.y<<endl;if(ison1(xx,yy,dxd.x-xx,dxd.y-yy,ex,ey)){flg=1;}}if (flg) {printf("Case #%d: Yes\n", cas++);} else {printf("Case #%d: No\n", cas++);}}return 0; }

B - Binary Tree

似乎是构造题目。J想了一发，得出可以全部用$1$,$2$,...,$2^k$表示出奇数。而且偶数可以-1变成奇数。然后尝试dp。。。
然后发现对于1变号，相当于-2，其他同理。
于是变成贪心。

#include <bits/stdc++.h>using namespace std; typedef long long ll;int main(){//freopen("in.txt","r",stdin);int T;ll n,k;cin>>T;for(int cas=1;cas<=T;cas++){scanf("%lld%lld",&n,&k);printf("Case #%d:\n",cas);ll s=(1ll<<(k))-1;//cout<<s<<endl;ll t=0;if(n%2==0) n--,t++;for(ll i=0;i<k-1;i++){ll tmp = (s-n)/2/(1ll<<i);//cout<<tmp<<endl;if(tmp%2==0){printf("%lld +\n",1ll<<i);} else {printf("%lld -\n",1ll<<i);s-=1ll<<(i+1);}}ll tmp = (s-n)/2;ll ret = 1ll<<(k-1);if(t) ret++;if(tmp%2==0){printf("%lld +\n",ret);} else {printf("%lld -\n",ret);}}return 0; }

F - Friendship of Frog

#include <bits/stdc++.h> #define maxn 1050 using namespace std; typedef long long ll; int t; char s[maxn]; int Case=1; int main(){//freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%s",s+1);int ans=INT_MAX;int len=strlen(s+1);for(int i=1;i<=len;i++){for(int j=i+1;j<=len;j++){if(s[j]==s[i]) ans=min(ans,j-i);}}if(ans==INT_MAX) ans=-1;printf("Case #%d: %d\n",Case++,ans);}return 0; }

K - Kingdom of Black and White

最多改变一次，枚举计算判断即可。

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5+55; typedef long long ll; char s[maxn]; int cnt[maxn]; ll res,tmp,temp;int main(){//freopen("in.txt","r",stdin);int T,cas=1;cin>>T;while(T--){scanf("%s",s+1);int len=strlen(s+1);cnt[0]=0;res=tmp=0;for(int i=1;i<=len;i++){if(i!=1&&s[i]==s[i-1])cnt[i]=cnt[i-1]+1;else {tmp+=(ll)cnt[i-1]*cnt[i-1];cnt[i]=1;}}tmp+=(ll)cnt[len]*cnt[len];//cout<<tmp<<endl;for(int i=len-1;i>=1;i--){if(s[i]==s[i+1])cnt[i]=cnt[i+1];}// for(int i=1;i<=len;i++)// printf("%d%c",cnt[i]," \n"[i==len]);res=tmp;for(int i=1;i<=len;i++){if(i==1){if(s[i]==s[i+1]) continue;temp=tmp-1-(ll)cnt[i+1]*cnt[i+1];temp+=(ll)((ll)(cnt[i+1]+1)*(cnt[i+1]+1));if(res<temp) res=temp;} else if(i==len){if(s[i-1]==s[i]) continue;temp=tmp-1-(ll)cnt[i-1]*cnt[i-1];temp+=(ll)((ll)(cnt[i-1]+1)*(cnt[i-1]+1));if(res<temp) res=temp;} else {if(s[i]==s[i-1]&&s[i]==s[i+1]) continue;if(s[i]==s[i-1]&&s[i]!=s[i+1]){temp=tmp-(ll)cnt[i]*cnt[i]-(ll)cnt[i+1]*cnt[i+1];temp+=(ll)(cnt[i]-1)*(cnt[i]-1)+(ll)(cnt[i+1]+1)*(cnt[i+1]+1);if(res<temp) res=temp;} else if(s[i]!=s[i-1]&&s[i]==s[i+1]){temp=tmp-(ll)cnt[i]*cnt[i]-(ll)cnt[i-1]*cnt[i-1];temp+=(ll)(cnt[i]-1)*(cnt[i]-1)+(ll)(cnt[i-1]+1)*(cnt[i-1]+1);if(res<temp) res=temp;} else {temp=tmp-1-(ll)cnt[i-1]*cnt[i-1]-(ll)cnt[i+1]*cnt[i+1];temp+=(ll)(cnt[i-1]+1+cnt[i+1])*(cnt[i-1]+1+cnt[i+1]);if(res<temp) res=temp;}}}printf("Case #%d: %lld\n",cas++,res);}return 0; }

L - LCM Walk

不放设$x<y$，那么一定是由$(x,y')$走到$(x,y)$。
并且$(y-y')=lcm(x,y')$，那么两者gcd相等，得到等式$z=\frac{x*y}{x+gcd(x,y)}$。
判断前后gcd相等，不等则break。z表达式得整除（因为1的时候）。

#include <bits/stdc++.h>using namespace std; typedef long long ll; ll ex,ey,lst;ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b); }int main(){//freopen("in.txt","r",stdin);int T,cas=1;cin>>T;while(T--){int cnt = 1;scanf("%lld%lld",&ex,&ey);lst=gcd(ex,ey);while(ex>=1&&ey>=1){if(ex>ey){ll z=(ex*ey)/(ey+gcd(ex,ey));//cout<<ey+gcd(ex,ey)<<endl;ll r=(ex*ey)%(ey+gcd(ex,ey));// cout<<ex<<" "<<ey<<" "<<z<<endl;// cout<<r<<endl;if(r!=0) break;ex-=z;if(gcd(ex,ey)!=lst) break;if(ex>=1) cnt++;} else if(ex<ey){ll z=(ex*ey)/(ex+gcd(ex,ey));ll r=(ex*ey)%(ex+gcd(ex,ey));// cout<<ex<<" "<<ey<<" "<<z<<endl;// cout<<r<<endl;if(r!=0) break;ey-=z;if(gcd(ex,ey)!=lst) break;if(ey>=1) cnt++;} else {break;}}printf("Case #%d: %d\n",cas++,cnt);}return 0; }

转载于:https://www.cnblogs.com/foreignbill/p/7875658.html

总结

以上是生活随笔为你收集整理的2015 ICPC 上海的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。