[LGR-073]Div2 游记

首先呢,先讲一下结果。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;
}

结语

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

5 2 votes
Article Rating
Subscribe
提醒
8 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
EricNTH

本文于 2020-7-28 15:45 审核通过

qyh

雾,第一题没AC,,,

Zhang, Xuheng

您是谁?

Zhang, Xuheng

大佬大佬我才141

23786 蘑菇蘑菇蘑菇蘑

笑死我了
我们三道题代码几乎一模一样

EricNTH

“不算强”。。啊啊啊啊扎心了我太弱了。

23786 蘑菇蘑菇蘑菇蘑

啊这这这这这这!
大佬!

8
0
Would love your thoughts, please comment.x
()
x