Atcoder ABC138

刺骨的言语ヽ痛彻心扉 2024-04-20 10:26 77阅读 0赞

##  ##

Atcoder ABC138

### A .Red or Not ###

> 一道网速题。  
> 大于3200输出原字符串，否则就输出red。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long int a; string ch; int main() { scanf("%d",&a); cin>>ch; if(a >= 3200) cout<<ch; else puts("red"); //system("pause"); return 0; }

## B. Resistors in Parallel ##

> 这不是网速题了，是一道手速题。（滑稽.jpg）  
> 直接暴力求所有数的倒数和，再对所有数的倒数和取倒数就行了，不用考虑精度问题。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 120 using namespace std; int a[N],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; system("pause"); return 0; }

## C. Alchemist ##

> 比之前的两道题要略难一点。  
> 考虑对数组从小到大进行一次排序，然后每次贪心的取两个最小的值。  
> 答案就是最后修改的值。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 1010 int a[N],n; double b[N]; int main() { scanf("%d",&n); for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); sort(a + 1,a + n + 1); int p1 = 2,p2 = 3; b[p1] = ((double)a[1] + (double)a[2]) / 2; while(p2 <= n) { //printf("%d %d\n",&a[p1],&a[p2]); b[p2] = ((double)b[p1] + (double)a[p2]) / 2; // printf("%lf \n",b[p2]); p1++,p2++; //printf("%d %d \n",p1,p2); } //for(int i = 1 ; i <= n ; i++) printf("%d ",a[i]); printf("%lf \n",b[n]); //system("pause"); return 0; }

## D.Strings of Impurity ##

> 数据只有2e6，所以就是一道树链剖分ZZ题。  
> 只需要写子树修改和链查询就可以。  
> 题目中要求的单点查询可以看作查询自己到自己这条链的权值。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 1000010 struct Edge { int to,from; }e[N*2+10]; struct Tree { int sum,tag; int lson,rson; }tree[N*2]; int deep[N],Top[N],idx[N],siz[N]; int n,m,p,root,son[N],tot = 1,cnt; int head[N],fa[N],val[N],w[N],t; inline void add_edge(int x,int y) { e[++cnt].from = y; e[cnt].to = head[x]; head[x] = cnt; } inline void pushup(int x) { tree[x].sum = (tree[tree[x].lson].sum + tree[tree[x].rson].sum); } void pushdown(int x,int l,int r) { int mid = (l + r) >> 1; tree[tree[x].lson].sum = (tree[tree[x].lson].sum + tree[x].tag * (mid - l + 1)); tree[tree[x].rson].sum = (tree[tree[x].rson].sum + tree[x].tag * (r - mid)); tree[tree[x].lson].tag = (tree[tree[x].lson].tag + tree[x].tag); tree[tree[x].rson].tag = (tree[tree[x].rson].tag + tree[x].tag); tree[x].tag = 0; } void build(int x,int l,int r) { if(l == r) { tree[x].sum = w[l]; return; } int mid = (l + r) >> 1; tree[x].lson = ++tot; build(tree[x].lson,l,mid); tree[x].rson = ++tot; build(tree[x].rson,mid+1,r); pushup(x); } void update(int x,int l,int r,int ll,int rr,int v) { if(l == ll && r == rr) { tree[x].sum = (tree[x].sum + (r - l + 1) * v); tree[x].tag = (tree[x].tag + v); return; } int mid = (l + r) >> 1; pushdown(x,l,r); if(rr <= mid) update(tree[x].lson,l,mid,ll,rr,v); else if(ll > mid) update(tree[x].rson,mid+1,r,ll,rr,v); else { update(tree[x].lson,l,mid,ll,mid,v); update(tree[x].rson,mid+1,r,mid+1,rr,v); } pushup(x); } inline int query(int x,int l,int r,int ll,int rr) { if(l == ll && r == rr) return tree[x].sum; int mid = (l + r) >> 1; pushdown(x,l,r); if(rr <= mid) return query(tree[x].lson,l,mid,ll,rr); else if(ll > mid) return query(tree[x].rson,mid + 1,r,ll,rr); else return (query(tree[x].lson,l,mid,ll,mid) + query(tree[x].rson,mid + 1,r,mid + 1,rr)); } void dfs1(int x,int f,int depth) { fa[x] = f; siz[x] = 1; deep[x] = depth; int maxs = -1; for(int i = head[x] ; i ; i = e[i].to) { int u = e[i].from; if(u == f) continue; dfs1(u,x,depth + 1); siz[x] += siz[u]; if(siz[u] > maxs) { son[x] = u; maxs = siz[u]; } } } void dfs2(int x,int topf) { idx[x] = ++t; w[t] = val[x]; Top[x] = topf; if(!son[x]) return; dfs2(son[x],topf); for(int i = head[x] ; i ; i = e[i].to) { int u = e[i].from; if(u == son[x] || u == fa[x]) continue; dfs2(u,u); } } inline int query_link(int x,int y) { int ans = 0; while(Top[x] != Top[y]) { if(deep[Top[x]] < deep[Top[y]]) swap(x,y); ans += query(1,1,n,idx[Top[x]],idx[x]); ans %= p; x = fa[Top[x]]; } if(deep[x] > deep[y]) swap(x,y); ans = (ans + query(1,1,n,idx[x],idx[y])); return ans; } inline void update_link(int x,int y,int val) { while(Top[x] != Top[y]) { if(deep[Top[x]] < deep[Top[y]]) swap(x,y); update(1,1,n,idx[Top[x]],idx[x],val); x = fa[Top[x]]; } if(deep[x] > deep[y]) swap(x,y); update(1,1,n,idx[x],idx[y],val); } inline int query_tree(int x) { return query(1,1,n,idx[x],idx[x] + siz[x] - 1); } inline void update_tree(int x,int val) { update(1,1,n,idx[x],idx[x] + siz[x] - 1,val); } int main() { scanf("%d%d",&n,&m); for(int i = 1 ; i < n ; i++) { int a,b; scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); while(m--) { int x,z; scanf("%d%d",&x,&z); update_tree(x,z); } for(int i = 1 ; i <= n ; i++) printf("%d ",query_link(i,i)); //system("pause"); return 0; }

## E.Strings of Impurity ##

> 一道字符串题。  
> 我们考虑在s串中查询t串中的每个字符出现的位置，统计出现了多少次，即统计需要循环s串多少次。  
> 那么答案就是 $ cnt \* s.length() + pos $ 。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; #define LL long long string s,t; LL pos,cnt; int main() { cin>>s>>t; for(int i = 0 ; i < t.length() ; i++) { pos = s.find(t[i],pos); if(pos == -1) { pos = s.find(t[i],0); if(pos == -1) { puts("-1"); return 0; } cnt++; } pos++; } LL ans = cnt * s.length() + pos; printf("%lld \n",ans); //system("pause"); return 0; }

## F.Coincidence ##

> 一道极端恶心的DP题。  
> 设 $ dp\[i\]\[0/1\]\[0/1\] $ 表示考虑到当前位置i，满足 $ x \\geq L $ ， 并且满足 $ y \\leq R $ 的方案数。  
> 因为数据上界为 $ 10^\{18\} $ ，不能直接存，所以我们考虑利用2进制，数组的第一维代表到 $ 2^i $ 的位置。  
> 此时数组只需要开 $ dp\[65\]\[2\]\[2\] $ ,第一维只有65是因为 $ 2^\{60\} \\geq 10^\{18\}$ 。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long const int mod = 1e9 + 7; LL dp[66][2][2],L, R; LL dfs(int x, bool Left, bool Right, bool zero) { if(x < 0) return 1; if(dp[x][Left][Right] >= 0 && !zero) return dp[x][Left][Right]; LL ans = 0; int l = 0, r = 1; if(Left) l = L >> x & 1; if(Right) r = R >> x & 1; for(int i = l ; i <= 1 ; i++) { for (int j = i ; j <= r ; j++) { if (j == 1 && zero) { if(i == 1) ans += dfs(x-1, Left && i == l, Right && j == r, zero && j == 0); } else ans += dfs(x-1, Left && i == l, Right && j == r, zero && j == 0); } } ans %= mod; if(!zero) dp[x][Left][Right] = ans; return ans; } int main() { scanf("%lld%lld", & L, & R); memset(dp, -1, sizeof(dp)); printf("%lld \n", dfs(60, 1, 1, 1)); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11378044.html