Rank2,终于没有$\cdots\cdots$不,挂分少了
显然一眼先扩欧
发现如果 $n$ 个数中有一个不能被 $\gcd(a,b)$ 整除就无解
那么对于每个 $x_i$ 我们要解 $ap+bq=x_i$ 中 $p+q$ 的最小值
扩欧即可求解
#include<cstdio> #include<cstring> #include<string> #define int long long #define WR WinterRain using namespace std; const int WR=10010; int n,a,b; int ans; int basea[WR],baseb[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } int ex_gcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int gcd=ex_gcd(b,a%b,x,y); int z=x;x=y; y=z-y*(a/b); return gcd; } signed main(){ n=read(),a=read(),b=read(); int tmpx,tmpy; int gcd=ex_gcd(a,b,tmpx,tmpy); basea[1]=a/gcd,baseb[1]=b/gcd; for(int i=2;i<=32;i++){ basea[i]=basea[i-1]<<1; baseb[i]=baseb[i-1]<<1; } for(int i=1;i<=n;i++){ int x=read();x=abs(x); if(x%gcd!=0){ printf("-1\n"); return 0; } int p=x/gcd*tmpx,q=x/gcd*tmpy; for(int i=32;i>=1;i--){ if(abs(p+baseb[i])+abs(q-basea[i])<=abs(p)+abs(q)) p+=baseb[i],q-=basea[i]; if(abs(p-baseb[i])+abs(q+basea[i])<=abs(p)+abs(q)) p-=baseb[i],q+=basea[i]; } ans+=abs(p)+abs(q); } printf("%lld\n",ans); return 0; }View Code
好像是一道 $\operatorname{DP}$ 题目
题解写得蛮清晰的
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #define int long long #define WR WinterRain using namespace std; const int WR=1001000,INF=1e16; struct SegmentTree{ int l,r,val,lzy; SegmentTree(){l=r=val=lzy=0;} }tree[WR]; struct Node{ int a,b,val; }pr[WR]; int n; int tmp[WR],cnt; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } bool cmp(Node a,Node b){ return min(a.a,a.b)<min(b.a,b.b); } void pushup(int k){ tree[k].val=max(tree[k<<1].val,tree[k<<1|1].val); } void pushdown(int k){ tree[k<<1].val+=tree[k].lzy,tree[k<<1|1].val+=tree[k].lzy; tree[k<<1].lzy+=tree[k].lzy,tree[k<<1|1].lzy+=tree[k].lzy; tree[k].lzy=0; } void build(int k,int l,int r){ tree[k].l=l,tree[k].r=r; if(l==r){return;} int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void modify_area(int k,int l,int r,int val){ if(tree[k].l>=l&&tree[k].r<=r){ tree[k].val+=val;tree[k].lzy+=val; return; } if(tree[k].lzy) pushdown(k); int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid) modify_area(k<<1,l,r,val); if(r>mid) modify_area(k<<1|1,l,r,val); pushup(k); } void modify_point(int k,int pos,int val){ if(tree[k].l==tree[k].r){ tree[k].val=max(tree[k].val,val); return; } if(tree[k].lzy) pushdown(k); int mid=(tree[k].l+tree[k].r)>>1; if(pos<=mid) modify_point(k<<1,pos,val); else modify_point(k<<1|1,pos,val); pushup(k); } int query(int k,int l,int r){ if(tree[k].l>=l&&tree[k].r<=r){ return tree[k].val; } if(tree[k].lzy) pushdown(k); int mid=(tree[k].l+tree[k].r)>>1,res=0; if(l<=mid) res=max(res,query(k<<1,l,r)); if(r>mid) res=max(res,query(k<<1|1,l,r)); return res; } signed main(){ n=read(); for(int i=1;i<=n;i++){ tmp[++cnt]=pr[i].a=read(),tmp[++cnt]=pr[i].b=read(),pr[i].val=read(); } sort(tmp+1,tmp+1+cnt); cnt=unique(tmp+1,tmp+cnt+1)-tmp-1; build(1,1,cnt); for(int i=1;i<=n;i++){ pr[i].a=lower_bound(tmp+1,tmp+cnt+1,pr[i].a)-tmp; pr[i].b=lower_bound(tmp+1,tmp+cnt+1,pr[i].b)-tmp; // printf("%lld %lld\n",pr[i].a,pr[i].b); } sort(pr+1,pr+1+n,cmp); for(int i=1;i<=n;i++){ if(pr[i].a>=pr[i].b){ modify_point(1,pr[i].a,query(1,1,pr[i].b)+pr[i].val); }else{ modify_area(1,pr[i].a+1,pr[i].b,pr[i].val); modify_point(1,pr[i].a,query(1,1,pr[i].a)+pr[i].val); } } printf("%lld\n",query(1,1,cnt)); return 0; }View Code
有意思,考虑一张图
我们把上图中加重的点看为关键点,考虑如何找出答案所求值
首先一个朴素的想法是跑 $p$ 遍最短路算法打暴力,但是显然会T飞
然后发现可以把所有的最短路合并成一个多源的最短路,以关键点为原点开跑
那么每个关键点会有一个“控制范围”,在控制范围内的所有点都由这个关键点更新而来
可以采用并查集简单维护
考虑一条路径:譬如上图中 $17\to 20\to 7\to 13\to 12$
不妨假设这条路径上 $20$ 是 $17$ 的受控点, $7$ 和 $13$ 是 $12$ 的受控点
它将会由 $dis[20]+dis[7]$ 以及链接 $7$ 和 $20$ 的边权组合成
考虑枚举每一条边,查询两个端点的归属,如果不同尝试更新即可
#include<cstdio> #include<cstring> #include<string> #include<queue> #define int long long #define WR WinterRain using namespace std; const int WR=1001000,INF=1e16; struct Edge{ int pre,to,val,frm; }edge[WR]; int n,m,p; int head[WR],tot; int fa[WR],dis[WR]; int x[WR],ans[WR]; bool vis[WR]; priority_queue<pair<int,int> >q; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } void add(int u,int v,int val){ edge[++tot].pre=head[u]; edge[tot].to=v;edge[tot].frm=u; edge[tot].val=val; head[u]=tot; } void Dijkstra(){ for(int i=1;i<=n;i++) dis[i]=INF; for(int i=1;i<=p;i++){ dis[x[i]]=0,fa[x[i]]=x[i]; q.push(make_pair(0,x[i])); } while(!q.empty()){ int u=q.top().second;q.pop(); // printf("%lld\n",u); if(!vis[u]){ vis[u]=true; for(int i=head[u];i;i=edge[i].pre){ int v=edge[i].to,val=edge[i].val; if(dis[v]>dis[u]+val){ dis[v]=dis[u]+val; fa[v]=fa[u]; q.push(make_pair(-dis[v],v)); } } } } } signed main(){ // freopen("C.in","r",stdin); n=read(),m=read(),p=read(); for(int i=1;i<=n;i++) ans[i]=INF; for(int i=1;i<=p;i++) x[i]=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),val=read(); add(u,v,val);add(v,u,val); } Dijkstra(); // for(int i=1;i<=n;i++) printf("%lld %lld %lld\n",i,dis[i],fa[i]); for(int i=1;i<=tot;i+=2){ int u=edge[i].frm,v=edge[i].to,val=edge[i].val; if(fa[u]==fa[v]) continue; // printf("%lld %lld %lld\n",u,v,val); ans[fa[u]]=min(ans[fa[u]],dis[u]+dis[v]+val); ans[fa[v]]=min(ans[fa[v]],dis[u]+dis[v]+val); } for(int i=1;i<=p;i++) printf("%lld ",ans[x[i]]); return 0; }View Code
#include<cstdio> #include<cstring> #include<string> #include<algorithm> #define int long long #define WR WinterRain using namespace std; const int WR=1000100; struct Fix_Computer{ int opt,k; }oier[WR]; struct Predictor{ int k,tru,fals,u; bool operator<(const Predictor &b)const{return k<b.k;} }pre[WR]; int n,cnt,num,tot; int tmp[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } bool SPJ(){ tmp[1]=1; for(int i=2;i<=n;i++) tmp[i]=tmp[i-1]^oier[i-1].opt; if(tmp[1]==(tmp[n]^oier[n].opt)) return true; tmp[1]=0; for(int i=2;i<=n;i++) tmp[i]=tmp[i-1]^oier[i-1].opt; if(tmp[1]==(tmp[n]^oier[n].opt)) return true; return false; } signed main(){ int t=read(); while(t--){ int con=0,inc=0; bool flag=false; n=read(),cnt=0; for(int i=1;i<=n;i++){ char ch[10]; scanf("%s",ch); if(ch[0]=='+') oier[i].opt=0; if(ch[0]=='-') oier[i].opt=1; if(ch[0]=='$') oier[i].opt=-1,flag=true,oier[i].k=read(); } if(!flag){ if(SPJ()) printf("consistent\n"); else printf("inconsistent\n"); continue; } for(int i=1;i<=n;i++){ if(oier[i].opt==-1){ int j=((i-1)?i-1:n); tmp[i]=1; pre[++cnt]=(Predictor){oier[i].k,1,0,0}; while(oier[j].opt!=-1){ tmp[j]=tmp[(j+1)>n?1:(j+1)]^oier[j].opt; if(tmp[j]) pre[cnt].tru++; else pre[cnt].fals++; j=((j-1)?j-1:n); } } } sort(pre+1,pre+cnt+1); int last=0;pre[0].k=-WR; for(int i=1;i<=cnt;i++){ if(pre[i].k==pre[last].k) pre[last].tru+=pre[i].tru,pre[last].fals+=pre[i].fals,pre[i].u=1; else last=i; } int cntfalse=0; for(int i=1;i<=cnt;i++){ if(!pre[i].u) cntfalse+=pre[i].fals; } for(int i=1;i<=cnt;i++){ if(!pre[i].u&&pre[i].k==cntfalse-pre[i].fals+pre[i].tru) con=1; if(pre[i].k==cntfalse) inc=1; } if(con||!inc){ printf("consistent\n"); }else{ printf("inconsistent\n"); } } return 0; }View Code