2018CCPC吉林赛区（重现赛）部分题解

前言

一个破计算器能搞出一堆幺蛾子，只能说博主就是个fw。
不管了，所有博主没法处理的就都是不合法操作。博主写了半天就只有一个东西是绝对没有bug的——遇到错误时的处理系统。
既然不想被人看到错误，那就干脆让别人一直都能看到你正确的那部分。

这套题的题目真的是让Jo厨狂喜啊，high到不行。

The Fool(规律)

比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6555

题目大意

请求出${\sum }_i^N[\frac{n}{i}]$的奇偶性，其中[x]为向下取整。

思路

伊奇真的好喜欢波波啊呜呜呜┭┮﹏┭┮

打表找规律，最后会发现这个值的奇偶性与其开方值的奇偶性相同。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;int main()
{int t;int cnt=0;cin>>t;while(t--){cout<<"Case "<<(++cnt)<<": ";int n;cin>>n;n=int(sqrt(n));if(n&1) cout<<"odd"<<endl;else cout<<"even"<<endl;}
}

The World(思维)

比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6556

题目大意

由于各地所属的时区不同，在旅游的过程中算出目的地的地方时显得尤为重要。

现给出四座城市的名称与其地方时的信息：

• 北京(Beijing)，中国首都，地方时为UTC(世界标准时间)+8；
• 华盛顿(Washington)，美国首都，地方时为UTC(世界标准时间)-5；
• 伦敦(London)，英国首都，地方时为UTC(世界标准时间)；
• 莫斯科(Moscow)，俄罗斯首都，地方时为UTC(世界标准时间)+3；

接下来会给出一个时间：XX:XX AM/PM，紧接着给出两个城市的名称A、B。
如果A城市的地方时为XX:XX AM/PM，请问：

城市B的地方时是多少？
城市B相对于城市A是昨天(Yesterday)/今天(Today)/(明天)Tomorrow？

按格式输出"Yesterday/Today/Tomorrow hour:minute AM/PM"。

思路

塑料的『The World』，铁打的『Lovers』。

很简单的一道题，先把A的地方时换算成世界标准时间，然后再换算成B的地方时，中间过程记录是哪一天即可。
不过这题还是挺坑的，它的时间是这样的：

注意一下即可。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
map<string,int> mp;void init()
{mp.clear();mp["Beijing"]=8;mp["Washington"]=-5;mp["Moscow"]=3;mp["London"]=0;
}int main()
{int t;init();int cnt=0;cin>>t;while(t--){string time,noon;string p1,p2;cin>>time>>noon;cin>>p1>>p2;int flag=0,h=0,pos=0;for(;;pos++){if(time[pos]==':') break;h=h*10+time[pos]-'0';}if(noon=="PM"&&h!=12) h+=12;if(noon=="AM"&&h==12) h=0;h=h-mp[p1]+mp[p2];if(h<0){flag=-1;h=24+h;}else if(h>=24){flag=1;h=h-24;}if(h==0) h=12,noon="AM";else if(h<=11) noon="AM";else if(h==12) noon="PM";else h-=12,noon="PM";cout<<"Case "<<(++cnt)<<": ";if(flag==-1) cout<<"Yesterday ";else if(flag==1) cout<<"Tomorrow ";else cout<<"Today ";cout<<h<<time.substr(pos)<<" "<<noon<<endl;}
}

The Tower(计算几何)

比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6559

题目大意

在三维坐标轴上存在一个圆锥。底部圆的圆心为$(0，0，0)$，半径为$r$，圆锥高为$h$。
现在有一个处于$(x_0，y_0，z_0)$的点以$(v_x，v_y，v_z)$的速度运动着。
请问这个点什么时候会撞到圆锥，输出碰撞时间。

思路

最近对这种几何题尤其的上瘾，所以当我看完题目之后整个人都是赛高泥high铁鸭子哒(bushi)。

首先我们假设点$(x_0，y_0，z_0)$与圆锥相撞于点$(x，y，z)$，那么就有：$\{\begin{array}{c}x=x_0+v_{x}t\\ y=y_0+v_{y}t\\ z=z_0+v_{z}t\end{array}$。
接下来取圆锥的纵截面：

由图可知(相似三角形)：$\frac{\sqrt{x^2+z^2}}{r}=\frac{\sqrt{x^2+y^2+(z-h{)}^2}}{\sqrt{r^2+h^2}}$。
等式两边同时平方：$\frac{x^2+z^2}{r^2}=\frac{x^2+y^2+(z-h{)}^2}{r^2+h^2}$。

联立方程组得：
$\{\begin{array}{c}x=x_0+v_{x}t\\ y=y_0+v_{y}t\\ z=z_0+v_{z}t\\ \frac{x^2+z^2}{r^2}=\frac{x^2+y^2+(z-h{)}^2}{r^2+h^2}\end{array}$

所有的字母中只有$t$是未知量，接下来我们就需要开始苦逼的化简过程了。

在博主薅了$20$分钟头发(也许不是头发)之后终于给它化简出来了：
$[h^2(v_x+v_y{)}^2-r^2{v}_z^2-2h^2{v}_x{v}_y]t^2$$+$$[2h^2(v_x+v_y)(x_0+y_0)-2r^2{v}_z(z_0-h)-(2h^2{x}_0{v}_y+2h^2{y}_0{v}_x)]t$$+$$[h^2(x_0+y_0{)}^2-r^2(z_0-h{)}^2-2h^2{x}_0{y}_0]$$==0$
(这要是没求对估摸着我当时就直接脑溢血爬不出机房了)

这就变成了一个简 单的一元二次方程式了：$\{\begin{array}{c}a=h^2(v_x+v_y{)}^2-r^2{v}_z^2-2h^2{v}_x{v}_y\\ b=2h^2(v_x+v_y)(x_0+y_0)-2r^2{v}_z(z_0-h)-(2h^2{x}_0{v}_y+2h^2{y}_0{v}_x)\\ c=h^2(x_0+y_0{)}^2-r^2(z_0-h{)}^2-2h^2{x}_0{y}_0\end{array}$

这样就可以求出两个$t$值，接下来只需要判断$t$值是否合理，合理的话取最小值即可。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
double r,h,x,y,z,vx,vy,vz;
bool judge(double t)
{double x_z=x+t*vx;double y_z=y+t*vy;double z_z=z+t*vz;if(z_z>=0&&z_z<=h&&x_z*x_z+y_z*y_z<=r*r)return true;else return false;
}
int main()
{int t,cnt=0;scanf("%d",&t);while(t--){//11scanf("%lf%lf",&r,&h);scanf("%lf%lf%lf%lf%lf%lf",&x,&y,&z,&vx,&vy,&vz);double a,b,c;a=h*h*(vx+vy)*(vx+vy)-r*r*vz*vz-2*h*h*vx*vy;b=2*h*h*(vx+vy)*(x+y)-2*r*r*vz*(z-h)-(2*h*h*x*vy+2*h*h*y*vx);c=h*h*(x+y)*(x+y)-r*r*(z-h)*(z-h)-2*h*h*x*y;double t1=(-b+sqrt(b*b-4*a*c))/(2.0*a);double t2=(-b-sqrt(b*b-4*a*c))/(2.0*a);double ans=inf;if(judge(t1)) ans=min(ans,t1);if(judge(t2)) ans=min(ans,t2);printf("Case %d: %.10f\n",++cnt,ans);}
}

几何题做起来是真的太上头了。

Strength(贪心)

比赛链接：https://acm.dingbacode.com/showproblem.php?pid=6563

题目大意

(找了半天没找到色猩猩对应的那一帧，就乎着看吧)

现在$Alice$有$n$个小兵，每个小兵的攻击力为$a_i$。
$Bob$有$m$个小兵，每个小兵的攻击力为$b_i$。

当$A$小兵(攻击力为$x$)进攻$B$小兵(攻击力为$y$)的时候会出现以下情况：

1. $B$小兵处于防御姿态，$x<y$。 =>$A$小兵死亡，$B$小兵毫发无伤；
2. $B$小兵处于防御姿态，$x>=y$。 =>$A$小兵死亡，B小兵死亡；
3. $B$小兵处于进攻姿态，$x<y$。=>$A$小兵死亡，$B$小兵毫发无伤，$A$小兵的主人受到$y-x$点伤害；
4. $B$小兵处于进攻姿态，$x>=y$。=>$A$小兵死亡，$B$小兵死亡，$B$小兵的主人受到$x-y$点伤害；

一旦主人没有小兵可以用的时候，对方接下来的进攻都会直接对主人造成伤害。
一开始所有的小兵都是进攻姿态。

接下来是$Alice$的进攻时间，$Bob$把他手下的一部分小兵改为防御姿态。
请问$Alice$最多可以对$Bob$造成多少伤害？

思路

贪心，分情况讨论。

一.只揍Bob的进攻姿态小兵。

如果我们打防御姿态的小兵，就算打赢了，也不会对$Bob$造成伤害，还会废掉我们的一个小兵，不是很划得来。
所以我们把主力全部用在打$Bob$的进攻姿态小兵上面，贪出最大伤害值。

二.杀掉Bob所有的兵。

如果我们有能力把Bob的兵全部干掉，这样我们剩下的兵就可以造成真实伤害，是有可能造成一个很高的伤害值的。
这样的话我们就要考虑如何处理Bob的防御兵了。我们要尽可能地用和其防御兵攻击力差不多的兵来完成自爆行动，这样的话最佳的处理方式就是lower_bound。
但一个兵只能用一次，所以还要记录一下自己哪些兵是在清理Bob所有的兵时所用的。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
struct node
{int x,y;
}b[maxn];int a[maxn];
bool vis[maxn];bool cmp(node z,node c)
{if(z.y!=c.y)return z.y<c.y;elsereturn z.x<c.x;
}int main()
{int t,cnt=0;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i],vis[i]=false;for(int i=1;i<=m;i++)cin>>b[i].x;for(int i=1;i<=m;i++)cin>>b[i].y;sort(a+1,a+1+n);sort(b+1,b+1+m,cmp);int maxx=-inf;int ans=0;int pos1=n,pos2=1;while(b[pos2].y==0) pos2++;pos2--;while(pos1&&pos2){if(a[pos1]>b[pos2].x)ans+=a[pos1]-b[pos2].x;elsebreak;pos1--,pos2--;}maxx=max(ans,maxx);ans=0;pos1=n,pos2=m;int flag=1;while(b[pos2].y==1){int pos=lower_bound(a+1,a+1+n,b[pos2].x)-a;while(vis[pos]&&pos<=n) pos++;if(pos==n+1){flag=0;break;}vis[pos]=true;pos2--;}if(flag){while(pos1&&pos2){if(vis[pos1]){pos1--;continue;}if(a[pos1]>b[pos2].x) //这里还是可以贪伤害的ans+=a[pos1]-b[pos2].x,pos1--,pos2--;else{flag=0;break;}}if(flag){while(pos1){if(vis[pos1]){pos1--;continue;}ans+=a[pos1];pos1--;}}maxx=max(maxx,ans);}cout<<"Case "<<(++cnt)<<": "<<maxx<<endl;}
}

后话

感谢阅读，希望能对你产生一点用处。

以下台词取自《银魂：完结篇·永远的万事屋》：
(每次看这一段的时候都会疯狂的起鸡皮疙瘩+落泪，真的是太燃了，配合着『現状ディストラクション』的BGM)
(SPYAIR，yyds!)