博客

T1 clique


很巧妙的转化思路的题。没想到。

• 将点(xi,wi)看成区间(xi-wi,xi+wi),那么两个点有连边当且仅当两个区间没有公共点。
• 删去所有包含其它区间的区间,在剩下的区间中每次贪心取一个能取的坐标最小的区间。
• 注意考虑 wi=0 的空区间。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 200010;
const int oo = 2147483647;

int n;
struct node{
    int l, r;
}a[N];

template <typename T>
T read(){
    T N(0), F(1);
    char C = getchar();
    for(; !isdigit(C); C = getchar()) if(C == '-') F = -1;
    for(; isdigit(C); C = getchar()) N = N*10 + C-48;
    return N*F;
}

bool cmp(node x, node y){
    return x.l < y.l;
}

int main(){
    freopen("clique.in", "r", stdin);
    freopen("clique.out","w",stdout);

    n = read<int>();
    for(int i = 1; i <= n; i++){
        int j = read<int>();
        int k = read<int>();
        a[i].l = j-k; 
        a[i].r = j+k;
    }

    sort(a+1, a+n+1, cmp);

    int k = 0;
    for(int i = 1; i <= n; i++){
        while(k && a[i].r < a[k].r) k--;
        a[++k] = a[i];
    }

    n = k; k = 0;
    int j = -oo;
    for(int i = 1; i <= n; i++){
        if(a[i].l >= j){
            j = a[i].r;
            k++;
        }
    }

    printf("%d\n", k);
    return 0;
}

T2 mod


一道呼喊着“我是线段树”的题目。但是我一直在维护区间和，没有想到mod的话可以维护最大值，可以省去很多步骤！

• 用线段树维护区间最大值以及区间和。
• 进行取模操作时,如果 x>区间最大值那么退出,否则两边都递归下去。
• 单个数被有效地取模一次只会花费
  
  
  
  
  
  
  
  
  O
  
  
  (
  
  
  l
  
  
  
  
  o
  
  
  g
  
  
  n
  
  
  )
  
  
  
  
  
  
  
  
  
  
  $O(logn)$
  的时间,并且数值至少减半,因此每次修改至多使时间复杂度增加
  
  
  
  
  
  
  
  
  O
  
  
  (
  
  
  l
  
  
  
  
  o
  
  
  g
  
  
  
  
  
  n
  
  
  
  
  
  
  2
  
  
  
  
  
  
  
  )
  
  
  
  
  
  
  
  
  
  
  $O(logn^2)$
  。

ps:以下代码还没A,freopen里是mod6是因为从第6个测试点开始就wa了。同学说是没开long long,然而我开了啊？？？哪里的问题呢？

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N = 100010;
const ll oo = 1e18+7;

int n, m;
ll da[N];
ll a[N];
struct Node{
    ll val, lazy;
}seg[N*4];

template <typename T>
T read(){
    T N(0), F(1);
    char C = getchar();
    for(; !isdigit(C); C = getchar()) if(C == '-') F = -1;
    for(; isdigit(C); C = getchar()) N = N*10 + C-48;
    return N*F;
}

void built(ll node, int be, int en){
    seg[node].lazy = 0;
    if(be == en){
        seg[node].val = a[be];
        da[node] = a[be];
//      printf("%d %lld %lld\n", node, seg[node].val, da[node]);
        return;
    }

    int mid = be+((en-be) >> 1);
    built(node*2, be, mid);
    built(node*2+1, mid+1, en);
    seg[node].val = seg[node*2].val + seg[node*2+1].val;
    da[node] = max(da[node*2], da[node*2+1]);
//  printf("%d %lld %lld\n", node, seg[node].val, da[node]);
}

void update_p(ll node, int be, int en, int num, ll x){
    if(be == en && num == be){
        seg[node].val = x;
        da[node] = x;
        return;
    }

    int mid = be+((en-be) >> 1);
    if(num <= mid) update_p(node*2, be, mid, num, x);
    else update_p(node*2+1, mid+1, en, num, x);
    seg[node].val = seg[node*2].val + seg[node*2+1].val;
    da[node] = max(da[node*2], da[node*2+1]);
}

ll query(ll node, int be, int en, int le, int ri){
    if(be >= le && en <= ri){
        return seg[node].val;
    }

    int mid = be+((en-be) >> 1);
    ll L = 0LL; ll R = 0LL;
    if(le <= mid) L = query(node*2, be, mid, le, ri);
    if(ri > mid) R = query(node*2+1, mid+1, en, le, ri);
    return L+R;
}

void update_q(ll node, int be, int en, int le, int ri, ll add){
    if(add > da[node]) return;
    if(be == en){
        seg[node].val %= add;
        da[node] = seg[node].val;
        return;
    }

    int mid = be+((en-be) >> 1);

    if(le <= mid) update_q(node*2, be, mid, le, ri, add);
    if(ri > mid) update_q(node*2+1, mid+1, en, le, ri, add);
    seg[node].val = seg[node*2].val + seg[node*2+1].val;
    da[node] = max(da[node*2], da[node*2+1]);
}

int main(){
    freopen("mod6.in", "r", stdin);
    freopen("mod.out","w",stdout);

    int l, r, k, cs;
    ll x;

    n = read<int>(); m = read<int>();
    for(int i = 1; i <= n; i++) a[i] = read<ll>();

    built(1, 1, n);

    for(int i = 1; i <= m; i++){
        cs = read<int>();
        if(cs == 1){
            l = read<int>();
            r = read<int>();
            printf("%lld\n", query(1, 1, n, l, r));
        }
        else if(cs == 2){
            l = read<int>();
            r = read<int>();
            x = read<ll>();
            update_q(1, 1, n, l, r, x);
        }
        else if(cs == 3){
            k = read<int>();
            x = read<ll>();
            update_p(1, 1, n, k, x);
        } 
    }

    return 0;
}

第三题还没看懂题解和std，之后可能会写，也可能会放弃第三题。

注：

多注重思维的转化吧。毕竟现在的题也不是让你创造什么新算法，所以肯定大多还是转化一下就知道结果了。对于一些比较有把握的题要想办法优化，其他的题打好暴力。

好好休息。