首页 > 其他分享 >The 2020 ICPC Asia Shenyang Regional Programming Contest

The 2020 ICPC Asia Shenyang Regional Programming Contest

时间：2022-11-08 22:23:23浏览次数：48  
标签：Shenyang const Contest int ll Regional mid seg id

VP题目列表

D.Journey to Un'Goro

statement: 略 Solution: dfs剪枝 Code: ⁢ 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define int ll
const int N = 1e6 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int cnt=0,n,limit;
ll ans;
char str[N];
void dfs(int k, int cnt0, int cnt1, int ok) {
    if (cnt0 > limit || cnt1 > limit) {
        return;
    }
    if (k == n) {
        cout << str << endl;
        cnt++;
        if (cnt >= 100) {
            exit(0);
        }
        return ;
    }
    str[k] = 'b';
    dfs(k + 1, cnt0 + !ok, cnt1 + ok, ok);
    ok = 1 - ok;
    str[k] = 'r';
    dfs(k + 1, cnt0 + !ok, cnt1 + ok, ok);
}
void solve() {
    cin >> n;
    ans = ((n + 1) / 2) * ((n + 2) / 2);
    limit = (n + 2) / 2;
    cout << ans << endl;
    dfs(0, 1, 0, 0);
}
signed main() {
    tententen;
    int T = 1;
    //cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

F.Kobolds and Catacombs

Solution: Code: 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
void solve() {
    int n;
    cin >> n;
    vector a(n + 1), num, suf(n + 2);
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        num.push_back(a[i]);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    for(int i = 1; i <= n; i ++) {
        a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin() + 1;
    }
    suf[n] = a[n];
    for (int i = n - 1; i >= 1; --i) {
        suf[i] = min(suf[i + 1], a[i]);
    }
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; ++i) {
        mx = max(a[i], mx);
        if (mx <= i && ((i + 1 <= n && suf[i + 1] >= mx) || i == n)) ans++;
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

G.The Witchwood

Solution: Code: 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int a[N];
void solve() {
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=n;i>=n-k+1;--i){
        ans+=a[i];
    }
    cout<<ans<<endl; }="" int="" main()="" {="" ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);="" t="1;" cin="">> t;
    while (t--) {
        solve();
    }
}

H.The Boomsday Project

statement: Aloha 要骑单车，可以单独花费$r$元骑 1 次，也可以购买某一种单车卡，第 种单车 卡 元，若在第 天购买，可以在 天使用，并且最多使用 次 给出 Aloha 一段时间内的单车使用情况，求出他需要的最小花费 给出 $n(1\le n\le500)$ 单车卡的种类

\(m(1\le m\le 10^5)\) 条使用记录

\(r(1\le r \le 10^9)\)单独骑 1 次的花费

\(n\)行输入，每行有\(1 \le d_i,k_i,c_i \le 10^9\) 第 \(i\) 种单车卡的有效期、使用次数、价格

\(m\) 行，每行有 $ 0 \le p_i \le 10^9 $, \(0 \le qi \le 3e5, ∑_{i=1}^{m} qi \le 3e5\) 表示在第\(p_i\) 天骑了 \(q_i\)次

Solution： '''''' Code： 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int ll
#define  tententen ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
const int N  =3e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll inf = 0x3f3f3f3f;
const ll mod =1e9 + 7;..);}
ll ksm(ll a, ll b, ll m) {ll ans = 1;while (b > 0) {if (b & 1) {ans = ans * a % m;}a = a * a % m;b >>= 1;}return ans;}
int n, m;
int  k[666], d[666], c[666],t[N];
int r;
ll dp[N];
struct Node{
    int day,cnt;
}a[N];
bool cmp(Node x,Node y){
    return x.day<y.day; }="" void="" solve()="" {="" cin="">> n >> m >> r;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> k[i] >> c[i];
    }
    int sum = 0, idx;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i].day >> a[i].cnt;
    }
    sort(a + 1, a + 1 + m, cmp);
    for (int i = 1; i <= m; ++i) {
        for (int j = sum + 1; j <= sum + a[i].cnt; ++j) {
            t[j] = a[i].day;
        }
        sum += a[i].cnt;
    }
    for (int i = 0; i <= sum + 1; ++i) {
        dp[i] = INF;
    }
    dp[0] = 0;
    for (int i = 1; i <= sum; ++i) {
        dp[i] = min(dp[i], dp[i - 1] + r);
        for (int j = 1; j <= n; ++j) {
            if (i + k[j] - 1 <= sum && t[i + k[j] - 1] <= t[i] + d[j] - 1) {
                idx = i + k[j] - 1;
            } else {
                idx = 0;
                int l = i, r = min(sum, i + k[j] - 1);
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (t[mid] <= t[i] + d[j] - 1) {
                        l = mid + 1;
                        idx = mid;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            dp[idx] = min(dp[idx], dp[i - 1] + c[j]);
        }
    }
    cout << dp[sum] << endl;
}
signed main() {
    tententen;
    int T = 1;
    //cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

I.Rise of Shadows

statement: 略 Solution： 不会！猜的！ Code：
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e6 + 10;
ll h, m, a;
void solve() {
    cin >> h >> m >> a;
    if (h * m  == a * 2ll) {
        cout << h * m << endl;
        return;
    }
    ll tmp = __gcd(h - 1, h * m);
    ll ans = 2ll * (a  / tmp);
    cout << tmp * ll( ans + 1 ) << endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}

J.Descent of Dragons

statement: Solution: ​ 比较容易想到动态开点，给每个等级建一棵线段树，然后操作就转变成从$level = x$的线段树上拆下$[L, R]$ 对应的子树，然后复制到$level = x + 1$的树上，这类似于线段树拆分合并。这样去实现的话，询问时$[L, R]$ 只会出现在一棵树上，那么处理询问的复杂度就不合理了。

​ 转变一下思路。之前每棵树的意义是\(level = x\)，那如果我们在操作时不把\([L, R]\)从旧版本拆下来，那每棵树的意义就会变成\(level\geqslant x\), 也就是说\([L, R]\)会出现在所有线段树的一段前缀上，那么就可以用二分处理询问了。

​ 在复制的时候，$level\geqslant x+1 $ 的树上原来有的路径也要开出新点，如果按原来的路径走，会导致走到历史版本的树上去更改信息。

​ 时间复杂度：操作\(O(log(n))\),询问\(O(log^2(n))\)，所以是\(O(qlog^2(n))\)。

Code: 
#include <bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
templateinline void read(T &x){
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    if(f) x=-x;
}
template
inline void read(T &a,V&... b){read(a); read(b...);}
const int maxn = 5e5 + 100, maxm = 1e6 + 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-8;
template  inline void chkmax(T &x,const T &y) {x=x>y?x:y;}
template  inline void chkmin(T &x,const T &y) {x=x<y?x:y;} inline="" ll="" add(ll="" x,ll="" y){x+="y;return(x<mod)?x:x-mod;}" dec(ll="" y){x-="y;return(x<0)?x+mod:x;}" mul(ll="" y){return(x*y%mod);}="" ksm(ll="" base,ll="" b){="" res="1;while(b){if(b&1)res=res*base%mod;base=base*base%mod;b">>=1;}
    return res;
}

struct Seg {
    int sum, ls, rs;
} seg[maxn * 72];

int n, q, rt[maxn], vtot;

void build(int id, int l, int r) {
    if (l == r) {
        seg[id].sum = 1;
        vtot = max(vtot, id);
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    seg[id].ls = id << 1;
    seg[id].rs = id << 1 | 1;
    seg[id].sum = seg[id << 1].sum + seg[id << 1 | 1].sum;
}

int update(int id, int id2, int l, int r, int ql, int qr) {
    if (!id2 || !seg[id2].sum) return 0;
    if (ql == l && qr == r) { return id2;}
    int x = ++vtot;
    seg[x] = seg[id];
    id = x;
    int mid = l + r >> 1;
    if (qr <= mid) seg[id].ls = update(seg[id].ls, seg[id2].ls, l, mid, ql, qr);
    else if (ql > mid) seg[id].rs = update(seg[id].rs, seg[id2].rs, mid + 1, r, ql, qr);
    else {
        seg[id].ls = update(seg[id].ls, seg[id2].ls, l, mid, ql, mid);
        seg[id].rs = update(seg[id].rs, seg[id2].rs, mid + 1, r, mid + 1, qr);
    }
    seg[id].sum = seg[seg[id].ls].sum + seg[seg[id].rs].sum;
    return id;
}

int query(int id, int l, int r, int ql, int qr) {
    if (!id || !seg[id].sum) return 0;
    if (ql == l && qr == r) return seg[id].sum;
    int mid = l + r >> 1;
    if (qr <= mid) return query(seg[id].ls, l, mid, ql, qr);
    else if (ql > mid) return query(seg[id].rs, mid + 1, r, ql, qr);
    else return query(seg[id].ls, l, mid, ql, mid) + query(seg[id].rs, mid + 1, r, mid + 1, qr);
}

int main() {
    ios;
    cin >> n >> q;
    build(1, 1, n);
    rt[0] = 1;
    while (q--) {
        int ty, l, r;
        cin >> ty >> l >> r;
        if (ty == 1) {
            int x;
            cin >> x;
            rt[x + 1] = update(rt[x + 1], rt[x], 1, n, l, r);
        } else {
            int L = 0, R = maxn - 1, mid;
            while (L < R) {
                mid = L + R + 1 >> 1;
                if (query(rt[mid], 1, n, l, r)) L = mid;
                else R = mid - 1;
            }
            cout << L << endl;
        }
    }
}

K.Scholomance Academy

statement: 略 Solution: 阅读题 Code: 
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
struct Node {
    char c;
    int v;
    bool operator<(const Node& p) const { return v < p.v; };
} a[1000010];
int cnt[1000010][2];
int n;
vector nums;
map<double, double=""> mp;
int main() {
    ios;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].c >> a[i].v;
        nums.push_back(a[i].v);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i++) {
        a[i].v =lower_bound(nums.begin(), nums.end(), a[i].v) - nums.begin() + 1;
        if (a[i].c == '+')
            cnt[a[i].v][1]++;
        else
            cnt[a[i].v][0]++;
    }
    for (int i = 1; i <= 1000000; i++) {
        cnt[i][0] += cnt[i - 1][0];
        cnt[i][1] += cnt[i - 1][1];
    }
    for (int i = 1; i <= n; i++) {
        int s = a[i].v;
        int tp = cnt[1000000][1] - cnt[s - 1][1];
        int fp = cnt[1000000][0] - cnt[s - 1][0];
        int tn = cnt[s - 1][0];
        int fn = cnt[s - 1][1];
        double fpr = 1.0 * fp / (tn + fp), tpr = 1.0 * tp / (tp + fn);
        mp[fpr] = max(mp[fpr], tpr);
    }
    double prex = 0, prey = 0;
    double sum = 0;
    for (auto [x, y] : mp) {
        if( y == prey) continue;
        // cout << x << " " << prex << " " << y << endl;
        sum += (x - prex) * prey;
        prex = x; prey = y;
    }
    sum += (1 - prex);
    cout << fixed << setprecision(12) << sum;
}

标签：Shenyang,const,Contest,int,ll,Regional,mid,seg,id
From： https://www.cnblogs.com/tentenn/p/16851847.html

相关文章

  • AtCoder Beginner Contest 275
    A-FindTakahashi找到序列中最高的数存在的位置#include<bits/stdc++.h>usingnamespacestd;intread(){intx=0,f=1,ch=getchar();while((c......
  • Atcoder Beginner Contest 276(A~G)
    赛时A简单字符串处理；B简单vector处理；C找上一个排列。D找到每一个数因子\(2\)的个数和\(3\)的个数，并判断除去这些因子之后剩下的值是否相同，若不同则不能满足条......
  • AtCoder Beginner Contest 276
    A-Rightmost#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){strings;cin>>s;for(inti=s.size();i>=1;i--)i......
  • [Leetcode Weekly Contest]318
    链接：LeetCode[Leetcode]2460.对数组执行操作给你一个下标从0开始的数组nums，数组大小为n，且由非负整数组成。你需要对数组执行n-1步操作，其中第i步操作（从0......
  • AtCoder Regular Contest 070&071
    ARC070只会个DQAQ，所以就合并到ARC071了。ARC070D-NoNeed给定\(n\)个整数\(a_1\sima_n\)，对于\(a_i\)，若原来所有包含\(a_i\)且和\(\geK\)的子集去掉\(......
  • contests-in-202211
    2022.11模拟赛日志postedon2022-11-0115:57:02|under日志|source希望NOIP2022GD赛区能正常举办！更希望初中生能正常参赛。CMB说：CSP-S分数高于某个线的初......
  • contests-in-202210
    2022.10模拟赛日志postedon2022-10-2316:03:39|under日志|source停课以来，每天都是模拟赛；怎么说呢，有点想念我的学校。膜拜SS221005（20221005）A简单构造，很会。......
  • AtCoder Beginner Contest 276
    今天来讲解一下AtCoderBeginnerContest276 C和D传送地址：https://atcoder.jp/contests/abc276一. C-PreviousPermutation题目大意：给你一个有数字1~n组成的序列......
  • AtCoder Beginner Contest 276
    咕咕咕咕。E-RoundTrip如果存在某个点双满足这个点双包含起点且点双大小大于\(4\)则有解。F-DoubleChance考虑不断在之前的基础上在末尾添加一个数，每次更新期......
  • AtCoder Beginner Contest 276 A~G 题解
    今天凌晨CFD题差一句判断AC，晚上ABCG题把插板法和快速幂搞混差点AC。事不过三，再这样一次我直接紫砂。太简单的题就不放翻译和代码了。（事实上这场A-E都是大水题......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99