头像

dys

qq:1115410174 西北大学




离线:8小时前


活动打卡代码 AcWing 2539. 动态树

dys
3天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
const int N = 1e5+10;
struct node{
    int s[2],p,v;
    int sum,rev;
}tr[N];
int stk[N];
void pushup(int x){
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}
void pushrev(int x){
    swap(tr[x].s[0],tr[x].s[1]);
    tr[x].rev ^= 1;
}
void pushdown(int x){
    if(tr[x].rev){
        pushrev(tr[x].s[0]);
        pushrev(tr[x].s[1]);
        tr[x].rev ^= 1;
    }
}
bool isroot(int x){
    return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}
void rotate(int x){
    int y = tr[x].p,z = tr[y].p;
    int k = tr[y].s[1] == x;
    if(!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k^1];
    tr[tr[x].s[k^1]].p = y;
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;
    pushup(y);
    pushup(x);
}
void splay(int x){
    int top = 0,r = x;
    stk[++top] = r;
    while(!isroot(r)) stk[++top] = r = tr[r].p;
    while(top) pushdown(stk[top--]);
    while(!isroot(x)){
        int y = tr[x].p,z = tr[y].p;
        if(!isroot(y))
            if((tr[y].s[1] == x)^(tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}
void access(int x){
    int z = x;
    for(int y = 0;x;y = x,x = tr[x].p){
        splay(x);
        tr[x].s[1] = y;
        pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){
    access(x);
    while(tr[x].s[0]) pushdown(x),x = tr[x].s[0];
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y) != x) tr[x].p = y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y) == x && tr[y].p == x && !tr[y].s[0]){
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> tr[i].v;
    int op,x,y,w;
    while(m--){
        cin >> op;
        if(op == 0){
            cin >> x >> y;
            split(x,y);
            cout<< tr[y].sum <<endl;
        }else if(op == 1){
            cin >> x >> y;
            link(x,y);
        }else if(op == 2){
            cin >> x >> y;
            cut(x,y);
        }else{
            cin >> x >> w;
            splay(x);
            tr[x].v = w;
            pushup(x);
        }
    }
    return 0;
}


活动打卡代码 AcWing 3188. manacher算法

dys
6天前
#include<bits/stdc++.h>
using namespace std;
const int N = 4e7+10;
char a[N],b[N];
int p[N];
int len;
void init(){
    int k = 0;
    b[k++] = '$';
    b[k++] = '#';
    for(int i=0;i<len;i++){
        b[k++] = a[i];
        b[k++] = '#';
    }
    b[k++] = '^';
    len = k;
}
void manacher(){
    int mr = 1,mid;
    for(int i=0;i<len;i++){
        if(i < mr) p[i] = min(p[2*mid-i],mr-i);
        else p[i] = 1;
        while(b[i-p[i]] == b[i+p[i]]) p[i]++;
        if(i + p[i] > mr){
            mr = i + p[i];
            mid = i;
        }
    }
}
int main(){
    scanf("%s",a);
    len = strlen(a);
    init();
    manacher();
    int ans = 0;
    for(int i=0;i<len;i++) ans = max(ans,p[i]);
    cout<<ans - 1<<endl;
    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

dys
9天前
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    int x = 1,y = 1;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    int s = 0;
    for(int i=1;i<=n*m;i++){
        a[x][y] = i;
        int sx = x + dx[s];
        int sy = y + dy[s];
        if(sx<1 || sy<1 || sx>n || sy>m || a[sx][sy]){
            s = (s+1)%4;
            sx = x + dx[s];
            sy = y + dy[s];
        }
        x = sx;
        y = sy;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
};


活动打卡代码 AcWing 2714. 左偏树

dys
12天前
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int l[N],r[N],d[N],v[N],p[N],idx;
int n;
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int cmp(int x,int y){
    if(v[x]!=v[y]) return v[x]<v[y];
    return x<y;
}
int merge(int x,int y){
    if(!x || !y) return x+y;
    if(cmp(y,x)) swap(x,y);
    r[x] = merge(r[x],y);
    if(d[r[x]] > d[l[x]]) swap(l[x],r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}
int main(){
    scanf("%d",&n);
    int op,a,x,y;
    v[0] = 2e9;
    while(n--){
        cin>>op;
        if(op == 1){
            cin>>x;
            v[++idx] = x;
            d[idx] = 1;
            p[idx] = idx;
        }else if(op == 2){
            cin>>x>>y;
            x = find(x),y = find(y);
            if(x == y) continue;
            if(cmp(y,x)) swap(x,y);
            p[y] = x;
            merge(x,y);
        }else if(op == 3){
            cin>>x;
            cout<<v[find(x)]<<endl;
        }else{
            cin>>x;
            x = find(x);
            if(cmp(r[x],l[x])) swap(r[x],l[x]);
            p[x] = l[x],p[l[x]] = l[x];
            merge(l[x],r[x]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

dys
13天前
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int a[N];
int main(){
    int res,ans=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    if(n%2==1) res=a[n/2+1];
    else res=a[n/2];
    for(int i=1;i<=n;i++) ans+=abs(a[i]-res);
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 3164. 线性基

dys
13天前
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5+10;
typedef long long ll;
ll a[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int k = 0;
    for(int i=62;i>=0;i--){
        for(int j=k;j<n;j++)
            if(a[j] >> i & 1)
            {
                swap(a[k],a[j]);
                break;
            }
        if(!(a[k]>>i&1)) continue;
        for(int j=0;j<n;j++)
            if(j!=k && a[j] >> i & 1)
                a[j]^=a[k];
        k++;
        if(k == n) break;
    }
    ll ans = 0;
    for(int i=0;i<k;i++) ans^=a[i];
    cout<<ans<<endl;
    return 0;
}


新鲜事 原文

dys
14天前
AcWing《寒假每日一题》拼团优惠!https://www.acwing.com/activity/content/introduction/37/group_buy/3706/


活动打卡代码 AcWing 1310. 数三角形

dys
14天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
ll C(int a){
    return (ll)a*(a-1)*(a-2)/6;
}
int main(){
    cin>>n>>m;
    n++,m++;
    ll res = C(n*m)-m*C(n)-n*C(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            res-=2ll*(gcd(i,j)-1)*(n-i)*(m-j);//i,j为长度
        }
    }
    cout<<res<<endl;
    return 0;
}



dys
14天前
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        unordered_map<int,int> cnt;
        int n = nums.size();
        for(int i=0;i<n;i++){
            cnt[nums[i]]++;
        }
        vector<int>f(10001,0);
        int res = 0;
        f[0] = 0;
        for(int i=1;i<10001;i++){
            f[i] = cnt[i]*i;
            if(i>=2 && cnt.count(i)) f[i] = max(f[i-1],f[i-2]+cnt[i]*i);
            res = max(res,f[i]);
        }
        return res;
   }
};


活动打卡代码 AcWing 265. 营业额统计

dys
15天前

操作之后一定要splay到根节点

#include<bits/stdc++.h>
using namespace std;
const int N = 4e4+10,INF = 1e9;
typedef long long ll;
struct node{
    int s[2],p,v;
    int size;
    void init(int _p,int _v){
        p = _p;
        v = _v;
        size = 1;
    }
}tr[N];
int root,idx;
void pushup(int x){
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x){
    int y = tr[x].p ,z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k^1];
    tr[tr[x].s[k^1]].p = y;
    tr[x].s[k^1] = y;
    tr[y].p = x;
    pushup(y);
    pushup(x);
}
void splay(int x,int k){
    while(tr[x].p != k){
        int y = tr[x].p,z = tr[y].p;
        if(z!=k)
            if((tr[y].s[1] == x)^(tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}
void insert(int v){
    int u = root,p = 0;
    while(u) p = u,u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(p,v);
    splay(u,0);
}
int get_prev(int v){
    int u = root,res = 0;
    while(u){
        if(tr[u].v <= v) res = u,u = tr[u].s[1];
        else u = tr[u].s[0];
    }
    //splay(u,0);
    // if(res){
    //     splay(res,0);
    //     return tr[res].v;
    // }
    return res;
}
int get_next(int v){
    int u = root,res = 0;
    while(u){
        if(tr[u].v >= v) res = u,u = tr[u].s[0];
        else u = tr[u].s[1];
    }
    // if(res){
    //     splay(u,0);
    //     return tr[res].v;
    // }
    return res;
}
int main(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    insert(-INF);
    insert(INF);
    insert(x);
    ll res = x;
    --n;
    while(n--){
        cin>>x;
        int a = tr[get_prev(x)].v;
        int b = tr[get_next(x)].v;
        res+=min(abs(a-x),abs(b-x));
        splay(get_prev(x),0);
        splay(get_prev(x),0);
        insert(x);
    }
    cout<<res<<endl;
    return 0;
}