1153 B

给你一个三维几何体的主视图、左视图、俯视图，要你输出俯视图中每个柱子的高度。( \(n,m,h\le 100\) )

Examples

input

3 7 3

2 3 0 0 2 0 1

2 1 3

1 0 0 0 1 0 0

0 0 0 0 0 0 1

1 1 0 0 0 0 0

output

1 0 0 0 2 0 0

0 0 0 0 0 0 1

2 3 0 0 0 0 0

input

4 5 5

3 5 2 0 4

4 2 5 4

0 0 0 0 1

1 0 1 0 0

0 1 0 0 0

1 1 1 0 0

output

0 0 0 0 4

1 0 2 0 0

0 5 0 0 0

3 4 1 0 0

解

\(h[i][j]=\min(a[i],b[j])\)

1153 C

题意

给你一个括号序列，由'(',')','?'组成，你可以把'?'替换成括号，现在要你构造一个合法的括号序列，使得除它本身的所有非空前缀都不合法。无解输出:(。

Examples

input

6

(?????

output

(()())

input

10

(???(???(?

output

:(

解

首先最左边一定是(，最右边一定是)， \(n\) 一定是偶数。

接下来贪心地构造。

Code

#include
    
     #define maxn 300003using namespace std;char s[maxn];int n,le;void FAIL(){puts(":(");exit(0);}int main(){    scanf("%d%s",&n,s+1);    if((n&1)||s[1]==')'||s[n]=='(')FAIL();    s[1]='(',s[n]=')';    for(int i=2;i
     
      >1))le++,top++,s[i]='(';            else top--,s[i]=')';        }        if(top<0)FAIL();    }    if(top)FAIL();    puts(s+1);    return 0;}
     
    

1153 D

题意

前面和ZJOI2019 Minimax基本一致，现在每个节点（包括根）的值为它所有孩子的 \(\min\) 或 \(\max\) ，要将数字 \(1-k\) （ \(k\) 为叶子节点数量）分配到每个叶子节点，问怎样分配能使得根节点的值最大。

Examples

input

6

1 0 1 1 0 1

1 2 2 2 2

output

1

input

5

1 0 1 0 1

1 1 1 1

output

4

input

8

1 0 0 1 0 1 1 0

1 1 2 2 3 3 3

output

4

input

9

1 1 0 0 1 0 1 0 1

1 1 2 2 3 3 4 4

output

5

解

对于每个节点我们考察把一串序列分给它子树的所有叶子，这个节点的值是序列的第几小元素。

那么对于叶子，\(dp[1]=1\) 。

对于 \(\min\) 节点， \(dp[u]=\min\{dp[v]\}\) 。

对于 \(\max\) 节点， \(dp[u]=\sum dp[v]\) 。

然后答案就是 \(dp[1]\) 。

1153 E

题意

交互题

在 \(n*n\) 的平面上有 \(n*n\) 个格子，现在有一条蛇，它的头部和尾部都在格子内，它的身子要么水平要么竖直。现在你有 \(2019\) 次询问机会，每次你选定一个矩形，评测机返回蛇的身体与矩形的边有几个交点。你要输出蛇的头、尾的坐标。\((n\le 1000)\)

解

分类讨论：

1. 蛇的头尾在不同的两列中
   从左往右扫，如果有奇数个交点就说明蛇的头肯定在当前矩形内。找到蛇的头尾所在的列后再二分答案行。
2. 蛇的头尾在相同的一列中
   从上往下扫找到行再二分列。

Code

#include
    
     using namespace std;int query(int x1,int y1,int x2,int y2){    printf("? %d %d %d %d\n",x1,y1,x2,y2);    fflush(stdout);    int ret;    scanf("%d",&ret);    if(ret==-1)exit(0);    return ret;}void submit(int x1,int y1,int x2,int y2){    printf("! %d %d %d %d\n",x1,y1,x2,y2);    fflush(stdout);    exit(0);}int main(){    int n,l,r,u,d;    scanf("%d",&n);    for(l=1;l
     
      =d;u--)if(query(1,u,n,n)&1)break;        int le=1,ri=n,mid,ans;        while(le<=ri){            mid=(le+ri)>>1;            if(query(1,u,mid,u)&1)ans=mid,ri=mid-1;            else le=mid+1;        }        l=ans;        le=1,ri=n;        while(le<=ri){            mid=(le+ri)>>1;            if(query(1,d,mid,d)&1)ans=mid,ri=mid-1;            else le=mid+1;        }        r=ans;        submit(l,u,r,d);    }    for(r=n;r>=l;r--)if(query(r,1,n,n)&1)break;    int le=1,ri=n,mid,ans;    while(le<=ri){        mid=(le+ri)>>1;        if(query(l,1,l,mid)&1)ans=mid,ri=mid-1;        else le=mid+1;    }    u=ans;    le=1,ri=n;    while(le<=ri){        mid=(le+ri)>>1;        if(query(r,1,r,mid)&1)ans=mid,ri=mid-1;        else le=mid+1;    }    d=ans;    submit(l,u,r,d);}