Educational Round 66 题解
作為橙名來水了一發(fā)……
這次題目就比上次良心多了。7題有5題會做。
然而風(fēng)格仍然很怪異……還是練少了？
A
水題。不過一開始沒注意細(xì)節(jié)掛了幾發(fā)，罰時罰的真痛……
明顯是能除以 $k$ 就除以 $k$，否則就 $-1$。但注意不能直接最裸的模擬。
時間復(fù)雜度 $O(T\log n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int maxn=100010; #define MP make_pair #define PB push_back #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline ll read(){char ch=getchar();ll x=0,f=0;while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return f?-x:x; } int t; ll n,k,cnt; int main(){t=read();while(t--){n=read();k=read();cnt=0;while(n){if(n%k==0) n/=k,cnt++;else{ll t=n/k*k;cnt+=n-t;n=t;}}cout<<cnt<<endl;} }View Code
?
B
堪比NOIP2017D1T2的模擬程序。
有很多細(xì)節(jié)，然后我的同學(xué)們就全掛了，就我一個幸存？？？
用 $y[i]$ 表示到第 $i$ 行時共會循環(huán)多少次，$hhh[i]$ 表示 $y[i]$ 是否溢出。
代碼寫著也不是很難受。時間復(fù)雜度 $O(n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int maxn=100010; #define MP make_pair #define PB push_back #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline ll read(){char ch=getchar();ll x=0,f=0;while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return f?-x:x; } int l,stk[maxn],tp; char op[maxn][10]; bool hhh[maxn]; ll x,y[maxn],a[maxn]; int main(){l=read();FOR(i,1,l){scanf("%s",op[i]+1);if(op[i][1]=='f') a[i]=read();}y[0]=1;FOR(i,1,l){if(op[i][1]=='f'){stk[++tp]=i;y[i]=y[i-1]*a[i];if(hhh[i-1] || y[i]>=(1ll<<32)) hhh[i]=true;}else{if(op[i][1]=='e') y[i]=y[stk[tp]-1],hhh[i]=hhh[stk[tp]-1],tp--;else{y[i]=y[i-1];hhh[i]=hhh[i-1];if(hhh[i]) return puts("OVERFLOW!!!"),0;x+=y[i];if(x>=(1ll<<32)) return puts("OVERFLOW!!!"),0;}}}cout<<x<<endl; }View Code
C
有一點點點點的難度。
發(fā)現(xiàn)對于一個點，與它前 $k$ 近的點是一個長度為 $k$ 的區(qū)間。
枚舉這個區(qū)間，對于一個區(qū)間最優(yōu)答案在中點取得。對所有中點取個最優(yōu)即可。
時間復(fù)雜度 $O(\sum n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int maxn=200020; #define MP make_pair #define PB push_back #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline ll read(){char ch=getchar();ll x=0,f=0;while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return f?-x:x; } int t,n,k,a[maxn],x,y; int main(){t=read();while(t--){n=read();k=read()+1;FOR(i,1,n) a[i]=read();y=1e9;FOR(l,1,n-k+1){int r=l+k-1,mid=(a[l]+a[r])>>1;if(a[r]-a[l]<y) y=a[r]-a[l],x=mid;}printf("%d\n",x);} }View Code
D
比B和C還水的水題。
我們假設(shè)分割點是 $x_1,x_2,x_3,\cdots,x_{k-1},x_k$。注意 $x_1=1$。那么題目中的式子就是 $\sum suf[x_i]$。（$suf$ 是后綴和）
那么在 $suf[2],suf[3],\cdots,suf[n]$ 中取前 $k-1$ 大，再與 $suf[1]$ 相加就是答案。
時間復(fù)雜度 $O(n\log n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int maxn=300030; #define MP make_pair #define PB push_back #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline ll read(){char ch=getchar();ll x=0,f=0;while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return f?-x:x; } int n,k,a[maxn]; ll suf[maxn],ans; int main(){n=read();k=read();FOR(i,1,n) a[i]=read();ROF(i,n,1) suf[i]=suf[i+1]+a[i];sort(suf+2,suf+n+1,greater<ll>());ans=suf[1];FOR(i,2,k) ans+=suf[i];cout<<ans; }View Code
E
開始有難度了。
首先發(fā)現(xiàn)對于左端點相同的區(qū)間，只需要保留右端點最右的一個。
（以下設(shè)詢問區(qū)間為 $[x,y]$）
然后假設(shè) $[x,y_0]$ 已經(jīng)被完全覆蓋了，那么下一個要選的區(qū)間的左端點要 $\le y_0$，且右端點盡可能右。
設(shè) $mx[l]$ 表示左端點 $\le l$ 的區(qū)間中的最右右端點。
那么問題就變成從 $x$ 開始跳，跳到 $mx[x]$，再跳到 $mx[mx[x]]$……一直跳跳到 $\ge y$ 為止，問要多少步。
那么就是顯然的倍增了。
設(shè) $to[i][j]$ 表示從 $i$ 開始跳 $2^j$ 會跳到哪。那么有 $to[i][0]=mx[i],to[i][j]=to[to[i][j-1]][j-1]$。
對于每個詢問，先判無解。
否則從 $19$ 到 $0$ 枚舉 $j$。如果 $to[x][j]<y$ 那么把 $x$ 跳到 $to[x][j]$。
這時當(dāng) $to[x][0]<y$ 那么無解，因為已經(jīng)跳了 $2^20$ 步了，如果還沒跳到那么說明沒法再跳到了（只能在原地跳環(huán)）。否則因為有解，所以枚舉完后再跳一步一定能 $\ge y$。
時間復(fù)雜度 $O(n+(q+A)\log A)$。（$A$ 為端點坐標(biāo)最大值）
代碼細(xì)節(jié)，為了不讓 $to[i][j]<i$，一開始把 $mx[i]$ 設(shè)成 $i$ 就行了，不影響答案。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=500050; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline ll read(){char ch=getchar();ll x=0,f=0;while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return f?-x:x; } int n,m,k=500000,mx[maxn],to[maxn][20]; int main(){n=read();m=read();FOR(i,0,k) mx[i]=i;FOR(i,1,n){int l=read(),r=read();mx[l]=max(mx[l],r);}FOR(i,1,k) mx[i]=max(mx[i-1],mx[i]);FOR(i,0,k) to[i][0]=mx[i];FOR(j,1,19) FOR(i,0,k) to[i][j]=to[to[i][j-1]][j-1];while(m--){int x=read(),y=read(),cnt=0;ROF(i,19,0) if(to[x][i]<y) cnt+=1<<i,x=to[x][i];if(to[x][0]<y) puts("-1");else printf("%d\n",cnt+1);} }View Code
F,G
還不會，以后再來搞。
?
轉(zhuǎn)載于:https://www.cnblogs.com/1000Suns/p/10987043.html
總結(jié)
以上是生活随笔為你收集整理的Educational Round 66 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： spring boot中的日志入门
- 下一篇： bash中case的用法