莫名其妙被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));
        }
    }
}