南外Day3

Posted on By 陈麒润

T1&T2&T3

水

T4

背包
dp[i][j]表示使用i个空间和j次半价机会的最高价值

T5

搜索

#include<bits/stdc++.h>
using namespace std;
string s;map<char,int> dy;
int a[45],d2[5],flg,bf=1;
void dfs(int t){
    if(t>4){flg=1;return;}
    for(int j=1;j<=29;j++){
        if(j%10==0) continue;
        if(a[j]<3) continue;
        a[j]-=3;dfs(t+1);a[j]+=3;
        if(flg){return;}
    }
    for(int j=1;j<=27;j++){
        if(j%10==0) continue;
        if(!a[j] || !a[j+1] || !a[j+2]) continue;
        a[j]--;a[j+1]--;a[j+2]--;dfs(t+1);
        a[j]++;a[j+1]++;a[j+2]++;
        if(flg){return;}
    }
}
signed main(){
    cin.tie(0);cout.tie(0);
    dy[&#039;s&#039;]=0;dy[&#039;b&#039;]=10;dy[&#039;c&#039;]=20;
    d2[0]=int(&#039;s&#039;);d2[1]=int(&#039;b&#039;);d2[2]=int(&#039;c&#039;);
    for(int i=1;i<=13;i++){
        cin>>s;
        a[s[0]-&#039;0&#039;+dy[s[1]]]++;
    }
    for(int i=1;i<=29;i++){
        if(i%10==0) continue;
        if(a[i]>3) continue;
        a[i]++;flg=0;
        for(int j=1;j<=29;j++){
            if(j%10==0) continue;
            if(a[j]<2) continue;
            a[j]-=2;dfs(1);a[j]+=2;
            if(flg){break;}
        }
        a[i]--;
        if(flg){bf=0;cout<<i%10<<char(d2[i/10])<<&#039; &#039;;}
    }
    if(bf) cout<<"None";
    return 0;
}

T6

倍增毒瘤，需要维护最大值最小值往上走的最大差往下走的最大差

#include <bits/stdc++.h>
#define MX 1000005
using namespace std;
vector<int> o[MX];
int num,head[MX],dep[MX],k=25,x,y; 
int n,m,s=1,w[MX],f[MX][40],mx[MX][40],mn[MX][40],xc[MX][40],nc[MX][40];
void dfs(int u){
    for(auto v:o[u]){
        if(f[u][0]==v){continue;}
        dep[v]=dep[u]+1;
        f[v][0]=u;
        mx[v][0]=max(w[u],w[v]);
        mn[v][0]=min(w[u],w[v]);
        xc[v][0]=max(0,w[u]-w[v]);
        nc[v][0]=max(0,w[v]-w[u]);
        dfs(v);
    }
}
void cst(){
    for(int i=1;i<=k;i++)
    for(int j=1;j<=n;j++){
    f[j][i]=f[f[j][i-1]][i-1];
    mx[j][i]=max(mx[j][i-1],mx[f[j][i-1]][i-1]);
    mn[j][i]=min(mn[j][i-1],mn[f[j][i-1]][i-1]);
    xc[j][i]=max(max(xc[j][i-1],xc[f[j][i-1]][i-1]),mx[f[j][i-1]][i-1]-mn[j][i-1]);
    nc[j][i]=max(max(nc[j][i-1],nc[f[j][i-1]][i-1]),mx[j][i-1]-mn[f[j][i-1]][i-1]);
    }
}
int getMX(int x,int y){
    int deepx=dep[x]-dep[y],res=0;
    for(int i=k;i>=0;i--)
    if((1<<i)&deepx){
        res=max(res,mx[x][i]);x=f[x][i];
    }
    return res;
}
int getMN(int x,int y){
    int deepx=dep[x]-dep[y],res=INT_MAX;
    for(int i=k;i>=0;i--)
    if((1<<i)&deepx){
        res=min(res,mn[x][i]);x=f[x][i];
    }
    return res;
}
int getUC(int x,int y){
    int deepx=dep[x]-dep[y],res=0,re2=INT_MAX;
    for(int i=k;i>=0;i--)
    if((1<<i)&deepx){
        res=max(res,max(xc[x][i],mx[x][i]-re2));re2=min(re2,mn[x][i]);x=f[x][i];
    }
    return res;
}
int getDC(int x,int y){
    int deepx=dep[x]-dep[y],res=0,re2=0;
    for(int i=k;i>=0;i--)
    if((1<<i)&deepx){
        res=max(res,max(nc[x][i],re2-mn[x][i]));re2=max(re2,mx[x][i]);x=f[x][i];
    }
    return res;
}
int LCA(int x,int y){
    if(dep[x]>dep[y]){swap(x,y);}
    for(int i=k;i+1;i--)
    if(dep[f[y][i]]>=dep[x])
        y=f[y][i];
    if(x==y){return x;}
    for(int i=k;i+1;i--)
    if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    cin.tie(0);cout.tie(0);cin>>n;
    for(int i=1;i<=n;i++){cin>>w[i];}
    for(int i=1;i<n;i++){
        int cs,zj;cin>>cs>>zj;
        o[cs].push_back(zj); 
        o[zj].push_back(cs); 
    } 
    dep[s]=1;
    memset(mn[0],0x3f,sizeof(mn[0]));
    mx[1][0]=mn[1][0]=w[1];
    dfs(s);cst();
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        int z=LCA(x,y);
        int res=getMX(y,z)-getMN(x,z);
        res=max(res,max(getUC(x,z),getDC(y,z)));
        cout<<res<<&#039;\n&#039;;
    } 
    return 0;
}

T7

T8

AC自动机
将每个字符串（ab）转化为（ba）
每个给定的串（a）转化为（a*a）
ac自动机带特判往下跑

训练日志