COCI 2018/2019 CONTEST #2 Solution

Problem1 Preokret

第一题一定不是什么难题。

第一个问题在读入的时候判断当前时间是不是在1440及以前就行

第二个问题考虑离线处理，由于每个时刻只能最多发生1个事件那么就弄个桶记录每一个事件就行了。

水过T1。

Code：

# include <bits/stdc++.h>

using namespace std;

const int N=;

int a[N];

int A,B,T,rec1,rec2;

template <typename T>inline void read(T &x)

{

    int w=,X=; char c=;

    while (c<''||c>'') w|=c=='-',c=getchar();

    while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    x=w?-X:X;

}

int main()

{

//    freopen("Preokret.in","r",stdin);

//    freopen("Preokret.out","w",stdout);

    memset(a,-,sizeof(a));

    read(A);

    for (int i=;i<=A;i++) read(T),a[T]=;

    read(B);

    for (int i=;i<=B;i++) read(T),a[T]=;

    int Ans1=,Ans2=,flag=-,s1=,s2=;

    for (int i=;i<=;i++) {

        if (a[i]==-) continue;

        if (a[i]==) s1++; else s2++;

        if (i<=) Ans1++;

        if (flag==-) { flag=s1<s2; continue;}

        if (s1>s2&&flag==) flag=,Ans2++;

        else if (s1<s2&&flag==) flag=,Ans2++;

    }

    cout<<Ans1<<'\n'<<Ans2<<'\n';

    return ;

}

Problem2 Kocka

这个题对于100%的数据一定不是O(n²)的构造，而是数学的判断。

我们可以简单考虑四种情况，我们记四个数组分别是left[],right[],up[],down[],

分别考虑四个数组元素值是x的时候代表什么含义，

以left[i]为例，left[i]=-1的时候表示第i行没有放东西，那么对应的right[i]必须也是-1否则构造不合法,而对于up[]和down[]无影响。

left[i]=x(x≠-1时)，那么意味着在(i,x+1)这个位置必须存在一个障碍物，那么从上面看下来可以看到的不能大于i-1吧，下面看上来不能超过n-i吧，右边看过来不能超过n-x-1吧。

对于 right[]和up[]和down[]同理。

这里需要注意在C++中up什么的可能是保留字，我Define了一下。

Code

# include <bits/stdc++.h>

# define fp(i,s,t) for (int i=s;i<=t;i++)

# define left Left

# define right Right

# define up Up

# define down Down

using namespace std;

const int N=1e5+;

int left[N],right[N],up[N],down[N],n;

inline void read(int &x)

{

    int w=,X=; char c=;

    while (c<''||c>'') w|=c=='-',c=getchar();

    while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    x=w?-X:X;

}

bool work()

{

    fp(i,,n) {

        if (left[i]==-) {

            if (right[i]==-) continue;

            return ;

        }

        if (up[left[i]+]==-||up[left[i]+]>i-) return ;

        if (down[left[i]+]==-||down[left[i]+]>n-i) return ;

        if (right[i]==-||right[i]>n-left[i]-) return ;

    }

    fp(i,,n) {

        if (up[i]==-) {

            if (up[i]==-) continue;

            return ;

        }

        if (left[up[i]+]==-||left[up[i]+]>i-) return ;

        if (right[up[i]+]==-||right[up[i]+]>n-i) return ;

        if (down[i]==-||down[i]>n-up[i]-) return ;

    }

    fp(i,,n) {

        if (right[i]==-) {

            if (left[i]==-) continue;

            return ;

        }

        if (up[n-right[i]]==-||up[n-right[i]]>i-) return ;

        if (down[n-right[i]]==-||down[n-right[i]]>n-i) return ;

        if (left[i]==-||left[i]>n-right[i]-) return ;

    }

    fp(i,,n) {

        if (down[i]==-) {

            if (up[i]==-) continue;

            return ;

        }

        if (left[n-down[i]]==-||left[n-down[i]]>i-) return ;

        if (right[n-down[i]]==-||right[n-down[i]]>n-i) return ;

        if (up[i]==-||up[i]>n-down[i]-) return ;

    }

    return ;

}

int main()

{

//    freopen("Kocka.in","r",stdin);

//    freopen("Kocka.out","w",stdout);

    read(n);

    fp(i,,n) read(left[i]);

    fp(i,,n) read(right[i]);

    fp(i,,n) read(up[i]);

    fp(i,,n) read(down[i]);

    puts(work()?"DA":"NE");

    return ;

}

Problem3 Deblo

这个题是树上路径计数，初步搞搞O(n²log₂ n)暴力还是搞得来的。

但是书上路径统计想到了淀粉质点分治暴力统计路径。

这里需要注意点分治的一般步骤：

每次在子树里面选定一个重心，考虑一条过重心的路径，统计这条边上的异或值。

这里用到异或的一个性质x xor y xor y=x，考虑以子树的根（不一定是重心）dfs下去找到根的xor前缀和

统计每个点的xor，那么就把01塞到桶里面就行了。

注意这个时候由于每一条路径一定过重心所以先把重心加入，其他的前缀和先xor一个重心，这样可以把重心的影响减去。

尤其注意先找这个点和其他点之间xor值然后再更新桶里面的值。

重心打标及时啊!一塞入就打标。

一开始先找重心可以快一点。。。

具体的可以看我的点分治blog例题1：https://www.cnblogs.com/ljc20020730/p/10347198.html

# include <bits/stdc++.h>

# define LL long long

# define fp(i,s,t) for (int i=s;i<=t;i++)

using namespace std;

const int N=1e5+;

const int MAXBIT=;

bool used[N];

int size[N],val[N],cnt[][MAXBIT],n;

struct rec{int pre,to;}a[*N];

int tot,head[N];

template <typename T>inline void read(T& t)

{

    char c=getchar();t=;

    while(c<''||c>'')c=getchar();

    while(c>=''&&c<='')t=(t<<)+(t<<)+(c^),c=getchar();

}

template <typename T,typename... Args> inline void read(T& t, Args&... args)

{

    read(t);read(args...);

}

void write(LL x)

{

    if (x>) write(x/);

    putchar(''+x%);

}

void writeln(LL x)

{

    write(x);putchar('\n');

}

void adde(int u,int v)

{

    a[++tot].pre=head[u];

    a[tot].to=v;

    head[u]=tot;

}

int Get_Root(int u,int fath,int S)

{

    int pos=;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to;

        if (v==fath||used[v]) continue;

        if (size[v]>size[pos]) pos=v;

    }

    if (pos!=&&size[pos]>=S/) return Get_Root(pos,u,S);

    return u;

}

void Get_Dist(int u,int fath,int num)

{

    num^=val[u]; size[u]=;

    fp(i,,MAXBIT-)

        cnt[(num & (<<i))>][i]++;

    for (int i=head[u];i;i=a[i].pre){

        int v=a[i].to;

        if (v==fath||used[v]) continue;

        Get_Dist(v,u,num);

        size[u]+=size[v];

    }

}

LL ans=;

void Get_Ans(int u,int fath,int num)

{

    num^=val[u];

    fp(i,,MAXBIT-)

     ans+=(LL) (<<i)*cnt[(num & (<<i))==][i];

    for (int i=head[u];i;i=a[i].pre){

        int v=a[i].to;

        if (v==fath||used[v]) continue;

        Get_Ans(v,u,num);

    }

}

void solve(int u,int fath)

{

    int root=Get_Root(u,fath,size[u]);

    used[root]=;

    memset(cnt,,sizeof(cnt));

    fp(i,,MAXBIT-)

     cnt[(val[root] & (<<i))>][i]++;

    ans+=(LL)val[root];

    for (int i=head[root];i;i=a[i].pre) {

        int v=a[i].to;

        if (used[v]) continue;

        Get_Ans(v,,);

        Get_Dist(v,,val[root]);

    }

    for (int i=head[root];i;i=a[i].pre) {

        int v=a[i].to;

        if (used[v]) continue;

        solve(v,u);

    }

}

int main()

{

    read(n); fp(i,,n) read(val[i]);

    int u,v;

    fp(i,,n-)

        read(u,v),adde(u,v),adde(v,u);

    int rt=Get_Root(,,n);

    Get_Dist(rt,,); solve(rt,);

    writeln(ans);

    return ;

}

Problem4 Maja

数据加强的三个点其实就是把大多数标程卡掉的点。

就是K不是偶数而是奇数的时候显然是不存在合法的一条路径的。

这点原题中没有说需要判断。（但是神奇的是没有卡WTF）

这道题显然K这么大不是搜索而是DP，

搜索的复杂度O(4^K)太大了吧！！！而且每个点不止重复走1次。

考虑一条性质：假设从原点(A,B)走到(i,j)恰好走了K/2步然后必然会选择走回去是最优的吧。

这个显然。

然后考虑全局的最优，答案一定是一个循环组成的，就是不停地在某一条路上来回走。

这个也是显然的吧。

那么有余数怎么办？可以证明贪心的选取中点四周的一个C_i,j最大的来回走完余数就是这个点最优的。

这个可以反证？简单yy一下如果不这样选取那么你还不如走到你最终的中点继续循环呢！

然后就是一个DP+贪心的神仙题目了。

先K/=2，只考虑去，回来其实近似乘以2就行。（其实并不是乘以2）

设f[i][j][r]指的是从(A,B)走到(i,j)经过(i,j)有r次的最优解，那么显然是从四个方向走来的吧。

转移是f[i][j][r]=Max{f[x][y][r-1]}+c[i][j]（x,y指的是(i,j)四个相邻点）

回去就是f[i][j][r]+Max{f[x][y][r-1]}，那是C_i,j少记一次。

然后剩余的步数（只记去，此时K已经除以2）就是K-r，余数走的步数就是

(K-r)*(Max{c[x][y]}+c[i][j])

然后每次到(i,j)r次计算一下答案。

那个r一维可以滚存，r的取值范围是[0,Min(k,n*m)]

Code：

# include<bits/stdc++.h>

# define fp(i,s,t) for (int i=s;i<=t;i++)

# define inf (0x7f7f7f7f7fll)

# define int long long

using namespace std;

const int N=;

int f[N][N][],c[N][N];

int n,m,A,B,K,ans;

int Get_Max(int a,int b,int c,int d)

{

    if (b>a) a=b;

    if (c>a) a=c;

    if (d>a) a=d;

    return a;

}

template <typename T>inline void read(T& t)

{

    char c=getchar();t=;

    while(c<''||c>'')c=getchar();

    while(c>=''&&c<='')t=(t<<)+(t<<)+(c^),c=getchar();

}

template <typename T,typename... Args> inline void read(T& t, Args&... args)

{

    read(t);read(args...);

}

void write(int x)

{

    if (x>) write(x/);

    putchar(''+x%);

}

void writeln(int x)

{

    write(x);putchar('\n');

}

signed main()

{

    read(n,m,A,B,K);

    if (K&) { puts("");exit();}

    K=K>>;

    fp(i,,n+) fp(j,,m+)

     c[i][j]=f[i][j][]=f[i][j][]=-inf;

    fp(i,,n) fp(j,,m) read(c[i][j]);

    f[A][B][]=; ans=-inf;

    fp (r,,min(K,n*m)) {

        int now=r&;

        int pst=now^;

        fp(i,,n) fp(j,,m) {

            int temp=Get_Max(f[i-][j][pst],f[i+][j][pst],f[i][j-][pst],f[i][j+][pst]);

            f[i][j][now]=max(temp+c[i][j],-inf);

            if (f[i][j][now]<) continue;

            int Whole_Dist=f[i][j][now]+temp;

            Whole_Dist+=(K-r)*(c[i][j]+Get_Max(c[i-][j],c[i+][j],c[i][j-],c[i][j+]));

            ans=max(ans,Whole_Dist);

        }

    }

    writeln(ans);

    return ;

 }

Problem5 Sunčanje

一道暴力的神仙T5，一看到数据范围就不想暴力的。

但是算算暴力的期望还是值得的。

先按照矩形右下角的x坐标排序，然后枚举每一个长方形，i，看看前面的长方形j是不是包含在i里面的，

被包含的必要条件是a[i].x-a[i].len<a[j].x对吧，不满足必要条件的那么前面也不满足必要条件，直接跳掉。

然后花四个图看看判包含。

           　 (a[i].y>a[j].y&&a[i].y<a[j].y+a[j].wid)

            ||(a[i].y+a[i].wid>a[j].y&&a[i].y+a[i].wid<a[j].y+a[j].wid)

            ||(a[j].y>a[i].y&&a[j].y<a[i].y+a[i].wid)

            ||(a[j].y+a[j].wid>a[i].y&&a[j].y+a[j].wid<a[i].y+a[i].wid)

更新的时候注意看看谁在谁的下面（一定是初始标号小的放在下面！）

然后瞎加点优化就可以用pascal过4000ms时限了（而C++不行）

然后我就把第19个点的时限改成了6000ms，于是pascal和C++都过了

如果C++代码在XOJ上过不了的话那么加一行

# pragma G++ optimize(3)

Code C++

# pragma G++ optimize(3)
# include <bits/stdc++.h>

# define fp(i,s,t) for (int i=s;i<=t;i++)

using namespace std;

const int N=1e5+;

struct rec{

    int x,y,len,wid,id;

}a[N];

int n;

bool ans[N];

inline int read()

{

    int X=,w=; char c=;

    while(c<''||c>'') {w|=c=='-';c=getchar();}

    while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    return w?-X:X;

}

inline void qsort(int l,int r)

{

    if (l==r) return;

    int t=rand()%(r-l)+l;

    swap(a[t],a[l]);

    rec v=a[l]; int i=l,j=r;

    while (i<j) {

        while (i<j&&a[j].x>v.x) j--;

        if (i<j) {a[i]=a[j];i++;} else break;

        while (i<j&&a[i].x<v.x) i++;

        if (i<j) {a[j]=a[i];j--;} else break;

    }

    a[i]=v;

    if (l<j) qsort(l,j-);

    if (i<r) qsort(i+,r);

}

signed main()

{

    srand(time(NULL)*);

    n=read();

    fp(i,,n) {

        a[i].x=read();a[i].y=read();a[i].len=read();a[i].wid=read();

        a[i].x+=a[i].len;

        a[i].id=i;

    }

    qsort(,n);

    fp(i,,n) {

        int j=i-;

        while (j>=&&(a[i].x-a[i].len<a[j].x)) {

            if ((a[i].y>a[j].y&&a[i].y<a[j].y+a[j].wid)

            ||(a[i].y+a[i].wid>a[j].y&&a[i].y+a[i].wid<a[j].y+a[j].wid)

            ||(a[j].y>a[i].y&&a[j].y<a[i].y+a[i].wid)

            ||(a[j].y+a[j].wid>a[i].y&&a[j].y+a[j].wid<a[i].y+a[i].wid))

            {

                if (a[i].id<a[j].id) ans[a[i].id]=;

                else ans[a[j].id]=;

            }

            j--;

        }

    }

    fp(i,,n)

     if (ans[i]) putchar('N'),putchar('E'),putchar('\n');

     else putchar('D'),putchar('A'),putchar('\n');

    return ;

}

Code Pascal

VAR

    n,i,j:int64; x,y,len,wid,poza,raspuns:array[..] of int64;

function Poz(a1,b1 : int64) : int64;

VAR aux,piv:int64;

Begin

    piv:=x[a1];

    while (a1 < b1) do

    Begin

    if (x[a1] > x[b1]) then Begin

        aux:=x[a1]; x[a1]:=x[b1]; x[b1]:=aux;

        aux:=y[a1]; y[a1]:=y[b1]; y[b1]:=aux;

        aux:=len[a1]; len[a1]:=len[b1]; len[b1]:=aux;

        aux:=wid[a1]; wid[a1]:=wid[b1]; wid[b1]:=aux;

        aux:=poza[a1]; poza[a1]:=poza[b1]; poza[b1]:=aux; end;

    if (piv = x[a1]) then b1:=b1 -  else a1:=a1 + ;

    end;

    Poz:=a1;

end;

procedure Quick(a1,b1 : int64);

VAR k:int64;

Begin

    if (a1 < b1) then

        Begin

            k:=Poz(a1,b1);

            Quick(a1,k - );

            Quick(k + ,b1);

    end;

end;

Begin

    Readln(n);

    for i:= to n do

    Begin

        Readln(x[i],y[i],len[i],wid[i]);

        x[i]:=x[i] + len[i];

        poza[i]:=i;

    end;

    Quick(,n);

    raspuns[]:=;

    for i:= to n do

    Begin

        j:=i - ;

        while (j > ) and (x[i] - len[i] < x[j]) do

        Begin

            if     (((y[i] > y[j]) and (y[i] < y[j] + wid[j]))

                or ((y[i] + wid[i] > y[j]) and (y[i] + wid[i] < y[j] + wid[j])))

                or (((y[j] > y[i]) and (y[j] < y[i] + wid[i]))

                or ((y[j] + wid[j] > y[i]) and (y[j] + wid[j] < y[i] + wid[i]))) then

            Begin

              if (poza[i] < poza[j]) then raspuns[poza[i]]:= else raspuns[poza[j]]:=;

            end;

            j:=j - ;

        end;

    end;

    for i:= to n do

        if (raspuns[i] = ) then Writeln('NE') else Writeln('DA');

END.

巴特西