AtCoder Beginner Contest 341

  • 开发
  • 31

A - Print 341 (atcoder.jp)

        1.思路：模拟输出即可。

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
void solve()
{
    int n;
    cin >> n;
    for (int i = 0;i < n;i ++) {
        cout << "10";
    }
    cout << 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

B - Foreign Exchange (atcoder.jp)

        1.思路：每一次把当前尽可能多的票换成后面的票。

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0;i < n;i ++) {
        cin >> a[i];
    }
    for (int i = 0;i < n - 1;i ++) {
        int s,t;
        cin >> s >> t;
        a[i + 1] += (a[i] / s) * t;
    }
    cout << a[n - 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

C - Takahashi Gets Lost (atcoder.jp)

        1.思路：对于每一个不为#的格子，作为起始点进行bfs即可。

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
pair<int,int> road[N];
void solve()
{
    int n,m,k;
    cin >> n >> m >> k;
    string r;
    cin >> r;
    vector<string> s(n);
    for (int i = 0;i < k;i ++) {
        switch (r[i]) {
            case 'R': road[i] = {0,1};break;
            case 'L': road[i] = {0,-1};break;
            case 'U': road[i] = {-1,0};break;
            case 'D': road[i] = {1,0};break;
        }
    }
    for (int i = 0;i < n;i ++) {
        cin >> s[i];
    }
    auto bfs = [&](int x,int y) {
        pair<int,int> ans(-1,-1);
        for (int i = 0;i < k;i ++) {
            int dx = x + road[i].first,dy = y + road[i].second;
            if (dx < 0 || dx >= n || dy < 0 || dy >= m) return ans;
            if (s[dx][dy] == '#') return ans;
            x = dx,y = dy;
        }
        return make_pair(x,y);
    };
    set<pair<int,int>> st;
    for (int i = 0;i < n;i ++) {
        for (int j = 0;j < m;j ++) {
            if (s[i][j] != '#') {
                auto [dx,dy] = bfs(i,j);
                if (dx != -1) {
                    st.insert({dx,dy});
                }
            }
        }
    }
    cout << sz(st);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

D - Only one of two (atcoder.jp)

        1.思路：这题考察的是容斥原理，考虑1-n有多少个a的倍数，显然就是(n / a),那有多少个b的倍数呢？显然就是(n / b)，那有多少个既是a的倍数也是b的倍数呢，那应该是n/(lcm(a,b)),为什么是n/(lcm(a,b))?考虑4和6，他们的最小公倍数是24？显然不是，应该是12。所以我们可以直接二分答案这个n，然后check用容斥原理计算即可。

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
void solve()
{
    ll l = 1,r = 4e18;
    ll n,m,k;
    cin >> n >> m >> k;
    auto calc = [&](ll p) {
        ll z = n * m / __gcd(n,m);
        return (p / n + p / m - (2ll * (p / z))) >= k;
    };
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (calc(mid)) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

E - Alternating String (atcoder.jp)

        1.思路：考虑直接做的话不太好做容易时间超限，我们考虑维护一个数据结构。

                      我们采用线段树做这种题目（ps:无脑），维护出区间是否有连续相同的。

                      Q1：怎么做merge呢？看下面的图，考虑连续相同的个数=左端连续相同的个数+右端连续相同的个数+(R1==L2)，因此我们需要维护每一段最左段是啥，最右端是啥，以及个数即可。

                      Q2：怎么做修改呢？我们考虑翻转一段区间，其整段区间的连续相同个数一定是不变的，唯一改变的就是这个区间的最左端标记和最右端标记改一下即可。

                                

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
struct SegTree {
    int l,r;
    int cn,lz;
    int lv,rv;
    SegTree() {}
    SegTree(int _l,int _r) {
        cn = lz = 0;
        lv = rv = -1;
        l = _l,r = _r;
    }
}tr[N << 2];
string s;
SegTree operator+(const SegTree& lhs,const SegTree& rhs) 
{
    SegTree t(lhs.l,rhs.r);
    t.cn = lhs.cn + rhs.cn;
    t.lv = lhs.lv,t.rv = rhs.rv;
    if (lhs.rv != -1 && lhs.rv == rhs.lv) {
        t.cn += 1;
    }
    return t;
}
void push_tag(int u)
{
    tr[u].lz ^= 1;
    tr[u].lv ^= 1;
    tr[u].rv ^= 1;
}
void push_dw(int u)
{
    if (tr[u].lz) {
        push_tag(u << 1);
        push_tag(u << 1 | 1);
        tr[u].lz = 0;
    }
}
void build(int u,int l,int r)
{
    tr[u] = SegTree(l,r);
    if (l == r) {
        tr[u].lv = tr[u].rv = s[l] - '0';
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
void modify(int u,int l,int r)
{
    if (tr[u].l >= l && tr[u].r <= r) {
        push_tag(u);
        return;
    }
    push_dw(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) {
        modify(u << 1,l,r);
    }
    if (r >  mid) {
        modify(u << 1 | 1,l,r);
    }
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
SegTree query(int u,int l,int r)
{   
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u];
    }
    push_dw(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    SegTree res(l,r);
    if (l <= mid) {
        res = query(u << 1,l,r);
    }
    if (r >  mid) {
        if (res.lv != -1) {
            res = res + query(u << 1 | 1,l,r);
        }
        else {
            res = query(u << 1 | 1,l,r);
        }
    }
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
    return res;
}

void solve()
{
    int n,m;
    cin >> n >> m;
    cin >> s;
    s = " " + s;
    build(1,1,n);
    while (m --) {
        int op,l,r;
        cin >> op >> l >> r;
        if (op == 1) {
            modify(1,l,r);
        }
        else {
            auto p = query(1,l,r);
            cout << (p.cn ? "No" : "Yes") << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

F - Breakdown (atcoder.jp)

        1.思路：如果你观察到这个w的数据范围并且你直到01背包的话，这个题你应该能做出来了。

题目说，每次可以把第i个节点分给他的邻接点子集不大于它的一些点放一个棋子，那么我们发现其实题目中的无向图，一定会转换成有向图，且一定是大的在根节点。我们考虑每一条边用大的指向小的。然后dfs把每一棵子树的贡献算出来即可。

                       对于每一颗子树，我们定义状态转移方程dp[i],表示i容量最多能分配给多少个子节点（子节点是带权重的，其权重就是他的dp值），所以说就转换成了树上做01背包，（ps：这个不叫树上背包，分析的过程不太一样的）。

        2.代码：

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5005;
const int inf = 1e9;
void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> w(n),a(n),f(n);
    vector<vector<int>> g(n);
    vector<bool> vis(n);
    vector<pair<int,int>> p(m);
    for (int i = 0;i < m;i ++) {
        cin >> p[i].fi >> p[i].se;
        p[i].fi --,p[i].se --;
    }
    for (int i = 0;i < n;i ++) {
        cin >> w[i];
    }
    for (int i = 0;i < n;i ++) {
        cin >> a[i];
    }
    for (int i = 0;i < m;i ++) {
        if (w[p[i].fi] > w[p[i].se]) {
            g[p[i].fi].pb(p[i].se);
        }
        if (w[p[i].se] > w[p[i].fi]) {
            g[p[i].se].pb(p[i].fi);
        }
    }
    ll ans = 0;
    auto dfs = [&](auto &&self,int x) -> int{
        vector<ll> dp(w[x],-inf);
        dp[0] = 0;
        vis[x] = true;
        for (auto &y: g[x]) {
            if (!vis[y]) {
                f[y] = self(self,y);
            }
            int v = f[y];
            for (int j = w[x] - 1;j >= w[y];j --) {
                if (dp[j - w[y]] != -inf) {
                    dp[j] = max(dp[j],dp[j - w[y]] + v);
                }
            }
        }
        int mx = *max_element(dp.begin(),dp.end());
        ans += 1ll * a[x] * (mx + 1);
        return f[x] = mx + 1;
    };
    for (int i = 0;i < n;i ++) {
        if (!vis[i]) {
            dfs(dfs,i);
        }
    }
    cout << ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

G - Highest Ratio (atcoder.jp)

        1.思路：这是一个比较典的题目，如果你学过斜率优化dp的话。我们首先看看i的贡献是啥把。

                定义s为前缀和数组。

                        i的答案一定是(s[r] - s[i - 1]) / (r - i + 1)。我们发现这玩意酷似求斜率？让我们来回顾一下斜率的计算k = (y2 - y1) / (x2 - x1)，那也就是说其实我们每一个点可以看成是(i,s[i])，最后问题转换成第i个点和后面哪个点的斜率最大。

                现在我们清楚了，答案=后面那个和自己构成直线斜率最大的点。

                我们考虑维护一个凸包，不用管这玩意的名字，实际上在这里的作用就是一个点集，和前面i点构造斜率的单调性，这里显然需要单调递减的（反过来），这里我们从后往前扫用栈维护即可。

                我们考虑现在栈中有两个节点，你该用哪个？

                我们假设有A(x1,y1),B(x2,y2),I(i,s[i]);

                i<x1<x2;

                

                1.若i->A的斜率要比A->B的斜率来的小，则i的答案一定就不是A，而是B或者后面的点。

                

                2.若i->A的斜率要比A->B的斜率来的大，则i的答案一定不会是B以后的了，因为斜率下降了。

        所以我们可以总结出弹出当前堆顶的条件是第一个情况，后面的式子就非常简单了，你们手动推一下即可。

        2.代码：

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using i128 = __int128;
const int N = 2e5 + 5;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	vector<ll> s(n + 1);
	vector<int> stk;
	vector<double> ans(n);
	for (int i = 1;i <= n;i ++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}	
	auto check = [&](int x,int y,int i) {
		return ((i128)(s[x] - s[y]) * (y - i) >= (i128)(s[y] - s[i]) * (x - y));
	};
	stk.push_back(n);
	for (int i = n - 1;i >= 0;i --) {
		while (stk.size() > 1 && check(stk[stk.size() - 2],stk[stk.size() - 1],i)) {
			stk.pop_back();
		}
		ans[i] = (s[stk.back()] - s[i] + 0.0) / (stk.back() - i);
		stk.push_back(i);
	}
	cout << fixed << setprecision(8);
	for (int i = 0;i < n;i ++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

阅读全部

相关推荐

  3. ABC341A-D题解

    2024-02-19 14:02:01       30 阅读

  4. abc-347

    2024-02-19 14:02:01       15 阅读

  8. AtCoder Beginner Contest 331

    2024-02-19 14:02:01       40 阅读

  9. Leetcode 344. Reverse String

    2024-02-19 14:02:01       38 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-02-19 14:02:01       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-02-19 14:02:01       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-02-19 14:02:01       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-02-19 14:02:01       18 阅读

热门阅读

  5. 服务器钓鱼攻击常用手法简介与防护建议

    2024-02-19 14:02:01       26 阅读

  8. SpringCloud：日志traceId错乱

    2024-02-19 14:02:01       26 阅读

  9. Redis为什么被设计为单线程

    2024-02-19 14:02:01       29 阅读

  12. python_数据分析_numpy库

    2024-02-19 14:02:01       28 阅读

  15. redis键的过期删除策略

    2024-02-19 14:02:01       27 阅读

  22. 第1章 计算机系统概述(2)

    2024-02-19 14:02:01       29 阅读

  23. Python re.findall()中的正则表达式包含多个括号时的返回值——包含元组的列表

    2024-02-19 14:02:01       22 阅读

  24. 突破编程_C++_面试（变量与常量）

    2024-02-19 14:02:01       27 阅读

  30. httpclient发送post请求、httpclient上传文件

    2024-02-19 14:02:01       23 阅读