Atcoder abc 138

谁践踏了优雅 2021-10-23 06:57 304阅读 0赞

# [题解][Link 1] #

# [视频][Link 2] #

# \\(\\color\{red\}A\\) #

![1522713-20190818215023786-1718659192.png][]  
![1522713-20190818215037499-1676554456.png][]  
![1522713-20190818215046035-1712091922.png][]

## 题意? ##

> 输入一个数,如果这个数大于3200,那么就输出后面的字符串,否则输出red

## 代码 ##

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std ; int a ; string s ; int main () { cin >> a >> s ; if(a >= 3200) { cout << s << endl ; }else { puts("red") ; } return 0 ; }

# \\(\\color\{blue\}B\\) #

![1522713-20190818215848430-1239334026.png][]  
![1522713-20190818215901012-1022676098.png][]  
![1522713-20190818215911631-134384950.png][]

## 题意 ##

> 就是让你把读到的数取到数加起来,然后把这个和取到数输出

## 代码 ##

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 120 using namespace std ; int a[maxn] , n ; double s ; int main () { cin >> n ; for(int i = 1 ; i <= n ; i ++) { double x ; cin >> x ; x = 1/x ; s += x ; } cout << 1/s <<endl ; }

# \\(\\color\{green\}C\\) #

![1522713-20190818220142908-884507216.png][]  
![1522713-20190818220210803-363642388.png][]  
![1522713-20190818220222893-2052304476.png][]  
![1522713-20190818220231897-1683040837.png][]

## 题意 ##

> 从小到大排个序,然后每次把前两小按照z=(x+y)/2的公式变成一个数,输出最后的唯一数

## 代码 ##

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define maxn 120 using namespace std ; priority_queue<double,vector<double>,greater<double> >q ; double a[maxn] , ans ; int n ; int main () { cin >> n ; for(int i = 1 ; i <= n ; i ++) { cin >> a[i] ; q.push(a[i]) ; } for(int i = 1 ; i < n ; i ++) { double x = q.top() ; q.pop() ; double y = q.top() ; q.pop() ; double c = (x+y)/2 ; q.push(c) ; } cout << q.top() <<endl ; }

# \\(\\color\{blue\}D\\) #

![1522713-20190818220419393-504528762.png][]  
![1522713-20190818220428065-812664205.png][]  
![1522713-20190818220441118-843682204.png][]  
![1522713-20190818220450176-1157175533.png][]

## 题意 : ##

> 一棵树,根节点为1号节点,有n各节点,m个操作,每次操作把i的子树增加x,最后问每个节点的大小

## 代码 ##

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long #define ls k<<1 #define rs k<<1|1 using namespace std; const int N=200005; struct node { int u,v,nxt; }edge[2*N]; struct Tree { int l,r,w,siz,f; }T[2*N]; int n,m,cnt=0,num=1,root=1,a[N],b[N],head[N]; int deep[N],fa[N],son[N],tot[N],top[N],idx[N]; void AddEdge(int x,int y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } int dfs1(int now,int f,int dep) { deep[now]=dep; fa[now]=f; tot[now]=1; int maxson=-1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==f) continue; tot[now]+=dfs1(edge[i].v,now,dep+1); if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v; } return tot[now]; } void update(int k) { T[k].w=T[ls].w+T[rs].w; } void Build(int k,int ll,int rr) { T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1; if(ll==rr) { T[k].w=a[ll]; return; } int mid=(ll+rr)>>1; Build(ls,ll,mid); Build(rs,mid+1,rr); update(k); } void dfs2(int now,int topf) { idx[now]=++cnt; a[cnt]=b[now]; top[now]=topf; if(!son[now]) return; dfs2(son[now],topf); for(int i=head[now];i!=-1;i=edge[i].nxt) if(!idx[edge[i].v]) dfs2(edge[i].v,edge[i].v); } void pushdown(int k) { if(!T[k].f) return ; T[ls].w=T[ls].w+T[ls].siz*T[k].f; T[rs].w=T[rs].w+T[rs].siz*T[k].f; T[ls].f=T[ls].f+T[k].f; T[rs].f=T[rs].f+T[k].f; T[k].f=0; } void IntervalAdd(int k,int ll,int rr,int val) { if(ll<=T[k].l&&T[k].r<=rr) { T[k].w+=T[k].siz*val; T[k].f+=val; return; } pushdown(k); int mid=(T[k].l+T[k].r)>>1; if(ll<=mid) IntervalAdd(ls,ll,rr,val); if(rr>mid) IntervalAdd(rs,ll,rr,val); update(k); } int IntervalSum(int k,int ll,int rr) { int ans=0; if(ll<=T[k].l&&T[k].r<=rr) return T[k].w; pushdown(k); int mid=(T[k].l+T[k].r)>>1; if(ll<=mid) ans=ans+IntervalSum(ls,ll,rr); if(rr>mid) ans=ans+IntervalSum(rs,ll,rr); return ans; } void TreeSum(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); ans=ans+IntervalSum(1,idx[top[x]],idx[x]); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); ans=ans+IntervalSum(1,idx[x],idx[y]); cout<<ans<<" "; } int main() { cin>>n>>m; memset(head,-1,sizeof(head)); for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; AddEdge(x,y); AddEdge(y,x); } dfs1(root,0,1); dfs2(root,root); Build(1,1,n); while(m--) { int x,y; cin>>x>>y; IntervalAdd(1,idx[x],idx[x]+tot[x]-1,y); } for(int i=1;i<=n;i++) TreeSum(i,i); cout<<endl; return 0; }

# \\(\\color\{yellow\}E\\) #

![1522713-20190818221733298-664819748.png][]  
![1522713-20190818221823613-535237077.png][]  
![1522713-20190818221831838-341663662.png][]

## 思路 ##

> 暴力

## 非AC代码 ##

#include <bits/stdc++.h> using namespace std ; string s , t ; char vis[30] ; int main () { cin >> s >> t ; for(int i = 0 ; i < s.size() ; i ++) { int c = s[i] - 'a' + 1 ; vis[c] ++ ; } for(int i = 0 ; i < t.size() ; i ++) { int c = t[i] - 'a' + 1 ; if(!vis[c]) { puts("-1") ; return 0 ; } } int _t = 0 ,_s = 0 ,tot = 0 ; int n = s.size() ; while(_t != t.size() ) { _s = _s%n ; tot ++ ; // cout <<tot<< ":" << _s << " " << s[_s] << "*" << _t << " " << t[_t] <<endl ; if(s[_s] == t[_t]) { _t ++ ; _s ++ ; }else { _s ++ ; } } cout << tot << endl ; return 0 ; }

# 附赠图片 #

[youtube 直播?][Link 2]

![1522713-20190818221810877-678447853.png][]  
![1522713-20190818221949049-1417304594.png][]  
![1522713-20190818222028873-697202322.png][]

转载于:https://www.cnblogs.com/lyt020321/p/11374090.html

[Link 1]: https://img.atcoder.jp/abc138/editorial.pdf
[Link 2]: https://www.youtube.com/watch?v=lWETOlGiuaI
[1522713-20190818215023786-1718659192.png]: /images/20211023/1ec087c0eb2a48e0add4467a012c3e85.png
[1522713-20190818215037499-1676554456.png]: /images/20211023/ce90a5008c174b919a52e25ad872f177.png
[1522713-20190818215046035-1712091922.png]: /images/20211023/f7926eac257d49ecba4cf9f6521005b7.png
[1522713-20190818215848430-1239334026.png]: /images/20211023/fe51b3c06c2e4be7a9c8f7b3bc78a0fa.png
[1522713-20190818215901012-1022676098.png]: /images/20211023/281090cde14b4ec4be0b37e046f7259c.png
[1522713-20190818215911631-134384950.png]: /images/20211023/efdf7dd5e97b438bae5ea9b2d2df3d15.png
[1522713-20190818220142908-884507216.png]: /images/20211023/71d9b3e1c5fd4f82bd01c5ea4d73654f.png
[1522713-20190818220210803-363642388.png]: /images/20211023/3569d525e97148b0b148ec6d264c9f04.png
[1522713-20190818220222893-2052304476.png]: /images/20211023/4fdf1370bc4a404d930ccf82122eac62.png
[1522713-20190818220231897-1683040837.png]: /images/20211023/2780203099fe410a8aedaec7bed71572.png
[1522713-20190818220419393-504528762.png]: /images/20211023/46a31ad08da840c995ea9f17e1558223.png
[1522713-20190818220428065-812664205.png]: /images/20211023/67c97eed749e498391ee9280ee0390a1.png
[1522713-20190818220441118-843682204.png]: /images/20211023/8c827851774b405c9071d435ba9455b8.png
[1522713-20190818220450176-1157175533.png]: /images/20211023/7c6be8a2eca54d1a8c1cf92cc301e1af.png
[1522713-20190818221733298-664819748.png]: /images/20211023/50c6f5324d6c40549f92ed8c7347a983.png
[1522713-20190818221823613-535237077.png]: /images/20211023/558748ed6cc24b679a762aaa9523d013.png
[1522713-20190818221831838-341663662.png]: /images/20211023/fd80ad29437c4b7db0b8976ce8c2264f.png
[1522713-20190818221810877-678447853.png]: /images/20211023/3b535e88b8354f0d82166f4f619661e6.png
[1522713-20190818221949049-1417304594.png]: /images/20211023/325a52af3eb44207b72905b9b615f463.png
[1522713-20190818222028873-697202322.png]: /images/20211023/d9ba91b753f6433dad9fc31983dd39b7.png