2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest-gym 102091 题解 A. Flying Squirrel B. 留坑，大佬说分类讨论，打表出特殊情况。 C. Evolution Game D. Bus Stop E. How many groups F. Lucky Pascal Triangle G. Communication H. As rich as Crassus I. Bowabowaukulipukuli J. Floating-Point Hazard K. The Stream of Corning 2
题意：给你n根柱子，高度分别为a[i]。m次询问：给两个数X，Y。从X出发到Y为止，当Y=0表示可以从X出发，任意位置停止。每一次行走的条件是中间不能有高于或者等于当前柱子高度。
问我们最多能走多少次？
首先我们有一个观察，在当前柱子上。我们选择下一根柱子去走的时候，肯定会考虑向左或者向右能走的所有最高的柱子，这相当于从这个点向他们连边。那不妨我们直接考虑从最高的柱子开始走，每次
向能走到的所有最高的柱子连边，并且递归的去建树，建树的时候顺便把无目的地的答案给处理出来。显然，如果有解的话，我们就把他们之间的深度差输出。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 200'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} int st[MAXN][20], lg[MAXN]; int h[MAXN], ans[MAXN], dep[MAXN]; int n, m; int query(int L, int R){ int k=lg[R-L+1]; if(h[st[L][k]]>=h[st[R-(1<<k)+1][k]])return st[L][k]; else return st[R-(1<<k)+1][k]; } int dfs(int L, int R, int d){ if(L>R)return -1; int all=0; int p=query(L, R); dep[p]=d; ans[p]=dfs(L,p-1,d+1)+1; all=max(all,ans[p]); while(p<R){ int q=query(p+1,R); if(h[p]!=h[q])break; int t=dfs(p+1,q-1,d+1)+1; ans[p]=max(ans[p],t); all=max(all,ans[p]); dep[q]=d; ans[q]=t; p=q; } ans[p]=max(ans[p],dfs(p+1,R,d+1)+1); all=max(all,ans[p]); return all; } int main(){ n=read();m=read(); for(int i=1;i<=n;++i)h[i]=read(), st[i][0]=i; for(int i=2;i<=n;++i)lg[i]=lg[i/2]+1; for(int j=1;j<=20;++j){ for(int i=1;i+(1<<j)-1<=n;++i){ if(h[st[i][j-1]]>=h[st[i+(1<<j-1)][j-1]])st[i][j]=st[i][j-1]; else st[i][j]=st[i+(1<<j-1)][j-1]; } } dfs(1,n,0); while(m--){ int l, r; l=read(); r=read(); if(!r){ cout<<ans[l]<<endl; }else{ if(h[l]==h[r]){ cout<<"0"<<endl; }else{ if(h[l]>h[r])swap(l,r);/*ºÃ¶àbug*/ int t; if(l<r)t=query(l,r-1); else t=query(r+1,l); if(h[t]>=h[r]){ cout<<"0"<<endl; }else{ cout<<dep[l]-dep[r]<<endl; } } } } return 0; } /* 12 8 2 3 4 4 4 3 3 3 1 2 5 2 3 0 4 0 5 0 7 0 7 11 7 9 11 1 9 12 */
B. 留坑，大佬说分类讨论，打表出特殊情况。
C. Evolution Game
现在有一些怪物，每一种分别有x个眼睛和y个角。眼睛数量有一个上界N，且每一个眼睛数量都是有其对应的角数量的，你可以以任意一类出生。再给定一个值w，表示眼睛数量的变化范围。i.e. 进化一次,眼睛数量的范围是[x-w,x+w]。还有一个限制条件是每次角的数量只能增加。问最多能进化多少次？
温暖的签到，记忆化搜索即可。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 5'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} int h[MAXN]; int f[MAXN]; int n, w; int dfs(int x){ if(f[x]!=-1)return f[x]; f[x]=0; for(int i=max(1,x-w);i<=min(n,x+w);++i){ if(h[i]>h[x]){ f[x]=max(f[x],1+dfs(i)); } } return f[x]; } int main(){ n=read();w=read(); for(int i=1;i<=n;++i){ h[i]=read(); f[i]=-1; } int ans=0; for(int i=1;i<=n;++i){ ans=max(ans,dfs(i)); } cout<<ans; return 0; } /* 5 5 5 3 2 1 4 */
D. Bus Stop
有一条直线，上面n个点，现在要安排一些点，使得原来的点的左右10单位内至少有一个新安排的点，问最少的新安排上的点的数量？
从左向右贪心即可。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define MP make_pair #define mid (l+r>>1) #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 2'000'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} int d[MAXN]; void solve(){ int n=read(); for(int i=1;i<=n;++i)d[i]=read(); if(n==0){ cout<<"0"<<endl; return; } int cnt=1; int r=d[1]+10; int idx=1; while(1){ while(abs(d[idx]-r)<=10)++idx; if(idx>n)break; else{ r=d[idx]+10; ++cnt; } } printf("%d ",cnt); } int main(){ int cases;cases=read(); while(cases--){ solve(); } return 0; } /* 2 5 1 2 3 200 210 4 10 30 80 200 */
E. How many groups
给你一个n个数的数组，你可以进行两次操作，包括将数组里的一个数+1或者-1，但不能对同一个元素操作两次。将两个数分成一组的条件是他们之间的差值的绝对值小于2。问其中的最大一组的size是多少？
设dp[x][i]为以x结尾，且总操作次数为i的组的最大尺寸，然后根据决策去转移就好了。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 205; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} int f[MAXN][3]; int temp[MAXN][3]; int a[MAXN]; int n; int main(){ int t;t=read(); int kase=1; while(t--){ n=read();memset(f,0,sizeof f); for(int i=1;i<=n;++i)a[i]=read(); sort(a+1,a+n+1); int ans=1; for(int i=1;i<=n;++i){ int x=a[i]; for(int j=max(x-3,0);j<=x+3;++j){ for(int k=0;k<=2;++k){ temp[j][k]=f[j][k]; } } for(int j=2;j>=0;--j)f[x][j]=max({temp[x+2][j],temp[x+1][j],temp[x][j],temp[x-1][j],x>=2?temp[x-2][j]:0})+1; for(int j=2;j>=1;--j)f[x-1][j]=max({temp[x+1][j-1],temp[x][j-1],temp[x-1][j-1],x-2>=0?temp[x-2][j-1]:0,x-3>=0?temp[x-3][j-1]:0})+1; for(int j=2;j>=1;--j)f[x+1][j]=max({temp[x+3][j-1],temp[x+2][j-1],temp[x+1][j-1],temp[x][j-1],temp[x-1][j-1]})+1; } for(int i=1;i<=200;++i) for(int j=0;j<=2;++j)ans=max(ans,f[i][j]); cout<<"Case "<<kase++<<": "<<ans<<endl; } return 0; } /* 5 10 2 1 7 4 3 8 9 12 13 20 3 1 2 3 4 1 2 7 8 3 10 30 20 2 5 5 Case 1: 9 Case 2: 3 Case 3: 2 Case 4: 1 Case 5: 2 */
F. Lucky Pascal Triangle
给你一个杨辉三角，问前n行中能被7整除的数的个数是多少。
首先应该打表找规律，这里只说规律。首先可以发现能被7整除的数是呈块状分布的。第一块从[1,7^1-1]，第二块[7^1,7^2-1]，第三块[7^2,7^3-1]...。其次，每一块里面都有21块大的块且每一行的个数为等差数列，
28块为前面所有的行组成的块。我们就能直接预处理出第一块，第二块...，再数出大块里面的块的个数，其他的递归求解。
#include<bits/stdc++.h> #define all(x) x.begin(),x.end() #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline LL read(){ LL res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 200'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} template<typename T> void chmin(T& a, T b){if(a>b)a=b;} template<typename T> void chmax(T& a, T b){if(b>a)a=b;} //打表找规律，每一个以7^i为结尾的数量都是有规律的 //f[i]=f[i-1]*28+(7^(i-1)-1)*7^(i-1)/2*28(具体来讲是考虑28个上一个块。在考虑21个新形成的块) map<LL, LL> H; LL powmod(LL x, LL y){ LL res=1; while(y){ if(y&1) res=res*x%MOD; y>>=1; x=x*x%MOD; } return res; } LL inv2; void init(){ LL base=7; H[base-1]=0; base=49; while(base<=(LL)(1e18)){ LL t=base/7; H[base-1]=(28*H[t-1]%MOD+21*inv2%MOD*((t-1)%MOD)%MOD*(t%MOD)%MOD)%MOD; base*=7; } } LL calc(LL n){ if(n<=6)return 0; LL ans=0; LL base=0; for(auto it:H){ LL x=it.fi,y=it.sd; if(x<=n){ ans=y;//先 take care 整块的情况 base=x; }else break; } ++base; LL a=base;//考虑接下来不为整块的情况 LL time=1; LL now=base%MOD*((base-1)%MOD)%MOD*inv2%MOD; while(a+base<=n){ ans+=now*time%MOD;//一个大块里面的小块 ans%=MOD; ++time; ans+=H[base-1]*time%MOD; ans%=MOD; a+=base; } if(n-a+1==base){ ans=(ans+(base%MOD)*((base-1)%MOD)%MOD*inv2%MOD*time%MOD)%MOD;//是整块 }else{ ans=(ans+((2*base-n+a-2)%MOD+MOD)%MOD*((n-a+1)%MOD)%MOD*inv2*time%MOD)%MOD;//等差数列而已 } ans=(ans+(time+1)*calc(n-a)%MOD)%MOD; return ans; } int main(){ inv2=powmod(2,MOD-2); LL cases;cases=read(); LL kase=1; init(); while(cases--){ LL n;n=read(); cout<<"Case "<<kase++<<": "<<calc(n)<<endl; } return 0; } /* 5 1 5 10 15 100000 */
G. Communication
给n个点的图，求其DAG的节点个数。
tarjan缩点。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define MP make_pair #define mid (l+r>>1) #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 205; const int MAXM = 10'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} #define go(e,u) for(int e=head[u];e;e=Next[e]) int to[MAXM<<1],Next[MAXM<<1],head[MAXN],tol; void add_edge(int u,int v){ Next[++tol]=head[u];to[tol]=v;head[u]=tol; // Next[++tol]=head[v];to[tol]=u;head[v]=tol; } int n, m; int dfn[MAXN],low[MAXN],dfncnt; int st[MAXN],top; int scc[MAXN], sc; void init(){ tol=0;top=0;sc=0; dfncnt=0; memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(head,0,sizeof head); memset(Next,0,sizeof Next); memset(to,0,sizeof to); memset(scc,0,sizeof scc); } void tarjan(int u){ dfn[u]=low[u]=++dfncnt; st[++top]=u; go(e,u){ int v=to[e]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(!scc[v]){ low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){ ++sc; while(st[top]!=u){ scc[st[top]]=sc; --top; } scc[st[top]]=sc; --top; } } void solve(){ init(); n=read();m=read(); for(int i=1;i<=m;++i){ int u, v; u=read(),v=read(); ++u,++v; add_edge(u,v); } for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i); cout<<sc<<endl; } int main(){ int cases;cases=read(); while(cases--){ solve(); } return 0; } /* 3 6 2 0 5 5 0 5 7 0 1 0 2 1 0 1 3 2 4 3 1 4 2 3 4 0 1 0 2 1 0 1 2 */
H. As rich as Crassus
给你三个数的立方值关于三个模数的模值，且每一个模值都互质，求这三个数。
CRT，但是会爆long long，所以需要龟速乘。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline LL read(){ LL res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 200'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} LL P,mods[4],rem[4]; LL mul(LL x, LL y){ LL ans=0; while(y){ if(y&1)ans=(ans+x)%P; y>>=1; x=(x+x)%P; } return (ans%P+P)%P; } LL exgcd(LL a, LL b, LL& x, LL& y){ if(!b){x=1;y=0;return a;} else{ LL d=exgcd(b,a%b,y,x); y-=(a/b)*x; return d; } } LL CRT(){ for(int i=1;i<=3;++i)P*=mods[i]; LL ans=0; for(int i=1;i<=3;++i){ LL x,y; LL d=exgcd(P/mods[i],mods[i],x,y); x=(x%mods[i]+mods[i])%mods[i]; if(d!=1)return -1; else{ ans=(ans+mul(mul(P/mods[i],x)%P,rem[i])%P)%P; } } return (ans%P+P)%P; } void solve(){ P=1; for(int i=1;i<=3;++i)mods[i]=read(); for(int i=1;i<=3;++i)rem[i]=read(); LL ans=CRT(); if(ans==-1){ cout<<"-1"<<endl; }else{ LL t=(LL)pow(ans,1.0/3.0); if(t*t*t<ans)cout<<t+1<<endl; else cout<<t<<endl; } } int main(){ LL cases;cases=read(); while(cases--){ solve(); } return 0; } /* 2 6 11 19 5 4 11 25 36 7 16 0 6 */
I. Bowabowaukulipukuli
防AK题，溜了溜了。
J. Floating-Point Hazard
给你一个函数f[x]=(x+1e-15)^(1/3)-(x)^(1/3)，给一个下界lo, 一个上界hi，求这个区间内函数值的和。
这个算式有一些特殊形式，如果分母除一个1e-15，就是求导式。考虑到1e-15已经足够小，这个算式可以用f'[x]*1e-15来代替。求和即可。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define mid (l+r>>1) #define MP make_pair #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; inline int read(){ int res=0, f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();} return res*f; } const int MAXN = 200'005; const int MOD = 1000000007; void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;} int mulmod(int a, int b){return 1ll*a*b%MOD;} int lo, hi; void solve(){ double ans=0.0; for(int i=lo;i<=hi;++i){ ans+=(1.0/3)*pow(i,-2.0/3.0); } int cnt=15; while(ans<1.0){ ans*=10.0; ++cnt; } while(ans>10){ ans/=10; --cnt; } printf("%.5fE%.3d ",ans,-cnt); } int main(){ while((cin>>lo>>hi)&&(lo+hi)){ solve(); } return 0; }
K. The Stream of Corning 2
给你m次询问或修改，op=1时，给一个值和它的出现时间，消失时间。op=2问当前的rank[k]。
将询问离线，写一颗权值线段树即可通过(值在1e6内甚至都不用离散化。
#include<bits/stdc++.h> #define fi first #define sd second #define lson (nd<<1) #define rson (nd+nd+1) #define PB push_back #define MP make_pair #define mid (l+r>>1) #define SZ(x) (int)x.size() using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; namespace FastIO { const int SIZE = 1 << 16; char buf[SIZE], str[64]; int l = SIZE, r = SIZE; int read(char *s) { while (r) { for (; l < r && buf[l] <= ' '; l++); if (l < r) break; l = 0, r = int(fread(buf, 1, SIZE, stdin)); } int cur = 0; while (r) { for (; l < r && buf[l] > ' '; l++) s[cur++] = buf[l]; if (l < r) break; l = 0, r = int(fread(buf, 1, SIZE, stdin)); } s[cur] = '