首页 > 其他分享 >AtCoder Regular Contest 177

AtCoder Regular Contest 177

时间：2024-05-14 22:54:48浏览次数：24  
标签：AtCoder 电线杆 int 单元格 yy xx Regular 177 now

AtCoder Regular Contest 177

A-Exchange

问题陈述

判断 \(n\) 个价格分别为 \(x_i\) 的商品，问能否通过有限数量的 \(1\) 元， \(5\) 元， \(10\) 元， \(50\) 元， \(100\) 元， \(500\) 元，购买。

思路

贪心。

每个商品从 \(500\) 元开始，能用就尽量用。如果中间某个商品无法被满足，则无解，反之有解。

证明就凭感觉想一下。如果前面用大面值，就可以留下小面值的给后面填空子。

代码

太丑了懒得放了。

B - Puzzle of Lamps

问题陈述

AtCoder 先生创建了一个由 \(N\) 个小灯泡(从左到右排列成一排)和两个开关 A 和 B 组成的装置：0"(关)和 "1"(开)。按下每个开关会产生以下结果：

  • 按下开关 A 会将最左边处于 "0 "状态的灯泡变成 "1"。
  • 按下开关 B 会将处于 "1 "状态的最左边灯泡变为 "0"。

如果没有适用的灯泡，则无法按下开关。

最初，所有灯泡都处于 "0 "状态。他希望灯泡的状态从左到右为 \(S_1, S_2, \dots, S_N\) 。请确定按下开关的顺序和次数。按动次数不一定要最少，但最多应为 \(10^6\) ，以便在实际时间内完成操作。可以证明，在该问题的约束条件下存在一个解。

思路

先考虑 0010 如何解决。

注意到一组可行解是 AAABB。

看到这里可能有点感觉了，先用A把每个 \(1\) 前面都填满 \(1\)，在用B把前面多余的 \(1\) 退掉。

再考虑 0101 如何解决。

注意到一组可行解为 AAABBBAAB。

发现可以先解决右边，再解决左边，这样可以把每个 \(1\) 拆开做，会方便更多。

最后考虑 00111000011 如何解决。

注意到一组可行解为 AAAAAAAAAAABBBBBBBBBAAAAABB。

一段 \(1\)，可以先用A把 \(1\) 延申到右端点，再用B把左端点前的 \(1\) 退掉。

从右到左解决每个区间。

这样构造出的解长度是 \(n^2\) 级别的，不会超限。

代码

#include <bits/stdc++.h>
using namespace std;
int n, cnt;
char s[35];
struct seg {int l, r;} sg[35];
vector <char> ans;
int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1, l, r; i <= n; i ++) {
        if (s[i] == '1' && s[i - 1] != '1') l = i;
        if (s[i] == '1' && s[i + 1] != '1') r = i, sg[++ cnt] = {l, r};  
    }
    for (int i = cnt; i >= 1; i --) {
        for (int j = 1; j <= sg[i].r; j ++) ans.emplace_back('A');
        for (int j = 1; j < sg[i].l; j ++) ans.emplace_back('B');
    }
    printf("%d\n", ans.size());
    for (auto c : ans) putchar(c);
    return 0;
}

C - Routing

问题陈述

有一个网格，网格中有 \(N\) 行和 \(N\) 列。设 \((i, j)\) \((1 \leq i \leq N, 1 \leq j \leq N)\) 表示位于从上往下第 \(i\) 行和从左往上第 \(j\) 列的单元格。每个单元格最初被涂成红色或蓝色，如果 \(c_{i,j}=\) R单元格 \((i, j)\) 被涂成红色，如果 \(c_{i,j}=\) B单元格 \((i, j)\) 被涂成蓝色。您想将某些单元格的颜色改为紫色，以便同时满足以下两个条件：

条件 1：从单元格 \((1, 1)\) 移动到单元格 \((N, N)\) 时，只能经过红色或紫色的单元格。
条件 2：您只能通过蓝色或紫色单元格，才能从单元格 \((1, N)\) 移动到单元格 \((N, 1)\) 。

这里的 "您可以移动"是指您可以通过重复移动到水平或垂直相邻的相关颜色的单元格，从起点到达终点。

要满足这些条件，最少有多少个单元格必须变为紫色？

思路

广搜或最短路板子。

搜一遍或跑一遍，求出 \((1,1)\) 到 \((N,N)\) 最少经过多少蓝色，\((1,N)\) 到 \((N,1)\) 最少经过多少红色，相加即答案。这里给出最短路代码。

代码

#include <bits/stdc++.h>
using namespace std;
char s[505][505];
int n, b[505][505], r[505][505];
bool vis[505][505];
int xz[] = {1, 0, -1, 0};
int yz[] = {0, 1, 0, -1};
struct node {int x, y, d;};
bool operator < (node a, node b) {
    return a.d > b.d;
}
priority_queue <node> q;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%s", s[i] + 1);
    memset(b, 0x3f, sizeof(b));
    memset(r, 0x3f, sizeof(r));
    b[1][1] = (s[1][1] == 'B');
    q.push({1, 1, b[1][1]});
    while (!q.empty()) {
        node now = q.top(); q.pop();
        if (vis[now.x][now.y]) continue;
        vis[now.x][now.y] = 1;
        if (now.x == n && now.y == n) continue;
        for (int i = 0; i < 4; i ++) {
            int xx = now.x + xz[i], yy = now.y + yz[i];
            if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
            if (b[xx][yy] > now.d + (s[xx][yy] == 'B')) {
                b[xx][yy] = now.d + (s[xx][yy] == 'B');
                q.push({xx, yy, b[xx][yy]}); 
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    r[n][1] = (s[n][1] == 'R');
    q.push({n, 1, r[n][1]});
    while (!q.empty()) {
        node now = q.top(); q.pop();
        if (vis[now.x][now.y]) continue;
        vis[now.x][now.y] = 1;
        if (now.x == 1 && now.y == n) continue;
        for (int i = 0; i < 4; i ++) {
            int xx = now.x + xz[i], yy = now.y + yz[i];
            if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
            if (r[xx][yy] > now.d + (s[xx][yy] == 'R')) {
                r[xx][yy] = now.d + (s[xx][yy] == 'R');
                q.push({xx, yy, r[xx][yy]}); 
            }
        }
    }
    printf("%d\n", b[n][n] + r[1][n]);
    return 0;
}

D - Earthquakes

问题陈述

AtCoder 街是一条在平地上用直线表示的道路。路上竖立着 \(N\) 根电线杆，高度为 \(H\) 。电线杆按时间顺序编号为 \(1, 2, \dots, N\) 。电线杆 \(i\) ( \(1 \leq i \leq N\) )垂直于坐标 \(X_i\) 。每根电线杆的底座都固定在地面上。

街道将经历 \(N\) 次地震。在 \(i\) /-次地震 \((1 \leq i \leq N)\) 中，会发生以下事件：

  1. 如果电线杆 \(i\) 尚未倒下，它会倒向数字线的左边或右边，每个概率为 \(\frac{1}{2}\) 。
    1. 如果一根倒下的电线杆与另一根尚未倒下的电线杆相撞(包括在电线杆底部相撞)，后一根电线杆也会朝同一方向倒下。这可能会引发连锁反应。

在步骤 1 中，一根电线杆倒下的方向与其他电线杆倒下的方向无关。

下图是在一次地震中电线杆可能倒下的示例：

为了防备地震，对于每一次 \(t = 1, 2, \dots, N\) ，求出在 \(t\) /-次地震中所有极点都倒下的概率。将其乘以 \(2^N\) ，并打印出结果的模数 \(998244353\) 。可以证明要打印的值是整数。

思路

1.分析

我们发现，所有的电线杆可以被划分为若干段。

定义一段为左端点的电线杆向右倒或右端点的电线杆向左倒均能让整段电线杆全部倒完的极长子区间。

不同段之间不会有任何影响。因此，我们可以将原问题拆分为子问题：

有一段位置升序的电线杆，每个电线杆在第 \(p_i\) 次地震中倒塌，求最后倒塌的电线杆是第 \(i\) 的概率。

2.解决子问题

2.1分析子问题

我们发现任何时刻，一段区间均可被分成三部分：

向左倒塌的一部分，站立的一部分，向右倒塌的一部分。

第 \(i\) 个电线杆未倒塌，当且仅当所有 \(j < i,p_j<p_i\) 的 \(j\) 都向左倒塌，所有 \(j>i,p_j<p_i\) 的 \(j\) 都向右倒塌。

第 \(i\) 个电线杆是最后倒塌的，当且仅当 \(i\) 未倒塌且 \(i\) 是站立的一段的起点或终点。

2.2分析概率

我们发现，第 \(i\) 个电线杆是最后倒塌的概率为 \(1/2^a\times b/2\)。

其中 \(a\) 为 \(j < i,p_j<p_i\) 或 \(j>i,p_j<p_i\) 的 \(j\) 的个数。

这些 \(j\) 代表了在 \(i\) 之前倒塌的电线杆。因为必须保持 \(i\) 站立，所以左边必须往左倒，右边必须往右倒，概率为 \(1/2^a\)。

若 \(i\) 为站立区间的左端点或右端点，\(b=1\)。

若 \(i\) 是单独的一个（即既是左端点又是右端点），\(b=2\)。

若 \(i\) 是左右端点中的一个，则 \(i\) 倒下的方向有要求，概率为 \(1/2\)。

若 \(i\) 同时是左右端点（单独），则 \(i\) 倒下的方向没有要求，概率为 \(1\)。

2.3求解概率

我们发现，概率中 \(a\) 的求解过程为单调栈的板子，\(b\) 的解决平凡。

至此，子问题已经解决，时间复杂度 \(O(l)\)，\(l\) 为段的长度。

3.合并子问题

设一共有 \(c\) 段，电线杆 \(i\) 所在的段的编号为 \(g_i\)。

时间 \(t\) 的答案为 \(s_1\times s_2\times \ldots \times s_{g_t-1}\times x \times s_{g_t+1} \times \ldots \times s_c\)。

其中 \(x\) 为子问题 \(g_t\) 中最后倒下的电线杆是 \(t\) 的概率，

\(s_i\) 为子问题 \(i\) 中最后倒下的电线杆编号小于 \(t\) 的概率之和。

直接朴素计算是 \(O(n^2)\) 。

我们发现这是一个单点修改，区间查询问题，考虑使用线段树优化。

线段树中维护 \(s\)，每次将答案算出后，将 \(x\) 加到 \(s_{g_t}\) 中。

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

实现细节

实现时题目要求要将答案乘上 \(2^N\)，但我们解决子问题时不能乘 \(2^N\)，而要乘 \(2^l\)，这样所有子问题乘起来才是 \(2^N\)。

代码

#include <bits/stdc++.h>
#define int long long
const int mod = 998244353;
const int N = 2e5 + 5;
using namespace std;
struct segt {
    struct node {int l, r, v;} t[N << 2];
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r, t[p].v = 0;
        if (l == r) return ;
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r); 
    }
    void add(int p, int id, int v) {
        if (t[p].l == t[p].r) {
            t[p].v += v, t[p].v %= mod;
            return ;
        }
        if (id <= t[ls].r) add(ls, id, v);
        else add(rs, id, v);
        t[p].v = t[ls].v * t[rs].v, t[p].v %= mod;
    }
    int query(int p, int l, int r) {
        if (l <= t[p].l && t[p].r <= r) return t[p].v;
        int res = 1;
        if (t[ls].r >= l) res *= query(ls, l, r), res %= mod;
        if (t[rs].l <= r) res *= query(rs, l, r), res %= mod;
        return res;
    }
} T; // 线段树板子
struct Point {int x, y;};
bool cmp(Point a, Point b) {return a.x < b.x;}
int n, h, c, x[N], g[N], t[N], k[N], pow2[N];
Point a[N];
vector <int> p[N];
vector <int> res[N];
void solve(int id) { // 解决子问题
    int m = p[id].size() - 1;
    stack <int> stk; 
    for (int i = 1; i <= m; i ++) {
        while (!stk.empty() && // 单调栈板子
        p[id][i] < stk.top()) stk.pop();
        stk.push(p[id][i]);
        k[i] = stk.size() - 1;
    }
    stack <int> sstk;
    for (int i = m; i >= 1; i --) {
        while (!sstk.empty() && // 单调栈板子
        p[id][i] < sstk.top()) sstk.pop();
        sstk.push(p[id][i]);
        k[i] += sstk.size() - 1;
    }
    res[id].emplace_back(0);
    for (int i = 1; i <= m; i ++) { // 计算概率
        int b = (i == 1 || p[id][i - 1] < p[id][i]) 
                + (i == m || p[id][i] > p[id][i + 1]);
        res[id].emplace_back(b * pow2[m - k[i] - 1] % mod); // 乘2^l
    }
}
signed main() {
    cin >> n >> h, pow2[0] = 1;
    for (int i = 1; i <= n; i ++) {
        cin >> x[i];
        a[i].x = x[i], a[i].y = i;
        pow2[i] = (pow2[i - 1] << 1) % mod;
    }
    for (int i = 1; i <= n; i ++) 
        p[i].emplace_back(0);
    sort(a + 1, a + n + 1, cmp);
    g[a[1].y] = ++ c, 
    p[c].emplace_back(a[1].y), 
    t[a[1].y] = p[c].size() - 1;
    for (int i = 2; i <= n; i ++) { // 分段
        if (a[i].x - a[i - 1].x <= h) 
            g[a[i].y] = c, 
            p[c].emplace_back(a[i].y), 
            t[a[i].y] = p[c].size() - 1;
        else g[a[i].y] = ++ c, 
            p[c].emplace_back(a[i].y), 
            t[a[i].y] = p[c].size() - 1; 
    }
    for (int i = 1; i <= c; i ++) solve(i); // 解决子问题
    T.build(1, 1, c);
    for (int i = 1; i <= n; i ++) { // 合并答案
        int x = res[g[i]][t[i]], ans = 1;
        if (g[i] - 1) 
            ans *= T.query(1, 1, g[i] - 1);
        if (g[i] + 1 <= c) 
            ans *= T.query(1, g[i] + 1, c), ans %= mod;
        ans *= x, ans %= mod;
        T.add(1, g[i], x);
        cout << ans << ' ';
    }
    return 0;
}

标签：AtCoder,电线杆,int,单元格,yy,xx,Regular,177,now
From： https://www.cnblogs.com/maniubi/p/18192439

相关文章

  • AtCoder Beginner Contest 351 E - Jump Distance Sum
    题目链接Hint1:只能斜着走，容易想到黑白棋盘，\((x+y)\%2==0\)位于一个团，\((x+y)\%2==1\)位于另一个团，分别求和。Hint2:\(dist=max(|x1-x2|,|y1-y2|)\)，这是切比雪夫距离，将坐标系倾斜\(45^{\circ}\)，改为曼哈顿距离\(dist=|x1-x2|+|y1-y2|\)，即\(X=x+y,Y=x-y\)，这样就可以将横纵坐标......
  • AtCoder Beginner Contest 352 E - Clique Connect
    题目链接不需要将所有边都建立出来，根据\(Kruskal\)最小生成树的贪心策略,相同权值的边不需要形成团，形成一个链就行，对结果没有影响。时间复杂度\(O(mlogm)[m=\sum_{i=1}^{n}k_{i}]\)。#pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#include<bits/stdc++.h>//#defineint......
  • AtCoder Beginner Contest 353
    AtCoderBeginnerContest353abc353_c题意：定义\(F(x,y)\)为\((x+y)mod10^8\)的值,求\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^Nf(A_i,A_j).\)思路：对于\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N\f(A_i,A_j).\)来说，每个\(A_i\)的次数都是\(n-1\)次，所以如果没有\(m......
  • Atcoder ABC 353 全题解
    最近看的人好少……都快不想写了……你们的支持就是我创作的最大动力！AB%你CDE题意：有一个一个一个函数，把函数两两配对式求值，求这些值最后的总和C考虑将所有的和减去$10^8$出现的次数。将整个数组排序，然后进行二分，求第一个与这个数的和$\ge10^8$的位置，然后与这个数......
  • Atcoder Beginner Contest 353
    AtcoderBeginnerContest353A问题陈述有\(N\)幢楼房排列成一排。左起的\(i\)th楼高\(H_i\)。请判断是否有比左起第一座高的建筑物。如果存在这样的建筑物，请找出从左边起最左边的建筑物的位置。思路签到题。代码#include<bits/stdc++.h>usingnamespacestd;int......
  • AtCoder Beginner Contest 353
    AtCoderBeginnerContest353A-Buildings求第一个\(h_i\)大于\(h_1\)的位置。模拟。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,h[103];signedmain(){ cin>>n;cin>>h[1]; for(inti=2;i<=n;i++){ cin&......
  • AtCoder Beginner Contest 353
    A-Buildings(abc353A)题目大意给定\(n\)个数字，输出第一个大于第一个数的下标。解题思路依次与第一个数比较，大于则输出。神奇的代码n=input()a=list(map(int,input().split()))b=[i>a[0]foriina]ifTruenotinb:print(-1)else:print(b.ind......
  • 洛谷题单指南-动态规划3-P1775 石子合并（弱化版）
    原题链接：https://www.luogu.com.cn/problem/P1775题意解读：计算合并石子的最小代价，区间DP。解题思路:状态表示：dp[i][j]表示将第i~j堆石子合并的最小代价，m[i]表示第i堆石子质量，s[i]表示前i堆石子质量前缀和状态转移：考虑最后一次合并，设最后一次合并是将i~k合成的一堆与k+1~j合成......
  • CF1773E Easy Assembly
    链接：https://codeforces.com/problemset/problem/1773/E思路首先先得出最终序列，因为它具有唯一性，然后再根据其中的前后关系来判断原来的数列需要切几刀。然后再根据切几刀形成的最终数列判断需要合并几次。例如：目标数列是ABCDEF，而给出的某两段序列是ADBC,EF，那么必要的解法一定......
  • AtCoder Beginner Contest 318 Ex Count Strong Test Cases
    洛谷传送门AtCoder传送门首先做一些初步的观察：A和B的解法是对称的，所以A对的方案数等于B对的方案数。同时若A和B同时对则每个置换环环长为\(1\)，方案数为\(n!\)。所以，若设A对的方案数为\(x\)，那么答案为\(n!^2-(x-n!)-(x-n!)-n!=n!^2+n!-x\)。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99