2024.1.19训练赛总结

是谁不可理喻 / 2024-01-20 / 原文

赛时做出 ABC

链接 https://vjudge.net/contest/604628

A题

思路：先处理要求相等的输入，将被要求相等的变量放在一个并查集中，然后对要求不相等的输入进行判断，如果要求 xi != xj，但 xi 和 xj 在同一个并查集中，则输出 NO，否则 YES

问题：

第一，要不是看了原题，我都不知道下标有1e11的范围，这个只需要简单离散化就可以

第二，数组又开小了，导致一直 wa 和 mle服了

#include<bits/stdc++.h>

const int MAXN = 1e5 + 10;
using namespace std;
typedef long long LL;

struct node{
    LL a,b;    
    int op;
    
};
node q[MAXN], ne[MAXN];
int T;
int n;
int cnt, cnt2;
LL tot[MAXN << 1];
int f[MAXN];
map<LL, int> mp;

int findfa(int x)
{
    if(x == f[x]) return f[x];
    return findfa(f[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>T;
    while(T--)
    {
        cin>>n;
        mp.clear();
        cnt = 0;
        cnt2 = 0;
        for(int i = 1;i <= n;i++) 
            cin>> q[i].a >> q[i].b >> q[i].op, tot[++cnt2] = q[i].a, tot[++cnt2] = q[i].b;
            
        sort(tot + 1, tot + cnt2 + 1);
        tot[cnt2 + 1] = -1;
        
        for(int i = 1;i <= cnt2;i++)
            if(tot[i] != tot[i+1]) mp[tot[i]] = ++cnt;
        
        for(int i = 1;i <= cnt;i++) f[i] = i;
        cnt = 0;
        
        int op, l, r;
        for(int i = 1;i <= n;i++)
        {
            op = q[i].op;
            l = mp[q[i].a];
            r = mp[q[i].b];
            if(op)
            {
                int f1 = findfa(l), f2 = findfa(r);
                f[max(f2, f1)] = min(f2, f1);
            }
            else ne[++cnt].a = l, ne[cnt].b = r;
        }
        int flag = 1;
        for(int i = 1;i <= cnt;i++)
        {
            if(findfa(ne[i].a) == findfa(ne[i].b))
            {
                flag = 0;
                break;
            }
        }
        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

View Code

B题

思路：直接暴力模拟就可以了，直接用一个优先队列来存储区间，每次从队列里面取出一个最靠左，最长的区间，取中间赋值，再把两边的区间放到队列里，注意什么时候要放进队列，什么时候不需要放进队列就可以。比如出现了左边界大于右边界，边界超出了1和n的范围等

问题：

1.优先队列是大根堆，一直不记

2.在结构体中只能自定义小于号，不能大于号（存疑）

3.没注意边界问题，又wa了

#include<bits/stdc++.h>

const int MAXN = 2e5 + 10; 
using namespace std;

int T;
int n;
int ans[MAXN];
struct node{
    int l;
    int r;
    friend operator < (const node a,const node b){
        if(a.r - b.r == a.l - b.l) return a.l > b.l;
        return a.r - a.l < b.r - b.l;
    }
        
};
priority_queue <node> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>T;
    while(T--)
    {
        cin>>n;
        int cnt = 0;
        while(!q.empty()) q.pop();
        q.push({1,n});
        while(!q.empty())
        {
            node ne = q.top();
            q.pop();
            if(!ans[ne.l + ne.r >> 1]) ans[ne.l + ne.r >> 1] = ++cnt;
            if(ne.l >= ne.r || !ne.l || !ne.r || ne.l > n || ne.r > n) continue;
            q.push({ne.l, (ne.l + ne.r >> 1) - 1});
            q.push({(ne.l + ne.r >> 1) + 1, ne.r});
        }
        for(int i = 1;i <= n;i++) cout<<ans[i]<<" \n"[i==n],ans[i] = 0;
    }
    return 0;
}

View Code

C题

思路：一开始还没看出来是个经典线段树，后面才想明白。

每个节点除了保存边界，再多一个变量存储左右子树的 gcd 就可以了。

问题在于如何询问，即确定在所给区间内最多修改一个值，使得该区间的 gcd 恰好为 x。

做的时候的思路是：

求出来需要修改的次数，如果小于等于1，就 yes，否则 no

如果当前节点表示的区间是被包含在所给区间的，那就根据它的 gcd 值分以下几种情况来判断：

1.如果是 x 的倍数，说明不需要修改

2.如果不是 x 的倍数，如果是单个节点，修改次数+1，否则分别对它的两个子区间进行询问

关于为什么只要是 x 的倍数都不用修改，因为如果区间的 gcd 是 x 的倍数，那么只需要修改一次，随便把一个数修改成 x，最终就都满足了

而如果该区间有数不含 x 这个因子，或者两个或多个数的 gcd 不为 x，那就需要把它们全部修改成 x 了，所以有几个就得改几个，而且不需要修改那些 gcd 是 x 或 x 倍数的区间，因为一旦区间中有了 x，那整个区间的 gcd 一定不会超过 x。

问题：

如果不加优化，会有很明显的问题：超时

这就需要剪枝了，只要当前需要修改的次数已经大于1，那就直接结束。（居然当时没想到）

总结：很好线段树，让我找回感觉，不再恐惧，第一次手写过。

#include<bits/stdc++.h>

const int MAXN = 5e5 + 10;
using namespace std;

int n;
int a[MAXN];
int q;
int op, poi, ll, rr, xx;
struct node{
    int l;
    int r;
    int g;
}t[MAXN<<3];

int gcd(int a,int b)
{
    if(!b) return a;
    return gcd(b, a % b);
}

void build(int rt, int L, int R)
{
    if(L == R)
    {
        t[rt].l = t[rt].r = L;
        t[rt].g = a[L];
        return;    
    }    
    int mid = L + R >> 1;
    build(rt << 1, L, mid);
    build(rt << 1 | 1, mid + 1, R);
    t[rt].l = L;
    t[rt].r = R;
    t[rt].g = gcd(t[rt << 1].g, t[rt << 1 | 1].g);
    return;
}

void update(int rt, int p, int x)
{
    if(t[rt].l == t[rt].r && t[rt].l == p)
    {
        t[rt].g = x;
        return ;
    }
    int mid = t[rt].l + t[rt].r >> 1;
    if(p <= mid) update(rt << 1, p, x);
    else update(rt << 1 | 1, p, x);
    t[rt].g = gcd(t[rt << 1].g, t[rt << 1 | 1].g);
    return;    
}
int summ = 0;
void query(int rt)
{
    if(summ > 1) return ; // ¼ôÖ¦ ºÜÖØÒª 
    if(ll > t[rt].r || rr < t[rt].l) return ;
    int mid = t[rt].r + t[rt].l >> 1;
    
    if(ll <= t[rt].l && rr >= t[rt].r)
    {
        if(t[rt].g % xx == 0) return ;
        else 
        {
            if(t[rt].l == t[rt].r)
            {
                summ++;
                return ;
            }
            query(rt << 1);
            query(rt << 1 | 1);
            return ;
        }
    }
    if(mid >= ll) query(rt << 1);
    if(rr > mid) query(rt << 1 | 1);
    return; 
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i = 1;i <= n;i++) cin>> a[i];
    build(1, 1, n);
    cin>>q;
    for(int i = 1;i <= q;i++)
    {
        cin>>op;
        if(op == 1)
        {
            cin>> ll >> rr >> xx;
            query(1);
            cout<<summ<<" ";
            if(summ <= 1) cout<<"YES\n";
            else cout<<"NO\n";
            summ = 0;
        }
        else 
        {
            cin>> poi >> xx;
            update(1, poi, xx);
        }
    }
    return 0;
}