hdu第九场多校

﹏ヽ暗。殇╰゛Y 2023-10-12 08:18 13阅读 0赞

02：线段树两次扫描

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define maxn 300005
    struct Line{
         int x,y;char s[10];}a[maxn];
    int n,m,K;
    int cmp1(Line &a,Line &b){
         return a.y<b.y;}
    int cmp2(Line &a,Line &b){
         return a.y>b.y;}
    int x[maxn],tot;
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    
    int lazy[maxn<<2];
    void pushdown(int rt){
        if(lazy[rt]){
            lazy[rt<<1]+=lazy[rt];
            lazy[rt<<1|1]+=lazy[rt];
            lazy[rt]=0;
        } 
    }
    void build(int l,int r,int rt){memset(lazy,0,sizeof lazy);} 
    void update(int L,int R,int val,int l,int r,int rt){
        if(L<=l && R>=r){
            lazy[rt]++;return;
        }
        int m=l+r>>1;
        pushdown(rt);
        if(L<=m)update(L,R,val,lson);
        if(R>m)update(L,R,val,rson);
    }
    int query(int pos,int l,int r,int rt){
        if(l==r)return lazy[rt];
        pushdown(rt);
        int m=l+r>>1;
        if(pos<=m)return query(pos,lson);
        else return query(pos,rson);
    }
    
    int main(){
        int t;cin>>t;
        while(t--){
            tot=0;
            
            cin>>n>>m>>K;
            for(int i=1;i<=K;i++)
                scanf("%d%d%s",&a[i].x,&a[i].y,a[i].s),x[++tot]=a[i].x;
            x[++tot]=0;x[++tot]=n;
            sort(x+1,x+1+tot);
            tot=unique(x+1,x+1+tot)-x-1;
            
            int ans=1;
            sort(a+1,a+1+K,cmp1);//先按y从小到大排序
            build(1,tot,1);
            for(int i=1;i<=K;i++){
                if(a[i].s[0]=='L'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    update(1,pos,1,1,tot,1);
                }
                if(a[i].s[0]=='R'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    update(pos,tot,1,1,tot,1);
                }
                if(a[i].s[0]=='D'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    ans+=query(pos,1,tot,1); 
                }
            }
            
            sort(a+1,a+1+K,cmp2);//按y从大到小排序 
            build(1,tot,1);
            for(int i=1;i<=K;i++){
                if(a[i].s[0]=='L'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    update(1,pos,1,1,tot,1);
                }
                if(a[i].s[0]=='R'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    update(pos,tot,1,1,tot,1);
                }
                if(a[i].s[0]=='U'){
                    int pos=lower_bound(x+1,x+1+tot,a[i].x)-x;
                    ans+=query(pos,1,tot,1); 
                }
            }
            
            cout<<ans<<endl; 
        }
    }

06：思维题+预处理

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<vector>
    #include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    const int maxn=210;
    int t,n;
    int wi[maxn];
    int calc(int i,int j,int k){
        int tmp=100;
        
        int p=k;
        while(tmp>=50 && p>0)
            tmp-=50,p--;
        p=j;
        while(tmp>=20 && p>0)
            tmp-=20,p--;
        p=i;
        while(tmp>=10 && p>0)
            tmp-=10,p--;
        if(tmp)return 0;
        
        tmp=200;
        p=k;
        while(tmp>=50 && p>0)
            tmp-=50,p--;
        p=j;
        while(tmp>=20 && p>0)
            tmp-=20,p--;
        p=i;
        if(tmp)return 1;
        return 2;
    }
    bool v[10][10][10][30];
    void calc1(int a,int b,int c){
        vector<int>vec;
        for(int i=1;i<=a;i++)vec.push_back(1);
        for(int i=1;i<=b;i++)vec.push_back(2);
        for(int i=1;i<=c;i++)vec.push_back(5);
        int W=a+b*2+c*5;
        v[a][b][c][0]=1;
        for(int i=0;i<vec.size();i++)
            for(int j=W;j>=vec[i];j--)
                v[a][b][c][j]|=v[a][b][c][j-vec[i]];
    }
    void init(){
        v[0][0][0][0]=1;
        for(int i=0;i<=9;i++)
            for(int j=0;j<=4;j++)
                for(int k=0;k<=1;k++)
                    calc1(i,j,k);
    }
    
    int main(){
        init();
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++) scanf("%d",&wi[i]);
            int flag=0;
            for(int i=1;i<=n;i++){
                if(wi[i]%10!=0) flag=1;
            }
            if(flag==1){printf("-1\n");continue;}
            
            ll ans=1e17+100;
            
            for(int i=0;i<=9;i++)
                for(int j=0;j<=4;j++)
                    for(int k=0;k<=1;k++){
                        int use=0,flag=0;
                        for(int l=1;l<=n;l++){
                            int f=0,tmp=wi[l]%100,Min=0x3f3f3f3f; 
                            //判tmp
                            if(v[i][j][k][tmp/10]){
                                Min=min(Min,i+j+k+wi[l]/100);
                                f=1;
                            }
                            //判tmp+100
                            if(wi[l]>=tmp+100 && v[i][j][k][(tmp+100)/10]){
                                Min=min(Min,i+j+k+(wi[l]-tmp-100)/100);
                                f=1;
                            }
                            //判tmp+200
                            if(wi[l]>=tmp+200 && v[i][j][k][(tmp+200)/10]){
                                Min=min(Min,i+j+k+(wi[l]-tmp-200)/100); 
                                f=1;
                            } 
                            if(!f){flag=1;break;}
                            use=max(use,Min);
                        }
                        if(!flag)
                            ans=min(ans,1ll*use);
                    }
            
            printf("%lld\n",ans);
        }
        return 0;
    }

05：思维题

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #include <bits/stdc++.h>
    using namespace std;
    #define fi first
    #define se second
    #define pb push_back
    #define mk make_pair
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    #define rp(i,s,t) for(int i=s;i<t;i++)
    #define RP(i,s,t) for(int i=s;i<=t;i++)
    #define DN(i,s,t) for(int i=s;i>=t;i--)
    #define dn(i,s,t) for(int i=s;i>t;i--)
    #define clr(a,b) memset(a,b,sizeof(a))
    #define debug(x) cout<<#x<<' '<<x<<endl
    
    typedef long long ll;
    typedef pair<int,int>pii;
    inline int lowbit(int x){ return x&(-x); }
    template<typename T>
    inline void rd(T&x){
        x=0;int f=1;char ch=getchar();
        while(ch<'0' ||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
        while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
        x*=f;
    }
    char str[110];
    
    int main(){
        int T;cin>>T;while(T--){
            cin>>str;
            int len=strlen(str);
            for(int i=0;i<len;i++){
                if(str[i]=='y')continue;
                else if(str[i]=='z'){
                    str[i]='b';
                    break;
                }else break;
            }
            printf("%s\n",str);
        }
    }

07：树形dp换根法（好题）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define N 200005
    vector<int>G[N];
    int n,u[N],v[N],a[N],down[N],up[N],dp[N][4],len[N][2],d[N];
    void dfs1(int u,int pre,int dep){
        d[u]=dep;    
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(v==pre)continue;
            dfs1(v,u,dep+1);
            int tmp=dp[v][0]+1;
            if(tmp>dp[u][0])swap(dp[u][0],tmp);
            if(tmp>dp[u][1])swap(dp[u][1],tmp);
            if(tmp>dp[u][2])swap(dp[u][2],tmp);
            down[u]=max(down[u],down[v]); 
        }
        down[u]=max(down[u],dp[u][0]+dp[u][1]);
    }
    void dfs2(int u,int pre){
        for(int i=0;i<G[u].size();i++){
         //求出u下不经过u的最长|次长 链 
            int v=G[u][i];
            if(v==pre)continue;
            int tmp=down[v];
            if(tmp>len[u][0])swap(tmp,len[u][0]);
            if(tmp>len[u][1])swap(tmp,len[u][1]);
        }
        for(int i=0;i<G[u].size();i++){
         //边(u,v)将原树分成两棵子树 
            int v=G[u][i];
            if(v==pre)continue; 
            //原树删掉v子树后，求v上的最长链dp[v][3]，同时求出第一种情况的up[v] 
            if(dp[u][0]==dp[v][0]+1){
         //v是u的最深子树 
                dp[v][3]=max(dp[u][3],dp[u][1])+1;
                up[v]=max(dp[u][2],dp[u][3])+dp[u][1]; 
            } 
            else if(dp[u][1]==dp[v][0]+1){
         //v是u的次深子树 
                dp[v][3]=max(dp[u][0],dp[u][3])+1; 
                up[v]=max(dp[u][2],dp[u][3])+dp[u][0];
            }
            else {
         //v是u的其他子树 
                dp[v][3]=max(dp[u][0],dp[u][3])+1;
                up[v]=max(dp[u][1],dp[u][3])+dp[u][0]; 
            }
            //求第二种情况的up[v],也要特别判一下v子树里是否有u下的最长链 
            if(len[u][0]==down[v])up[v]=max(up[v],len[u][1]); 
            else up[v]=max(up[v],len[u][0]);
            dfs2(v,u);
        }
    }
    void init(){
        memset(dp,0,sizeof dp);
        memset(a,0,sizeof a);
        memset(len,0,sizeof len);
        memset(down,0,sizeof down);
        memset(up,0,sizeof up);
        for(int i=1;i<=n;i++)G[i].clear();
    }
    int main(){
        int t;cin>>t;while(t--){
            init();cin>>n;
            for(int i=1;i<n;i++){
                scanf("%d%d",&u[i],&v[i]);
                G[u[i]].push_back(v[i]);
                G[v[i]].push_back(u[i]);
            }
            dfs1(1,1,0);
            dfs2(1,1);
            for(int i=1;i<n;i++){
                int x=u[i],y=v[i];
                if(d[x]<d[y])swap(x,y);
                a[up[x]+1]=max(a[up[x]+1],down[x]+1);
                a[down[x]+1]=max(a[down[x]+1],up[x]+1);
            }
            long long ans=0;
            for(int i=n;i>=1;i--){
                a[i]=max(a[i],a[i+1]);
                ans+=a[i];
            }
            cout<<ans<<'\n';
        }    
    }

转载于:https://www.cnblogs.com/zsben991126/p/11392369.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif