C2020 2020.11.1模拟赛

信息学——模拟赛

比赛情况

期望得分VS实际得分

期望得分：

实际得分：

T1 haybales

$1^o$ 分析

考虑对于一组询问，我们考虑将给出的左右端点对应到数组上，将两个下标相减。

将数组排序，二分出第一个小于$l$的$lnum$（类似前缀和，所以要求下小于），二分出第一个小于等于$r$的$rnum$

$rnum-lnum$即为答案。

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,q;
int a[100005];
inline int find_l(int x)
{
    int l=0,r=n+1;
    while (l+1<r)
          {
          int mid=(l+r)>>1;
          if (x>=a[mid])
             l=mid;
          else
             r=mid;
          }
    return l;
}
inline int find_r(int x)
{
    int l=0,r=n+1;
    while (l+1<r)
          {
          int mid=(l+r)>>1;
          if (x<a[mid])
             r=mid;
          else
             l=mid;
          }
    return l;
}
int main(){
    n=read(),q=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    for (register int i=1;i<=q;++i)
        {
        int l=read(),r=read(),lnum=find_l(l),rnum=find_r(r);
        if (a[lnum]==l)
           lnum--;
        printf("%d\n",rnum-lnum);
        }
    return 0;
}

$2^o$ 反思与总结

开始被某$@woshiSB$搞了心态，闭着眼睛码了个离散化+树状数组，然后发现排序二分就行了，裂开。

T2 states

$1^o$ 分析

因为只考虑前两位，考虑将城市名也只取前两位，开一个$map$，记录对应的数量，每次$mapp[(name,shen)]++$。

这里第一个坑点，不能用$bool$，可能有多个城市的前两位相同但名字不同。

然后当前贡献就是反过来，即$mapp[(shen,name)]$。

这里第二个坑点：如果城市的前两位和名字的前两位相同则不能算进答案中（如$NBA$与$NB$，会统计多）。

所以如果当前$name=shen$，就把$ans-=mapp[(name,shen)]$就好。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
int name,shen,ans;
map <pair <int,int>,int> mapp;
int main(){
    n=read();
    string cnt;
    for (register int i=1;i<=n;++i)
        {
        cin>>cnt;
        name=(cnt[0]-'A'+1)*26+(cnt[1]-'A'+1);
        cin>>cnt;
        shen=(cnt[0]-'A'+1)*26+(cnt[1]-'A'+1);
        ans+=mapp[mp(shen,name)];
        if (name==shen)
           ans-=mapp[mp(name,shen)];
        mapp[mp(name,shen)]++;
        }
    printf("%d",ans);
    return 0;
}

$2^o$ 反思与总结

题面翻译有那么亿点点问题，不过好像还是有人切了？？？

T3 moocast

$1^o$ 分析

考虑对每两个点都连一条边，边权为这两点的距离。

对于每个点跑$dfs$，算出能到达的点数，取$max$即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
struct Point{
    double x,y,p;
}point[205];
struct node{
    int v,nex;
    double w;
}edge[80005];
int head[205],len;
int vst[205],tot,ans;
inline void make_map(int u,int v,double w)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    edge[len].w=w;
    head[u]=len;
}
inline double calc(Point x,Point y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline void search(int x)
{
    vst[x]=1,tot++;
    for (register int i=head[x];i;i=edge[i].nex)
        {
        int y=edge[i].v;
        double z=edge[i].w;
        if (vst[y])
           continue;
        if (z>point[x].p)
           continue;
        search(y);
        }
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i) 
        scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].p);
    for (register int i=1;i<=n;++i)
        for (register int j=1;j<=n;++j)
            make_map(i,j,calc(point[i],point[j]));
    for (register int i=1;i<=n;++i)
        {
        memset(vst,0,sizeof(vst)),tot=0;
        search(i),ans=max(ans,tot);
        }
    printf("%d",ans);
    return 0;
}