8月19日NOIP模拟测试26(B): 嚎叫声回荡在贪欲的工厂,主仆见证Hobo的告别,征途孕育出长久的友情
T1 嚎叫响彻在贪婪的厂房
以前做过一个等比数列的题「序列」,这个类似
是等差数列且公差不为1的条件就是各项差的绝对值的$gcd!=1$,每次拿出序列前两个数,求出差值,插入到set里,每次向后扩展,如果该数出现过或与前面的公差的$gcd==1$,更新答案和序列起点,进行下一轮;否则插入到$set$中,记得清空
#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<cmath> #define ll long long using namespace std; ll n,a[100100],st,ans; set<ll>s; ll read() { ll aa=0,bb=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-') bb=-1;cc=getchar();} while(cc>='0'&&cc<='9'){aa=(aa<<3)+(aa<<1)+(cc^'0');cc=getchar();} return aa*bb; } ll gcd(ll a,ll b) { if(b==0) return a; return gcd(b,a%b); } int main() { n=read(); for(ll i=1;i<=n;i++) a[i]=read(); ll st=1; while(st<=n){ if(st==n){ ans++; break; } ll d=abs(a[st+1]-a[st]); if(d==0||d==1){ ans++; st++; continue; } s.insert(a[st]);s.insert(a[st+1]); ll i; for(i=st+2;i<=n;i++){ if(s.find(a[i])!=s.end()) break; d=gcd(d,abs(a[i]-*s.begin())); if(d==1) break; s.insert(a[i]); } st=i; ans++; s.clear(); } printf("%lld\n",ans); return 0; }
T2 主仆见证了 Hobo 的离别
建边,数据较水,暴力跑$dfs$就能过
如果是交集,就将合并的点向新点连边,并集就将新点向合并的点连边,$k==1$的情况交集和并集是一样的,所以建双向边。
最后的查询就是问$x$是否是$y$的一个子集,也就是从$y$出发能否找到$x$,这样建边就保证了从当前点出发,能到达的点都是自己能包含的
#include<iostream> #include<cstdio> #include<vector> using namespace std; struct node { int to,nxt; }h[5001000]; int n,m,nn,num,a[4001000],tot,nxt[5001000],son; int read() { int aa=0,bb=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-') bb=-1;cc=getchar();} while(cc>='0'&&cc<='9'){aa=(aa<<3)+(aa<<1)+(cc^'0');cc=getchar();} return aa*bb; } void add(int x,int y) { h[++tot].to=y; h[tot].nxt=nxt[x]; nxt[x]=tot; } bool dfs(int x,int fa) { if(x==son) return true; for(int i=nxt[x];i;i=h[i].nxt){ int y=h[i].to; if(y==fa) continue; if(dfs(y,x)) return true; } return false; } int main() { n=read();m=read();nn=n; int tpy,op,k,a,x,y; for(int i=1;i<=m;i++){ tpy=read(); if(!tpy){ op=read();k=read();nn++; if(!op){ for(int i=1;i<=k;i++){ x=read(); add(x,nn); if(k==1) add(nn,x); } } else{ for(int i=1;i<=k;i++){ x=read(); add(nn,x); if(k==1) add(x,nn); } } } else{ son=read();y=read(); printf("%d\n",dfs(y,0)); } } return 0; }
T3 征途堆积出友情的永恒
暴力建边跑$spfa$可以得到50分,加一手特判就能拿到80分的好成绩。
$f[i]$表示到i点的最小费用,$s[i]$表示$a[i]$的前缀和,转移很简单 $f[i]=min{f[j]+max(b[j],s[i]-s[j])}$ 复杂度n2显然抗不住
考虑优化,发现$f[j]+s[i]-s[j]$是单调递增的,$f[j]+b[j]$是一个定值,每次找可行范围内的最小值就行,考虑用两个小根堆维护
一个维护$f[j]+b[j]$,一个维护$f[j]-s[j]$
每次更新$f[i]$的时候找到距离不超过k的且最小的,$f[i]=min(第一个堆的堆顶,第二个堆的堆顶+s[i])$
距离不超过$k$就每次取堆顶,如果$id<i-k$就把他$pop$出去,直到找到合法的
如果第一个堆的堆顶$<f[j]+s[i]-s[j]$(答案不会是他,因为费用是要找路费和税中较大的)就$pop$出来,并把j插入到第二个堆里(税已经小于当前路程了,那么这个点以后对答案的贡献只可能是路径费用而不是税)
每次都将走过的点$i$的$f[i]+b[i]$插入到第一个堆里
注意最大值要开大一点。。。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; ll n,m,a[500100],b[500100],s[500100],f[500100]; priority_queue< pair<ll,ll> ,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q,qq; ll read() { ll aa=0,bb=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-') bb=-1;cc=getchar();} while(cc>='0'&&cc<='9'){aa=(aa<<3)+(aa<<1)+(cc^'0');cc=getchar();} return aa*bb; } int main() { n=read();m=read(); for(ll i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i]; for(ll i=0;i<n;i++) b[i]=read(); f[0]=0; for(ll i=1;i<=n;i++){ q.push(make_pair(f[i-1]+b[i-1],i-1)); ll ans=0x7fffffffffffff; while(q.size()&&q.top().second<i-m) q.pop(); while(qq.size()&&qq.top().second<i-m) qq.pop(); while(q.size()&&q.top().first<f[q.top().second]+s[i]-s[q.top().second]){ qq.push(make_pair(f[q.top().second]-s[q.top().second],q.top().second)); q.pop(); } while(q.size()&&q.top().second<i-m) q.pop(); while(qq.size()&&qq.top().second<i-m) qq.pop(); if(q.size()) ans=min(ans,q.top().first); if(qq.size()) ans=min(ans,qq.top().first+s[i]); f[i]=ans; } printf("%lld\n",f[n]); return 0; }
原文地址:https://www.cnblogs.com/jrf123/p/11379100.html