2019 牛客多校第八场

All-one Matrices

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Gromah and LZR entered the great tomb, the first thing they see is a matrix of size n×mn\times mn×m, and the elements in the matrix are all 00_{}0​ or 11_{}1​.
LZR finds a note board saying “An all-one matrix is defined as the matrix whose elements are all 11_{}1​, you should determine the number of all-one submatrices of the given matrix that are not completely included by any other all-one submatrices”.
Meanwhile, Gromah also finds a password lock, obviously the password should be the number mentioned in the note board!
Please help them determine the password and enter the next level.

输入描述:

The first line contains two positive integers n,mn,m_{}n,m​, denoting the size of given matrix.
Following nn_{}n​ lines each contains a string with length mm_{}m​, whose elements are all 00_{}0​ or 11_{}1​, denoting the given matrix.

1≤n,m≤30001\le n,m \le 30001≤n,m≤3000

输出描述:

Print a non-negative integer, denoting the answer.

示例1

输入

3 4
0111
1110
0101

输出

5

说明

The 5 matrices are (1,2)−(1,4),  (1,2)−(2,3),  (1,2)−(3,2),  (2,1)−(2,3),  (3,4)−(3,4)(1,2)-(1,4), \; (1,2)-(2,3), \; (1,2)-(3,2), \; (2,1)-(2,3), \; (3,4)-(3,4)_{}(1,2)−(1,4),(1,2)−(2,3),(1,2)−(3,2),(2,1)−(2,3),(3,4)−(3,4)​.

对于每一个[i,j],记录从它开始向上连续的1的个数num;

枚举每一行作为矩阵底边所在行,从前向后枚举每一列,维护一个num单调上升的栈,对于栈中每一个num值,还要维护一个该num对应位置向左最远能扩展到的位置pos;

元素出栈时,设该元素是(num,pos),那么可以得到一个全1矩阵(i-num+1,pos)->(i,j);

此时该矩阵最左为pos已经记录(不可向左扩展),向上最多为num已经记录(不可向上扩展),因为大于当前num才出栈(不可向右扩展),所以只要判定能否向下扩展,如果不能,那么这就是一个答案矩阵。

#include<iostream>
#include<cstdio>
 
using namespace std;
 
int z,x,n,m,w,h,a[3010][3010],b[3010][3010],t[3010],tt[3010],ans;
char c;
int main()
{
    scanf("%d%d",&z,&x);ans=0;
     
    for (int i=1;i<=z;i++)
    {
        getchar();
        for (int j=1;j<=x;j++)
        {
            c=getchar();
            a[i][j]=c-'0';
            b[i][j]=a[i][j]+b[i][j-1];
        }
    }
    for (int i=1;i<=z;i++)
    {
        n=0;
        for (int j=1;j<=x;j++)
        {
            m=j-1;w=j;
            if (a[i][j]) a[i][j]+=a[i-1][j]; else a[i][j]=0;
            while (n&&tt[n]>a[i][j])
            {
                if (b[i+1][m]-b[i+1][t[n]-1]!=m-t[n]+1) ans++;
                w=t[n];
                n--;
            }
            if (a[i][j]&&(!n||tt[n]!=a[i][j])) t[++n]=w,tt[n]=a[i][j];
        }
         
        m=x;
        while (n)
        {
            if (b[i+1][m]-b[i+1][t[n]-1]!=m-t[n]+1) ans++;
            n--;
        }
    }
    printf("%d",ans);
    return 0;
 }

 


Beauty Values

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the second level. There is a sequence a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​ on the wall.
There is also a note board saying “the beauty value of a sequence is the number of different elements in the sequence”.
LZR soon comes up with the password of this level, which is the sum of the beauty values of all successive subintervals of the sequence on the wall.
Please help them determine the password!

输入描述:

The first line contains one positive integer nn_{}n​, denoting the length of the sequence.
The second line contains nn_{}n​ positive integers a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​, denoting the sequence.

1≤ai≤n≤1051 \le a_i \le n \le 10^51≤ai​≤n≤105

输出描述:

Print a non-negative integer in a single line, denoting the answer.

示例1

输入

4
1 2 1 3

输出

18

说明

The beauty values of subintervals [1,1],[2,2],[3,3],[4,4][1,1], [2,2], [3,3], [4,4]_{}[1,1],[2,2],[3,3],[4,4]​ are all 11_{}1​.
The beauty values of subintervals [1,2],[1,3],[2,3],[3,4][1,2], [1,3], [2,3], [3,4]_{}[1,2],[1,3],[2,3],[3,4]​ are all 22_{}2​.
The beauty values of subintervals [1,4],[2,4][1,4], [2,4]_{}[1,4],[2,4]​ are all 33_{}3​.
As a result, the sum of all beauty values are 1×4+2×4+3×2=181\times 4 + 2\times 4 + 3\times 2 = 181×4+2×4+3×2=18.

我们可以把每种数字对答案的贡献分开来计算,即枚举每个数字,求原序列有多少个子区间包含至少一个该数字,最后把答案累加起来即可。
问题在于求序列有多少个子区间包含至少一个某数字,可以考虑用全集减去不包含的子区间。不包含的子区间的个数可以枚举相邻两个数字,并累加中间空隙的子区间个数,再统计一下边界即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
int pre[100100];
int a[100100];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(pre,-1,sizeof(pre));
        ll ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);;
            if(pre[a[i]]==-1){
                ans+=1ll*i*(n-i+1);
                pre[a[i]]=i;
            }
            else{
                ans+=1ll*(i-pre[a[i]])*(n-i+1);
                pre[a[i]]=i;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 


CDMA

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
Special Judge, 64bit IO Format: %lld

题目描述

Gromah and LZR have entered the third level. There is a blank grid of size m×mm\times mm×m, and above the grid is a word “CDMA”.
In CDMA Technology, a Technology about computer network, every network node should be appointed a unique binary sequence with a fixed and the same length. Moreover, if we regard 00_{}0​ in the sequence as −1-1_{}−1​, and regard 11_{}1​ as +1+1_{}+1​, then these sequences should satisfy that for any two different sequences s,ts,t_{}s,t​, the inner product of s,ts,t_{}s,t​ should be exactly 00_{}0​.

The inner product of two sequences s,ts,t_{}s,t​ with the same length nn_{}n​ equals to ∑i=1nsiti\sum_{i=1}^{n} s_it_i∑i=1n​si​ti​.
So, the key to the next level is to construct a grid of size m×mm\times mm×m, whose elements are all −1-1_{}−1​ or 11_{}1​, and for any two different rows, the inner product of them should be exactly 00_{}0​.
In this problem, it is guaranteed that mm_{}m​ is a positive integer power of 22_{}2​ and there exists some solutions for input mm_{}m​. If there are multiple solutions, you may print any of them.

输入描述:

Only one positive integer mm_{}m​ in one line.
m∈{2k  ∣  k=1,2,⋯ ,10}m \in \{2^k \; | \;k = 1, 2, \cdots, 10\}m∈{2k∣k=1,2,⋯,10}

输出描述:

Print mm_{}m​ lines, each contains a sequence with length mm_{}m​, whose elements should be all −1-1_{}−1​ or 11_{}1​ satisfying that for any two different rows, the inner product of them equals 00_{}0​.

You may print multiple blank spaces between two numbers or at the end of each line, and you may print any number of blank characters at the end of whole output file.

示例1

输入

2

输出

1 1
1 -1

说明

The inner product of the two rows is 1×(−1)+1×1=01\times(-1) + 1\times 1 = 01×(−1)+1×1=0.

首先 m=2 时的答案是已经知道了的,考虑用 m 构造出 2m 的解:
不妨设方阵 A 为 m 的解,那么下面这个方阵则是 2m 的一个解:[A][A -A]
把每一行记为 (0/1, i),表示是上半区/下半区的第 i 行。
首先如果 i 不相同,那么内积显然就是 0 了。
现在考虑 (0,i) 和 (1,i),可知左半部分的内积贡献为 m,右半部分的内积贡献为 -m,加起来也就是 0 了

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
int s[1500][1500];
void rev(int x,int y,int xx,int yy){
    for(int i=x;i<=xx;i++){
        for(int j=y;j<=yy;j++){
            s[i][j]^=1;
        }
    }
}
void gao(int x,int y,int xx,int yy){
    if(xx==x && yy==y) s[x][y]=0;
    else{
        int mx=(x+xx)/2,my=(y+yy)/2;
        gao(x,y,mx,my);gao(x,my+1,mx,yy);
        gao(mx+1,y,xx,my);gao(mx+1,my+1,xx,yy);
        rev(mx+1,my+1,xx,yy);
    }
    return;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==2){
            printf("1 1\n1 -1\n");
        }
        else{
            gao(1,1,n,n);
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(j!=1) printf(" ");
                    printf("%d",s[i][j]?1:-1);
                }
                printf("\n");
            }
        }
    }
    return 0;
}

 


Explorer

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.
There are nn_{}n​ vertices and mm_{}m​ bidirectional roads in this level, each road is in format (u,v,l,r)(u, v, l, r)_{}(u,v,l,r)​, which means that vertex uu_{}u​ and vv_{}v​ are connected by this road, but the sizes of passers should be in interval [l,r][l, r]_{}[l,r]​. Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.
Moreover, vertex 11_{}1​ is the starting point and vertex nn_{}n​ is the destination. Gromah and LZR should go from vertex 11_{}1​ to vertex nn_{}n​ to enter the next level.
At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from 11_{}1​ to nn_{}n​.
Please help them to find the number of valid sizes.

输入描述:

The first line contains two positive integers n,mn,m_{}n,m​, denoting the number of vertices and roads.
Following m lines each contains four positive integers u,v,l,ru, v, l, r_{}u,v,l,r​, denoting a bidirectional road (u,v,l,r)(u, v, l, r)_{}(u,v,l,r)​.

1≤n,m≤105,1≤u<v≤n,1≤l≤r≤1091 \le n,m \le 10^5, 1 \le u < v \le n, 1 \le l \le r \le 10^91≤n,m≤105,1≤u<v≤n,1≤l≤r≤109

输出描述:

Print a non-negative integer in a single line, denoting the number of valid sizes.

示例1

输入

5 5
1 2 1 4
2 3 1 2
3 5 2 4
2 4 1 3
4 5 3 4

输出

2

说明

There are 2 valid sizes : 2 and 3.
For size 2, there exists a path 1→2→3→51 \rightarrow 2 \rightarrow 3 \rightarrow 51→2→3→5.
For size 3, there exists a path 1→2→4→51 \rightarrow 2 \rightarrow 4 \rightarrow 51→2→4→5.

时间分治
首先将size离散,之后建一颗以size为关键字的线段树,再把所有边按照规定的size区段加进对应的线段树节点;

然后从线段树的跟向下DFS每次用按秩合并优化并查集,回溯时要求可撤销;

然后到了叶子结点就看1和n是否在同一个集合内是的话这个叶子节点的size就可以带来贡献,否则不行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
inline int read(){
    int x = 0;
    char c = getchar();
    bool flag = 0;
    while(!isdigit(c)) {
        if(c == '-')
            flag = 1;
        c = getchar();
    }
    while(isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return flag ? -x : x;
}
vector<int> seg[100010<<4];
int u[100010],v[100010],n,m,fa[100010],sz[100010];
int l[100010],r[100010],b[200020];
void modi(int pos,int l,int r,int ll,int rr,int pt){
    if(l>r) return;
    if(l==ll && r==rr){seg[pos].push_back(pt);return;}
    int md=(l+r)>>1;
    if(md>=rr) modi(pos<<1,l,md,ll,rr,pt);
    else if(md<ll) modi((pos<<1)|1,md+1,r,ll,rr,pt);
    else modi(pos<<1,l,md,ll,md,pt),modi((pos<<1)|1,md+1,r,md+1,rr,pt);
    return;
}
ll ans=0;
struct node{int* a;int b;};
vector<node> p[40];
int fi(int pt){
    return pt==fa[pt]?pt:fi(fa[pt]);
}
void gao(int pos,int l,int r,int d){
    if(l>r) return;
    p[d].clear();
    for(int i:seg[pos]){
        int x=fi(u[i]),y=fi(v[i]);
        if(x==y) continue;
        if(sz[x]<sz[y]) swap(x,y);
        p[d].push_back((node){&fa[y],fa[y]});
        p[d].push_back((node){&fa[y],fa[y]});
        sz[x]+=sz[y];
        fa[y]=x;
    }
    if(l==r){
        int f=fi(1),t=fi(n);
        if(f==t){
            ans+=b[r+1]-b[l];      
        }
        for(int i=0;i<(int)p[d].size();i++) *(p[d][i].a)=p[d][i].b;
        return;
    }
    int md=(l+r)>>1;
    gao(pos<<1,l,md,d+1);gao((pos<<1)|1,md+1,r,d+1);
    for(int i=0;i<(int)p[d].size();i++) *(p[d][i].a)=p[d][i].b;
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        u[i]=read(),v[i]=read(),l[i]=read(),r[i]=read();
        r[i]++;b[i*2-1]=l[i];b[i<<1]=r[i];
    }
    sort(b+1,b+2*m+1);
    for(int i=1;i<=m;i++) modi(1,1,2*m-1,lower_bound(b+1,b+1+2*m+1,l[i])-b,lower_bound(b+1,b+1+2*m+1,r[i])-b-1,i);
    for(int i=1;i<=m;i++) sz[i]=1,fa[i]=i;
    gao(1,1,2*m-1,0);
    printf("%lld\n",ans);
    return 0;
}

 


Gemstones

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the seventh level. There are a sequence of gemstones on the wall.
After some tries, Gromah discovers that one can take exactly three successive gemstones with the same types away from the gemstone sequence each time, after taking away three gemstones, the left two parts of origin sequence will be merged to one sequence in origin order automatically.
For example, as for “ATCCCTTG”, we can take three ‘C’s away with two parts “AT”, “TTG” left, then the two parts will be merged to “ATTTG”, and we can take three ‘T’s next time.
The password of this level is the maximum possible times to take gemstones from origin sequence.
Please help them to determine the maximum times.

输入描述:

Only one line containing a string ss_{}s​, denoting the gemstone sequence, where the same letters are regarded as the same types.

1≤∣s∣≤1051 \le |s| \le 10^51≤∣s∣≤105
ss_{}s​ only contains uppercase letters.

输出描述:

Print a non-negative integer in a single line, denoting the maximum times.

示例1

输入

ATCCCTTG

输出

2

说明

One possible way is that ‘‘ATCCCTTG "  →  ‘‘ATTTG "  →‘‘AG "``ATCCCTTG\,"  \; \rightarrow \; ``ATTTG\," \; \rightarrow ``AG\,"‘‘ATCCCTTG"→‘‘ATTTG"→‘‘AG".

从左到右依次把字符加入栈中,如果某个时刻栈顶的三个字符相同,则将其弹出栈顶并把答案加 1,最后输出一下答案即可。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
char sta[100100];
int main(){
    char s[100100];
    while(scanf("%s",s)!=EOF){
        int l=strlen(s);
        int top=0,cnt=0;
        for(int i=0;i<l;i++){
            sta[top]=s[i];
            if(top>=2){
                if(sta[top]==sta[top-1] && sta[top]==sta[top-2]){
                    top-=3;
                    cnt++;
                }
            }
            top++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

 


Just Jump

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the final level. In this level, they need to cross the sea of death to gain the treasures.
The sea of death is of width LL_{}L​, and there are L−1L-1_{}L−1​ stones inside the sea. Assume that Gromah and LZR are at position 00_{}0​ initially, that the treasures are at position LL_{}L​, and that stones are at position 1,2,⋯ ,L−11,2, \cdots, L-11,2,⋯,L−1 respectively. So Gromah and LZR can jump on the stones to cross the sea.
Unfortunately, the stones are not stable. To ensure safety, Gromah and LZR should go forward at least dd_{}d​ positions each time. Formally, if they are at position xx_{}x​ currently, they should jump onto the positions not less than x+dx+d_{}x+d​. Moreover, they can’t be at positions greater than LL_{}L​ in any time, which means that the destination of their last jump should be exactly position LL_{}L​, or the treasure keepers will see them and come to eat them.
More unfortunately, the Infernos under the sea will attack them mm_{}m​ times in total, each attack can be described as a tuple (t,p)(t,p)_{}(t,p)​, denoting that the stone at position pp_{}p​ will be attacked right after their tt_{}t​-th jump, which means their destination of tt_{}t​-th jump can’t be position pp_{}p​.
But fortunately, here comes the farmer(mentioned in problem I but not necessary to care in this problem) and he tells Gromah and LZR all the attack plans, so they can work out some jumping plans according to the information given by the farmer to get to the destination without being attacked.
Please help them determine the number of jumping plans satisfying all the restrictions described above. Since the number may be very large, you should report it modulo 998244353998244353_{}998244353​.
Two jumping plans are considered different if there exists at least one tt_{}t​ that their positions after tt_{}t​-th jump are different in two plans.

输入描述:

The first line contains three positive integers L,d,mL,d,m_{}L,d,m​, denoting the width of the sea, the lower bound of jumping distance, and the number of attacks.
Following mm_{}m​ lines each contains two positive integers t,pt,p_{}t,p​, denoting an attack (t,p)(t,p)_{}(t,p)​.

1≤d≤L≤107,1≤t,p<L,1≤m≤30001 \le d \le L \le 10^7, 1 \le t,p < L, 1 \le m \le 30001≤d≤L≤107,1≤t,p<L,1≤m≤3000
mm_{}m​ attacks are pairwise distinct, where two attacks (t1,p1),(t2,p2)(t_1, p_1), (t_2, p_2)(t1​,p1​),(t2​,p2​) are considered different if t1≠t2t_1 \neq t_2t1​​=t2​ or p1≠p2p_1 \neq p_2p1​​=p2​ or both.

输出描述:

Print a non-negative integer in one line, denoting the answer modulo 998244353998244353_{}998244353​.

示例1

输入

5 2 1
1 2

输出

2

说明

There are three plans originally : 0→2→5,  0→3→5,  0→50\rightarrow 2 \rightarrow 5, \; 0\rightarrow 3 \rightarrow 5, \; 0\rightarrow 50→2→5,0→3→5,0→5. But after the first jump, the stone at position 2 will be attacked, so plan 0→2→50 \rightarrow 2 \rightarrow 50→2→5 should be abandoned and 2 valid plans remain.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll md=998244353;
const int N=1e7+7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
int l,d,m;
int fac[N*2+1],inv[N*2+1];
int qp(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=1ll*ret*a%md;
        a=1ll*a*a%md;b>>=1;  
    }
    return ret;
}
struct node{
    int t,p;
    bool operator < (const node& b){
        if(t!=b.t)return t<b.t;
        else return p<b.p;
    }
} g[4000];
int dp[2][4000];
int pre[N+1];
int gao(int p,int t){
    if(1ll*p-1ll*t*d<0) return 0;
    p-=t*d;
    return 1ll*fac[p+t-1]*inv[p]%md*inv[t-1]%md;
}
int main(){
    scanf("%d%d%d",&l,&d,&m);
    fac[0]=1;
    for(int i=1;i<=2*N;i++) fac[i]=1ll*fac[i-1]*i%md;
    inv[2*N]=qp(fac[2*N],md-2);
    for(int i=N*2-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%md;
    int cnt=0;pre[0]=1;for(int i=1;i<=l;i++) cnt=(1ll*cnt+((i-d)>=0?pre[i-d]:0))%md,pre[i]=cnt;
    for(int i=1;i<=m;i++) scanf("%d%d",&g[i].t,&g[i].p);
    sort(g+1,g+1+m);
    dp[0][0]=1;
    ll ans=pre[l];
    for(int i=1;i<=m;i++){
        for(int pt=0;pt<=1;pt++)for(int j=0;j<i;j++)
            dp[pt][i]=(1ll*dp[pt][i]+1ll*dp[pt^1][j]*gao(g[i].p-g[j].p,g[i].t-g[j].t)%md)%md;
        ans=(ans+1ll*(dp[0][i]+1ll*(md-1)*dp[1][i]%md)%md*pre[l-g[i].p]%md)%md;
    }
    printf("%lld\n",ans);
    return 0;
}

 

发表评论,支持MarkDown语法