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

AtCoder Beginner Contest 340 考试总结

时间：2024-02-12 22:22:17浏览次数：35  
标签：AtCoder ch Beginner Contest int void namespace read define

前言

可惜的是我是VP的，却打得相对较好（服了。

得分明细：

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

改题明细：

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

第一次打 AT，发挥还可以。

A. Arithmetic Progression

Problem

打印一个包含第一项 \(A\)，最后一项 \(B\) 和公差 \(C\) 的算术序列。

Solve

模拟

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 a, b, c; 

signed main() {
  read(a, b, c);
  for (int i = a; i <= b; i += c) cout << i << ' ';
  cout << '\n';
  return 0;
}

B. Append

Problem

初始给定空序列 \(A\)，\(q\) 次操作：

  1. 1 x 在序列末尾插入数字 \(x\)；
  2. 2 k 查询从后往前第 \(k\) 个数字是多少；

保证合法。

Solve

又是模拟

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 = 105;

int q, a[N], n;

signed main() {
  read(q);
  while(q--) {
    int op, x;
    read(op, x);
    if(op == 1) {
      a[++n] = x;
    } else {
      cout << a[n - x + 1] << '\n';
    }
  }
  return 0;
}

C. Divide and Divide

Problem

给定一个数 \(n\)，写在黑板上。每次选择黑板上一个不小于 \(1\) 的数 \(x\) 擦去，并写上 \(\left\lfloor\frac{x}{2}\right\rfloor\) 与 \(\left\lceil\frac{x}{2}\right\rceil\)，并付出代价 \(x\)。问最后使黑板上的数全部小于 \(1\) 的代价是多少。

Solve

记 \(f_i\) 表示给定的数为 \(i\) 时的代价。

这样显然有（最优）子结构。可以 \(dp\)：

\[f_i= \begin{cases} f_{\left\lfloor\frac{i}{2}\right\rfloor}+f_{\left\lceil\frac{i}{2}\right\rceil}+i & i>1\\ 0 & otherwise \end{cases} \]

先暴搜，然后暴搜转记搜。

时间复杂度 \(O(\log n)\)。

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 = 1e5 + 10;

int n, ans;

map<int, int> f;

int solve(int x) {
  if(x < 2) return 0;
  if(f[x]) return f[x];
  return f[x] = solve(x / 2) + solve(ceil(1.0 * x / 2)) + x;
}

signed main() {
  read(n);
  cout << solve(n) << '\n';
  return 0;
}

D. Super Takahashi Bros

Problem

高桥正在玩一个游戏。

游戏由编号为 \(1,2,3\dots,n\) 的 \(n\) 个阶段组成。最初，只有阶段 \(1\) 可以玩。

对于每个阶段 \(i\)，可执行两种操作之一：

  • 花费 \(A_i\) 秒清除阶段 \(i\)。这样就可以进入 \(i+1\) 阶段。
  • 花费 \(B_i\) 秒清除阶段 \(i\)。这样就可以进入 \(X_i\) 阶段。

至少需要多少秒才能通关 \(n\)？

Solve

对于每个阶段的操作，都有两种转移状态：

  • 花费 \(A_i\) 秒清除阶段 \(i\)。这样就可以进入 \(i+1\) 阶段。
  • 花费 \(B_i\) 秒清除阶段 \(i\)。这样就可以进入 \(X_i\) 阶段。

显然，阶段与阶段之间构成图论关系。因此建图。

考虑到求最小时间。所以建图后跑最短路即可。

时间复杂度 \(O(n\log n)\)。

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 v, w, nx;
  bool operator < (const Node &x) const {
    return x.w < w;
  }
} e[N << 1];

int n, h[N], tot, dis[N];

bool vis[N];

void add(int u, int v, int w) {
  e[++tot] = (Node){v, w, h[u]};
  h[u] = tot;
}

void dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  dis[1] = 0;
  priority_queue<Node> q; 
  q.push((Node){1, 0});
  while(!q.empty()) {
    int x = q.top().v;
    q.pop();
    if(vis[x]) continue;
    for (int i = h[x]; i; i = e[i].nx) {
      int y = e[i].v, w = e[i].w;
      if(dis[y] > dis[x] + w) {
        dis[y] = dis[x] + w;
        q.push((Node){y, dis[y]});
      }
    }
  }
}

signed main() {
  read(n);
  For(i,1,n-1) {
    int a, b, x;
    read(a, b, x);
    add(i, i + 1, a);
    add(i, x, b);
  }
  dijkstra();
  cout << dis[n] << '\n'; 
  return 0;
}

E. Mancala 2

Problem

有 \(N\) 个编号为 \(0\) 至 \(N-1\) 的盒子。最初，\(i\) 盒里有 \(A_i\) 个球。

高桥将依次对 \(i=1,2,\ldots,M\) 进行以下操作：

  • 将变量 \(C\) 设为 \(0\)。
  • 从盒子 \(B_i\) 中取出所有的球并握在手中。
  • 在手拿至少一个球的同时，重复下面的过程：
    • 将 \(C\) 的值增加 \(1\)。
    • 将手中的一个球放入盒子 \((B_i+C) \bmod N\)。

完成所有操作后，确定每个盒子中的球数。

Solve

若把序列 \(0\) 到 \(N-1\) 顺时针看成环，则操作在环上顺时针进行。

考虑贡献的形式，每次我只会在盒子中放入一个球。操作在环上连续，则在序列上为前缀 \(+\) 后缀 \(+\) 全局加的形式。

计算出每轮操作的起点，终点，周期。则可以用线段树维护（建议用树状数组，不然常数一坨屎）。

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 v, w, nx;
  bool operator < (const Node &x) const {
    return x.w < w;
  }
} e[N << 1];

int n, h[N], tot, dis[N];

bool vis[N];

void add(int u, int v, int w) {
  e[++tot] = (Node){v, w, h[u]};
  h[u] = tot;
}

void dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  dis[1] = 0;
  priority_queue<Node> q; 
  q.push((Node){1, 0});
  while(!q.empty()) {
    int x = q.top().v;
    q.pop();
    if(vis[x]) continue;
    for (int i = h[x]; i; i = e[i].nx) {
      int y = e[i].v, w = e[i].w;
      if(dis[y] > dis[x] + w) {
        dis[y] = dis[x] + w;
        q.push((Node){y, dis[y]});
      }
    }
  }
}

signed main() {
  read(n);
  For(i,1,n-1) {
    int a, b, x;
    read(a, b, x);
    add(i, i + 1, a);
    add(i, x, b);
  }
  dijkstra();
  cout << dis[n] << '\n'; 
  return 0;
}

F. S = 1

Problem

给你整数 \(X\) 和 \(Y\)，它们至少满足 \(X \neq 0\) 和 \(Y \neq 0\) 中的一个。
请找出一对满足以下所有条件的整数 \((A, B)\)。如果不存在这样的一对，请报告。

  • \(-10^{18} \leq A, B \leq 10^{18}\).
  • 顶点位于 \(xy\) 平面上点 \((0, 0), (X, Y), (A, B)\) 的三角形的面积为 \(1\).

Solve

对于点 \((0, 0), (X, Y), (A, B)\) 所围成的三角形面积计算公式为 \(\frac{1}{2}|XB-YA|\)。

\(S=1\) 代入上式得：\(|XB-YA|=2\)。

绝对值随便取（两种情况皆可以），于是得到 \(XB-YA=2\)

扩展欧几里得定理即可解决。

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;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T 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();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

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 a, b, x, y;

void exgcd(int a, int b) {
  if(!b) {
    x = 1, y = 0;
    return ;
  }
  exgcd(b, a % b);
  int t = y;
  y = x - a / b * t, x = t;
  return ;
}

signed main() {
  read(a, b);
  if(2 % __gcd(a, -b)) {
    puts("-1"); return 0;
  }
  exgcd(a, -b);
  cout << 2 / __gcd(a, -b) * y << ' ' << 2 / __gcd(a, -b) * x << '\n';
  return 0;
}

G. Leaf Color

Problem

有一棵树 \(T\) 有 \(N\) 个顶点，编号从 \(1\) 到 \(N\)。连接顶点 \(u_i\) 和 \(v_i\) 的是 \(i\) 边。此外，顶点 \(i\) 被涂上了颜色 \(A_i\)。
求满足以下条件的顶点集合 \(T\) 的（非空）子集 \(S\) 的个数（模为 \(998244353\)）：

  • \(T\) 的子图 \(G\) 由 \(S\) 引导，满足以下所有条件：
    • \(G\) 是一棵树。
    • 所有阶数为 \(1\) 的顶点颜色相同。

Solve

（咕咕咕...）

Code

（咕咕咕...）

标签：AtCoder,ch,Beginner,Contest,int,void,namespace,read,define
From： https://www.cnblogs.com/Daniel-yao/p/18013140

相关文章

  • Atcoder Educational DP Contest 题解
    比赛链接：Atcoderr或者题单A：Frog1常规线性dp，注意到对于每个落点来说，青蛙只能由第\(i-1\)个石头或者第\(i-2\)个石头转移得到，那么我们让\(dp[i]\)为当跳到第\(i\)个石头上的最小费用。此时显然有：\[dp_i=\min(dp_{i-1}+\left|h_i-h_{i-1}\right|,dp_{i-2}+\left|h_......
  • AtCoder-abc340_f题解
    题意简述给定整数\(x,y\)，询问是否存在整数\(a,b\)，满足：\(-10^{18}\lea,b\le10^{18}\)。由\((0,0),(x,y),(a,b)\)三点构成的三角形面积为\(1\)。如果存在，输出任意一组；否则输出-1。思路先假设\(x,y,a,b\)都是正数。那么图大概是这样：此时红色三角形的面积就......
  • AtCoder Beginner Contest 340
    A-ArithmeticProgression(abc340A)题目大意给定等差数列的首项、末项、公差。输出这个等差数列。解题思路从首相依次累加公差到末项即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_std......
  • The 18th Heilongjiang Provincial Collegiate Programming Contest
    A.MagicComputer看题目猜规律#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;usingi32=int32_t;constintmod=998244353;intpower(intx,inty){intans=1;while(y){if(y&......
  • Atcoder Grand Contest 056 B - Range Argmax
    因为一组\(x\)可能对应多组\(p\)，考虑怎么让决策唯一化。我们从大到小依次钦定每个值的位置，即倒着遍历\(i=n,n-1,\cdots,1\)，找到最左端的位置\(v\)满足，对于现在还活着的所有区间\(j\)满足\(l_j\lev\ler_j\)，都有\(x_j=v\)，令\(p_j=i\)，然后删去所有包含\(i\)的区间。......
  • Atcoder Grand Contest 041 F - Histogram Rooks
    考虑容斥。我们钦定一些格子组成的集合不能被覆盖，设为\(A\)。把与\(A\)中的点同行同列的点抠掉，剩余的点则是可放可不放的，总方案数就是\(2^{\text{剩余点的个数}}\)，乘以\((-1)^{|A|}\)并求和即可。这个做法直接优化显然不行。我们考虑设\(A\)中的点所在的列组成的不可重集......
  • AtCoder ABC 263 D 题解
    AtCoderABC263D题解前言本蒟蒻的第一篇题解，大佬勿喷QwQ传送门们洛谷传送门AtCoder传送门正文设有\(x\)使得\(x\leqk\)时，令\(f(k)\)为对\(A'\)进行运算后\(A'=(A_1,A_2,\ldots,A_k)\)的最小和。同理，对于\(y\)使得\(y\leqk\)时，令\(g(k)\)为对\(A......
  • AtCoder Beginner Contest 339 A-G
    A模拟即可voidsolve(){strings;cin>>s;for(inti=s.size()-1;i>=0;i--)if(s[i]=='.'){cout<<s.substr(i+1)<<endl;return;}}B模拟，可以让下标从0开始，这样......
  • AtCoder-ABC-Ex乱写
    ABC233ExManhattanChristmasTree先将\((x,y)\)变成\((x+y,x-y)\)，也就是曼哈顿转切比雪夫，之后曼哈顿距离\(\lek\)的在切比雪夫坐标系下就是一个正方形。用主席树做矩形和，外层套一个二分即可，时间复杂度\(\mathcal{O}(n\log^2n)\)。ABC233Ex#include<bits/stdc++.h......
  • 我也要板刷 AtCoder！
    板刷AtCoderARCC！[ARC171C]SwaponTreeProblem给定一棵\(n\)个节点的树，每个点有个权值\(a_i\)，初始时\(a_i=i\)。你可以执行任意操作：选择一条边\((u,v)\)，交换\(a_u\)和\(a_v\)，并将这条边删掉。问通过上述操作，最后\((a_1,a_2,\cdots,a_n)\)有多少种不同的排列方......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99