[LGR-073]Div2 游记

本文作者：Rolling_Code  本文分类：Luogu 游记  浏览：1856
阅读时间：3513字, 约4-6分钟

首先呢，先讲一下结果。232名，不算强。

（因为各种各样的原因，现在的T1是原来的T3，T2是原来的T1，T3是原来的T2，T4是原来的T4）

题目评分如下：

赛时其实尝试写过EF两题，但是没时间了，在这里先阐明一下。

PS：由于课程关系，少了一个小时切题/kk

A题：可持久化动态仙人掌的直径问题

水题一道，但是不知道赛时卡住了多少人。大约10min切了。

贴上代码：

#include<bits/stdc++.h>
#define N
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;int c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
ll n,m,tmp,i=2;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read();
    if(m>=30){printf("1");return 0;}
    if(m==1){printf("%lld",n);return 0;}
    while(1){
        tmp=1;
        for(int j=1;j<=m;j++){
            tmp*=i;
            if(tmp>n){printf("%lld",i-1);return 0;}
        }
        if(tmp==n){printf("%lld",i);return 0;}
        i++;
    }
    return 0;
}

B题：混凝土数学

离线？在线？

我一开始选择的是在线，抱灵。

后来我选择了离线，AC。

#include<bits/stdc++.h>
#define N 200009
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;int c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
ll n,a[N],cnt[N],tot[N],s[N],vst[N],ans;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        cnt[a[i]]++;
        tot[a[i]]+=(cnt[a[i]]-1),tot[a[i]]%=MOD;
    }
    for(int i=1;i<N;i++){s[i]=s[i-1]+cnt[i];}
    for(int i=1;i<=n;i++){
        if(vst[a[i]]) continue;
        vst[a[i]]=1;
        ans+=tot[a[i]]*(s[min((ll)N-1,2*a[i]-1)]-cnt[a[i]]),ans%=MOD;
        ans+=tot[a[i]]*(cnt[a[i]]-2)/3,ans%=MOD;
    }
    printf("%lld",ans%MOD);
    return 0;
}

C题：论如何玩转 Excel 表格

随便口胡一个算法，结果对了，就是T飞了……（逆序对+特判）

#include<bits/stdc++.h>
#define N 2000009
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;int c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
ll bit1[2*N],bit2[2*N],ans1,ans2,n,s[2*N],rk[2*N],t[2*N];
set<ll> S;
inline ll LSB(ll i){return i&(-i);}
ll query1(ll i){
    int sum=0;
    while(i) sum=(sum+bit1[i]),i-=LSB(i);
    return sum;
}
void add1(ll i){
    while(i<N) bit1[i]++,i+=LSB(i);
}
ll query2(ll i){
    int sum=0;
    while(i) sum=(sum+bit2[i]),i-=LSB(i);
    return sum;
}
void add2(ll i){
    while(i<N) bit2[i]++,i+=LSB(i);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        s[i]=read();
        if(i%2==1) rk[s[i]]=i,S.insert(s[i]);
        else rk[s[i]]=i+n;
    }
    for(int i=n+1;i<=2*n;i++){
        s[i]=read();
        if((i-n)%2==1) rk[s[i]]=i;
        else rk[s[i]]=i-n,S.insert(s[i]);
    }
    for(int i=1;i<=n;i++){
        t[i]=read();
        if(i%2==1) S.erase(t[i]);
    }
    for(int i=1+n;i<=2*n;i++){
        t[i]=read();
        if((i+n)%2==0) S.erase(t[i]);
    }
    if(S.size()!=0){printf("dldsgay!!1");return 0;}
    for(int i=1,k;i<=n;i++){
        if(i%2==1) k=i;
        else k=n+i;
        add1(rk[t[k]]+1);
        ans1+=i-query1(rk[t[k]]+1);
    }
    for(int i=1,k;i<=n;i++){
        if(i%2==1) k=n+i;
        else k=i;
        add2(rk[t[k]]+1);
        ans2+=i-query2(rk[t[k]]+1);
    }
    if(ans1==ans2){printf("%lld",ans1);return 0;}
    printf("dldsgay!!1");
    return 0;
}

D题：可重集

没什么特别的想法，写个暴力拿了25分……

#include<bits/stdc++.h>
#define N 10009 
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;int c=getchar();
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
ll n,q,a[N],tmp1[N],tmp2[N],d,l; 
bool flag;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1,op,l1,r1,l2,r2;i<=q;i++){
		op=read();
		if(!op){l1=read(),r1=read(),a[l1]=r1;continue;}
		l1=read(),r1=read(),l2=read(),r2=read();
		d=r1-l1+1,flag=1;
		for(int j=1;j<=d;j++) tmp1[j]=a[j+l1-1],tmp2[j]=a[j+l2-1];
		sort(tmp1+1,tmp1+d+1);sort(tmp2+1,tmp2+d+1);
		l=tmp1[1]-tmp2[1];
		for(int j=2;j<=d;j++) flag&=(l==tmp1[j]-tmp2[j]);
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

结语

这场月赛还是比较成功的。所以~下次加油吧。

关于作者Rolling_Code

• Rolling_Code官方账号。 23868 热衷于OI无法自拔。
• Email: gary_hy@163.com
• 注册于: 2020-06-27 03:47:58