2019牛客暑期多校训练营（第三场）

题目

B Crazy Binary String（签到+前缀和）

题意：给定一个 01 字符串，求最长的 01数量相等的子串和子序列的长度。
思路：前缀和相等的位置累积一下答案即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;

int n;
char s[100010];
map<int,int> mp;
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    mp[0]=0;
    int now=0,ans1=0;
    int cnt0=0,cnt1=0;
    for(int i=1; i<=n; ++i)
    {
        now+=(s[i]=='1'?1:-1);
        if(mp.count(now)) ans1=max(ans1,i-mp[now]);
        else mp[now]=i;
        if(s[i]=='1') cnt1++;
        else cnt0++;
    }
    int ans2=min(cnt0,cnt1)*2;
    printf("%d %d\n",ans1,ans2);
    return 0;
}

D Big Integer （循环节）

题意：定义 A ( 1 ) = 1 , A ( 2 ) = 11 , A ( 3 ) = 111 , … A(1)=1,A(2)=11,A(3)=111,\dots A(1)=1,A(2)=11,A(3)=111,…。求 ∑ i = 1 n ∑ j = 1 m [ A ( i j ) ≡ 0 ( m o d   p ) ] \sum_{i=1}^n\sum_{j=1}^m [A(i^j)\equiv 0 (mod\ p)] ∑i=1n​∑j=1m​[A(ij)≡0(mod p)] ( 1 ≤ n , m , p ≤ 1 0 9 ) (1\le n,m,p\le 10^9) (1≤n,m,p≤109)

思路：

  • A ( n ) = 1 0 n − 1 9 A(n)=\frac {10^n-1}{9} A(n)=910n−1​
  • 当 p ≠ 3 p\ne 3 p​=3 时，9 和 p 互质， 9存在逆元。式子转化为： 1 0 n ≡ 1 ( m o d   p ) 10^n\equiv 1 (mod \ p) 10n≡1(mod p)
  • 当 10 和 p 互质的时候，根据费尔马小定理 a ϕ ( p ) ≡ 1 ( m o d   p ) a^{\phi (p)} \equiv 1 (mod \ p) aϕ(p)≡1(mod p) 可得， 1 0 p − 1 ≡ 1 ( m o d   p ) 10^{p-1} \equiv 1 (mod \ p) 10p−1≡1(mod p)
  • 但是这个 p − 1 p-1 p−1 不一定是最小的循环节 d d d 。因此可以枚举 p − 1 p-1 p−1 的因子，找到符合条件的最小循环节。
  • 现在就是求 i j i^j ij 是否是 d d d 的倍数，如果是，那就是符合条件的。即求， ∑ i = 1 n ∑ j = 1 m [ d ∣ i j ] \sum_{i=1}^n\sum_{j=1}^m [d | i^j] ∑i=1n​∑j=1m​[d∣ij]
  • 假设 d = p 1 a 1 p 2 a 2 … p k a k d = p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} d=p1a1​​p2a2​​…pkak​​ 此时可以枚举 j j j 的次数。那么 i i i 需要满足的条件是 g = p 1 ⌈ a 1 j ⌉ p 2 ⌈ a 2 j ⌉ … p k ⌈ a k j ⌉ g = p_1^{\lceil \frac {a_1}{j} \rceil}p_2^{\lceil \frac {a_2}{j} \rceil}\dots p_k^{\lceil \frac {a_k}{j} \rceil} g=p1⌈ja1​​⌉​p2⌈ja2​​⌉​…pk⌈jak​​⌉​。那么就是 n g \frac ng gn​ 个数是满足条件的。
  • 而 a i a_i ai​ 的最大值为 30 。那么 j j j 最多枚举到 30 时，后面的 g g g 就可以固定为 g = p 1 p 2 … p k g = p_1p_2\dots p_k g=p1​p2​…pk​
  • 另外当 10 和 p 不互质的时候，即 p 为 2 或 5 的时候，答案显然是 0
  • p 为 3 时，可以发现是 ⌊ n 3 ⌋ m \lfloor \frac {n}{3}\rfloor m ⌊3n​⌋m
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int t,n,m,p;
int qpow(int b,int n,int mod)
{
    int res=1;
    while(n)
    {
        if(n&1) res=1ll*res*b%mod;
        b=1ll*b*b%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&p,&n,&m);
        if(p==2||p==5) puts("0");
        else if(p==3) printf("%lld\n",1ll*n/3*m);
        else
        {
            int d=p-1,a=p-1;
            for(int i=2; i*i<=a; ++i)
            {
                if(a%i==0)
                {
                    if(qpow(10,i,p)==1) d=min(d,i);
                    if(qpow(10,a/i,p)==1) d=min(d,a/i);
                }
            }
            a=d;
            int mx=0;
            vector<pair<int,int> >dd;
            for(int i=2; i*i<=a; ++i)
            {
                if(a%i==0)
                {
                    int cnt=0;
                    while(a%i==0) a/=i,cnt++;
                    dd.push_back({i,cnt});
                    mx=max(mx,cnt);
                }
            }
            if(a>1) dd.push_back({a,1}),mx=max(mx,1);

            ll ans=0,g=1;
            for(int j=1; j<=min(m,mx); ++j)
            {
                g=1;
                for(auto x: dd)
                {
                    g*=pow(x.first,(x.second+j-1)/j);
                }
                ans+=n/g;
            }
            ans+=max(m-mx,0)*(n/g);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

F Planting Trees（单调队列）

题意： 给定 n × n n\times n n×n 的矩阵中，每个点有权值 a i j a_{ij} aij​，求 m x − m n ≤ m mx-mn\le m mx−mn≤m 的最大子矩阵的大小。

思路：枚举上界和下界，然后开两个单调队列分别维护，最大值单调递减队列，最小值单调递增队列。每次取队首判断是否符合条件，然后在条件内更新答案。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=505;
int t,n,m,a[maxn][maxn];
int mx[maxn],mn[maxn],q1[maxn],h1,t1,q2[maxn],h2,t2;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                scanf("%d",&a[i][j]);
        int ans=0;
        for(int i=1; i<=n; ++i)
        {
            for(int j=i; j<=n; ++j)
            {
                if(i==j) for(int k=1; k<=n; ++k) mx[k]=mn[k]=a[i][k];
                else
                {
                    for(int k=1; k<=n; ++k)
                    {
                        mx[k]=max(mx[k],a[j][k]);
                        mn[k]=min(mn[k],a[j][k]);
                    }
                }
                h1=1,t1=0,h2=1,t2=0;
                int l=1;
                for(int r=1; r<=n; ++r)
                {
                    while(h1<=t1&&mn[r]<=mn[q1[t1]]) t1--;
                    q1[++t1]=r;
                    while(h2<=t2&&mx[r]>=mx[q2[t2]]) t2--;
                    q2[++t2]=r;

                    while(h1<=t1&&h2<=t2&&mx[q2[h2]]-mn[q1[h1]]>m)
                    {
                        l++;
                        while(h1<=t1&&q1[h1]<l) h1++;
                        while(h2<=t2&&q2[h2]<l) h2++;
                    }
                    ans=max(ans,(j-i+1)*(r-l+1));
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

G Removing Stones （分治）

题意：给定一个长度为 n 的数组。查询有多少个区间满足： 2 m x < = s u m 2mx<=sum 2mx<=sum。 ( 1 ≤ n ≤ 300000 ) (1\le n \le 300000) (1≤n≤300000)。区间长度为 2 时，要求两个数相等。

思路：

  • 分治：区间为 [ l , r ] [l,r] [l,r] 时用 rmq 找到最大值的位置 k 之后，找包含这个最大值的区间数量。在 k-l 和 r -k 中，找一个小区间，枚举端点，然后二分出符合条件的另一个端点。然后分治剩余区间。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int maxn=3e5+5;

int t,n;
ll a[maxn],pref[maxn];
int Log[maxn];
pii dp[maxn][22];

void init()
{
    for(int i=1; i<=n; ++i) dp[i][0]= {a[i],i};
    for(int j=1; (1<<j)<=n; ++j)
        for(int i=1; i+(1<<j)-1<=n; ++i)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
pii queryMax(int l,int r)
{
    int k=Log[r-l+1];
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
ll ans=0;
void solve(int l,int r)
{
    if(l>=r) return;
    if(l+1==r)
    {
        if(a[l]==a[r]) ans++;
        return;
    }
    int k=queryMax(l,r).second;
    if(k-l<r-k)
    {
        for(int i=l; i<=k; ++i)
        {
            int pos=lower_bound(pref+k,pref+1+r,2*a[k]+pref[i-1])-pref;
            if(pos>=k&&pos<=r+1&&pref[pos]-pref[i-1]>=2*a[k]) ans+=r-pos+1;
        }
    }
    else
    {
        for(int i=k; i<=r; ++i)
        {
            int pos=upper_bound(pref+l-1,pref+k,pref[i]-2*a[k])-pref-1;
            if(pos>=l-1&&pos<=k&&pref[i]-pref[pos]>=2*a[k]) ans+=pos+1-l+1;
        }
    }
    solve(l,k-1);
    solve(k+1,r);
}
int main()
{
    Log[1]=0;
    for(int i=2; i<maxn; ++i) Log[i]=Log[i/2]+1;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; ++i) scanf("%lld",&a[i]),pref[i]=pref[i-1]+a[i];
        init();
        ans=0;
        solve(1,n);
        printf("%lld\n",ans);
    }
    return 0;
}

H Magic Line （几何思维）

思路：找到中间位置，然后找个斜率比较大的直线。

I Median （DP求方案数）

题意：给定一个序列 b 1 , b 2 , … , b n − 2 b_1,b_2,\dots ,b_{n-2} b1​,b2​,…,bn−2​，要求构造一个序列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1​,a2​,…,an​。满足 b i = m i d ( a i , a i + 1 , a i + 2 ) b_i=mid(a_i,a_{i+1},a_{i+2}) bi​=mid(ai​,ai+1​,ai+2​)。

思路：可以发现，每个 a i a_i ai​ 会影响 b b b 序列中的 3 个位置 b i − 2 , b i − 1 , b i b_{i-2} ,b_{i-1}, b_i bi−2​,bi−1​,bi​ 。而且 a i a_i ai​ 可以完全取这 3 个值中的一个没有任何影响。假设 a i a_i ai​ 不取这 3 个值，那么必然是大于这 3 个值，或者小于这 3 个值。此时，把 a i a_i ai​ 调整成其中的大者或者小者完全没有影响。

  • 因此处理出每个 a i a_i ai​ 可以取的 3 个 b i b_i bi​ 的值。设为 v[i][0/1/2]。
  • 设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示 a i a_i ai​ 取 v [ i ] [ j ] v[i][j] v[i][j]， a i − 1 a_{i-1} ai−1​ 取 v [ i − 1 ] [ k ] v[i-1][k] v[i−1][k]，是否合法。此时可以枚举 d p [ i − 1 ] [ k ] [ l ] dp[i-1][k][l] dp[i−1][k][l] 表示 a i − 1 a_{i-1} ai−1​ 取 v [ i − 1 ] [ k ] , a i − 2 v[i-1][k],a_{i-2} v[i−1][k],ai−2​ 取 v [ i − 2 ] [ l ] v[i-2][l] v[i−2][l] 是否合法。判断 v [ i ] [ j ] 、 v [ i − 1 ] [ k ] 、 v [ i − 2 ] [ l ] v[i][j]、v[i-1][k]、v[i-2][l] v[i][j]、v[i−1][k]、v[i−2][l] 这 3 个数的中位数是否等于 b i b_i bi​ 即可。
  • 用 pre[i][j][k] 来记录转移的前一个位置，最后还原出答案即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;

int t,n,a[maxn],b[maxn];
int v[maxn][3];
bool dp[maxn][3][3];
int pre[maxn][3][3],ans[maxn];
int getMed(int a,int b,int c)
{
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
    return b;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=3; i<=n; ++i) scanf("%d",&b[i]);
        b[1]=b[2]=b[3];
        b[n+2]=b[n+1]=b[n];
        for(int i=1; i<=n; ++i)
        {
            v[i][0]=b[i];
            v[i][1]=b[i+1];
            v[i][2]=b[i+2];
        }
        for(int i=0; i<=n; ++i)
            for(int j=0; j<3; ++j)
                for(int k=0; k<3; ++k)
                    dp[i][j][k]=pre[i][j][k]=0;
        for(int j=0; j<3; ++j)
            for(int k=0; k<3; ++k)
                dp[2][j][k]=1;

        for(int i=3; i<=n; ++i)
            for(int j=0; j<3; ++j)
                for(int k=0; k<3; ++k)
                    for(int l=0; l<3; ++l)
                        if(dp[i-1][k][l]&&getMed(v[i-2][l],v[i-1][k],v[i][j])==b[i])
                        {
                            dp[i][j][k]=1;
                            pre[i][j][k]=l;
                        }
        bool ok=0;
        int now,last;
        for(int j=0; j<3; ++j)
            for(int k=0; k<3; ++k)
                if(dp[n][j][k])
                {
                    ok=1;
                    now=j;
                    last=k;
                }
        if(!ok) puts("-1");
        else
        {
            for(int i=n; i>=1; --i)
            {
                ans[i]=v[i][now];
                int p=pre[i][now][last];
                now=last;
                last=p;
            }
            for(int i=1; i<=n; ++i) printf("%d%c",ans[i],i==n?'\n':' ');
        }
    }
    return 0;
}

J LRU management （双向链表）

题意：维护长度为 M 的数组 array，Q个询问，维护两种操作

  • opt =0 时，读入字符串 s 和 v 。如果 array 中存在 s ，那么就将 s 移动到数组的末尾，并输出 array 中原来存在的 s 的权值。如果不存在 s ，那么将 s 插入到 array 的末尾。如果此时 array 数组满了，那么就删掉 array 的第一个元素，然后插入 s 到末尾，并输出 v 。
  • opt =1 时， 读入字符串 s 和 v 。假设 s 在数组中的位置为 k ，则输出 k + v 位置处字符串的权值。 ( v ∈ − 1 , 0 , 1 ) (v\in {-1,0,1}) (v∈−1,0,1)

( 1 ≤ Q , M ≤ 5 × 1 0 5 ) (1\le Q,M \le 5\times 10^5) (1≤Q,M≤5×105)

思路：用双向链表来维护数组，用 pre 和 nxt 数组维护指针，用 q 数组来存放地址中的字符串，用 map 来存放字符串的指针和权值。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
struct Node
{
    int idx,data;
};
int t,Q,m;
string q[maxn];
char ss[15];
int pre[maxn],nxt[maxn],sz,head,tail;
map<string,Node> mp;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&Q,&m);
        head=1,tail=0,sz=0;
        mp.clear();
        while(Q--)
        {
            int opt,v;
            string s;
            scanf("%d%s%d",&opt,ss,&v);
            for(int i=0; ss[i]; ++i) s.push_back(ss[i]);

            if(opt==0)
            {
                if(mp.count(s))
                {
                    int k=mp[s].idx;
                    if(sz==1||k==tail) printf("%d\n",mp[s].data);
                    else
                    {
                        if(k==head)
                        {
                            head=nxt[head];
                            nxt[pre[head]]=0;
                            pre[head]=0;
                        }
                        else
                        {
                            if(pre[k]&&nxt[k])
                            {
                                pre[nxt[k]]=pre[k];
                                nxt[pre[k]]=nxt[k];
                            }
                        }
                        q[++tail]=s;
                        nxt[tail-1]=tail;
                        pre[tail]=tail-1;
                        nxt[tail]=0;
                        mp[s].idx=tail;
                        printf("%d\n",mp[s].data);
                    }
                }
                else
                {
                    if(sz==m)
                    {
                        mp.erase(q[head]);
                        head=nxt[head];
                        nxt[pre[head]]=0;
                        pre[head]=0;
                        sz--;
                    }
                    if(sz==0) head=1,tail=0;
                    sz++;

                    q[++tail]=s;
                    nxt[tail-1]=tail;
                    pre[tail]=tail-1;
                    nxt[tail]=0;

                    mp[s]= {tail,v};
                    printf("%d\n",v);
                }
            }
            else
            {
                if(!mp.count(s)) puts("Invalid");
                else
                {
                    int k=mp[s].idx;
                    if(v==0) printf("%d\n",mp[s].data);
                    else if(v==1)
                    {
                        if(nxt[k]!=0) printf("%d\n",mp[q[nxt[k]]].data);
                        else puts("Invalid");
                    }
                    else if(v==-1)
                    {
                        if(pre[k]!=0) printf("%d\n",mp[q[pre[k]]].data);
                        else puts("Invalid");
                    }
                }
            }          
        }
    }
    return 0;
}