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

传送门

B.Crazy Binary String（前缀和）

•题意

　　给你一个只包含 0,1 的串 s；

　　求满足 0 与 1 的个数相同的子串和子序列；

　　输出这两个串的最大长度；

•思路

找01个数相同的子串，类似于这个(A题)，(话说比那个简单有没有

根据前缀和求增量，如果增量相同的话，那这段区间里01个数就相同，然后每次取最大的ans

找01个数相同的子序列，那肯定是01中个数少的那个所组成的，输出两倍就好了

•代码

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
char s[10005];
int zero,one;
int ans;
int main()
{
    int n;
    cin>>n;
    mp[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        if(s[i]=='0')
            zero++;
        else
            one++;
        if(mp.count(zero-one))
            ans=max(ans,i-mp[zero-one]);
        else
            mp[zero-one]=i;
    }
    cout<<ans<<' '<<min(zero,one)*2<<endl;
}

 

D.Big Integer（数论）

•题意

$A_{n}=underbrace{1......1}_{n}$

$A_{i^j}$ ≡ 0 (mod p)的个数，其中 1 ≤ i ≤ n , 1 ≤ j ≤ m；

•思路

写起来有点麻烦...具体戳这里吧

防止忘记推导过程，记一下重点...

•代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int p,n,m;
ll ans;
int P[105];
int x[105];

ll qpow(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int F()//因子分解得到最小循环节d,Max(d)=p-1
{
    int d=p-1;
    for(int i=1;i*i<=p-1;i++)
    {
        if((p-1)%i==0)
        {
            if(qpow(10,i,p)==1)
                d=min(d,i);
            if(qpow(10,(p-1)/i,p)==1)
                d=min(d,(p-1)/i);
        }
    }
    return d;
}

int PrimeF(int d)//质因子分解 得到pi,xi,k
{
    int k=0;
    for(int i=2;i*i<=d;i++)
    {
        if(d%i==0)
        {
            P[++k]=i;
            x[k]=0;
        }
        while(d%i==0)
        {
            x[k]++;
            d/=i;
        }
    }
    if(d!=1)
    {
        P[++k]=d;
        x[k]=1;
    }
    return k;
}

void Slove()
{
    int d=F();
    int k=PrimeF(d);
    int maxX=*max_element(x+1,x+1+k);
    for(int j=1;j<=m;j++)//固定j,求个数
    {
        ll g=1;
        for(int i=1;i<=k;i++)
            g*=qpow(P[i],(x[i]+j-1)/j,p);  //p^(x+j-1)/j
        ans+=n/g;

        if(j>=maxX)//此时g为最小不再变化，共有(n/g)*(m-j)种
        {
            ans+=n/g*(m-j);
            break;
        }
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>p>>n>>m;
        ans=0;
        if(p==3)
            ans=n/3*m;
        else if(p==2||p==5)
            ans=0;
        else
            Slove();
        cout<<ans<<endl;
    }
}

 

F.Planting Trees（单调队列优化）

•题意

　　在一块 n×n 的土地上植树；

　　第(i,j) 块有棵高为 a[ i ][ j ] 树;

　　必须要找一片满足任意两棵树的高度差都不超过 m 的矩形区域；

　　并且想要这个矩形区域面积尽可能大；

　　求出这个矩形区域，输出这个矩形区域包含的树的个数；

•思路

注意：

单调队列代码实现时

①要分清楚值和索引，蟹蟹可爱的猪猪帮我找bug,此致敬礼！

②在出队列时(head++时）要注意队列非空,借鉴猪猪的经验！

•代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int a[maxn][maxn];
int demin[maxn];
int demax[maxn];
int Min[maxn];
int Max[maxn];
int n,m;
int ans;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];


        for(int i=1;i<=n;i++)
        {
            //初始化
            for(int j=1;j<=n;j++)
                Min[j]=Max[j]=a[i][j];

            //枚举上下边界
            //从第i行到第k行求最优解
            for(int k=i;k<=n;k++)
            {
                for(int j=1;j<=n;j++)
                {
                    //维护当前上下边界第i到第k行 每列的最大值最小值
                    Min[j]=min(Min[j],a[k][j]);
                    Max[j]=max(Max[j],a[k][j]);
                }

                int l=1,r=1;
                int headmin=1,headmax=1;
                int tailmin=0,tailmax=0;
                //枚举右边界r
                //维护两个单调队列
                while(r<=n)
                {
                    //单调递增队列，头是最小值
                    while(headmin<=tailmin&&Min[demin[tailmin]]>=Min[r])
                        tailmin--;
                    demin[++tailmin]=r;
                    //单调递减队列，头是最大值
                    while(headmax<=tailmax&&Max[demax[tailmax]]<=Max[r])
                        tailmax--;
                    demax[++tailmax]=r;
                    
                    //每个右边界确定后(也就是在此右边界下)
                    //找符合条件并使面积尽量大的左边界
                    while(l<=r&&Max[demax[headmax]]-Min[demin[headmin]]>m)
                    {
                        l++;
                        while(headmax<=tailmax&&demax[headmax]<l)
                            headmax++;
                        while(headmin<=tailmin&&demin[headmin]<l)
                            headmin++;
                    }
                    ans=max(ans,(r-l+1)*(k-i+1));
                    r++;//枚举下一个右边界 找最大值
                }
            }
        }
        cout<<ans<<endl;
    }
}

G.Removing Stones（假博弈 思维?）

•题意

有n堆石头，如果石头总数是奇数的话，就从最小堆中拿走一块

如果总数是偶数堆或者是减少石头后，那每次从不为0的任意两堆中同时拿走一块

如果最后都拿完，则Mark胜利

现在给出每堆石头数，问存在多少对[l,r]使得可以有优胜情况

•思路

可以想一种极端情况，所有的堆都和最大的一堆一起拿

那最大的一堆个数就是除本身以外所有堆的和

通常情况就是其他堆之间也可以一起拿，

那这个问题就转化成了

有多少个区间使得在这个区间里，最大的堆<=其他堆的和

貌似不太好找...但是！有一句话叫做正难则反！

那我们可以用所有的情况-不符合的情况_(:з」∠)_

那怎么找不符合的情况呢？

我们可以通过枚举每一个堆 i，以这个堆为最大堆

利用 最大的堆>其他堆的和，找到极限左边界，

然后枚举左边界，通过固定的左边界L，找到右边界R

那这个左边界L所构成情况就是 L—i，L—i+1...... L—R

也就是每个L都有(R-i+1)种不符合的情况

•代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300005
ll T,n,m;
ll a[N];

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        ll ans=(ll)n*(n+1)/2;
        for(ll i=1;i<=n;i++)
            cin>>a[i];
        for(ll i=1;i<=n;i++)//枚举堆i
        {
            ll l=i,r=i,sum=0;
            while(l>1&&a[i]>sum+a[l-1])   //对于每一个a[i],找符合条件的最左边界
                l--,sum+=a[l];

            for(int L=l;L<=i;L++)         //枚举L
            {
                while(r<n&&a[i]>sum+a[r+1])//固定L,找到最右边界的
                    r++,sum+=a[r];

                ans-=(r-i+1);//减去由L与i及其右边组成的
                sum-=a[L];
            }
        }
        cout<<ans<<endl;
    }
}

H.Magic Line（思维）

•题意

        给你 n 个点，满足 n 为偶数，并且这 n 个为不重复的整数点；

　　求将这 n 个点均分为两部分的直线 L，即有 n/2 个点严格在 L 上方，n/2个点严格在 L 下方；

　　输出 L 上的任意两个点 (x₁,y₁),(x₂,y₂) 的坐标；

　　要 x₁,y₁,x₂,y₂ 为整数，且 |x₁|,|y₁|,|x₂|,|y₂| ≤ 10⁹;

•思路

看到这个题，我第一反应是分蛋糕的题

但是他不是！

然后...然后就game over了

用出题人的话来说就是

假设没有x重复，可以按x排序，然后在中间画一条线

现在有x重复，可以按照(x,y)双关键字排序，在中间偏左和中间偏右的两个中间点之间，画一条稍微稍微倾斜的线

两种实现方式的具体细节在代码中解释

•代码

实现方式一

#include<bits/stdc++.h>
using namespace std;
const int inf=1e8+5;
struct node
{
    int x,y;
}s[1005];

bool cmp(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>s[i].x>>s[i].y;
        sort(s+1,s+1+n,cmp);
        int x1=s[n/2].x-1;
        int x2=s[n/2+1].x+1;
        int y1=s[n/2].y+inf;
        int y2=s[n/2+1].y-inf;
        cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
        //①为什么要±1
        //稍微倾斜一下，并且保证不能有交点
        //x±(0,1],又因为是整数,x±1
              
        //②为什么是inf
        //y变化的很大，x变化的很小,这条线及其接近于竖直
        //才是稍微稍微倾斜一下
        
        //③为什么是±inf
        //y±相同的数，使得中间两个点这关于条线对称
        //正好分成左右两个部分使得左右的点个数相同
    }
}

实现方式二

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e8+5;
struct node
{
    int x,y;
}s[maxn];
bool cmp(node a,node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int t;
int main()
{
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>s[i].x>>s[i].y;
        sort(s+1,s+n+1,cmp);
        int xx=s[n/2].x;
        int yy=s[n/2].y;
        cout<<xx-1<<' '<<yy+maxn<<' '<<xx+1<<' '<<yy-maxn+1<<endl;
        //①为什么要±1
        //稍微倾斜一下，并且保证不能有交点
        //x±(0,1],又因为是整数,x±1
        
        //②为什么要是inf
        //y变化的很大，x变化的很小,这条线及其接近于竖直
        //才是稍微稍微倾斜一下
        
        //③为什么是±inf
        //y±相同的数，使得中间两个点这关于条线对称
        //正好分成左右两个部分使得左右的点个数相同
        
        //④为什么y要+1
        //中间可能有整点，为了防止对称的时候过中间的整点y+1
        //为什么是+1，因为x2-x1>=2，当x2-x1=2时，k=y2-y1+2/x2-x1=(y2-y1/x2-x1)+1
        //可能过整点，就可能相交！
    }
}

J.LRU management（模拟 unordered_map+list）

•题意

一个固定长度的LRU数组，每次有两种操作

0号操作：若查询的字符串在数组中存在，就把它取出来，并原有值保持不变，压入数组末尾。

　　　　  若查询的字符串不存在则直接加入到末尾，值为输入的v。

　　　　  输出此字符串的值v

1号操作：先得出输入的字符串在数组中的下标k，查询下标为（k+v）的数组元素的值，

　　　　  若k或（k+v）不存在都输出Invalid。

•思路

用unordered_map<string,list<>::iterator>来模拟

不会这两个函数的可以先去看下用法....

注意用cout时换行用endl会TLE，改成' '就会AC，时间快的还很多

以前都不知道endl这么费时间_(:з」∠)_

•代码

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    string ss;
    int v;
};
list<Node> l;
unordered_map<string,list<Node>::iterator> mp;

int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0);
    int t;;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        int op,v;
        string s;
        mp.clear(),l.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>op>>s>>v;

            ///1操作
            if(op)
            {
                ///存在则得出输入的字符串在数组中的下标k，查询下标为（k+v）的数组元素的值
                if(mp.count(s))
                {
                    list<Node> ::iterator it=mp[s];
                    if(v==-1)
                    {
                        if(it==l.begin())
                            cout<<"Invalid
";
                        else
                        {
                            it--;
                            cout<<it->v<<"
";
                        }
                    }
                    else if(v==0)
                        cout<<it->v<<"
";
                    else
                    {
                        it++;
                        if(it==l.end())
                            cout<<"Invalid"<<"
";
                        else
                            cout<<it->v<<"
";
                    }
                }
                ///若k或（k+v）不存在都输出Invalid。
                else
                    cout<<"Invalid
";
            }
            ///0操作
            else
            {
                ///存在则 把它取出来，原有值保持不变，压入数组末尾。
                if(mp.count(s))
                {
                    list<Node> ::iterator it=mp[s];
                    cout<<it->v<<"
";
                    l.push_back(Node{it->ss,it->v});
                    l.erase(it);
                    it=l.end();
                    it--;
                    mp[s]=it;
                }
                ///不存在则直接加入到末尾，值为输入的v。
                else
                {
                    cout<<v<<"
";
                    l.push_back(Node{s,v});
                    list<Node> ::iterator it=l.end();
                    it--;
                    mp[s]=it;
                }
                int sz=l.size();
                while(sz>m)
                {
                    mp.erase(l.begin()->ss);
                    l.pop_front();
                    sz--;
                }
            }
        }
    }
}