AtCoder Beginner Contest 340(A-G)

A - Arithmetic Progression (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 a,b,c;
    cin >> a >> b >> c;
    while (a <= b) {
        cout << a << ' ';
        a += c;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

B - Append (atcoder.jp)

        1.思路:vector模拟即可。

        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()
{
    vector<int> v;
    int q;
    cin >> q;
    while (q --) {
        int op,x;
        cin >> op >> x;
        if (op == 1) {
            v.pb(x);
        }
        else {
            cout << v[v.size() - x] << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

C - Divide and Divide (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;
map<ll,ll> mem;
ll dfs(ll x)
{
    if (x == 1) {
        return 1ll;
    }
    if (mem.count(x)) {
        return mem[x];
    }
    return mem[x] = (dfs(x / 2) + dfs((x + 1) / 2)) + x;
}
void solve()
{
    ll n;
    cin >> n;
    cout << dfs(n / 2) + dfs((n + 1) / 2) << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

D - Super Takahashi Bros. (atcoder.jp)

        1.思路:发现每行给出的实际上可以等价于两条边

                        一条是i-->i + 1 花费a

                        一条是i-->c 花费b

        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;
//从0开始
template<typename T>
class Graph {
    using pli = pair<T,int>;
private:
    const int n;
    vector<vector<pair<int,int>>> g;
public:
    Graph(int _n): n(_n) {
        g.resize(n);
    }

    void addEdge(int x,int y,int z = 0) {
        g[x].push_back({y,z});
    }

    vector<T> shortestPath(int s) {
        vector<T> dis(n);
        memset(dis.data(),0x3f,dis.size() * sizeof(T));
        priority_queue<pli,vector<pli>,greater<pli>> q;
        q.push({0,s});
        dis[s] = 0;
        while(!q.empty()) {
            auto [val,ver] = q.top();
            q.pop();
            if(val != dis[ver]) {
                continue;
            }
            for(auto &[y,w]: g[ver]) {
                if(dis[y] > val + w) {
                    dis[y] = val + w;
                    q.push({dis[y],y});
                }
            }
        }
        return dis;
    }
};
void solve()
{
    int n;
    cin >> n;
    Graph<ll> g(n);
    for (int i = 1;i < n;i ++) {
        int a,b,c;
        cin >> a >> b >> c;
        g.addEdge(i - 1,i,a);
        g.addEdge(i - 1,c - 1,b);        
    }
    auto p = g.shortestPath(0);
    cout << p[n - 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

E - Mancala 2 (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;
template <typename T>
struct Fenwick {
    const int n;
    std::vector<T> a;

    Fenwick (int n) : n(n), a(n + 1) {}

    void add(int pos, T x) {
        for (int i = pos; i <= n; i += i & -i) {
            a[i] += x;
        }
    }

    T query(int x) {
        T res = 0;
        for (int i = x; i; i -= i & -i) {
            res += a[i];
        }
        return res;
    }

    T query(int l, int r) {
        if (l == 0 || l > r) {
            return 0;
        }
        return query(r) - query(l - 1);
    }

    //找到大于k得第一个地方
    T kth(int k) {
        int pos = 0;
        for(int j = 31 - __builtin_clz(n);j >= 0;j --) {
            if(pos + (1 << j) <= n && k > a[pos + (1 << j)]) {
                pos += 1 << j;
                k -= a[pos];
            }
        }
        return pos + 1;
    }
};
void solve()
{
    int n,q;
    cin >> n >> q;
    Fenwick<ll> fen(n);
    int pre = 0,x;
    for (int i = 1;i <= n;i ++) {
        cin >> x;
        fen.add(i,x - pre);
        pre = x;
    }
    for (int i = 1;i <= q;i ++) {
        cin >> x;
        x ++;
        ll rs = fen.query(x);
        ll mi = min(rs,0ll + n - x);
        fen.add(x,-rs);
        fen.add(x + 1,rs);
        if (mi) {
            rs -= mi;
            fen.add(x + 1,1);
            fen.add(x + 1 + mi,-1);
        }
        if (rs) {
            ll cz = rs / n,cm = rs % n;
            fen.add(1,cz);
            fen.add(1,1);
            fen.add(1 + cm,-1);
        }
    }
    for (int i = 1;i <= n;i ++) {
        cout << fen.query(i) << ' ';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

F - S = 1 (atcoder.jp)

        1.思路:考虑使用鞋带公式化简,我们可以得到,这么个方程|ay - bx| = 2,考虑把绝对值拆开,做两次exgcd求解即可。

        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;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
void solve()
{
    ll a,b;
    cin >> a >> b;
    ll x,y;
    ll d1 = exgcd(a,-b,y,x);
    if (2 % d1) {
        ll d2 = exgcd(b,-a,x,y);
        x *= 2 / d2,y *= 2 / d2;
        if (2 % d2) {
            cout << -1 << endl;
        }
        else {
            cout << x << ' ' << y << '\n';
        }
    }
    else {
        x *= 2 / d1,y *= 2 / d1;
        cout << x << ' ' << y << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

G - Leaf Color (atcoder.jp)

        1.思路:考虑每个遍历每个颜色单独求一遍答案,因此可以建一棵虚树进行dp即可。

                f[i] 表示以i为根节点,(不管符不符合的答案为多少),g[i]表示\sum_{j \epsilon son[i]}f[j]

                当i为枚举的颜色时,答案加上f[i]的方案数即可。

                当i不是枚举的颜色时,首先f[i]应该-1(因为i不能作为根节点),其次答案应该加上f[i] - g[i](所有选择一个子树的方案和)。

        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;
using i64 = long long;

constexpr int P = 998244353;
// assume -P <= x < 2P
int Vnorm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Mint {
    int x;
    Mint(int x = 0) : x(Vnorm(x)) {}
    Mint(i64 x) : x(Vnorm(x % P)) {}
    int val() const {
        return x;
    }
    Mint operator-() const {
        return Mint(Vnorm(P - x));
    }
    Mint inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Mint &operator*=(const Mint &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Mint &operator+=(const Mint &rhs) {
        x = Vnorm(x + rhs.x);
        return *this;
    }
    Mint &operator-=(const Mint &rhs) {
        x = Vnorm(x - rhs.x);
        return *this;
    }
    Mint &operator/=(const Mint &rhs) {
        return *this *= rhs.inv();
    }
    friend Mint operator*(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res *= rhs;
        return res;
    }
    friend Mint operator+(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res += rhs;
        return res;
    }
    friend Mint operator-(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res -= rhs;
        return res;
    }
    friend Mint operator/(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Mint &a) {
        i64 v;
        is >> v;
        a = Mint(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
        return os << a.val();
    }
};
vector<int> son[N],g[N];
int c[N],dep[N],dfn[N],fa[N][20],stk[N],top,tim;
inline void dfs(int u,int f)
{
    dfn[u] = ++ tim;
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for(int i = 1;i <= 18;i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(auto v : g[u]) {
        if(v == f) continue;
        dfs(v,u);
    }
}
inline int LCA(int x,int y)
{
    if(dep[x] > dep[y]) swap(x,y);
    int d = dep[y] - dep[x];
    for(int i = 18;i >= 0;i --) {
        if(d >> i & 1) y = fa[y][i];
    }
    if(x == y) return x;
    for(int i = 18;i >= 0;i --) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
Mint ans = 0;
int tarc = 0;
void add(int &a,int &b)
{
    son[a].push_back(b);
}
Mint DP(int x)
{
    Mint f = 1,g = 0;
    for (auto &y: son[x]) {
        auto nf = DP(y);
        f *= (nf + 1);
        g += nf;
    }
    if (c[x] == tarc) {
        ans += f;
    }
    else {
        f -= 1;
        ans += f - g;
    }
    son[x].clear();
    return f;
}
void buildTree(vector<int> &ver)
{
    if (ver.size() == 1) {
        ans += 1;
        return;
    }
    sort(ver.begin(),ver.end(),[&](int &x,int &y){
        return dfn[x] < dfn[y];
    });
    stk[top = 1] = 1;
    if (ver[0] != 1) {
        stk[++ top] = ver[0];
    }
    for (int i = 1;i < ver.size();i ++) {
        int lca = LCA(ver[i],stk[top]);
        while (top > 1 && dfn[stk[top - 1]] >= dfn[lca]) {
            add(stk[top - 1],stk[top]);
            top --;
        }
        if (lca != stk[top]) {
            add(lca,stk[top]);
            stk[top] = lca;
        }
        stk[++ top] = ver[i];
    }
    while (top) {
        add(stk[top - 1],stk[top]);
        top --;
    }
    DP(1);
}
vector<int> cor[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i ++) {
        cin >> c[i];
        cor[c[i]].push_back(i);
    }
    for (int i = 1;i < n;i ++) {
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    for (int i = 1;i <= n;i ++) {
        if (cor[i].size()) {
            tarc = i;
            buildTree(cor[i]);
        }
    }
    cout << ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/384626.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

利用Windows10漏洞破解密码(保姆级教学)

前言: 本篇博客只是技术分享并非非法传播知识,实验内容均是在虚拟机中进行,并非真实环境 正文: 一.windows10电脑密码破解 1)开启windows10虚拟机,停留在这个页面 2&#xff09;按5次Shift键,出现这个粘滞键,如果没有出现的,则说明漏洞已经修复 3)重新启动,在这个页面的时候…

Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN

摘要 https://arxiv.org/pdf/2009.12021.pdf 卷积是卷积神经网络&#xff08;CNN&#xff09;的主要构建块。我们观察到&#xff0c;随着通道数的增加&#xff0c;优化后的CNN通常具有高度相关的滤波器&#xff0c;这降低了特征表示的表达力。我们提出了Tied Block Convolutio…

文件包含知识点详细总结

如果想看图片和观感更好的话,可以直接去我的github或者gitbook github:https://github.com/kakaandhanhan/cybersecurity_knowledge_book-gitbook.22kaka.fun gitbook:http://22kaka.fun description: 这里将通过参考文章和做题一起进行总结,并且文件包含漏洞,很多都利用了…

Hive调优——explain执行计划

一、explain查询计划概述 explain将Hive SQL 语句的实现步骤、依赖关系进行解析&#xff0c;帮助用户理解一条HQL 语句在底层是如何实现数据的查询及处理&#xff0c;通过分析执行计划来达到Hive 调优&#xff0c;数据倾斜排查等目的。 https://cwiki.apache.org/confluence/d…

C++ //练习 5.24 修改你的程序,使得当第二个数是0时抛出异常。先不要设定catch子句,运行程序并真的为除数输入0,看看会发生什么?

C Primer&#xff08;第5版&#xff09; 练习 5.24 练习 5.24 修改你的程序&#xff0c;使得当第二个数是0时抛出异常。先不要设定catch子句&#xff0c;运行程序并真的为除数输入0&#xff0c;看看会发生什么&#xff1f; 环境&#xff1a;Linux Ubuntu&#xff08;云服务器…

那些也许你不知道的操作符!

前言 操作符有很多种&#xff0c;目前我们已经了解了一部分 例如最简单的、-、*、/、&#xff0c;还有我们学到的&&&#xff0c;||&#xff0c;!等&#xff0c;但是操作符可不是就只有这么些的&#xff0c;让我们一起来看看吧 目录 1. 移位操作符 原码、反码、补码…

Ubuntu Desktop - scrolling (Terminal 缓存更多终端历史输出内容)

Ubuntu Desktop - scrolling [Terminal 缓存更多终端历史输出内容] 1. ubuntu-14.04.5-desktop-amd64.iso2. ubuntu-16.04.3-desktop-amd64.isoReferences Terminal -> 右键 Profiles -> Profile Preferences 1. ubuntu-14.04.5-desktop-amd64.iso 2. ubuntu-16.04.3-de…

手动汉化unity编辑器,解决下载中文语言报错问题

手动汉化unity编辑器&#xff0c;解决下载中文语言报错问题 START 最近在下载支持微信小程序版本的编辑器时&#xff0c;中文语言包&#xff0c;一直无法下载。记录一下 手动汉化unity编辑器的方法 &#xff0c;帮助和我遇到同样问题的人。 解决方案 1. 下载汉化包 https:…

origin技巧

origin技巧 1.去掉白边2.曲线平滑3.合并多层图例3.图例换方向 1.去掉白边 ctrlu 2.曲线平滑 3.合并多层图例 3.图例换方向 图例右键 “图例” 水平排布修改图例字&#xff1a;双击图例修改 https://blog.csdn.net/m0_47746156/article/details/121295151 https://blog.csdn.…

Ocr之TesseractOcr的安装及使用

目录 一、安装环境 二、安装内容 三、安装过程及识别测试 1. 安装过程 2. 程序编写 总结 1. 安装复杂度较低 2. 国外开源Ocr 3. 可设置识别参数 4. 工具类 一、 系统环境windows 10 linux环境也可安装, 可借鉴此篇文章>> | 二、安装内容 Tesseract exe 程序安…

CVE-2022-25578 漏洞复现

CVE-2022-25578 路由/admin/admin.php是后台&#xff0c;登录账号和密码默认是admin、tao&#xff0c;选择文件管理。 是否还记得文件上传中的.htaccess配置文件绕过发&#xff0c;在这个文件中加入一句AddType application/x-httpd-php .jpg&#xff0c;将所有jpg文件当作php…

位运算+leetcode(1)

基础 1.基础知识 以下都是针对数字的二进制进行操作 >> 右移操作符<< 左移操作符~ 取反操作符 & 有0就是0&#xff0c;全一才一 | 有一才一 &#xff0c;全0才0^ 相同为0&#xff0c;相异为1 异或( ^ )运算的规律 a ^ 0 a a ^ a 0a ^ b ^ c a ^ (b …

【Java程序设计】【C00252】基于Springboot的实习管理系统(有论文)

基于Springboot的实习管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的实习管理系统 本系统分为前台功能模块、管理员功能模块、教师功能模块、学生功能模块以及实习单位功能模块。 前台功能模块&#xf…

hook函数——useMemo

useMemo 1.useMemo定义 useMemo 是一个 React Hook&#xff0c;它在每次重新渲染的时候能够缓存计算的结果。 const 变量名 useMemo(calculateValue, dependencies) calculateValue&#xff1a;要缓存计算值的函数。它应该是一个没有任何参数的纯函数&#xff0c;并且可以返…

【程序设计竞赛】竞赛中的细节优化

必须强调下&#xff0c;以下的任意一种优化&#xff0c;都应该是在本身采用的算法没有任何问题情况下的“锦上添花”&#xff0c;而不是“雪中送炭”。 如果下面的说法存在误导&#xff0c;请专业大佬评论指正 读写优化 C读写优化——解除流绑定 在ACM里&#xff0c;经常出现…

网络协议与攻击模拟_16HTTP协议

1、HTTP协议结构 2、在Windows server去搭建web扫描器 3、分析HTTP协议流量 一、HTTP协议 1、概念 HTTP&#xff08;超文本传输协议&#xff09;用于在万维网服务器上传输超文本&#xff08;HTML&#xff09;到本地浏览器的传输协议 基于TCP/IP(HTML文件、图片、查询结构等&…

Python实现桶排序

如果在对给定的一些数据进行排序的时候&#xff0c;给定的被排序的数据存在某种特征的时候&#xff0c;我们就可以利用这种特征&#xff0c;设计出相应的排序算法&#xff0c;以达到加快排序速度的目的。 而假设要排序的数组的每个元素的取值在一个区间0,1之间随机分布&#x…

C#,卢卡斯数(Lucas Number)的算法与源代码

1 卢卡斯数&#xff08;Lucas Number&#xff09; 卢卡斯数&#xff08;Lucas Number&#xff09;是一个以数学家爱德华卢卡斯&#xff08;Edward Lucas&#xff09;命名的整数序列。爱德华卢卡斯既研究了这个数列&#xff0c;也研究了有密切关系的斐波那契数&#xff08;两个…

【开源】基于JAVA+Vue+SpringBoot的二手车交易系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 二手车档案管理模块2.3 车辆预约管理模块2.4 车辆预定管理模块2.5 车辆留言板管理模块2.6 车辆资讯管理模块 三、系统设计3.1 E-R图设计3.2 可行性分析3.2.1 技术可行性分析3.2.2 操作可行性3.2.3 经济…

如何升级至ChatGPT Plus:快速指南,ChatGPT的秘密武器GPT4.0是什么?

提到 ChatGPT。想必大家都有所耳闻。自从 2022 年上线以来&#xff0c;就受到国内外狂热的追捧和青睐&#xff0c;上线2个月&#xff0c;月活突破1个亿&#xff01;&#xff01;&#xff01; 而且还在持续上涨中。因为有很多人都在使用 ChatGPT 。无论是各大头条、抖音等 App、…