莫名其妙被Tian-Xing拉过来打计蒜客的tg模拟赛。
一般我都懒得打比赛。但这个题目背景都是点兔的，必打。
然而题目是真的水，水到我这种菜鸡都能2小时AK。。。
至于为啥要写水题笔记，是为了以后便于欣赏点兔的题面复习。
我非常认可所有题面的第一句话。
吐槽：没有千夜！一家人要整整齐齐才好！
炮击
题目
描述
$rize$是一个可爱的女孩子。
一天，$rize$进行了炮击的练习。炮击用的靶子为一个圆，其中有$n−1$个与靶子同心的圆，将靶子划分成了$n$个区域。这些区域里到外从$1$到$n$编号，第$i$个区域的外径为$R_i$。每个区域有一个分数，第$i$个区域的分数为$s_i$。$rize$发射了$m$枚炮弹。在靶平面上的以靶心为原点的直角坐标系下，第$i$枚炮弹击中的区域为一个半径为$r_i$的圆，其圆心的坐标为$(x_i, y_i)$。若一枚炮弹击中的区域与靶子中的某个区域存在交集，则发射这枚炮弹会得到这个区域的分数。这里的区域不包含边界。
$rize$想知道发射每一枚炮弹的得分。
输入输出格式
输入格式
第一行两个数$n, m$；
之后$n$行，每行两个整数$R_i,s_i$；
之后$m$行，每行三个整数$x_i, y_i, r_i$。
输出格式
$m$行，每行一个数表示答案。
样例
输入样例
3 3
1 2
2 2
3 1
3 -1 1
-2 -1 1
2 -4 2
输出样例
1
3
1
数据范围
有$30\%$的数据$n, m \le 1000$；
另有$20\%$的数据$r_i = 1$；
另有$20\%$的数据$s_i = 1$；
对于$100\%$的数据，$1 \le n, m \le 2 \times 10^5$，$1 \le s_i \le 10^4$，$-10^7 \le x_i, y_i \le 10^7$，$1 \le r_i \le 10^7$，$1 \le R_1 < R_2 < \cdots < R_n \le 10^7$。
题解
对分数做个前缀和。求出$(x_i,y_i)$到原点的距离$dis$，$dis-d$的后继记为$l$，$dis+d$的后继记为$r$，答案就是$R_l\sim R_r$的分数和。
一开始手写二分挂了，换成了lower_bound。
很坑的是本机上lower_bound返回了long long，而计蒜客的返回的是int，$\min$函数出锅导致$CE$。。。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int sum[maxn];
double R[maxn];
inline int minn(int x,int y){return x<y?x:y;}
int main(){
int n=read(),m=read();
for(register int i=1;i<=n;++i)R[i]=(double)read(),sum[i]=sum[i-1]+read();
while(m--){
int x=read(),y=read(),ans=0;
double d=(double)read(),dis=sqrt(1ll*x*x+1ll*y*y);
if(dis>d)ans-=sum[lower_bound(R+1,R+1+n,dis-d)-R-1];
ans+=sum[minn(lower_bound(R+1,R+1+n,dis+d)-R,n)];
printf("%d\n",ans);
}
}
出行
题目
描述
$syaro$是一个可爱的女孩子。
$syaro$所在的城市有$n$个街区，街区之间共有$m$条双向通行的道路，且任意两个街区可以通过这些道路互相到达。
一天，$syaro$要带着无数只兔子从$1$号街区走到$n$号街区。由于$syaro$无法管理太多的兔子，于是她决定，如果她经过的道路中存在长度为$w$的道路，那么她出发时只会带不大于$w$只兔子。为了节省时间，她只会在总长度最短的若干条路径中选择一条走。
另外，有$k$个街区由于开了很多咖啡店，整个街区都弥漫着咖啡的气味。由于$syaro$闻到咖啡的气味就会迷失方向，因此她只会从不经过任何一个这样的街区的最短路径中选择一条走。如果所有最短路径都会经过这样的街区，她就会放弃出行。
$syaro$告诉了$cocoa$自己的出行计划。$cocoa$作为一个擅长算术的女孩子，想知道$syaro$最多能带多少只兔子。当然，放弃出行意味着最多能带$0$只兔子。
输入输出格式
输入格式
第一行三个数$n, m, k$；
第二行$k$个数，表示开了很多咖啡店的街区编号；
之后$m$行，每行三个数$u, v, w$，表示有一条从$u$到$v$的长度为$w$的道路。
输出格式
输出一行一个数表示答案。
样例
输入样例
5 8 1
4
1 2 1
3 2 1
3 5 2
1 4 1
4 2 1
2 3 4
2 4 0
3 4 3
输出样例
1
数据范围
对于$10\%$的数据$n, m \le 50$，$m-n \le 10$；
对于$30\%$的数据$n, m \le 10^3$；
对于$60\%$的数据$n, m \le 10^5$；
另有$20\%$的数据$k = 0$；
对于$100\%$的数据$1 \le n, m \le 10^6$，$0 \le k \le n$，$0 \le w \cdot n \le 10^9$。不保证没有重边，保证没有自环。
题解
第一眼：最短路图+最大生成树。
写出来挂了，而且我也并不确定正确性。。。
后来发现自己傻了，最短路的时候每个点记录到该点的最短路的边权最小值的最大值。
感觉题目有歧义：
因此她只会从不经过任何一个这样的街区的最短路径中选择一条走。如果所有最短路径都会经过这样的街区，她就会放弃出行。
我的理解是在原图的最短路中选一条不经过咖啡店的，若都经过则输出$0$。
但也可以理解为在删掉咖啡店后的图上找一条最短路，若此时$1$与$n$不联通输出$0$。
然而两种写法都能过，应该是数据水了。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
priority_queue<pair<long long,int> >q;
long long dis[maxn];
int ma[maxn],h[maxn],fa[maxn],n,num,cnt;
bool co[maxn],vis[maxn];
struct EDGE{
int x,y,l;
bool operator < (const EDGE &X)const{return l>X.l;}
}E[maxn];
struct edge{int pre,to,l;}e[maxn<<1];
inline void add(int from,int to,int l){e[++num]=(edge){h[from],to,l},h[from]=num;}
void DJ1(){
memset(dis,0x3f,sizeof dis);
q.push(make_pair(dis[1]=0,1));
while(!q.empty()){
int x=q.top().second,y;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(register int i=h[x];i;i=e[i].pre){
y=e[i].to;
if(dis[y]>dis[x]+e[i].l)q.push(make_pair(-(dis[y]=dis[x]+e[i].l),y));
}
}
}
void DJ2(){
memset(ma,0x3f,sizeof ma);
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
q.push(make_pair(dis[1]=0,1));
while(!q.empty()){
int x=q.top().second,y;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(register int i=h[x];i;i=e[i].pre){
y=e[i].to;
if(co[y])continue;
if(dis[y]>dis[x]+e[i].l)q.push(make_pair(-(dis[y]=dis[x]+e[i].l),y)),ma[y]=min(e[i].l,ma[x]);
else if(dis[y]==dis[x]+e[i].l)ma[y]=max(ma[y],min(e[i].l,ma[x]));
}
}
}
int main(){
n=read();
int m=read(),k=read();
while(k--)co[read()]=1;
while(m--){
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
DJ1();
long long d=dis[n];
DJ2();
if(d!=dis[n]){puts("0");return 0;}
else printf("%d\n",ma[n]);
}
会和
题目
描述
$cocoa$和$chino$是两个可爱的女孩子。
一天，她们要一起去参观花展。花展有$n$个花田，从$1$到$n$编号，其中花展的出入口在$1$号花田处。任意两个花田之间有且仅有一条路径。每个花田都有一个牌子，牌子上有一个数字，表示从这里回到出入口需要经过的道路数量。每个花田中仅有一种花，参展的花共有$m$种，从$1$到$m$编号。
为了更有趣一些，她们决定先分头行动，各自寻找漂亮的花。到了某个时间，$cocoa$走到了编号为$u$的花田，$chino$走到了编号为$v$的花田。她们决定在返回出入口的路上会合。她们会联系后确认双方所在地的牌子上的数字，数字更大的人会先往出入口方向走，另一个人待在原地。如果数字一样，那么$cocoa$ 走。如果走到了另一个人的所在地，两人就会合了。否则，当走到种着编号为$k$的花的花田或者出入口时，就会停下来，然后重新和另一个人联系，重复之前的过程。
现在她们很好奇，对于不同的$u, v, k$，两人会在哪个花田会合。
输入输出格式
输入格式
第一行三个数$n, m, q$；
第二行$n$个数，第$i$个数表示编号为$i$的花田中种的花的种类的编号；
之后$n-1$行，每行两个数$a, b$，表示编号分别为$a$和$b$的花田之间有一条道路；
之后$q$行，每行三个数$u, v, k$，意义如题目所述。
输出格式
输出$q$行，每行一个数表示会合的花田的编号。
样例
输入样例
8 3 8
3 2 2 2 1 1 1 1
1 2
2 3
3 4
2 5
4 6
2 7
7 8
7 2 1
8 6 3
8 7 1
7 3 1
8 2 3
6 4 1
7 7 1
5 5 1
输出样例
2
1
7
1
2
4
7
5
数据范围
有$30\%$的数据$n, m, q \le 1000$；
另有$20\%$的数据$m = 1$，$n, q \le 2 \times 10^5$；
另有$30\%$的数据$n, q \le 5 \times 10^4$；
对于$100\%$的数据$1 \le n, m, q \le 3 \times 10^5$。
题解
记$x$为$lca(u,v)$。分两种情况：
- $x=u$或$x=v$，答案就是$x$。
- $otherwise$，答案是$x$到根节点第一个颜色为$k$的点。若不存在这样的点答案为根。
没想到什么高论直接强上主席树。
题解给了个离线的线性做法：
虚树也可以搞。
别的题做的都很坎坷，但$T3$我最先切的而且一遍$A$。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 300005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define ls(x) ls[x]
#define rs(x) rs[x]
int ls[maxn<<5],rs[maxn<<5],dat[maxn<<5],root[maxn],m,cnt;
int a[maxn],h[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn],deep[maxn],num;
struct edge{int pre,to;}e[maxn<<1];
inline void add(int from,int to){e[++num]=(edge){h[from],to},h[from]=num;}
void build(int poi,int l,int r,int &node,int ol,int d){
node=++cnt;
if(l==r){dat[node]=d;return;}
int mid=l+r>>1;
if(poi<=mid)rs(node)=rs(ol),build(poi,l,mid,ls(node),ls(ol),d);
else ls(node)=ls(ol),build(poi,mid+1,r,rs(node),rs(ol),d);
}
int ask(int poi,int l,int r,int node){
if(!node)return 0;
if(l==r)return dat[node];
int mid=l+r>>1;
if(poi<=mid)return ask(poi,l,mid,ls(node));
else return ask(poi,mid+1,r,rs(node));
}
void dfs1(int node=1){
siz[node]=1;
build(a[node],1,m,root[node],root[fa[node]],node);
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(siz[x])continue;
deep[x]=deep[node]+1,fa[x]=node,dfs1(x);
siz[node]+=siz[x];
if(siz[x]>siz[son[node]])son[node]=x;
}
}
void dfs2(int node=1){
siz[node]=0;
if(!son[node])return;
top[son[node]]=top[node],dfs2(son[node]);
for(register int i=h[node],x;i;i=e[i].pre){
x=e[i].to;
if(siz[x])top[x]=x,dfs2(x);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y])deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];
return deep[x]<deep[y]?x:y;
}
int main(){
int n=read();
m=read();
int t=read(),x,y,k,z;
for(register int i=1;i<=n;++i)a[i]=read();
for(register int i=1;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
dfs1(),dfs2();
while(t--){
x=read(),y=read(),z=lca(x,y),k=read();
if(x==z||y==z)printf("%d\n",z);
else {
x=ask(k,1,m,root[z]);
printf("%d\n",max(1,x));
}
}
}
