[游记]暑假集训3-2022.8.15

本文主要是介绍[游记]暑假集训3-2022.8.15，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Rank2，终于没有$\cdots\cdots$不，挂分少了

A. 数列

显然一眼先扩欧

发现如果 $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;
}

B. 数对

好像是一道 $\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;
}

C. 最小距离

有意思，考虑一张图

 我们把上图中加重的点看为关键点，考虑如何找出答案所求值

首先一个朴素的想法是跑 $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;
}

D. 真相

#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;
}

这篇关于[游记]暑假集训3-2022.8.15的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！