本文作者:Rolling_Code
本文分类:Luogu 游记 浏览:1822
阅读时间: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
啊这这这这这这!
大佬!
本文于 2020-7-28 15:45 审核通过
“不算强”。。啊啊啊啊扎心了我太弱了。
您是谁?
@Zhang, Xuheng 23868
@Rolling_Code 大佬大佬我才141
@Zhang, Xuheng 笑死我了
我们三道题代码几乎一模一样
雾,第一题没AC,,,