V2AS问路
2021ICPC网络赛第一场部分题解-The 2021 ICPC Asia Regionals Online Contest (I)
阅读原文时间：2021年09月20日阅读：1

写在前面

本来应该6题的，结果不知道哪个铸币发了H的clar，当即把我们的思路转向三维几何上。当时我们还在想这三维计算几何的正确率有点太高了还在感叹ICPC选手的含金量，直到赛后我才知道这H题的铸币出题人压根不想让我们知道他脑子里在想什么。还好赛时将机位让给了队友写A，不然抄了你吗半天的三维计算几何最后WA那真的是心态炸了。

其他题倒是没啥好说的，就是这H越想越气，有这瞎琢磨的时间去开个B或者C说不定又能++rank。

真的气。不过突然之间看到F。哦，出题人是原*啊，那就说得通了。

A Busiest Computing Nodes

队友写。一开始直接交了发暴力TLE，后来在我想H的时候，用线段树维护下就过了。

这里要提一嘴lexicographic了。由于三个大傻子都没带字典而且英语水平不够，于是直接交了个大小顺序，过了。后来看Clar不明白为啥要特意说不是字典序。

赛后查了下直接笑出声。

不是你但凡提下dict我们也能懂啊。搁这考专八呢。

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;
const LL N=100010;
LL t[N*8],a[N*2];
LL n,k;

LL query(LL l,LL r,LL p,LL x,LL y)
{
    if(x<=l&&r<=y)
        return t[p];
    LL mid=l+r>>1;
    if(y<=mid)
        return query(l,mid,p<<1,x,y);
    if(x>mid)
        return query(mid+1,r,p<<1|1,x,y);
    return min(query(l,mid,p<<1,x,y),query(mid+1,r,p<<1|1,x,y));
}

void modify(LL l,LL r,LL p,LL x,LL y)
{
    if(l==r)
        return void(t[p]=y);
    LL mid=l+r>>1;
    if(x<=mid)
        modify(l,mid,p<<1,x,y);
    if(x>mid)
        modify(mid+1,r,p<<1|1,x,y);
    t[p]=min(t[p<<1],t[p<<1|1]);
}

int main()
{
    scanf("%lld%lld",&k,&n);
    LL res=0;
    for(LL i=0;i<n;++i)
    {
        LL arr,pro;
        scanf("%lld%lld",&arr,&pro);
        LL l=i%k+1,r=i%k+k;
        if(query(1,2*k,1,l,r)>arr)
            continue;
        while(l<r)
        {
            LL mid=l+r>>1;
            if(query(1,2*k,1,l,mid)<=arr)
                r=mid;
            else l=mid+1;
        }
        modify(1,2*k,1,l,arr+pro);
        modify(1,2*k,1,(l+k-1)%(2*k)+1,arr+pro);
        res=max(res,++a[(l-1)%k+1]);
    }
    bool flag=false;
    for(LL i=1;i<=k;++i)
        if(a[i]==res)
            if(flag)
                printf(" %lld",i-1);
            else
            {
                printf("%lld",i-1);
                flag=true;
            }
    return 0;
}

B Convex Polygon

比赛时候没开，回来看了下是裸的二维凸包。虽然学过但是比赛没看到也是没用。但是好像要判断什么输入是否正确我就觉得离谱，算法竞赛还要考察ROBUST的嘛？MARK下，回头补。

D Edge of Taixuan

队友写，图+线段树？

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int N=100010;
struct Edge
{
    int l,r,w;
    bool operator < (const Edge &W) const
    {
        return w<W.w;
    }
}e[N];
struct Node
{
    LL idx,pri;
}tr[N*4];
int n,m,t;

void pushdown(int p)
{
    tr[p<<1]=tr[p];
    tr[p<<1|1]=tr[p];
    tr[p]={0,0};
}

void modify(int l,int r,int p,int x,int y,int z,int w)
{
    if(x<=l&&r<=y)
        return void(tr[p]={z,w});
    if(tr[p].idx)
        pushdown(p);
    int mid=l+r>>1;
    if(x<=mid)
        modify(l,mid,p<<1,x,y,z,w);
    if(y>mid)
        modify(mid+1,r,p<<1|1,x,y,z,w);
}

LL query(int l,int r,int p)
{
    //cout<<l<<' '<<r<<' '<<p<<' '<<tr[p].idx<<' '<<tr[p].pri<<endl;
    if(tr[p].idx)
        return (LL)(r-l+1)*tr[p].pri;
    if(l==r)
        return 0;
    int mid=l+r>>1;
    LL res=query(l,mid,p<<1)+query(mid+1,r,p<<1|1);
    return res;
}

bool cmp(Edge &a,Edge &b)
{
    return a.l<b.l;
}

bool judge()
{
    sort(e+1,e+m+1,cmp);
    int l=e[1].l,r=1;
    for(int i=1;i<=n;++i)
    {
        if(e[i].l>r)
            return false;
        r=max(e[i].r,r);
    }
    return e[1].l==1&&r==n;
}

int main()
{
    bool _=false;
    scanf("%d",&t);
    for(int i=1;i<=t;++i)
    {
        memset(tr,0,sizeof tr);
        LL res=0;
        scanf("%d%d",&n,&m);
        for(int j=1;j<=m;++j)
        {
            scanf("%d%d%d",&e[j].l,&e[j].r,&e[j].w);
            res+=(LL)(e[j].r-e[j].l+1)*(e[j].r-e[j].l)/2*e[j].w;
        }
        sort(e+1,e+m+1);
        for(int j=m;j>=1;--j)
            modify(1,n,1,e[j].l+1,e[j].r,e[j].l,e[j].w);
        if(_)
            puts("");
        _=true;
        if(judge())
        {
            res-=query(1,n,1);
            printf("Case #%d: %lld",i,res);
        }
        else
            printf("Case #%d: Gotta prepare a lesson",i);
    }
    return 0;
}

F Land Overseer

看着样例就直接猜中垂线(也就是(a,b-r)这个点，以及它和(2a,0)的连线和第二个圆的交点)，于是直接输出2_sqrt(a_a+(b-r)*(b-r))-r交一发WA。后来就开始用纯数学方法计算距离方程，结果是不管用什么方法都做不出来，最主要的是其他比较合理的猜想都验证不了样例这个数据。最后思路回到原点，发现假如A圆的最低点低于X轴，也就是b<=r的时候，直接沿x轴走到圆B更近，遂加上特判，AC。这题不需要考虑两圆相交，O在圆内之类的情况，因为条件已经将其排除。所以还是相当简单的题目

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;cin >> t;
    for (int i = 1;i <= t;++i) {
        long long a,b,r;
        cin >> a >> b  >> r;
        cout <<"Case #" << i << ": ";
        if(b > r)
            printf("%.2lf\n",2 * sqrt(a * a + (b-r) * (b - r)) - r);
        else printf("%.2lf\n", (double)(2*a - r));
    }
    return 0;
}

H Mesh Analysis

在给Clar之前，读完题我说：这neighboring不会是和它一起构成这个图形的点吧。看了Clar，哦，原来要考虑在三角形内部的点啊，还是三维，挺难的。遂开始抄板子……

用set保存每个点相连的点以及属于的图形即可（因为会重复），最好用unordered_map映射下，谁知道id范围是多少呢。

对，这题2~n+1行的输入完全没用。服了。

输出要稍微考虑下，注意最后不能空行，空集输出[]，也不是很难。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

unordered_map<ll,set<ll> > belongel;
unordered_map<ll,set<ll> > belongpo;

int main() {
    int n,m;
    cin >> n >> m;
    for (int i = 0;i < n;++i) {
        ll id;
        double x,y,z;
        cin >> id >> x >> y >> z;
    }

    for (int i = 0;i < m;++i) {
        ll id,idx;
        cin >> id >> idx;
        if (idx == 102) {
            ll x,y;
            cin >> x >> y;
            belongpo[x].insert(y);
            belongpo[y].insert(x);
            belongel[x].insert(id);
            belongel[y].insert(id);
        }else{
            ll x,y,z;
            cin >> x >> y >> z;
            belongpo[x].insert(y);
            belongpo[x].insert(z);
            belongpo[y].insert(x);
            belongpo[y].insert(z);
            belongpo[z].insert(x);
            belongpo[z].insert(y);

            belongel[x].insert(id);
            belongel[y].insert(id);
            belongel[z].insert(id);
        }
    }

    int L;cin >> L;
    bool fir = 1;
    while (L--) {
        if (fir){
            fir = false;
        }else{
            cout << endl;
        }

        ll id ;cin >> id;
        cout << id << endl;
        bool _ = true;
        //point
        set<ll> &outt = belongpo[id];
        if (outt.empty()){
            cout <<"[]\n";
            _ = false;
        }
        if (_){
            cout << '[';
            for (auto it : outt) {
                if (it != *outt.begin())    cout << ',';
                cout << it;
            }
            cout << "]\n";
        }

        _ = true;

        set<ll> &oute = belongel[id];
        if (oute.empty()) {
            cout << "[]";
            _ = false;
        }

        if (_){
            cout << '[';
            for (auto it : oute) {
                if (it != *oute.begin())    cout << ',';
                cout << it;
            }
            cout << ']';
        }
    }
    return 0;
}

第一个A的题目。题意：在数轴上找到被A为圆心，R为半径包围且属于集合S的元素（除它自己）。这题关键是输入，我们想了个办法，先while(cin >> x)读到eof，并且记录个数n，然后最后两个数拎出来为A和R，最后排序前n-2个元素找就行了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
long long tmp[maxn];
long long a[maxn];
int main() {
    int n = 0;
    long long x;
    while (cin >> x) {
        tmp[n++] = x;
    }

    n = n - 3;
    sort(tmp,tmp+n+1);
    long long A = tmp[n + 1];
    long long r = tmp[n + 2];
    //cout << A << ' ' << r << endl;
    bool f = false;

    for (int i = n;i >= 0;--i) {
        if (tmp[i] <= A + r && tmp[i] >= A - r) {
            cout << tmp[i] << ' ';
            f = true;
        }
    }

    if(!f) cout << '\n';

    return 0;
}

K Segment Routing

队友写，应该是图的遍历（？），反正是模拟。题目太长压根没看，（其实是没学过计网）

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N=100010,M=2000010;
int t,n,m,h[N],e[M],d[N],r[N];

int main()
{
    scanf("%d",&t);
    bool _=false;
    for(int i=1;i<=t;++i)
    {
        if(_) puts("");
        _=true;
        printf("Case #%d: ",i);
        scanf("%d%d",&n,&m);
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&d[j]);
            h[j]=h[j-1]+d[j-1];
            for(int k=1;k<=d[j];++k)
                scanf("%d",&e[h[j]+k-1]);
        }
        for(int j=1;j<=m;++j)
        {
            int s,l;
            scanf("%d%d",&s,&l);
            for(int k=1;k<=l;++k)
                scanf("%d",&r[k]);
            bool flag=true;
            for(int k=1;k<=l&&flag;++k)
            {
                if(r[k]>d[s])
                    flag=false;
                s=e[h[s]+r[k]-1];
                if(s>n)
                    flag=false;
            }
            puts("");
            if(flag)
                printf("%d",s);
            else
                printf("Packet Loss");
        }
    }
    return 0;
}

总结

下场总不是华为出题了吧。XCPC今年太梦幻了。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章

【Codeforces Beta Round #45 D】Permutations
P4754 True Vegetable
扩展kmp入门+比赛模板

4

KMP算法基础分析讲解（5分钟包教包会）

5

Strength(HDU6563+2018年吉林站+双指针瞎搞)

6

树链剖分详解

7

【BZOJ4173】数学 欧拉函数神题

8

ACM 逆序对（逆序数）总结

9

BZOJ 3744: Gty的妹子序列 【分块求区间逆序对】

10

Nowcoder 7.E 珂朵莉的数列 逆序数,BIT