ICPC 2018 EC-Final游记


强行续了一场比赛,打乱了我寒假前的复习、自学的计划2333

day -x

感觉EC的机会还是挺难得的,于是VP了两年的EC,都是银……VP以外我主要就是改题补题,然后那段时间被一些事缠身,再加上成天写题,越来越自闭,不过好在在出发前一天缓过神来了,算是比较积极开朗地踏上了西安之旅。
话说回来,一开始本来和SR是打算考完四级再去的,因而没有和大家一起买机票。但是,考虑到四级可以再考,免费的西安旅游机会可并不多,就毅然决然地翘掉了四级。
我一直向往西安碑林,许多小时候练过的原碑陈列在那里。因此,我打算周五下午去了之后直奔碑林朝圣。
结合我和SR的旅游路线规划,发现飞机其实不如高铁舒适。高铁到西安北站,直接二号线可以到我心心念念的碑林,但是坐飞机的话,虽然路上时间短,但是需要坐公交从市郊的咸阳机场到市里,最后可能到碑林的时间比坐高铁还长。于是我们买了高铁票。
但是,在某y姓人士的极力劝说下,我最终承受不了,撺掇SR改成了机票。

day -1

叫的10座商务车,司机貌似非常晕,费了好大的劲才找到了学校。去机场的路上,还走错调头数次。惴惴不安之中我们好歹是顺利到了机场。然而司机把我们带到了地下车库让我们下车,又走了一段才到了航站楼门口……
飞达咸阳机场以后,我们坐的机场大巴又在路上堵得走不动,等到了小寨已经接近四点了。
到宾馆办好入住之后,一个人出发了。

第一个让我激动的是颜体的地铁站牌。进站之后,发现地铁站的石柱上居然刻着一些仿古的图样。在永宁门站下车,在去碑林的路上还看到了绵延的古城墙。不过粗略一看应该是最近刚刚修缮过,看起来挺新的…
路上还经过了一个类似于文玩街的地方……强行克制住买毛笔的冲动……

然后就到了碑林

这里人很少,正合我意。
第一个展厅里面放了一些四书五经的碑刻毫无吸引力。
第二个展厅里面有多宝塔、玄秘塔和怀仁圣教序。我一直特别喜欢多宝塔的一板一眼的结构和比较劲道硬朗的笔画,小学的时候也尝试练过一段时间,但当时手上功夫太弱并不能出什么效果。不过,虽然我对多宝塔碑较为熟悉,看到原碑还是对我产生了很大的震撼,感觉与刻碑的匠人和书写的书法家的距离一下子拉近了💗刚刚看到矗立着的多宝塔碑时,我不由得兴奋地跳了起来
第三个展厅里有我最想看的勤礼碑。从六岁到十岁,这里面这些字被我临摹了至少四年。站在这块碑前,像是面对着一位熟知已久却未曾谋面的老朋友,回忆如潮水一般涌来。看完了剩下的熟悉的曹全碑、瘦金体、各种墓志之后,我又回到了这块碑前,站到脚被冻得发僵。

在怀着对北京的向往来到了北京之后,在同学的启发下,才发现北京其实并不一定是唯一的选择。选择一个城市并不只是选择工作,也是选择城市的气质、环境、宜居程度。我还是到过的城市太少了……我觉得,西安,就会是一个我愿意常来的地方。

离开碑林,在那条文玩街上买了一份赵孟頫心经的拓片。虽然号称是拓片,墨香很浓、字也是凹进去的,但我觉得这些碑应该不会让人随便去拓吧。

街边随便吃了个肉夹馍,然后想去找家SONY体验店去试一试wh-h800。地图上找了家最近的,进商场之后找了很久,倒是有BOSE和B&O,就是没找到SONY。无奈之下问了一下服务台,得知这里只有SONY电视没有耳机。再见。

感觉就吃一顿很不值,就问了一下在XJTU的江志东有什么好吃的地方,然后他邀请我去找他请我吃。于是,费尽周折找到了站台,又在晚高峰的公交车上挤到变形,终于到了又一个圣地——原JTU。
不过XJTU里面好像没有很多可以膜的地方,而且校园也并不怎么大(当然比小破邮大不少)。江志东请我吃了顿灌汤包,还让我尝到了西安的特色果啤,还让我试了试他的我心心念念已久的dpt-rp1——不过讲真,书写的延迟真是挺大的。还学习到了南苑机场是中国的第一个机场,而且明年就要停运了,北京城里没有飞机场了……

day 0

早晨在KFC吃了一顿,感觉不饱,就又去dicos吃了个汉堡。去nwpu的长安校区实在很远,我们坐地铁到了终点站,又在校车上颠簸了挺久,才到了坐落在秦岭脚下,麦田中央的nwpu。
报到的时候发现每个人都有书包,而且比赛的服装比较好看。而且报道的时候还给每个队伍录了一小段视频,像World Final那样。我和SR一起把PY的刘海捋了起来露出了他充满智慧的脑门😄。期待着视频放出来。
报道完之后,碰上俩采访的,杨老师让一队和我们去接受采访。在采访过程中,PY口出狂言:如果我们三个都超常发挥,我们是有实力夺金的!站在一边的我听得鏼鏼发抖。
食堂实在是弄得不大好。只开了两个窗口,只能打几个普通的小菜,还做的并不好吃,和桂电食堂有一拼。看着本校那些人吃着各种好吃的,感觉非常不爽。

在开幕式上碰到了Menci和牛神,得知RUC CS的男女比例3:7,和北航全校的男女比例正好互为倒数233333
试机赛总体打的很迷,我个人很不在状态。感觉很虚。
ECNU的One,Two,Three,AK队坐的离我们很近,发现那支队里居然有个可爱的小姐姐,而且还很野,他们背后的大连理工队伍没来,她就上去敲他们的电脑!

晚饭是杨老师在nwpu的一个朋友推荐的饭店吃的,吃到了久违的凉皮,感觉非常怀念。吃饭的时候月加聊了来年的训练计划,聊了他们当年因为出题太忙耽误训练的一些教训……吃的过程中对面桌上不停传来y哥洪亮的声音,他还时不时跑到我们这桌要和我们唠嗑23333

晚上在温泉酒店,有一个叫PingCAP的公司是比赛的赞助商,在酒店做抽奖活动,而PingCAP的创始人之一是bupt的学长。他对我们很热情,送给我们一人一个纪念U盘,我们也就一直在楼下给他们捧场。在抽奖结束之后,还给了我们一些多余的奖品,看他们的文案貌似工作环境挺不错的!

day 1(终于写到day1了)

问了ST_Saint和fqk,都表示丝毫不慌。我怎么就这么慌呢!!!!

开场南大4分钟过了D,还没反应过来,一堆队伍疯狂过D。我拿过D来一看,感觉好像就是分n,m大小关系输出就行了,然后读入的n+m个数字无关???白读入这种操作我还真是没怎么见过,所以有点怂,就让SR去写。写完之后还是怂,但是SR一拍大腿,说:这么多队都过了,交吧!然后就过了。
接着发现L有一堆队伍过了,看了看题分析了一下,SR感觉差不多就去写了。我不大懂他的具体想法,于是在一边又推了一遍具体做法以防万一。此时根据试机赛的气球颜色提示盯上了G,和PY一起研究G。结果SR写了一会儿L发现不行,我就上去把我的做法写完过掉了。
写完L之后得知F是个计算几何,讨论了一下发现应该就两条切线+一段弧长,SR提供了三维转二维的思路,于是接着上手写了。写完之后交了一发WA了,发现把一个sqr写成了sqrt……改掉之后,三个人又一起手出了几组数据,交上去A了。
接着榜上显示最可做的题目是I,而SR和PY都已经自闭好久了……这破玩意想最短路建不出图,想DP有后效性,三人一起自闭的很欢畅。看着一支支队伍暴过I题,我开始突发奇想,出了一个贪心,PY把我的贪心否了,又结合我的思路又出了一个贪心,也被我否了,我又结合这个思路出了一个贪心,三个贪心写完之后取max可以过样例。然后,按照SR的理论,小范围数据可以精心手造,于是小范围判了个DFS+剪枝。然后心怀梦想地交了一发,刷出来CORRECT的一刻我们三个不由得大声喊*
过掉I之后是rank 70+,本来以为得再过一题才能保住银,然而当继续多线程自闭了一个小时之后,封榜前排名是75。
封榜之后绝望中开始读大模拟H题。读完之后写了二十分钟发现太麻烦了根本写不动。。剩下半个多小时PY打表找规律,我和SR搞C,但根本没什么戏了——封榜前自闭一个小时都不会怎么可能半个小时想出来写完。结束之前写了个乱搞随便交了几发,本赛季最后一场比赛就这么结束了。

总结

三个银结束大学的第一个赛季,也还可以吧。
因为水平没那么强,一直怕打铜,最终还是成功凭借RP苟过了三场比赛。除了ccpc桂林的银比较稳之外,沈阳精准卡线,EC贪心过题,都有很大的运气成分吧。
一队今年没出线,心里也是挺压抑的。也许可以指望下个赛季能出现大腿?毕竟RJJ的WF红利马上就要到期了,如果明年还是进不了WF,以后的ICPC名额可能就比较尴尬了。
过年以后,该好好训练还是要好好训练,下个赛季奔着金牌去吧。
开始准备期末考试了……可能考前就不再研究竞赛了

[EC-Final 2017H]Mr. Panda and Birthday Song

Link

Solution

两次dp,一次尽量符合要求,一次尽量不符合要求,即一次让连续的元音、辅音尽量长,一次让连续的辅音元音尽量短,判断判断就能转移出来了。

Code

const int XN=1e6+11,INF=0x1f1f1f1f;

int main() {
    int T;fin>>T;
    const char *Ans[]={"LIKE","SURPRISE","DISLIKE"};
    std::set<char> vowels({'a','e','i','o','u'});
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        static char s[XN];
        int x,y;
        fin>>(s+1)>>x>>y;//x vow y non-vow
        int n=strlen(s+1);
        static int f[XN][2];
        int type=0;
        for(int i=1;i<=n;++i) {
            f[i][0]=f[i][1]=-1;
            if(s[i]=='?') {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            } else if(vowels.count(s[i])) {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
            } else {
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            }
            if(f[i][0]==y)
                f[i][0]=-1;
            if(f[i][1]==x)
                f[i][1]=-1;
            if(f[i][0]==-1 && f[i][1]==-1) {
                type=2;
                break;
            }
        }
        if(type!=2) {
            for(int i=1;i<=n;++i) {
                f[i][0]=f[i][1]=-1;
                if(s[i]=='?') {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                } else if(vowels.count(s[i])) {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                } else {
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                }
                if(f[i][0]==y || f[i][1]==x) {
                    type=1;
                    break;
                }
            }
        }
        puts(Ans[type]);
    }
    return 0;
}

[ECL-Final 2017D]Mr. Panda and Geometric Sequence

Link

Solution

x划分出的前三项为a[1],a[2],a[3],则a[1]a[2]a[3]=a[2]^3\le x\le 10^{15}a[2]\le 10^5

Code

std::vector<long long> nums;
void Prep() {
    const int N=1e5;
    const long long UP=1e15;
    //k*p*q
    auto Join=[](long long a,long long b)->long long {
        for(long long x=b;x;x/=10)
            if((a*=10)>UP)
                return UP+1;
        return a+=b;
    };

    for(long long p=1;p<=N;++p)
        for(long long q=p+1;p*q<=N;++q)
            if(std::__gcd(p,q)==1) {
                for(long long k=1;k*p*q<=N;++k) {
                    long long x=Join(Join(k*p*p,k*p*q),k*q*q),a=k*q*q;
                    while(x<=UP) {
                        nums.push_back(x);
                        if(a*q%p)
                            break;
                        else
                            x=Join(x,a=a*q/p);
                    }
                }
            }
    std::sort(nums.begin(),nums.end());
    nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
}

int main() {
    Prep();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long l,r;fin>>l>>r;
        auto Solve=[&](long long x) {
            return std::upper_bound(nums.begin(),nums.end(),x)-nums.begin();
        };

        fout<<Solve(r)-Solve(l-1)<<'\n';
    }
    return 0;
}

[ECL-Final 2017 G]Image Recognition

Link

Solution

最开始的想法是,把每次的询问中相邻两个串找到一个不同的位置就能区分开。然而,“不同”关系不具有传递性。如何才能让A、B不同,B、C不同,那么A、C就不同?考虑把01串排序,也将询问的串排序。那么设A、B第一个不同的位置为i。由于A<B,则A[i]=0,B[i]=1,C[i]=1,由此推出了A、C不同。

Code

暴力的实现:

const int XN=2e3+11,XM=4e5+11;

struct BitSet {

    static int BW;

    unsigned long long s[(XM>>6)+1];

    void Set(unsigned int pos,bool val) {
        val==0?(s[pos>>6]&=~(1ull<<(pos&63))):(s[pos>>6]|=1ull<<(pos&63));
    }

    static int XorFirst1(BitSet const &a,BitSet const &b) {
        for(int i=0;i<BW;++i) {
            unsigned long long x=a.s[i]^b.s[i];
            if(x)
                return 64*i-1+__builtin_ffsll(x);
                    //(x&(-1u)?__builtin_ffs(x&(-1u)):__builtin_ffs(x>>32)+32);
        }
        return -1;
    }

    void Reset() {
        for(int i=0;i<BW;++i)
            s[i]=0;
    }
}b[XN];
int BitSet::BW;

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        BitSet::BW=(m>>6)+1;
        static std::pair<std::string,int> c[XN];
        for(int i=0;i<n;i++){
            std::cin>>c[i].first;
            c[i].second=i;
        }
        std::sort(c,c+n);
        static int ref[XN];
        for(int i=0;i<n;++i) {
            ref[c[i].second]=i;
            b[i].Reset();
            for(int j=0;j<m;j++)
                b[i].Set(j,c[i].first[j]=='1');
        }
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i) {
                fin>>a[i];
                a[i]=ref[a[i]];
            }
            std::sort(a,a+cnt);
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=BitSet::XorFirst1(b[a[i]],b[a[i+1]]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

Hash+二分
从CF上学来的做法。注意这是01串,可以将字符串的hash转化成集合的hash。

const int XN=2e3+11,XM=4e3+11;

int main() {
    srand(233);
    static unsigned long long h[XM];
    for(int i=0;i<XM;++i)
        h[i]=(unsigned long long)rand()<<32|rand();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        static unsigned long long hash[XN][XM];
        static char s[XN][XM];
        static int seq[XN],rank[XN];
        for(int i=0;i<n;++i) {
            fin>>s[i];
            hash[i][0]=s[i][0]=='1'?h[0]:0;
            for(int j=1;j<m;++j)
                hash[i][j]=hash[i][j-1]^(s[i][j]=='1'?h[j]:0);
            seq[i]=i;
        }
        auto First=[&](int x,int y)->int {
            if(hash[x][0]!=hash[y][0])
                return 0;
            else {
                int L=0,R=m-2;
                while(L!=R) {
                    int M=(L+R+1)/2;
                    if(hash[x][M]==hash[y][M])
                        L=M;
                    else
                        R=M-1;
                }
                return L+1;
            }
        };
        std::sort(seq,seq+n,[&](int x,int y)->bool {return s[x][First(x,y)]=='0'; });
        for(int i=0;i<n;++i)
            rank[seq[i]]=i;
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i)
                fin>>a[i];
            std::sort(a,a+cnt,[&](int x,int y)->bool { return rank[x]<rank[y]; });
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=First(a[i],a[i+1]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

非标准库的一些好用的东西

Bit Opearation Built-in Functions

int __builtin_ffs (int x)
//Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. 
int __builtin_clz (unsigned int x)
//Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 
int __builtin_ctz (unsigned int x)
//Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. 
int __builtin_clrsb (int x)
//Returns the number of leading redundant sign bits in x, i.e. the number of bits following the most significant bit that are identical to it. There are no special cases for 0 or other values.
int __builtin_popcount (unsigned int x)
//Returns the number of 1-bits in x.
int __builtin_parity (unsigned int x)
//Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

[CF1088E]Ehab and a component choosing problem

Link

Solution

答案的值等于整棵树的点权最大联通块,可以用一次树形DP求出来。
接下来就求最多有多少个点权和等于所求答案的联通块。
有一个贪心是,凑出顶点深度更深的联通块一定不会比凑出顶点深度更浅的联通块更优。因此第二次DFS的时候如代码所示再DP一遍。

Code

const int XN=3e5+11;

std::vector<int> G[XN];
int a[XN];

long long f[XN],g[XN],res;

void DP(int pos,int fa) {
    f[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DP(u,pos);
        f[pos]+=std::max(f[u],0ll);
    }
}

int cnt=0;

void DFS(int pos,int fa) {
    g[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DFS(u,pos);
        g[pos]+=std::max(g[u],0ll);
    }
    if(g[pos]==res) {
        cnt++;
        g[pos]=0;
    }
}

int main() {
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i];
    for(int i=1;i<=n-1;++i) {
        int x,y;fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DP(1,0);
    res=*std::max_element(f+1,f+1+n);
    DFS(1,0);
    fout<<res*cnt<<' '<<cnt<<'\n';
    return 0;
}

[CF1043E]Make It One

Link

Solution

将找最小值变成求是否可行,而求是否可行的方法又是容斥计数判断是否为0,这波操作666
f[i][j]表示选i个数字\gcdj的方案数目,答案就是最小的i使得f[i][1]\not=0
f[i][j]=\binom {i}{c[j]}-\sum_{k=2}f[i][j*k]c[j]表示所有数字中整除j的个数。

Code

const int XN=3e5+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;(v>>=1),(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int main() {
    static int f[8][XN],a[XN],fact[XN],ifact[XN],cnt[XN],c[XN];
    int n,m=0;fin>>n;

    fact[0]=1;
    for(int i=1;i<=n;++i)
        fact[i]=Mul(fact[i-1],i);
    ifact[n]=Pow(fact[n],P-2);
    for(int i=n-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    auto C=[](int n,int m) { return n>=m?Mul(fact[n],Mul(ifact[n-m],ifact[m])):0; };

    for(int i=1;i<=n;++i) {
        fin>>a[i];
        f[1][a[i]]=1;
        Enlarge(m,a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
            c[i]+=cnt[i*j];
    for(int i=2;i<=7;++i) {
        for(int j=m;j>=1;--j) {
            f[i][j]=C(c[j],i);//整除j的个数
            for(int k=2;k*j<=m;++k)
                f[i][j]=Minus(f[i][j],f[i][k*j]);
        }
    }
    int Ans=-1;
    for(int i=1;i<=7;++i)
        if(f[i][1]) {
            Ans=i;
            break;
        }
    fout<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Shenyang Onsite L][Gym 101955L]Machining Disc Rotors

Link

Solution

最远点对一定出现在一对交点处,或者交点和它的未被覆盖的对称点处。考虑弦长变化的单调性即可证明。

Code

const int XN=2e2+11;
const double eps=1e-10,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return Point{-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return Point{a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return Point{a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

void Work() {
    int n,R;fin>>n>>R;
    Point o{0,0};
    auto Atan2=[](double const &y,double const &x) { double r=atan2(y,x); return r<0?r+pi*2:r; };
    bool flag=0;
    auto Calc=[&](Point p,int r)->std::vector<Point> {
        int d1=sgn(Dist(o,p)-R-r),d2=sgn(Dist(o,p)-fabs(R-r));
        if(d1==0)
            return {p/(R+r)*R};
        else if(d1<0 && d2==0) {
            return {p/(R-r)*R};
        } else if(d1<0 && d2>0) {
            double d=Dist(o,p),x=(R*R-r*r+d*d)/(2*d),h=sqrt(R*R-x*x);
            Point v=(p-o).Unit(),n=v.Normal();
            return {v*x-n*h,v*x+n*h};
        } else
            return {};
    };

    std::vector<Point> cross;
    std::vector<std::pair<double,double> > ranges;
    for(int i=1;i<=n;++i) {
        int x,y,r;
        fin>>x>>y>>r;
        std::vector<Point> nc=Calc(Point{(double)x,(double)y},r);
        for(Point &p : nc)
            cross.push_back(p);
        if(nc.size()==1) {
            double x=Atan2(nc[0].y,nc[0].x);
            ranges.push_back({x,x});
        } else if(nc.size()==2)
            ranges.push_back({Atan2(nc[0].y,nc[0].x),Atan2(nc[1].y,nc[1].x)});
    }
    std::sort(ranges.begin(),ranges.end());
    double Ans=0;
    for(size_t i=0;i<cross.size();++i) {
        for(size_t j=i+1;j<cross.size();++j)
            Enlarge(Ans,Dist(cross[i],cross[j]));
        double ang=Atan2(-cross[i].y,-cross[i].x);
        auto Cover=[&](std::pair<double,double> const &x,double const &y)->bool {
            if(x.first<=x.second)
                return x.first<=y && y<=x.second;
            else
                return x.first<=y || y<=x.second;
        };
        auto iter=std::upper_bound(ranges.begin(),ranges.end(),std::pair<double,double>(ang,ang));
        if(iter!=ranges.begin())
            flag|=!Cover(*--iter,ang) && !Cover(ranges.back(),ang);
        else
            flag|=!Cover(ranges.back(),ang);
        if(flag)
            break;
    }
    if(flag)
        Ans=R*2;
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

[ICPC 2018 Shenyang Onsite K][Gym 101955K]Let the Flames Begin

Link

Solution

求步长为k的约瑟夫游戏中第m个出圈的人。
n\le 10^{18},\min{m,k}\le 10^6

The Initial Josephus Problem Solution

f[n]表示n个人围成一圈玩约瑟夫最后剩下的人的标号。
由于删掉一个人之后就会变成n-1的问题,只需要考虑删掉这一个人对于n-1问题的影响。可以发现,删掉第k个人的影响只是n-1问题中的第一个人变成大问题中的第k+1个人,也就是所有人的标号都增加了k
因此f[n]=(k+f[n-1])\mod n(从0开始标号)

This Enhanced Problem Solution

类似的思路
f[n][m]表示n个人第m个出圈的是谁,那么根据前面的分析f[n][m]=(k+f[n-1][m-1])\mod n
边界条件f[n][1]=m-1,在m小的时候直接递推过去就行了。
km大的时候,核心思想是优化递推式。由于kn大,所以走很多步才会被膜一次,那么就算一下会走几步被膜,把k乘上次数去算,一次走多步。
假设当前递推值为p,当前总人数为tx步之后需要mod,则有下式
p+xk\ge t+x。根据此式就能解出x了。

Code

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long n,m,k;fin>>n>>m>>k;
        long long Ans=(k-1)%(n-m+1);
        if(m<k) {
            for(int i=2;i<=m;++i)
                Ans=(Ans+k)%(n-m+i);
            ++Ans;
        } else {
            if(k==1)
                Ans=m;
            else {
                long long tot,p,x;
                for(tot=n-m+1,p=(k-1)%(n-m+1);
                        tot+(x=(tot-p)/(k-1)+((tot-p)%(k-1)!=0))<=n;
                        (p+=k*x)%=(tot+=x));
                p+=(n-tot)*k;
                Ans=++p;
            }
        }
        fout<<Ans<<'\n';
    }
    return 0;
}

[ICPC 2018 Shenyang Onsite E][Gym101955E]The Kouga Ninja Scrolls

Link

Solution

曼哈顿转切比雪夫之后x,y独立了。
问题变成从区间中选取两个颜色不同的数字使得差值最大。
维护区间最大次大、最小次小值,满足最大次大、最小次小值分别是不同的颜色,最大差值一定来源于这四个数字。枚举合法情况判一判就好了。

Code

const int XN=1e5+11;
const long long INF=1e18;

struct SegTree {

    struct Data {
        std::pair<long long,int> mn[2],mx[2];

        Data() {
            mn[0]=mn[1]=std::pair<long long,int>(INF,-1);
            mx[0]=mx[1]=std::pair<long long,int>(-INF,-1);
        }

        long long Solve() {
            long long res=0;
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    if(mn[i].second!=mx[j].second)
                        Enlarge(res,mx[j].first-mn[i].first);
            return res;
        }

        friend Data Merge(Data const &a,Data const &b) {
            Data res;
            auto Update=[&](Data const &x) {
                for(int i=0;i<2;++i) {
                    if(x.mn[i].first<res.mn[0].first) {
                        if(x.mn[i].second!=res.mn[0].second)
                            res.mn[1]=res.mn[0];
                        res.mn[0]=x.mn[i];
                    } else if(x.mn[i].first<res.mn[1].first && x.mn[i].second!=res.mn[0].second)
                        res.mn[1]=x.mn[i];

                    if(x.mx[i].first>res.mx[0].first) {
                        if(x.mx[i].second!=res.mx[0].second)
                            res.mx[1]=res.mx[0];
                        res.mx[0]=x.mx[i];
                    } else if(x.mx[i].first>res.mx[1].first && x.mx[i].second!=res.mx[0].second)
                        res.mx[1]=x.mx[i];

                }
            };
            Update(a);Update(b);
            return res;
        }
    };

    struct Node {
        Node *son[2];
        Data v;
        Node(std::pair<long long,int> const &x) {
            v.mn[0]=v.mx[0]=x;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc(XN*10*sizeof(Node)),*mem=0;
            return flag?mem++:mem=pool;
        }

        void Up() {
            v=Merge(son[0]->v,son[1]->v);
        }
    }*root;

    int L,R;

    SegTree(std::pair<long long,int> a[],int n):L(1),R(n) {
        std::function<void(Node*&,int,int)> Build=
            [&](Node *&pos,int L,int R) {
                pos=new Node(a[L]);
                if(L==R)
                    return;
                else {
                    int M=(L+R)/2;
                    Build(pos->son[0],L,M);
                    Build(pos->son[1],M+1,R);
                    pos->Up();
                }

            };
        Build(root,1,n);
    }

    long long Query(int l,int r) {
        std::function<Data(Node*,int,int)> Query=
            [&](Node *pos,int L,int R) {
                if(l<=L && R<=r)
                    return pos->v;
                else {
                    int M=(L+R)/2;
                    Data res;
                    if(l<=M)
                        res=Merge(res,Query(pos->son[0],L,M));
                    if(M+1<=r)
                        res=Merge(res,Query(pos->son[1],M+1,R));
                    return res;
                }
            };
        return Query(root,L,R).Solve();
    }

    template <class T>
    void Modify(int goal,T F) {
        std::function<void(Node*,int,int)> Modify=
            [&](Node *pos,int L,int R) {
                if(L==R) {
                    F(pos->v.mn[0]);
                    F(pos->v.mx[0]);
                } else {
                    int M=(L+R)/2;
                    goal<=M?Modify(pos->son[0],L,M):Modify(pos->son[1],M+1,R);
                    pos->Up();
                }
            };
        Modify(root,L,R);
    }
};

void Work() {
    SegTree::Node::operator new(0);

    auto Convert=[](int x,int y)->std::pair<int,int> { return std::pair<int,int>(x+y,x-y); };

    int n,m;fin>>n>>m;
    static std::pair<long long,int> cx[XN],cy[XN];
    for(int i=1;i<=n;++i) {
        int x,y,c;fin>>x>>y>>c;
        std::tie(cx[i].first,cy[i].first)=Convert(x,y);
        cx[i].second=cy[i].second=c;
    }

    SegTree segX(cx,n),segY(cy,n);

    for(int q=1;q<=m;++q) {
        int op;fin>>op;
        switch(op) {
            case 1 : {
                int id,x,y;fin>>id>>x>>y;
                std::tie(x,y)=Convert(x,y);
                segX.Modify(id,[&](std::pair<long long,int> &a) { a.first+=x; });
                segY.Modify(id,[&](std::pair<long long,int> &a) { a.first+=y; });
            } break;
            case 2 : {
                int id,c;fin>>id>>c;
                auto Change=[&](std::pair<long long,int> &a) { a.second=c; };
                segX.Modify(id,Change);
                segY.Modify(id,Change);
            } break;
            case 3 : {
                int l,r;fin>>l>>r;
                fout<<std::max(segX.Query(l,r),segY.Query(l,r))<<'\n';
            } break;
        }
    }
}

int main() {
    int T;fin>>T;

    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        Work();
    }
    return 0;
}