头像

linjunhao2009

台三小




在线 


最近来访(21)
用户头像
khalil
用户头像
zombotany
用户头像
acmdyh
用户头像
氢氧化氢
用户头像
Liu_7
用户头像
我要出去乱说
用户头像
JYLeeLYJ
用户头像
啦啦啦啦啦_8

活动打卡代码 AcWing 1285. 单词

#include<bits/stdc++.h>

using namespace std;

const int N=200;
const int S=1e6;

map<string,int>m;
string str[N+10];
int n,cnt,q_size;
int tr[S+10][27],sum[S+10],nxt[S+10],ans_num[S+10],flag[S+10],top_num[S+10],id[S+10];

void insert(int x){
    int u=0;
    for(int i=0;i<str[x].size();i++){
        int ch=str[x][i]-'a';
        if(!tr[u][ch])
            tr[u][ch]=++cnt;
        u=tr[u][ch];
        sum[u]++;
    }
    id[x]=u;
//  cout<<"a"<<str<<endl;
//  if(m.find(str)==m.end())
//         m[str]=u;
//  cout<<"a"<<endl;
    return;
}


void build(){
    queue<int>q;
    for(int i=0;i<26;i++){
        if(tr[0][i]){
            q_size++;
            top_num[q_size]=tr[0][i];
            q.push(tr[0][i]);
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=tr[u][i];
            if(!v){
                tr[u][i]=tr[nxt[u]][i];
            }else{
                nxt[v]=tr[nxt[u]][i];
                q_size++;
                top_num[q_size]=v;
                q.push(v);
            }
        }
    }
    return;
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ans=0;
//  cnt=0;
    memset(tr,0,sizeof(tr));
    memset(sum,0,sizeof(sum));
    memset(nxt,0,sizeof(nxt));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>str[i];
        insert(i);
    }
//  cout<<(char)('z'+1);
    build();
    for(int i=q_size;i>=1;i--)
        sum[nxt[top_num[i]]]+=sum[top_num[i]];
    for(int i=1;i<=n;i++){
        printf("%d\n",sum[id[i]]);
    }
    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

#include<bits/stdc++.h>

using namespace std;

const int N=1e4;
const int S=50;

int n,cnt;
int tr[N*S+10][27],sum[N*S+10],nxt[N*S+10];

void insert(string str){
    int u=0;
    for(int i=0;i<str.size();i++){
        int ch=str[i]-'a';
        if(!tr[u][ch])
            tr[u][ch]=++cnt;
        u=tr[u][ch];
    }
    sum[u]++;
    return;
}

void build(){
    queue<int>q;
    for(int i=0;i<26;i++){
        if(tr[0][i])
            q.push(tr[0][i]);
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            int v=tr[u][i];
            if(!v){
                tr[u][i]=tr[nxt[u]][i];
            }else{
                nxt[v]=tr[nxt[u]][i];
                q.push(v);
            }
        }
    }
    return;
}

int main(){
    int t,ans,ch;
    string str;
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%d",&t);
    while(t--){
        ans=0;
        cnt=0;
        memset(tr,0,sizeof(tr));
        memset(sum,0,sizeof(sum));
        memset(nxt,0,sizeof(nxt));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cin>>str;
            insert(str);
        }
        build();
//      for(int i=1;i<=n*3;i++){
//          cout<<nxt[i]<<" ";
//      }cout<<endl;
        cin>>str;
        for(int i=0,u=0;i<str.size();i++){
            ch=str[i]-'a';
            u=tr[u][ch];
            int v=u;
            while(v){
                ans+=sum[v];
                sum[v]=0;
                v=nxt[v];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 252. 树

#include<bits/stdc++.h>

using namespace std;

const int N=1e4;

struct node{
    int to,nxt,w;
}e[N*2+10];

int n,k,cnt,f[N+10],head[N+10],minn=1e9,root,vis[N+10],dep[N+10],d[N+10],siz[N+10],all_node,ans;

void add(int a,int b,int c){
    e[cnt].to=b;
    e[cnt].w=c;
    e[cnt].nxt=head[a];
    head[a]=cnt++;
    return;
}

void get_root(int u,int fa){
    siz[u]=1;
    f[u]=0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]||v==fa)
            continue;
        get_root(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],all_node-siz[u]);
    if(f[u]<f[root]){
        root=u;
    }
    return;
}

void get_dep(int u,int fa){
    dep[++dep[0]]=d[u];
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]||v==fa)
            continue;
        d[v]=d[u]+e[i].w;
        get_dep(v,u);
    }
    return;
}

int get_sum(int u,int dis){
    d[u]=dis;
    dep[0]=0;
    get_dep(u,0);
    sort(dep+1,dep+1+dep[0]);
    int l=1,r=dep[0],sum=0;
    while(l<r){
        if(dep[l]+dep[r]<=k){
            sum+=r-l;
            l++;
        }else{
            r--;
        }
    }
    return sum;
}

void solve(int u){
    vis[u]=true;
        // cout<<"a"<<endl;
    ans+=get_sum(u,0);
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])
            continue;
        // cout<<v<<" ";
        // cout<<ans<<" ";
        ans-=get_sum(v,e[i].w);
        // cout<<ans<<endl;
        all_node=siz[v];
        root=0;
        get_root(v,u);
        // cout<<root<<endl;
        solve(root);
    }
}

int main(){
    int a,b,c;
    while(scanf("%d%d",&n,&k),n,k){
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a+1,b+1,c);
            add(b+1,a+1,c);
        }
        all_node=n;
        f[0]=1e9;
        get_root(1,0);
        ans=0;
        // cout<<root<<endl;
        solve(root);
        // cout<<ans<<endl;
        printf("%d",ans);
    }
    return 0;
}


活动打卡代码 AcWing 2568. 树链剖分

#include<bits/stdc++.h>

using namespace std;

const int N=1e5;
const int INF=1e9;

struct tree{
    int to,nxt;
}e[N+10];

struct node{
    int l,r;
    long long lazy,sum;
}tr[N*4+10];

int n,m,cnt_e,cnt_tr;
int head[N+10],dep[N+10],fa[N+10],siz[N+10],son[N+10],top[N+10],id[N+10];
long long nums[N+10],tw[N+10];

void add(int a,int b){
    e[cnt_e].to=b;
    e[cnt_e].nxt=head[a];
    head[a]=cnt_e++;
}

void dfs(int u,int father,int depth){
    dep[u]=depth;
    fa[u]=father;
    siz[u]=1;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(v==father)
            continue;
        dfs(v,u,depth+1);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]){
            son[u]=v;
        }
    }
    return;
}

void dfs2(int u,int t){
    id[u]=++cnt_tr;
    tw[cnt_tr]=nums[u];
    top[u]=t;
    if(!son[u])
        return;
    dfs2(son[u],t);
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u]||son[u]==v)
            continue;
        dfs2(v,v);
    }
}

void push_up(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    return;
}

void push_down(int u){
    node&root=tr[u];
    node&lc=tr[u<<1];
    node&rc=tr[u<<1|1];
    if(root.lazy){
        lc.lazy+=root.lazy;
        lc.sum+=(lc.r-lc.l+1)*root.lazy;
        rc.lazy+=root.lazy;
        rc.sum+=(rc.r-rc.l+1)*root.lazy;
        root.lazy=0;
    }
    return;
}

void build(int u,int l,int r){
    tr[u]={l,r,0,tw[l]};
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
    return;
}

void update(int u,int l,int r,long long val){
    if(l<=tr[u].l&&r>=tr[u].r){
        tr[u].lazy+=val;
        tr[u].sum+=(long long)(tr[u].r-tr[u].l+1)*val;
        return;
    }
    push_down(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid)
        update(u<<1,l,r,val);
    if(r>mid)
        update(u<<1|1,l,r,val);
    push_up(u);
    return;
}

void update_tree(int x,int k){
    update(1,id[x],id[x]+siz[x]-1,k);
    return;
}

void update_path(int u,int v,long long val){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        update(1,id[top[u]],id[u],val);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    update(1,id[v],id[u],val);
    return;
}

long long query(int u,int l,int r){
    if(l<=tr[u].l&&r>=tr[u].r){
        return tr[u].sum;
    }
    push_down(u);
    int mid=(tr[u].l+tr[u].r)>>1;
    long long ans=0;
    if(l<=mid)
        ans+=query(u<<1,l,r);
    if(r>mid)
        ans+=query(u<<1|1,l,r);
    return ans;
}

long long query_tree(int x){
    return query(1,id[x],id[x]+siz[x]-1);
}

long long query_path(int u,int v){
    long long ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        ans+=query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    ans+=query(1,id[v],id[u]);
    return ans;
}

int main(){
    long long a,b,c;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&nums[i]);
    }
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,-1,1);
    dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d",&a);
        if(a==1){
            scanf("%d%d%lld",&a,&b,&c);
            update_path(a,b,c);
        }else if(a==2){
            scanf("%d%lld",&a,&b);
            update_tree(a,b);
        }else if(a==3){
            scanf("%d%d",&a,&b);
            printf("%lld\n",query_path(a,b));
        }else{
            scanf("%d",&a);
            printf("%lld\n",query_tree(a));
        }
    }
    return 0;
}



#include<bits/stdc++.h>

using namespace std;

const int N=500000;

struct Node{
    int lc,rc;
    long long sum,d;
}tr[N*4+10];

int n,m;
long long nums[N+10];

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

void pushup(Node&u,Node&lc,Node&rc){
    u.sum=lc.sum+rc.sum;
    u.d=gcd(lc.d,rc.d);
    return;
}

void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
    return;
}

void build(int u,int l,int r){
    if(l==r){
        long long b=nums[l]-nums[l-1];
        tr[u].lc=l;
        tr[u].rc=r;
        tr[u].sum=b;
        tr[u].d=b;
        return;
    }
    tr[u].lc=l;
    tr[u].rc=r;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
    return;
}

Node query(int u,int l,int r){
    if(tr[u].lc>=l&&tr[u].rc<=r){
        return tr[u];
    }else{
        int mid=(tr[u].lc+tr[u].rc)>>1;
        if(r<=mid){
            return query(u<<1,l,r);
        }else if(l>mid){
            return query(u<<1|1,l,r);
        }else{
            Node left=query(u<<1,l,r);
            Node right=query(u<<1|1,l,r);
            Node res;
            pushup(res,left,right);
            return res;
        }
    }
}

void insert(int u,int x,long long val){
    if(tr[u].lc==x&&tr[u].rc==x){
        tr[u].sum+=val;
        tr[u].d=tr[u].sum;
        return;
    }
    int mid=(tr[u].lc+tr[u].rc)>>1;
    if(x<=mid){
        insert(u<<1,x,val);
    }else{
        insert(u<<1|1,x,val);
    }
    pushup(u);
    return;
}

int main(){
    char ch[2];
    int n1,n2;
    long long n3;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&nums[i]);
        // cout<<nums[i]<<endl;
    }
    build(1,1,n);
    while(m--){
        scanf("%s%d%d",ch,&n1,&n2);
        if(*ch=='C'){
            scanf("%lld",&n3);
            insert(1,n1,n3);
            if(n2+1<=n)
                insert(1,n2+1,-n3);
        }else{
            Node l=query(1,1,n1);
            Node r={0,0,0,0};
            if(n1+1<=n2){
                r=query(1,n1+1,n2);
            }
            printf("%lld\n",abs(gcd(l.sum,r.d)));
        }
    }
    return 0;
}



#include<bits/stdc++.h>

using namespace std;

const int N=50000; 

struct Node{
    int lc,rc;
    multiset<int>s;
}tr[N*4+10];

int n,m,nums[N+10];

void build(int u,int l,int r){
    tr[u].lc=l;
    tr[u].rc=r;
    tr[u].s.insert(-1e9);
    tr[u].s.insert(1e9);
    for(int i=l;i<=r;i++){
        tr[u].s.insert(nums[i]);
    }
    // cout<<"---"<<l<<" "<<r<<" "<<*tr[u].s.lower_bound(4)<<endl;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    return;
}

int query(int u,int l,int r,int val){
    if(tr[u].lc>=l&&tr[u].rc<=r){
        multiset<int>::iterator it=tr[u].s.lower_bound(val);
        // cout<<" "<<val<<" "<<l<<" "<<r<<" "<<*it<<endl;
        it--;
        // cout<<"  "<<*it<<endl;
        return *it;
    }
    int mid=(tr[u].lc+tr[u].rc)>>1,maxn=0;
    if(l<=mid)
        maxn=max(maxn,query(u<<1,l,r,val));
    if(r>mid)
        maxn=max(maxn,query(u<<1|1,l,r,val));
    return maxn;
}

void insert(int u,int x,int val){
    tr[u].s.erase(tr[u].s.find(nums[x]));
    tr[u].s.insert(val);
    if(tr[u].lc==tr[u].rc)
        return;
    int mid=(tr[u].lc+tr[u].rc)>>1;
    if(x<=mid){
        insert(u<<1,x,val);
    }else{
        insert(u<<1|1,x,val);
    }
    return;
}

int main(){
    int n1,n2,n3;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&nums[i]);
    }
    build(1,1,n);
    while(m--){
        scanf("%d",&n1);
        if(n1==1){
            scanf("%d%d",&n1,&n2);
            insert(1,n1,n2);
            nums[n1]=n2;
        }else{
            scanf("%d%d%d",&n1,&n2,&n3);
            printf("%d\n",query(1,n1,n2,n3));
        }
    }
    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

#include<bits/stdc++.h>

using namespace std;

const int N=100;

int n,m,cnt;
int path[N+10];
int e[N+10][N+10],d[N+10][N+10],p[N+10][N+10];

void dfs(int x,int y){
    if(p[x][y]==0)
        return;
    int z=p[x][y];
    dfs(x,z);
    path[cnt++]=z;
    dfs(z,y);
    return;
}

int main(){
    int a,b,c;
    scanf("%d%d",&n,&m);
    memset(e,0x3f,sizeof(e));
    for(int i=1;i<=n;i++){
        e[i][i]=0;
    }
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        e[a][b]=e[b][a]=min(e[a][b],c);
    }
    memcpy(d,e,sizeof(d));
    int ans=0x3f3f3f3f;
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if(ans>(long long)d[i][j]+e[j][k]+e[k][i]){
                    ans=d[i][j]+e[j][k]+e[k][i];
                    cnt=0;
                    path[cnt++]=k;
                    path[cnt++]=i;
                    dfs(i,j);
                    path[cnt++]=j;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                    p[i][j]=k;
                }
            }
        }
    }
    if(ans==0x3f3f3f3f){
        printf("No solution.");
    }else{
        for(int i=0;i<cnt;i++){
            printf("%d ",path[i]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 366. 看牛

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N=1e4;
const int M=5*1e4;

struct node{
    int to,nxt,flag;
}e[(M<<1)+10];

vector<int>ans;
int n,m,cnt,h[N+10];

void add(int a,int b){
    e[cnt].to=b;
    e[cnt].nxt=h[a];
    h[a]=cnt++;
    return;
}

void print(vector<int>&ans){
    for(int i=ans.size()-1;i>=0;i--){
        printf("%lld\n",ans[i]);
    }
    return;
}

void dfs(int u){
    // cout<<u<<endl;
    // cout<<"---"<<endl;
    // print(ans);
    // cout<<"end"<<endl;
    for(int i=h[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(!e[i].flag){
            e[i].flag=1;
            dfs(v);
            // e[i].flag=0;
        }
    }
    ans.push_back(u);
    return;
}

signed main(){
    int a,b;
    memset(h,-1,sizeof(h));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a,&b);
        add(a,b);
        add(b,a);
    }
    // cout<<ji<<endl;
    dfs(1);
    print(ans);
    return 0;
}


活动打卡代码 AcWing 1184. 欧拉回路

#include<bits/stdc++.h>

using namespace std;

const int N=1e5;
const int M=2*1e5;

struct node{
    int nxt,to,used;
}e[(M<<1)+10];

vector<int>ans;
int n,m,t,cnt,din[N+10],dout[N+10],h[N+10];

void add(int a,int b){
    e[cnt].to=b;
    e[cnt].nxt=h[a];
    // e[cnt].used=0;
    h[a]=cnt++;
    return;
}

void print(){
    for(int i=ans.size()-1;i>=0;i--){
        printf("%d ",ans[i]);
    }
    return;
}

void dfs(int&u){
    // cout<<u<<endl;
    for(int&i=h[u];~i;){
        int v=e[i].to;
        if(e[i].used){
            i=e[i].nxt;
            continue;
        }
        int bian;
        e[i].used=1;
        if(t==1){
            e[i^1].used=1;
            if(i&1){
                bian=-((i>>1)+1);
            }else{
                bian=(i>>1)+1;
            }
        }else{
            bian=i+1;
        }
        i=e[i].nxt;
        dfs(v);
        ans.push_back(bian);
    }
    return;
}

int main(){
    memset(h,-1,sizeof(h));
    int a,b;
    scanf("%d",&t);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        if(t==1){
            add(a,b);
            add(b,a);
        }else{
            add(a,b);
        }
        dout[a]++;
        din[b]++;
        // minn=min(minn,min(a,b));
    }
    if(t==1){
        for(int i=1;i<=n;i++){
            if((din[i]+dout[i])&1){
                printf("NO");
                return 0;
            }
        }
    }else{
        for(int i=1;i<=n;i++){
            if(din[i]!=dout[i]){
                printf("NO");
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(h[i]!=-1){
            dfs(i);
            break;
        }
    }
    if(ans.size()<m){
        printf("NO");
        return 0;
    }
    printf("YES\n");
    // cout<<ji<<endl;
    // cout<<endl;
    print();
    // cout<<ans.size();
    // cout<<"a";
    return 0;
}


活动打卡代码 AcWing 1124. 骑马修栅栏

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N=500;

int n,e[N+10][N+10],d[N+10];
int maxn=0,minn=1e9;

vector<int>ans;

void print(){
    for(int i=ans.size()-1;i>=0;i--){
        printf("%lld\n",ans[i]);
    }
    return;
}

void dfs(int u){
    // cout<<u<<endl;
    for(int v=1;v<=maxn;v++){
        if(e[u][v]){
            e[u][v]--;
            e[v][u]--;
            dfs(v);
        }
    }
    ans.push_back(u);
    return;
}

signed main(){
    int a,b;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a,&b);
        e[a][b]++;
        e[b][a]++;
        d[a]++;
        d[b]++;
        maxn=max(max(a,b),maxn);
        minn=min(min(a,b),minn);
    }
    int ji=minn;
    for(int i=1;i<=maxn;i++){
        if(d[i]&1){
            ji=i;
            break;
        }
    }
    // cout<<ji<<endl;
    dfs(ji);
    // cout<<endl;
    print();
    return 0;
}