头像

_Crush

$ \color{blue}{AcWing小学} $




离线:1天前


最近来访(184)
用户头像
稚始稚终
用户头像
acmdyh
用户头像
Eureka_7
用户头像
Ungoliant
用户头像
小雪菜本菜
用户头像
gwj12345
用户头像
猫南北_5
用户头像
一只奇怪的小魔女
用户头像
暑假寒假不可能学习
用户头像
再也不会
用户头像
峰峰爱吃肉
用户头像
1668120228
用户头像
宇智波-鼬
用户头像
死亡之主
用户头像
不出锁料
用户头像
tangmmmy
用户头像
不care
用户头像
leimingze
用户头像
凌乱之风
用户头像
21KINGDMG

活动打卡代码 AcWing 4084. 号码牌

_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int p[N], a[N], d[N];

int main ()
{
    function<int(int)> f = [&](int x) {
        return x == p[x] ? x : p[x] = f(p[x]);
    };
    auto mg = [&](int x, int y) {
        x = f(x); y = f(y);
        p[x] = y;
    };

    int n; cin >> n;
    iota(p + 1, p + n + 1, 1);

    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> d[i];

    for (int i = 1; i <= n; i ++ )
    {
        if (i - d[i] >= 1) mg(i-d[i], i);
        if (i + d[i] <= n) mg(i+d[i], i);
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (f(a[i]) != f(i)) return cout << "NO\n", 0;
    }
    cout << "YES\n";
    return 0;
}


活动打卡代码 AcWing 4083. 最大公约数

_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], c[N]; // c(i) 表示以i为因子的所有数字的数量

int main ()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], ++ c[a[i]];
    for (int i = 1; i < N; i ++ ) // 枚举所有因子
        for (int j = i + i; j < N; j += i)
            c[i] += c[j];
    int ret = 1;
    for (int i = 2; i < N; i ++ ) ret = max(ret, c[i]);
    cout << ret << endl;
    return 0;
}


活动打卡代码 AcWing 4082. 子序列

_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

int main ()
{
    string s; cin >> s;
    int q1 = 0, a = 0, q2 = 0;
    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] == 'A') a += q1;
        if (s[i] == 'Q') q2 += a, ++ q1;
    }
    cout << q2 << endl;
    return 0;
}



_Crush
3天前

Edu 118(Div.2)

A. Long Comparison

题意

给定四个数字 $x, p_1, y, p_2$ ,$p_1$ 表示 $x$ 后面的 $0$ 个数, $p_2$ 表示 $y$ 后面的 $0$ 个数,比较 $x, y$ 的大小。

分析

  1. 位数相同:根据位数判断。
  2. 位数不同:把 $x$ 和 $y$ 的后导 $0$ 去掉,再比较 $x, y$ 。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

void solve ()
{
    string a; int p; cin >> a >> p;
    string b; int p2; cin >> b >> p2;
    if (a.size() + p != b.size() + p2)
    {
        if (a.size() + p > b.size() + p2) cout << '>' << endl;
        else cout << '<' << endl;
    }
    else
    {
        while(a[a.size() - 1] == '0') p ++ , a = a.substr(0, a.size() - 1);
        while(b[b.size() - 1] == '0') p2 ++, b = b.substr(0, b.size() - 1);
        if (a == b) cout << '=' << endl;
        else if (a > b) cout << '>' << endl;
        else cout << '<' << endl;
    }
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

B. Absent Remainder

题意

给定长度为 $n$ 的序列 $a$,找出 $\lfloor \dfrac n 2 \rfloor$ 个序偶 $(x, y)$ 满足:

  1. $x != y$ 。
  2. $x \in a, y \in a$ 。
  3. $x \ \ mod \ \ y \notin a$ 。

分析

对序列排序,输出后面 $\lfloor \dfrac n 2 \rfloor$ 和 $a_1$ 组成的序偶即可,因为模数一定小于 $a_1$ ,而 $a_1$ 是序列最小的数字,因此模数一定不存在在 $a$ 中。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std;
const int N = 200010;

int a[N];

void solve ()
{
    int n; cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 0, p = 2; i < n / 2; i ++, p ++ )
        cout << a[p] << ' ' << a[1] << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

C. Poisoned Dagger

题意

敌人有 $h$ 血量,你有 $n$ 次攻击,第 $i$ 次攻击会从 $a_i$ 秒开始,每秒对敌人造成 $1$ 血量,同时前面的攻击无效(即每秒只会造成 $1$ 伤害),攻击有 $k$ 秒的延长时间,即如果从 $a_i$ 开始攻击,敌人会在 $a_i, a_{i+1} \ldots a_{i+k-1}$ 秒受到伤害。问 $k$ 的最小值。

分析

每次攻击会造成 $min(k, d_i)$ 伤害 ($d_i$ 为两次攻击的间隔)。

由于答案有单调性,可以二分枚举 $k$ 的值。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;

int d[N]; // 间隔,n-1个
int n, h;

bool check (int mid)
{
    int m = 0;
    for (int i = 1; i < n; i ++ )
        m += min(d[i], mid);
    m += mid;
    return m >= h;
}

void solve ()
{
    cin >> n >> h;
    int last; cin >> last;
    for (int i = 1; i < n; i ++ )
    {
        int x; cin >> x;
        d[i] = x - last;
        last = x;
    }
    int l = 1, r = 1e18 + 10;
    while(l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

D. MEX Sequences

题意

定义序列为 $MEX-correct$ 当且仅当序列满足:$|x_i - Mex(x_1, x_2 \ldots x_i)| \le 1$ 。

给定长度为 $n$ 的序列$a$ ,问序列 $a$ 有多少子序列为 $MEX-correct$ 。

分析

参考了嘉心糖的代码

当一个元素为 $x$ 时,它的 $mex$ 只能为 $x-1$ 或者 $x+1$ 。

假设序列某一个前缀 $mex$ 为 $x$ ,那么这个前缀序列的最大值只能为 $x-1$ 或 $x+1$ 。

所以对于某一个元素 $x$ ,可以对$MEX-correct$分为四类:

  1. $mex = x-1, max = x$ 。
  2. $mex = x-1, max = x-2$ 。
  3. $mex = x+1, max = x+2$ 。
  4. $mex = x + 1, max = x$ 。

假设 $(x, y)$ 表示 $(mex, max)$ 。

我们设 $dp1(i)$ 表示序列性质为 $(i, i-1)$ 的序列数量,$dp2(i)$ 表示 $(i, i+1)$ 的序列数量。


对于 $(x-1, x)$ 而言,由于当前元素为 $x$ ,我们可以选择把元素加或者不加入 $(x-1, x)$ 序列,不会影响 $(x-1, x)$ 序列性质。

同时可以把 $x$ 加入到 $(x-1, x-2)$ 序列中使得它变为 $(x-1, x)$ 。但是这个对于 $x = 1$ 时,$(0, -1)$ 一定方案数为 $0$ ,但是我们可以选择直接选择 ${1}$ ,这个也满足 $(x-1, x)$ ,贡献为 $1$。

所以 $dp2(x-1) = dp2(x-1) \times 2 + dp1(x-1) + (x == 1)$ 。


对于 $(x-1, x-2)$ ,它是没有转移的。


对于 $(x+1, x+2)$ ,由于 $mex = x+1$ ,所以序列里一定有 $x$ ,加入 $x$ 不会影响序列性质。

所以 $dp2(x+1) = dp2(x+1) \times 2$ 。


对于 $(x+1, x)$ ,可以选择加入 $x$ 不改变性质,也可以把 $x$ 加入 $(x, x-1)$ 转移为 $(x+1, x)$ 。

注意当 $x = 0$ 时 $(0, -1)$ 一定为 $0$ 个。但是可以直接选择 ${0}$ ,满足 $(x+1, x)$ ,贡献为 $1$。

所以 $dp1(x+1) = dp1(x+1) \times 2 + dp1(x) + (x == 0)$ 。


根据 $dp1, dp2$ 的定义,把所有方案加起来就是总方案。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define int long long
using namespace std;

const int mod = 998244353;

/*
 * dp1(i) 表示mex为i且最大值为i-1的方案数量
 * dp2(i) 表示mex为i且最大值为i+1的方案数量
*/

void solve ()
{
    int n, ret = 0; cin >> n;
    map<int, int> dp1, dp2;
    rep(i, 1, n)
    {
        int x; cin >> x;
        dp2[x-1] = (dp2[x-1] * 2 + dp1[x-1] + (x == 1)) % mod;
        dp2[x+1] = (dp2[x+1] * 2) % mod;
        dp1[x+1] = (dp1[x+1] * 2 + dp1[x] + (x == 0)) % mod;
    }
    for (auto & [k, v] : dp1) ret = (ret + v) % mod;
    for (auto & [k, v] : dp2) ret = (ret + v) % mod;
    cout << ret << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

E. Crazy Robot

题意

给定矩阵图,上面有 $L$ 表示实验室, $#$ 表示障碍物,$.$ 表示空地。

有一个机器人可能在图上的任意一个空地上,你可以给它任意下达方向指令,它会选择一个与指令不同的方向且该方向不为障碍物,向这个方向走,否则不会移动。

问有多少可能的空地,使得机器人在该点时,无论机器人如何行动,总能选择指令使它到达实验室。

分析

从实验室出发,如果机器人只有一个方向有空地,则我们可以选择走这个空地的指令,那么机器人一定会向实验室走。

注意最后输出地图不要使用 $endl$ ,否则输出 $10^6$ 次会超时。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std; using PII = pair<int, int>;
const int N = 1000010;

const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
PII q[N];

void solve ()
{
    int n, m, x, y; cin >> n >> m;
    vector g(n, vector<char>(m));
    rep(i, 0, n-1) rep(j, 0, m-1)
    {
       cin >> g[i][j];
       if (g[i][j] == 'L') x = i, y = j;
    }
    int hh = 0, tt = -1;
    // 把周围点加进来
    for (int i = 0; i < 4; i ++ )
    {
        int dx = x + dr[i], dy = y + dc[i];
        if (dx < 0 || dx >= n || dy < 0 || dy >= m || g[dx][dy] == '#') continue;
        q[++ tt] = {dx, dy};
    }
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        int x = t.first, y = t.second, cnt_free = 0;
        for (int i = 0; i < 4; i ++ )
        {
            int dx = x + dr[i], dy = y + dc[i];
            if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
            if (g[dx][dy] == '.') cnt_free ++ ;
        }
        if (cnt_free > 1) continue;
        g[x][y] = '+';
        for (int i = 0; i < 4; i ++ )
        {
            int dx = x + dr[i], dy = y + dc[i];
            if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
            if (g[dx][dy] == '.') q[++ tt] = {dx, dy};
        }
    }
    rep(i, 0, n-1)
    {
        rep(j, 0, m-1) cout << g[i][j];
        cout << '\n';
    }
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; )
        solve();
    return 0;
}


活动打卡代码 AcWing 149. 荷马史诗

_Crush
4天前
// Trie + Haffman Tree
#include <iostream>
#include <queue>
#include <vector>
#define int long long

using namespace std;
using PLI = pair<long long, long long>; // 存储权值和深度

signed main ()
{
    priority_queue<PLI, vector<PLI>, greater<PLI> > q;
    long long n, k; cin >> n >> k;
    for (int i = 1, x; i <= n && cin >> x; i ++ ) q.push({x, 0});
    while(((int)q.size() - 1) % (k - 1)) q.push({0, 0}); // 满足k叉哈夫曼树性质
    long long ret = 0;
    // 构建haffman树
    while(q.size() >= k)
    {
        long long t = 0; // 新结点权值
        int dep = -1; // 新结点深度
        // 找出k小权值构造一个结点
        for (int i = 1; i <= k; i ++ )
        {
            PLI node = q.top(); q.pop();
            t += node.first;
            dep = max(dep, (int)node.second);
        }
        ret += t;
        q.push({t, dep + 1});
    }
    cout << ret << endl << q.top().second << endl;
    return 0;
}


活动打卡代码 AcWing 147. 数据备份

_Crush
4天前
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
using PLI = pair<long long, int>;

const int N = 100010;

int n, k;
long long d[N];
int l[N], r[N];

void del (int idx)
{
    // 把idx从链表中删除
    r[l[idx]] = r[idx];
    l[r[idx]] = l[idx];
}

int main ()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> d[i];
    for (int i = n; i >= 1; i -- ) d[i] -= d[i-1];
    for (int i = 1; i <= n; i ++ )
    {
        // 把相对位置插入到双链表中
        l[i] = i - 1;
        r[i] = i + 1;
    }
    d[1] = d[n + 1] = 1e18;
    set<PLI> S; // set找最小的贡献,这里的功能等价于二叉堆
    for (int i = 1; i <= n; i ++ ) S.insert({d[i], i});
    long long ret = 0;
    for (int i = 1; i <= k; i ++ )
    {
        PLI t = *S.begin();
        long long v = t.first;
        // cout << v << endl;
        int p = t.second, left = l[p], right = r[p];
        del(left); del(right);
        ret += v;
        S.erase(t); S.erase({d[left], left}); S.erase({d[right], right});
        d[p] = d[left] + d[right] - d[p];
        S.insert({d[p], p});
    }
    cout << ret << endl;
    return 0;
}



_Crush
6天前

Deltix Round, Automn 2021

A. Divide and Multiply

题意

给定 $n$ 个数字,每次可以选择其中两个数字(其中一个为偶数),把其中的一个偶数除以 $2$ ,另一个数字乘以 $2$ ,问若干次操作后,这 $n$ 个数字的最大和为多少。

分析

把所有的 $2$ 提取出来,再放到最大的数字上去。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define int long long
using namespace std;
const int N = 200010;

int a[N];

void solve ()
{
    int n; cin >> n;
    int ans = 0, cnt = 0;
    rep(i, 1, n)
    {
        cin >> a[i];
        while(a[i] % 2 == 0) ++ cnt, a[i] /= 2;
    }
    sort(a + 1, a + n + 1);
    cout << accumulate(a+1, a+n, 0ll) + (1ll<<cnt) * a[n] << endl;
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

B. William the Vigilant

题意

给定长度为 $n$ 的字符串,给定若干次操作($pos, c$),每次操作把字符串第 $pos$ 位替换为 $c$ (字符串从1开始计数),问每次操作后至少再需要几次替换可以使此字符串没有子串 “$abc$” 。

分析

计算出字符串 $abc$ 的次数,对于每一次替换,只能替换一次。

对于 $pos$ 位,由于它要被替换,那么如果它是 $abc$ 的一个,就要减去一次计数。

替换之后,检查是不是产生了一个 $abc$ ,如果产生则增加一次计数。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

int n, q;
string s;

bool check (int p)
{
    if (s[p] == 'a' && p + 2 < n && s.substr(p, 3) == "abc") return true;
    if (s[p] == 'b' && p - 1 >= 0 && p + 1 < n && s.substr(p-1, 3) == "abc") return true;
    if (s[p] == 'c' && p - 2 >= 0 && s.substr(p-2, 3) == "abc") return true;
    return false;
}

void solve ()
{
    int cnt = 0; cin >> n >> q;
    cin >> s;
    for (int i = 0; i < (int)s.size() - 2; i ++ )
        if (s.substr(i, 3) == "abc") ++ cnt;
    for (int i = 1; i <= q; i ++ )
    {
        int p; char chg; cin >> p >> chg;
        p -- ;
        if (check(p)) -- cnt;
        s[p] = chg;
        if (check(p)) ++ cnt;
        cout << cnt << endl;
    }
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    // int _; for (cin >> _; _--; )
        solve();
    return 0;
}

C. Complex Market Analysis

题意

给定长度为 $n$ 的序列 $a$ 和正数 $e$ 。问有多少序偶对 $(i, k)$ 满足:

$a_i, a_{i + e}, a_{i + 2 * e}, \ldots a_{i + k * e}$ 的乘积为质数。

分析

质数最多只能有一个因子(除了 $1$) ,所以序偶 $(i, k)$ 一定要满足只有一个质数,其他都是 $1$ 。

设 $f(i)$ 表示 $i$ 前面每隔 $e$ 位的 $1$ 的数量, $g(i)$ 表示 $i$ 后面每隔 $e$ 位的 $1$ 的数量。

那么就把间隔的问题变成了相邻的问题。

对于第 $i$ 位,如果它是质数,那么它前面的 $1$ ,每个都能取 $g(i) + 1$ 。(取到 $i$,$i + e$ ,$i + 2e$ $\ldots$ )

对于这一位本身也能取 $g(i)$ 种,所以方案一共 $f(i) \times (g(i) + 1) + g(i) = f(i) \times g(i) + f(i) + g(i)$ 种。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define int long long
using namespace std;
const int N = 200010, M = 1000020;

int prime[M], cnt;
bool st[M];

void get_prime(int n)
{
    st[1] = true;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cnt ++ ] = i;
        for (int j = 0; i * prime[j] <= n; j ++ )
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

int f[N], g[N], a[N];

void solve ()
{
    int n, e, ret = 0; cin >> n >> e;
    rep(i, 1, n) f[i] = g[i] = 0;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, e) f[i] = (a[i] == 1);
    rep(i, e + 1, n)
    {
        f[i] = (a[i] == 1);
        if (a[i-e] == 1) f[i] += f[i-e];
    }
    per(i, n, n - e + 1) g[i] = (a[i] == 1);
    per(i, n - e, 1)
    {
        g[i] = (a[i] == 1);
        if (a[i+e] == 1) g[i] += g[i+e];
    }
    rep(i, 1, n) if (!st[a[i]]) ret = ret + f[i] * g[i] + f[i] + g[i];
    cout << ret << endl;
}

signed main ()
{
    get_prime(1000010);
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--; ) solve();
    return 0;
}

D. Social Network

题意

对于一张有 $n$ 个点的图,有 $d$ 个条件 $(i, j)$ ,表示 $i$ 和 $j$ 需要在一个连通块。

在第 $i$ 个条件时,你可以连 $i$ 条边,但是要满足前面 $i$ 个条件成立。

满足第 $i$ 个条件后,问最大的可能的连通块大小。(题目是某个人认识的最大人数,要连通块大小 $-1$) 。

每个问题都是独立的,上一个答案需要连的边和这一个答案无关。

分析

并查集,假设前 $i$ 个条件,有 $k$ 个条件是已经满足的,那么可以自由连 $k$ 条边,那就可以选择连通块大小最大的 $k$ 个,把他们连起来。最开始只能选择一个连通块。

Code

/* 终点是一切概率的结束,也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std;
const int N = 200010;

int p[N], siz[N];

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

void solve ()
{
    int n, d, base = 1; cin >> n >> d;
    rep(i, 1, n) p[i] = i, siz[i] = 1;
    rep(i, 1, d)
    {
        int x, y, ret = 0; cin >> x >> y;
        x = f(x); y = f(y);
        if (x == y) base ++ ;
        else siz[y] += siz[x], p[x] = y;

        priority_queue<int> q;
        rep(j, 1, n) if (j == f(j)) q.push(siz[j]);
        rep(j, 1, base) ret += q.top(), q.pop();
        cout << ret - 1 << endl;
    }
}

signed main ()
{
    cout.tie(0)->sync_with_stdio(0);
    // int _; for (cin >> _; _--; )
        solve();
    return 0;
}


活动打卡代码 AcWing 4081. 选数

_Crush
8天前
#include <iostream>
#include <cstring>
using namespace std;
// #define int long long
const int N = 210;

int f[N][30 * N + 10]; // f(i, j, k) 表示前i个数字选j个数字,且5的数量为k时2的数量,压缩第一维

signed main ()
{
    int n, k; cin >> n >> k;
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        long long x; cin >> x;
        int c2 = 0, c5 = 0;
        while(x % 2 == 0) { ++ c2; x /= 2; }
        while(x % 5 == 0) { ++ c5; x /= 5; }
        // 体积为c5,价值为c2
        for (int j = k; j >= 1; j -- ) // 选j个数字
            for (int r = j * 26; r >= c5; r -- )
                f[j][r] = max(f[j][r], f[j-1][r - c5] + c2);
    }
    int ans = 0;
    for (int i = 0; i <= 25 * N; i ++ ) ans = max(ans, min(i, f[k][i]));
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 4080. 第k个数

_Crush
8天前

如果某个数字为第 $k$ 小数,就意味着有至少 $k$ 个数字小于等于它。

#include <iostream>
using namespace std;

typedef long long ll;

ll n, m, k;

bool check (ll x)
{
    ll res = 0;
    for (int i = 1; i <= n; i ++ )
        res += min(m, x / i);
    return res >= k;
}

int main ()
{
    cin >> n >> m >> k;
    ll l = 1, r = n * m;
    while(l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}


活动打卡代码 AcWing 4079. 数字串

_Crush
8天前
#include <iostream>
#include <string>
using namespace std;

int main ()
{
    int T; cin >> T; while( T -- )
    {
        int n, cur = 0; cin >> n;
        string t = to_string(cur);
        while(n -- )
        {
            t = t.substr(1);
            if (t == "") ++ cur, t = to_string(cur);
        }
        cout << t[0] << endl;
    }
    return 0;
}