2024CCPC长春邀请赛IGLE

nannandbk / 2024-10-19 / 原文

2024CCPC长春邀请赛IGLE

I. The Easiest Problem

签到

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    string s; 
    getline(cin,s);
    int n = s.size();
    s = "?" + s;
    int cnt = 0;
    // cout<<"s = "<<s<<"\n";
    for(int i = 1;i <= n; i++)
    {
        if(s[i] >= 'a' && s[i] <= 'z')
            cnt++;
    }
    cout<<cnt<<"\n";


    return 0;
}

G. Platform Game

思路: 非常简单，先按高度排序，高度一样左端点小的优先。然后做一个模拟就行了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

struct ty
{
    ll l,r,h;
}a[N];


bool cmp(ty a,ty b)
{
    if(a.h == b.h)
        return a.l < b.l;
    return a.h > b.h;
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i].l>>a[i].r>>a[i].h;
        sort(a+1,a+1+n,cmp);

        ll sx,sy; cin>>sx>>sy;
        for(int i = 1;i <= n; i++)
        {
            int l = a[i].l,r = a[i].r,h = a[i].h;
            // cout<<"sy = "<<sy<<" h = "<<h<<"\n";
            if(h > sy)continue;
            // cout<<"h = "<<h<<" sx = "<<sx<<" sy = "<<sy<<"\n";
            if(l < sx && sx < r)
                sx = r,sy = h;
        }
        cout<<sx<<"\n";
    }
 
 
    return 0;
}

L. Recharge

这个题有点恶心，比较的细节，de了好久bug

思路：想法倒是非常的简单。分奇偶来看。

k为偶数就很简单了，因为不用用多一个2去补。直接算贡献就行了。

那么k为奇数呢？考虑优先用2，看放2放到最后一个$\le k$，剩下不够用1去补。这样完整的满足k的为一组(不用浪费2) 。看能做多少组？

在y够的情况下到最后一个$< k$（因为k是奇数所以不可能等于）需要放的y的个数，即$t = \min(y,k/2)$个。还需要多少个x去补呢？$need = k-t*2$。那么能做：$can = min(need?x/need:inf,t?y/t:inf)$个完整的组。

剩余的$x = x-can*need,y = y-can*t$。

①如果说剩余的$x,y$还能满足一次$k$，任然优先用2，用1去补：$ans = can+1+(x-(k-2*y))/k$

②如果只剩$x$，直接算就好了：$ans = can+x/k$

③如果只剩$y$，那么我们每次需要多用一个2去补,也就是说需要满足到k+1才算一次。$ans = can + y*2/(k+1)$

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        ll k,x,y; cin>>k>>x>>y;
        ll ans = 0;
        ll t = k/2;
        t = min(t,y);
        ll need = k-t*2;
        ll inf = 1e18;
        ll can = min(need?x/need:inf,t?y/t:inf);//循环轮数
        ans = can; x -= can*need; y -= can*t;
        if(x && y && x + 2 * y >= k)
            ans = ans + 1 + (x - (k-2*y))/k;
        else if(x){
            ans = ans + x/k ;
        }else if(y){
            ans = ans + y*2/(k+1);
        }

        cout<<ans<<"\n";

    }

    return 0;
}

E. Connected Components

思路：看到数据范围那么大，肯定要对给定式子化简。

由$a_i-a_j\le i-j \le b_i-b_j$

可以很容易得到：

①$a_i-a_j\le i-j\rightarrow a_i-i\le a_j-j$

②$i-j\le b_i-b_j\rightarrow i-b_i\le j-b_j$

要①和②同时满足。

我们预处理，让$a[i] = i-a[i],b[i]=b[i]-j$

也就是说，如果我能找到一个数，我的$a$和$b$都比它大就能连边。

我们先按$a$排序，现在只需要考虑$b$就行了。我们考虑如果当前出现的$b$是最小的，那么不可能和前面的任何一个连边，它暂时需要单独开一个组。我们把它放到队列里面。如果说再往后看，有比当前最小的$b$大的话，说明可以连边，因为我们的队列是单减的，那么队列里面其他的也同时可以连边。也就是说我们有一个往回看的步骤。具体看代码：

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;

int n;
struct ty
{
    ll a,b;
}c[N];

int fa[N];

bool cmp(ty x, ty y)
{
    if(x.a == y.a)
        return x.b < y.b;
    return x.a < y.a;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    cin>>n;
    for(int i = 1;i <= n; i++)
    {
        cin>>c[i].a>>c[i].b;
        c[i].a = c[i].a - i, c[i].b = i - c[i].b;
    }
    for(int i = 1;i <= n; i++)
        fa[i] = i;
    sort(c+1,c+1+n,cmp);
    
    vector<ll>ans;

    for(int i = 1;i <= n; i++)
    {
        ll now = c[i].b;
        if(!ans.size() || now < ans.back())
            ans.push_back(now);
        else if(now > ans.back())
        {
            ll t = ans.back();
            while(ans.size() > 0 && now >= ans.back())
                ans.pop_back();
            ans.push_back(t);
        }
    }

    cout<<ans.size()<<"\n";

    return 0;
}

或者用并查集：

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;

int n;
struct ty
{
    ll a,b;
}c[N];

int fa[N];

bool cmp(ty x, ty y)
{
    if(x.a == y.a)
        return x.b < y.b;
    return x.a < y.a;
}

int find(int x)
{
    if(fa[x] != x)      fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    // cout<<"x = "<<x<<" y = "<<y<<"\n";

    x = find(x);
    y = find(y);

    if(x != y)
        fa[y] = x;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    cin>>n;
    for(int i = 1;i <= n; i++)
    {
        cin>>c[i].a>>c[i].b;
        c[i].a = c[i].a - i, c[i].b = i - c[i].b;
    }
    for(int i = 1;i <= n; i++)
        fa[i] = i;
    sort(c+1,c+1+n,cmp);
    int minv = c[1].b,idx = 1;
    
    vector<array<int,2>>v;
    v.push_back({minv,idx});
    for(int i = 2;i <= n; i++)
    {
        int t = c[i].b;
        if(t < minv){
            minv = t;
            idx = i;
            v.push_back({minv,idx});
        }
        else{
            auto tmp = v.back();
            while(v.size() && t >= v.back()[0]){
                merge(v.back()[1],i);
                v.pop_back();
            }
            merge(idx,i);
            v.push_back(tmp);
        }
    }

    set<ll>s;
    

    

    for(int i = 1;i <= n; i++)
    {
        s.insert(fa[i]=find(fa[i]));
    }

    // cout<<"fa[i] = ";
    // for(int i = 1;i <= n; i++)
    //     cout<<fa[i]<<" ";
    // cout<<"\n";

    cout<<s.size();



    return 0;
}