for_each,generate,transform

std::for_each

template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

std::generate

template <class ForwardIterator, class Generator>
  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
  while (first != last) {
    *first = gen();
    ++first;
  }
}

std::transform

template <class InputIterator, class OutputIterator, class UnaryOperator>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
  while (first1 != last1) {
    *result = op(*first1);  // or: *result=binary_op(*first1,*first2++);
    ++result; ++first1;
  }
  return result;
}

[ICPC Northern Eurasia Finals 2018 K]King Kog’s Reception

Link

多年不碰数据结构的老年选手,估计是做麻烦了。

Solution

对所有来的时刻开线段树,记录每个区间来的骑士的开始时间和结束时间,再记录一下这段时间内有多少时间是空白的,那么这些空白时间可以在开始时间延后时起到“缓冲作用”。
合并也好合并,就是一开始写错了没看出来。

Code

#include <bits/stdc++.h>

const int XN=3e5+11;

struct SegTree {
    struct Info {
        long long l,r,blank;
        Info():l(0),r(-1) {}

        operator bool() const {
            return l<=r;
        }

        friend Info Merge(Info const &a,Info const &b) {
            if(!a) return b;
            else if(!b) return a;
            else {
                Info res=a;
                long long rblank=b.blank+std::max(b.l-a.r-1,0ll);
                res.r=b.r+std::max(a.r-b.l+1-rblank,0ll);
                res.blank+=std::max(rblank-std::max(a.r-b.l+1,0ll),0ll);//
                return res;
            }
        }
    };
    struct Node {
        Node *son[2];
        Info v;
        Node() {
            son[0]=son[1]=0;
        }
    }*root;
    int L,R;

    SegTree(int L,int R):root(0),L(L),R(R) {}

    void Modify(int t,int d) {
        std::function<void(Node*&,int,int)> Modify=[&](Node *&pos,int L,int R) {
            if(!pos)
                pos=new Node;
            if(L==R) {
                pos->v.r=(pos->v.l=t)+d-1;
                pos->v.blank=0;
            } else {
                int M=(L+R)/2;
                t<=M?Modify(pos->son[0],L,M)
                    :Modify(pos->son[1],M+1,R);
                pos->v=Merge(pos->son[0]?pos->son[0]->v:Info()
                            ,pos->son[1]?pos->son[1]->v:Info());
            }
        };
        Modify(root,L,R);
    }

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

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SegTree seg(1,1e6);
    int q;std::cin>>q;
    static int vt[XN];
    for(int ks=1;ks<=q;++ks) {
        char op[10];
        std::cin>>op;
        if(op[0]=='+') {
            int t,d;std::cin>>t>>d;
            vt[ks]=t;
            seg.Modify(t,d);
        } else if(op[0]=='-') {
            int id;std::cin>>id;
            seg.Modify(vt[id],0);
        } else {
            int t;std::cin>>t;
            std::cout<<std::max(0ll,seg.Query(t).r+1-t)<<'\n';
        }
    }
    return 0;
}

[Codeforces 908D]New Year and Arbitrary Arrangement

Link

Solution

首先,前导b对于ab子序列的个数不会产生影响,为了简化,强制第一个位置是a。
一个比较好用的想法是,任意一个合法解都以b为结尾,可以在最后一个b前面添加任意个a。
从第二个位置开始填,f[i][j]表示填了i个a,有j个ab子序列的概率。
i + j < n时,转移显然。
否则,就直接将在f[i][j]后面加任意个a和一个b产生的贡献累加到答案里,不再进行转移。因为如果将这部分f[i][j]加上一个a继续转移到f[i+1][j]中,就会与f[i][j]后面加任意个a和一个b重复。
f[i][j]后面加任意个a和一个b产生的贡献如下:

\begin{aligned}
&f[i][j]p_b\sum_{k=0}^{\infty}(i+j+k)p_a^k\\
=&f[i][j]p_b[\frac {i+j}{1-p_a}+\frac {p_a}{(1-p_a)^2}]
\end{aligned}

求出最后的答案还要乘上\sum_{i=0}^{\infty}p_b^i=\frac 1{1-p_b},因为在序列前方加上任意个b对概率是有影响的,因而对期望也有影响。

Code

#include <bits/stdc++.h>

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

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

void AddBy(int &x,int const &y) {
    x=Add(x,y);
}

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) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int Inverse(int x) {
    return Pow(x,P-2);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,a,b;std::cin>>n>>a>>b;
    int pa=Mul(a,Inverse(a+b)),pb=Mul(b,Inverse(a+b));
    static int f[XN][XN];
    f[1][0]=pa;
    int c1=Inverse(Minus(1,pa)),c2=Mul(pa,Mul(c1,c1));
    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j) {
            if(i+j<n) {
                AddBy(f[i+1][j],Mul(pa,f[i][j]));
                AddBy(f[i][i+j],Mul(pb,f[i][j]));
            } else
                AddBy(Ans,Mul(Mul(pb,f[i][j]),((long long)(i+j)*c1+c2)%P));
        }
    Ans=Mul(Ans,Inverse(Minus(1,pb)));
    std::cout<<Ans<<'\n';
    return 0;
}

ICPC EC-Final 2018 I Misunderstood … Missing

Link

Solution

小数据爆搜,大数据三个贪心取max
DP的话,需要让2、3操作的贡献能够提前计算。
而2的贡献与后面攻击的下标和有关,3的贡献和后面攻击的次数有关,这样就有了状态。

Code

const int XN=1e2+11;

void Work() {
    static int a[XN],b[XN],c[XN];
    static long long f[2][XN][XN*XN];
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i]>>b[i]>>c[i];
    memset(f,0,sizeof(f));
    int cur=0;
    for(int i=1,sum=n*(n+1)/2-1;i<=n;sum-=++i,cur^=1)
        for(int j=0;j<=n-i;++j)
            for(int k=0;k<=sum;++k)
                f[cur][j][k]=Max(f[cur^1][j][k]+Max((long long)b[i]*(k-i*j),(long long)c[i]*j),f[cur^1][j+1][k+i]+a[i]);
    fout<<f[cur^1][0][0]<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

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.