【LGR-089】洛谷 8 月月赛 II总结

【LGR-089】洛谷 8 月月赛 II总结

前言

很少正式的打完一场月赛，每次都是因为各种各样奇妙的原因咕咕咕了。

终于比较完整的打完了一场，虽然打的并不是很好，甚至有点失常了。

题目

T191672 谜

看到了 $k$ 的范围，然而推错了范围所以还是老老实实的写了循环。但是调了三个半小时怎么也没有调出来...

根据 $k$ 的范围，走的路径不会超过最后两行。两个等差数列公式就好了。满分代码如下：

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll t,n,k;
ll l,r,ans,tmp,res;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

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

inline ll getsum(ll x){
    return x*(x+1)%mod*qpow(2,mod-2)%mod;
}

inline ll getlast(ll x,ll y){
    ll pos=getsum(x);
    return (pos+pos-y+1)*y%mod*qpow(2,mod-2)%mod;
}

int main(){
    t=read();
    for(register int ac=1;ac<=t;++ac){
        n=read();k=read();
        res=0;
        res+=getlast(n,k/2)+getlast(n-1,k/2);
        if(k&1)
            res+=getsum(n)-(k/2+1)+1,res%=mod;
        printf("%lld\n",(res+2*mod)%mod);
    }
    return 0;
}

T166874 心の記憶

和上一场 vp 很像。

对于一些字符串，我们需要一些特判。具体点，以下字符串：

$0$ 或 $1$

$01$ 或 $10$

$n==m$

直接输出 $-1$ 。

在可行字符串里面，下面这种：

$00000000001$ 或 $11111111111110$

将 $1$ 或 $0$ 往里面插就好了。也就是 $01010101...001$ ，诸如此类，一直到长度达到了 $m$ 就可以了。万一字符串都遍历完了还没达到，在字符串后面强行插入 $a[n-1]$ ，直到长度到了 $m$ 即可。

剩下的就是普通的了。在 $a[n-2]$ 和 $a[n-1]$ 之间插入 $a[n-1]$ 对立的值（即 $a[n-1]$ 为 $0$ 它就为 $1$ 这种）。不断的插入同一个值，一直到 $m$ ，就完成了。应该没有情况了吧，这道题还算签到（比第一题签到）

#include <bits/stdc++.h>
#define ll long long
#define maxn 2000001
using namespace std;
ll t,n,m;
char a[maxn];

int main(){
    cin>>t;
    for(register int ac=1;ac<=t;++ac){
        cin>>n>>m>>a;
        if(n==1){
            printf("-1\n");
            continue;
        }
        if((a[0]=='0'&&a[1]=='1'||a[0]=='1'&&a[1]=='0')&&n==2){
            printf("-1\n");
            continue;
        }
        if(n==m){
            printf("-1\n");
            continue;
        }
        int ok=0;
        for(register int i=1;i<n-1;++i)
            if(a[i]!=a[i-1]){
                ok=1;
                break;
            }
        if(!ok&&a[n-2]!=a[n-1]){
            ll pos=m-n;
            for(register int i=0;i<n;++i)
                if(pos){
                    cout<<a[i];
                    if(a[i]=='1')
                        cout<<0;
                    else
                        cout<<1;
                    --pos;
                }
                else
                    cout<<a[i];
            if(pos)
                for(register int i=0;i<pos;++i)
                    cout<<a[n-1];
            cout<<endl;
            continue;
        }
        for(register int i=0;i<n-1;++i)
            cout<<a[i];
        if(a[n-1]=='0')
            for(register int i=1;i<=m-n;++i)
                cout<<1;
        else
            for(register int i=1;i<=m-n;++i)
                cout<<0;
        cout<<a[n-1]<<endl;
    }
    return 0;
}

T164010 自傷無色

算法太显然了，考试的时候就想到了。迫于第一题 $0$ 分的压力和这道题惊人的码量，考场上写了一半没有写完。

考虑三边关系：

$b-a<c<b+a$

把它变成闭区间：

$b-a+1 \le c \le b+a-1$

这个区间一共有：

$b+a-1-(b-a+1)+1=2a-1$

个可行的 $c$ 。

直接上等差：

$(b+a-1+b-a+1)*(2a-1)/2=b*(2a-1)=2ab-b$

这只是 $c$ 的和，还要加上 $a,b$。

$sum=(2a-1)(a+b)+2ab-b=2a^{2}-a+4ab-2b$

把 $b$ 提出来，

$sum=2a^{2}-a+b*(4a-2)$

对于每一个 $a$ 和 $b$ （$a<b$ ），就可以很快的求出来了。

为什么还要枚举 $b$ 呢。。。这时候显然权值线段树啊。$b$ 不就是比 $a$ 大的所有的数的和吗。。。开个线段树维护一下就好了。非叶子节点维护一下总值。

数据范围有点小大，$10^9$ ，需要离散化（到底怎么离散化这里貌似把我卡住了

最后直接跑 dsu on tree 就好了。。。

T177198 以父之名

？