首页 > 其他分享 >AtCoder Beginner Contest 352 考试总结

AtCoder Beginner Contest 352 考试总结

时间：2024-05-04 23:13:42浏览次数：25  
标签：AtCoder ch Beginner Contest int rint 10 read define

前言

正常发挥。属于是 \(4\) 个月没搞 OI，复健成功了！

得分明细：

A B C D E F G Total
√ √ √ √ √ × × 1475

改题明细：

A B C D E F G
√ √ √ √ √ × ×

第一次正式 rated 打 AT，行吧！

A. AtCoder Line

Problem

AtCoder 铁路线有 \(N\) 个车站，编号为 \(1, 2, \ldots, N\)。

在这条线路上，有趟进站列车从 \(1\) 站出发，依次停靠 \(2, 3, \ldots, N\) 站，有趟出站列车从 \(N\) 站出发，依次停靠 \(N - 1, N - 2, \ldots, 1\) 站。

高桥站即将从 \(X\) 站前往 \(Y\) 站，只需使用进站和出站列车中的一列。

求列车在 \(Z\) 站停留的时间。

Solve

当 \(\{z\in [x,y]|x\le y\}\) 即为 "Yes"，否则即为 "No"。

Code

#include <bits/stdc++.h>
#define ll long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

int n, x, y, z;

signed main() {
  n = read(), x = read(), y = read(), z = read();
  if(x > y) swap(x, y);
  if(x <= z && z <= y) puts("Yes");
  else puts("No");
  return 0;
}

B. Typing

Problem

高桥尝试使用键盘输入由小写英文字母组成的字符串 \(S\)。

他打字时只看键盘，不看屏幕，实际键入的字符串是 \(T\)。

\(T\) 中没有被误输入的字符称为正确输入字符。

确定正确键入的字符在 \(T\) 中的位置。

Solve

指针 \(i\) 指着 \(S\) 一边判一边扫即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 2e5 + 10;

int n, m;

char s[N], t[N];

signed main() {
  cin >> (s + 1) >> (t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  int i = 1;
  For(j,1,m) {
    if(s[i] == t[j]) cout << j << ' ', i++;
  }
  return 0;
}

C. Standing On The Shoulders

Problem

有 \(N\) 个巨人，他们的名字分别是 \(1\) 到 \(N\)。当巨人 \(i\) 站在地上时，他们的肩高是 \(A_i\)，头高是 \(B_i\)。

你可以选择 \((1, 2, \ldots, N)\) 的 \((P_1, P_2, \ldots, P_N)\) 排列组合，并根据以下规则堆叠 \(N\) 个巨人：

  • 首先，将巨人 \(P_1\) 放在地上。巨人 \(P_1\) 的肩膀距离地面的高度为 \(A_{P_1}\)，头部距离地面的高度为 \(B_{P_1}\)。
  • 为了 \(i = 1, 2, \ldots, N - 1\) 的顺序，要把巨人 \(P_{i + 1}\) 放在巨人 \(P_i\) 的肩膀上。如果巨人 \(P_i\) 的肩膀距离地面的高度是 \(t\)，那么巨人 \(P_{i + 1}\) 的肩膀距离地面的高度就是 \(t + A_{P_{i + 1}}\)，他们的头距离地面的高度就是 \(t + B_{P_{i + 1}}\)。

求最上面的巨人 \(P_N\) 的头部距离地面的最大可能高度。

Solve

考虑到每种排列的叠加总高度为某 \(n-1\) 个巨人的肩高加上剩下 \(1\) 个巨人的头高。

则答案为：\(\max\limits_{1\le i \le n}\sum\limits_{j=1,i\not=j}^{n}A_j+B_i\)。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 2e5 + 10;

struct Node {
  int a, b;
} a[N];

int n, res = 0, ans;

signed main() {
  n = read();
  For(i,1,n) a[i].a = read(), a[i].b = read(), res += a[i].a;
  For(i,1,n) {
    ans = max(ans, res - a[i].a + a[i].b);
  }
  cout << ans << '\n';
  return 0;
}

D. Permutation Subsequence

Problem

给你一个 \((1, 2, \dots, N)\) 的排列组合 \(P = (P_1, P_2, \dots, P_N)\)。

如果一个索引序列 \((i_1, i_2, \dots, i_K)\) 同时满足以下两个条件，那么这个索引序列被称为好索引序列：

  • \(1 \leq i_1<i_2<\dots<i_K \leq N\)。
  • 子序列 \((P_{i_1}, P_{i_2}, \dots, P_{i_K})\) 可以通过重新排列一些连续的 \(K\) 整数而得到。
    形式上，存在一个整数 \(a\) ，使得 \(\lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace\)。

求所有好的索引序列中 \(i_K - i_1\) 的最小值。可以证明，在此问题的约束条件下，至少存在一个好的索引序列。

Solve

记 \(a_{p_i} = i\)，发现答案贡献区间为一个宽度为 \(k\) 的窗口。

滑动窗口求 max/min 即可。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 2e5 + 10;

int n, k, p[N], a[N], q[N], Max[N], Min[N], ans = INT_MAX;

signed main() {
  n = read(), k = read();
  For(i,1,n) p[i] = read(), a[p[i]] = i;
  int h = 1, t = 0;
  For(i,1,n) {
    while(h <= t && i - q[h] + 1 > k) h++;
    while(h <= t && a[i] < a[q[t]]) t--;
    q[++t] = i;
    if(i >= k) {
      Min[i] = a[q[h]];
    }
  }
  h = 1, t = 0;
  For(i,1,n) {
    while(h <= t && i - q[h] + 1 > k) h++;
    while(h <= t && a[i] > a[q[t]]) t--;
    q[++t] = i;
    if(i >= k) {
      Max[i] = a[q[h]];
    }
  }
  For(i,k,n) {
    ans = min(ans, Max[i] - Min[i]);
  }
  cout << ans << '\n';
  return 0;
}

E. Clique Connect

Problem

给你一个加权无向图 \(G\)，其中有 \(N\) 个顶点，编号为 \(1\) 至 \(N\) 。最初，\(G\) 没有边。

您将执行 \(M\) 次操作为 \(G\) 添加边。\(i\)-th 操作 \((1 \leq i \leq M)\) 如下：

  • 给你一个由 \(K_i\) 个顶点组成的顶点子集 \(S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace\)。对于每一对 \(u, v\) 这样的顶点 \(u, v \in S_i\) 和 \(u < v\)，在顶点 \(u\) 和 \(v\) 之间添加一条边，边的权重为 \(C_i\)。

完成所有 \(M\) 操作后，确定 \(G\) 是否相连。如果是，求 \(G\) 最小生成树中各条边的总重。

Solve

一个组内的点与其连边组成的图必为一个团，团内两两联通，且边权相等。

考虑 kruskal，先决策边权最小的团。然后暴力团内 kruskal。

加两个限制：

  1. 如果当前点已经在团内联通，就不需要加边了，跳过此回合；
  2. 如果此时生成树的边数已经为 \(n-1\)，结束决策；

然后就 A 了。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 4e5 + 10;

struct Eg {
  int k, c;
} b[N];

int n, m, f[N], p[N], ans, net;

vector<int> a[N];

bool vis[N];

bool cmp(int x, int y) {
  return b[x].c < b[y].c;
}

int find(int x) {
  return (x == f[x] ? x : f[x] = find(f[x]));
}

signed main() {
  n = read(), m = read();
  For(i,1,n) f[i] = i;
  For(i,1,m) {
    p[i] = i;
    b[i] = (Eg){read(), read()};
    For(j,1,b[i].k) {
      int x = read();
      a[i].push_back(x);
      f[find(a[i][0])] = find(a[i][a[i].size()-1]);
    }
  }
  int res = 0;
  For(i,1,n) {
    if(find(i) != find(1)) res++; 
  }
  if(res) return puts("-1"), 0;
  For(i,1,n) f[i] = i;
  sort(p + 1, p + m + 1, cmp);
  For(i,1,m) {
    int tg = i; i = p[i];
    For(j,0,b[i].k-1) {
      if(vis[find(a[i][j])]) continue;
      For(k,j+1,b[i].k-1) {
        int u = a[i][j], v = a[i][k];
        int fu = find(u), fv = find(v);
        if(fu == fv) continue;
        f[fu] = fv; vis[fu] = 1;
        ans += b[i].c; net++;
        if(net == n-1) goto yzsy;
      }
    }
    i = tg;
  }
  yzsy: ;
  cout << ans << '\n';
  return 0;
}

标签：AtCoder,ch,Beginner,Contest,int,rint,10,read,define
From： https://www.cnblogs.com/Daniel-yao/p/18172801

相关文章

  • AtCoder abc352
    EProblemStatementYouaregivenaweightedundirectedgraph$G$with$N$vertices,numbered$1$to$N$.Initially,$G$hasnoedges.Youwillperform$M$operationstoaddedgesto$G$.The$i$-thoperation$$(1\leqi\leqM)$$isasfollows:Youar......
  • AtCoder Beginner Contest 351
    A-Thebottomoftheninth(abc351A)题目大意给定\(9\)个\(a_i\)和\(8\)个\(b_i\)，问最后一个\(b_9\)是多少，使得\(\suma_i<\sumb_i\)。解题思路答案就是\(\suma_i-\sumb_i+1\)。神奇的代码a=sum(map(int,input().split()))b=sum(map(int,input().......
  • [atcoder]【LCR114] [
    importjava.util.*;classSolution{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();Stringstr=solution.alienOrder(newString[]{"wrt","wrf","er","e......
  • 2023-2024 ICPC German Collegiate Programming Contest (GCPC 2023)
    B.BalloonDarts首先上一些计算几何的板子。如果\(k\)条直线覆盖\(n\)个点成立的，则有两种情况。如果\(n\lek\)则一定成立，反之在前\(k+1\)个点中必然存在两个点被一条直线经过，我们可以枚举出这条直线，然后暴力的删掉点，然后递归做。#include<bits/stdc++.h>usingnamespaces......
  • [atcoder 351] [F Double Sum] [线段树]
    解法，使用线段树。请看代码：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.math.BigInteger;importjava.util.StringTokenizer;publicclassMain{staticclassSegmentNode{intleft;......
  • 2020-2021 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Sub
    E-EasyCompare-and-Set题意给定n个条件，如果存在一个合法序列使得这n个判断条件成立，则输出Yes和这个合法序列，否则输出No。分析首先可以发现对于\(w_i=0\)的操作我们可以在处理完\(w_i=1\)的操作之后讨论一下即可。发现\(a_i\)和\(b_i\)很大需要对其进行离散化操作。离......
  • Atcoder ABC 351 全题解
    乾岩我：G题来咯！！！大火：这G题，大家都不敢做，说是有人在里面放了毒瘤。我：做，做，为什么不做！不做也别想活着！！！（两天后）我：我的G题完成辣！！！！！！AB不讲C显然$2^a*2=2^{a+1}$。考虑用一个栈存球的大小是$2$的多少次方，每次插入球后，不断取出后面两个球，大小相同则合并，否则插入下一个......
  • AtCoder-abc350_g 题解
    原题链接题意简述有一个无向图，初始时没有边。接下来有一些操作：将\(u,v\)连边。询问\(u,v\)的距离是否为\(2\)，如果是，则输出中间的那个点的编号，否则输出0。每次询问后，更新\(lastans\)为询问的答案，初始时为\(0\)。每次操作的\(opt,u,v\)使用\(lastans\)解码，......
  • AtCoder-abc350_f 题解
    原题链接题意简述给定一个字符串\(S\)，对于每个匹配的括号，将括号内的字符左右翻转并大小写反转，然后删除括号。输出最后的序列。思路本题为文艺平衡树的模板题。扫一遍字符串进行括号匹配，每次把最内层的括号进行操作。最后遍历一遍平衡树，将不为括号字符的字符输出。FHQ_Treap......
  • AtCoder Beginner Contest 351
    B-SpottheDifference难度:⭐题目大意给定两个矩阵,找不同解题思路数据很小,暴力就行;神秘代码#include<bits/stdc++.h>#defineintunsignedlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespa......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99