首页 > 其他分享 >[游记]暑假集训3-2022.8.15

[游记]暑假集训3-2022.8.15

时间：2022-08-15 21:35:47浏览次数：48  
标签：pr ch 15 val int WR 2022.8 include 集训

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;
}
View Code

 

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;
}
View Code

 

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;
}
View Code

 

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;
}
View Code

 

标签：pr,ch,15,val,int,WR,2022.8,include,集训
From： https://www.cnblogs.com/WintersRain/p/16589669.html

相关文章

  • 2022-8-15 第一组 （≥▽≤） 学习笔记
    目录1.MySQL数据库1.1数据库1.2MySQL1.3基本操作1.4表2.SQL语言2.1SQL语句的分类2.1.1DCL(数据控制语言)给用户授权撤销授权查看指定用户授权删除用户2.1.2DDL(数据......
  • 暑假集训3
    去年暑假打过一次，但是当时太菜，今天看到之前写过，好奇多少分，考后交了一发，发现自己是真的菜然后，就算开了个坑吧，四道题。。。A.数列\(exgcd\)板子然后，\(exgcd\)咋用来着？......
  • 【2022-08-15】mysql基础知识(二)
    mysql基础知识(二)字符编码与配置文件windows系统下查看mysql的版本信息：\s由于5.6版本编码不统一，会导致乱码的情况出现，所以统一修改编码格式为>>>:utf8my-defaul......
  • 2022-08-15 第四小组 王星苹 学习笔记
    学习心得       开始MySQL数据库的学习，创建库，再创建表，在表中保存多条数据，一列就是一个字段，也可以增删改查心情 又新学个新东西，新起点，出发加油掌握情况：背......
  • 8.15
    A.begin一道显而易见的结论题因为\(a^2+b^2\leq(a+b)^2\),所以排个序，算一下（1,2），（i，i-2）···（n-1,n)的路长的和，即得答案ACCode#include<bits/stdc++.h>usingnamespace......
  • 2022/8/15 总结
    题单贴贴A.Begin这是道结论题。但令人惊奇的是我完全没往这方面想用奇怪的策略做居然得到了\(\mathtt{80pts}\)；Solution观察样例，再结合一点数学知识，我们可以知道......
  • 2022-08-15第七组薛雯匀
    Mysql数据库数据库数据库【按照数据结构来组织、存储和管理数据的仓库】。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。数据对于公司......
  • 2022 8-15 第四组 曹雨 MySQL数据库01
    MySQLMySQl是一个“关系型数据库管理系统”。MySQL使用了一种语言“SQL语言”MySQL分为社区版和商业版，体积小，速度快，成本低，开源以表的形式存取数据基本操作MySQL操......
  • 20220815 随笔
    昨天是个好日子，我们大部分时间都在宿舍里度过。前一天晚上我们睡得太晚了，所以昨天我们也起得很晚。早上没吃饭，中午和晚上点了外卖。我觉得外卖烤肉饭很好吃，只是酱汁有点......
  • 20220815 第一组 于芮 mysql数据库第一天（第三十一天）
     小白成长记——第三十一天   今天我们告别了java基础，开始了新的旅程——mysql数据库，之前有接触过一点mysql数据库，所以有一点点的基础，对于今天新学的内容，没有那么......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99