首页 > 其他分享 >AtCoder Beginner Contest 294

AtCoder Beginner Contest 294

时间:2023-03-21 16:25:49浏览次数:55  
标签:AtCoder num1 Beginner int cin long maxn 294 include

题解报告

基本的一些理解和问题都在注释中
A:Filter

//水题
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main(void)
{
    int N;cin>>N;
    for(int i=0;i<N;i++)
    {
        int x;cin>>x;
        if(!(x&1))cout<<x<<' ';
    }
    cout<<endl;
    return 0;
}

B:ASCII Art

//水题,但是错了一发,可惜可惜,注意输出格式。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000;
char ans[maxn][maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,M;cin>>N>>M;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            int x;cin>>x;
            if(x==0)ans[i][j]='.';
            else ans[i][j]=x-1+'A';
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
            cout<<ans[i][j];//注意输出的规格,这里没有空格
        cout<<endl;
    }
    return 0;
}

C:Merge Sequences

//水题
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int maxn=1e6+10;
unordered_map<int,int> mp;
int num1[maxn];
int num2[maxn];
struct node
{
    int x;
    bool operator <(const node &a)const
    {
        return x<a.x;
    }
}res[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,M;cin>>N>>M;
    int pos=0;
    for(int i=1;i<=N;i++)cin>>num1[i],res[pos++].x=num1[i];
    for(int j=1;j<=M;j++)cin>>num2[j],res[pos++].x=num2[j];
    sort(res,res+pos);
    for(int i=0;i<pos;i++)mp[res[i].x]=i+1;
    for(int i=1;i<=N;i++)cout<<mp[num1[i]]<<' ';cout<<endl;
    for(int i=1;i<=M;i++)cout<<mp[num2[i]]<<' ';
    return 0;
}

D:Bank

//优先队列模拟,读懂题目就容易写
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=5e5+10;
int vis[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    priority_queue<int,vector<int>,greater<int> >q1;
    int Q,N;cin>>N>>Q;
    int Cpos=0;
    for(int i=1;i<=Q;i++)
    {
        int op;cin>>op;
        if(op==1){
            if(Cpos<N)
                q1.push(++Cpos);
        }else if(op==2){
            int k;cin>>k;
            vis[k]=1;
        }else{
            while(!q1.empty()&&vis[q1.top()])q1.pop();
            cout<<q1.top()<<endl;
        }
    }
    return 0;
}

E:2xN Grid

//模拟题,上下两边同时推进。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn=1e5+10;
struct node
{
    long long v,l;
};
node num1[maxn];
node num2[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    long long L;cin>>L;
    int N1,N2;
    cin>>N1>>N2;
    for(int i=1;i<=N1;i++)cin>>num1[i].v>>num1[i].l;
    for(int j=1;j<=N2;j++)cin>>num2[j].v>>num2[j].l;
    long long i=0,j=0;
    int pos1=1,pos2=1;
    long long res=0;
    while(i!=L&&j!=L&&pos1<=N1&&pos2<=N2)
    {
        if(num1[pos1].l+i>num2[pos2].l+j)//更新左边
        {
            if(num1[pos1].v==num2[pos2].v)
                res+=num2[pos2].l+j-max(i,j);
            j+=num2[pos2].l;pos2++;
            num1[pos1].l=num1[pos1].l+i-j;
            i=j;
        }else{
            if(num1[pos1].v==num2[pos2].v)
                res+=num1[pos1].l+i-max(i,j);
            i+=num1[pos1].l;pos1++;
            num2[pos2].l=num2[pos2].l+j-i;
            j=i;
        }
    }
    cout<<res<<endl;
    return 0;
}

F:Sugar Water 2

//一道二分的题目,虽然刚开始我也是想二分,二分的也是浓度,但是写check函数的时候就写出问题了
//chek函数要根据每个的贡献来的,不能盲目枚举,以后要是有分数的,都直接看贡献。
//这道题上周在周赛的时候有做过类似的,做不出来不应该的。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=5e4+10;
double A[maxn],B[maxn];
double C[maxn],D[maxn];
double temp[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,M;cin>>N>>M;
    long long K;cin>>K;
    for(int i=1;i<=N;i++)cin>>A[i]>>B[i];
    for(int i=1;i<=M;i++)cin>>C[i]>>D[i];
    double l=0,r=1;
    while(abs(r-l)>=1e-15)
    {
        double mid=(l+r)/2;
        double k=mid/(1-mid);
        for(int i=1;i<=N;i++)temp[i]=A[i]-B[i]*k;//看提供的糖是多了还是少了
        sort(temp+1,temp+N+1);
        long long res=0;
        for(int i=1;i<=M;i++)
        {
            double has=C[i]-D[i]*k;
            res+=N-(lower_bound(temp+1,temp+1+N,-has)-(temp+1));
            //获取的浓度大于等于它的个数。
            //这里是大于等于它的,可能全部都是大于的,所以就算,等于了,
            //那么也还是得提高浓度,找到一个存在的且真正是临界点的才行。
        }
        //个数多了,浓度加大。
        if(res>=K)l=mid;//要实实在在的找到里面有的才行,所以
        else r=mid;
    }
    printf("%.16lf",r*100);
    return 0;
}

G:Distance Queries on a Tree

//树链刨分的板子题,只不过是边权的而已,要注意以下就行了。
//会就乱杀,不会就不会写。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=4e5+10;
//建树
int head[maxn],edge[maxn],nxt[maxn],ver[maxn],tot;
ll w[maxn];
//边权化为点权,遍历的时候转换。
int dep[maxn],siz[maxn],hson[maxn],fa[maxn],top[maxn],dfn[maxn],rnk[maxn];
void addEdge(int u,int v,int w)
{
    ver[tot]=w;
    edge[tot]=v;
    nxt[tot]=head[u];
    head[u]=tot++;
}
int mp[maxn];
//线段树
struct node
{
    int lson,rson;
    long long data;
}tree[maxn<<2];
//刨分
void build(int pos,int l,int r)
{
    tree[pos].lson=l;tree[pos].rson=r;
    if(l==r)
    {
        tree[pos].data=w[rnk[l]];
        return;
    }
    int mid=l+r>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    tree[pos].data=tree[pos<<1].data+tree[pos<<1|1].data;
}
ll query(int pos,int l,int r)
{
    if(l<=tree[pos].lson&&tree[pos].rson<=r)return tree[pos].data;
    int mid=tree[pos].lson+tree[pos].rson>>1;
    ll ans=0;
    if(l<=mid)
        ans+=query(pos<<1,l,r);
    if(r>=mid+1)
        ans+=query(pos<<1|1,l,r);
    return ans;
}
void update(int pos,int x,int val)
{
    if(tree[pos].lson==tree[pos].rson)
    {
        tree[pos].data=val;
        return;
    }
    int mid=tree[pos].lson+tree[pos].rson>>1;
    if(x<=mid)
        update(pos<<1,x,val);
    else 
        update(pos<<1|1,x,val);
    tree[pos].data=tree[pos<<1].data+tree[pos<<1|1].data;
}
void dfs1(int now,int pre,int step)
{
    siz[now]=1;
    hson[now]=-1;
    dep[now]=step;
    fa[now]=pre;
    for(int i=head[now];~i;i=nxt[i])
    {
        int v=edge[i];
        if(v==pre)continue;
        mp[i/2*2]=v;
        w[v]=ver[i];
        dfs1(v,now,step+1);
        siz[now]+=siz[v];
        if(hson[now]==-1||siz[hson[now]]<siz[v])
            hson[now]=v;
    }
}
int tp=0;
void dfs2(int now,int t)
{
    top[now]=t;
    tp++;
    dfn[now]=tp;
    rnk[tp]=now;
    if(hson[now]==-1)return;
    dfs2(hson[now],t);
    for(int i=head[now];~i;i=nxt[i])
    {
        int v=edge[i];
        if(v==hson[now]||v==fa[now])continue;
        dfs2(v,v);
    }
}
void init(int N,int rt=1)
{
    tp=0;
    dfs1(rt,rt,1);
    dfs2(rt,rt);
    build(1,1,N);
}
ll solve(int a,int b)
{
    ll ans=0;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]])swap(a,b);
        ans+=query(1,dfn[top[a]],dfn[a]);
        a=fa[top[a]];
    }
    if(dep[a]>dep[b])swap(a,b);
    if(a!=b)
        ans+=query(1,dfn[a]+1,dfn[b]);
    return ans;
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(head,-1,sizeof(head));
    int N;cin>>N;
    for(int i=0;i<N-1;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    init(N,1);
    int Q;cin>>Q;
    for(int i=0;i<Q;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
           update(1,dfn[mp[(x-1)*2]],y);//改的位置不一样。
        }else{
            cout<<solve(x,y)<<endl;
        }
    }
    return 0;
}

这次的还算比较简单的,但是我的排名却不咋地,继续努力吧。

标签:AtCoder,num1,Beginner,int,cin,long,maxn,294,include
From: https://www.cnblogs.com/WUTONGHUA02/p/17240386.html

相关文章

  • 【AT_abc294_g 题解】
    题意给定一颗\(n\)个节点的带权无向树。给出\(q\)个操作:1iw:把第\(i\)条边的边权变成\(w\)。2uv:求\(u\tov\)简单路径的边权和。解法根据树上差分。......
  • [??记录] AtCoder 练习
    3.19arc066_c(dp,观察)观察:只会在负号右边添加\((/)\)两个位置之间至多一个括号。括号不会嵌套多层。\(f[i][j]\)表示处理完\(i\)个数,有\(j\)个未匹配左括号......
  • abc294G
    UpdG看上好模板的样子,果然是个模板题好题,首先考虑这张图的\(Euler\Tour\),简单点说,就是dfs一遍,把每个点入栈出栈顺序存起来,举个例子·21223这棵树的......
  • [ABC294Ex] K-Coloring
    考虑dfs后搞出dfs树,考虑若干返祖边有限制,那么,我们一个朴素的想法是枚举这些有被返祖边搞到的点的颜色,但这样最坏是\(O(K^n)\)的。但显然一条返祖边在钦定完一个端点......
  • AtCoder Beginner Contest 294
    A-Filter(abc294a)题目大意给定一个数组,不改变原顺序,输出是偶数的数。解题思路模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL......
  • 【题解】ABC294
    AtCoderBeginnerContest294AFilter无意义题,找出所有偶数。BASCIIArt无意义题,按题意模拟。CMergeSequences无意义题,离散化即可。DBank无意义题,set维护即......
  • AtCoder Beginner Contest 293
    A-SwapOddandEven#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){ strings; cin>>s; for(inti=0;i+1<s.size();i+=2) swap(......
  • AtCoder Beginner Contest 293
    上周因为GDKOI咕咕咕了A-SwapOddandEven(abc293a)题目大意给定一个字符串,交换每两个相邻字母,输出结果。解题思路模拟即可。神奇的代码#include<bits/std......
  • AtCoder Beginner Contest 293(C,D ,E,F)
    AtCoderBeginnerContest293(C,D,E,F)CC这道题其实还蛮好写的,就是一个\(dfs\),然后我看错了题意,就记录一下这道题的大意是我们需要从\((1,1)\)走到\((n,m)\),我们只......
  • [AtCoder Beginner Contest 281][G. Farthest City]
    和CF1657E的做法十分相似题目链接:G-FarthestCity题目大意:问有多少个\(n(3\len\le500)\)个点的无向连通图满足,若设\(1\)到\(i\)的最短路距离为\(dis_i\),则......