Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)


A.Kuroni and the Gifts

  • 给定两个数组,这两个数组分别pairwise distinct,要求给两个数组分别设计一个排列,使得a[i]+b[i]也是pairwise distinct。

  • 排序即可。


B. Kuroni and Simple Strings


  • 给定一个由左右括号组成的字符串,每次可删除一个左右括号匹配的合法子序列,问最少删几次可使得字符串中无任何匹配子序列。

  • 结论:至多删除一次即可。找到一个min(前缀左括号,后缀右括号)最大的分割点,然后在此处删除。删除后的状态一定为)))((((。

  • 证明:我们另|为分界点,删除|左边的(和右边的)。我们令当前位置后缀右括号的数量<=左括号的数量,不失一般性。即当前状态为)))|((((。此时,右边无右括号。假设左边仍有匹配的,如))()|((((。此时将分割线往左移,))(|)((((,可以发现,此时的min大于刚才位置的min。所以,仍然可按上述方法删除。


C. Kuroni and Impossible Calculation


  • 计算∏(1≤i<j≤n)|ai−aj|%m,其中n<200000,m<1000。

  • 可以发现,暴力一定是不可取的。观察到m的范围为1000,那么可从此处着手。将ai%m之后统计到0~999。考察现在的|ai-aj|与原来的|ai-aj|。若离散化之前与之后的大小顺序不变,那么值相等,若大小变换了,那么两者值相加等于m。所以对于取模之后的两组vector,他们的差值只有这两种可能。计数一下即可。复杂度O(m^2)。

    D. Kuroni and the Celebration


  • 交互题。给定一棵n个结点的额树,需要求出根结点。每次可询问两个结点的lca是谁,最多询问n/2(向下取整)次。

  • 按照拓扑排序的思路。每次取度为1的结点,询问两个的lca。若lca为这两者中的一个,则那个点必为root。否则将这两个叶子结点删除。可以发现,每次都能删除两个结点,所以询问的次数符合要求。
#include
using namespace std;
struct node{
        int v,next;
}edge[105000];
queue q;
int vis[105000],de[105000],head[105000],cnt,n;
void add(int u,int v){
        cnt++;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
}
void dec(int k){
        int i,v;
        for (i=head[k];i!=-1;i=edge[i].next) {
                v=edge[i].v;
                if (vis[v]==0){
                        de[v]--;
                        if (de[v]==1) {
                                q.push(v);
                                vis[v]=1;
                        }
                }
        }
}
void bfs(){
        int i,k,fir,sec;
        while(q.empty()==false) q.pop();
        memset(vis,0,sizeof(vis));
        for (i=1;i<=n;i++) if (de[i]==1) {q.push(i);vis[i]=1;}
        while(q.empty()==false) {
                fir=q.front();q.pop();
                if (q.empty()==true) {
                        printf("! %d
",fir);
                        break;
                }
                sec=q.front();q.pop();
                dec(fir);
                dec(sec);
                printf("? %d %d
",fir,sec);
                fflush(stdout);
                scanf("%d",&k);
                if (k==fir||k==sec) {
                        printf("! %d
",k);
                        break;
                }
        }
}
int main(){
        int i,x,y;
        scanf("%d",&n);
        memset(de,0,sizeof(de));
        memset(head,-1,sizeof(head));
        cnt=0;
        for (i=1;i
原文地址:https://www.cnblogs.com/nowheretrix/p/12410355.html