2017.10.27 오프라인 경기 총결산

stone ——4127

사고방식: 최대치가 가장 작고 뚜렷한 2점 답안.

substring ——4128

사고방식: 방안의 수를 구하고 뿌리 조건이 반사되는 것을 보면 머리가 없는 dp이다. 정의에 대해 모두 다르지만 공통된 것은 모두 dp[i][j]가 있다. 이것은 앞의 i개가 j번을 선택했기 때문에 쉽게 옮겼다는 것을 의미한다. 다시 접두사와 롤러 그룹을 최적화하면 된다.

#include
#define REP(i,f,t ) for(int i=(f),i##_end_=(t);i<=i##_end_;i++)
#define DREP(i,f,t ) for(int i=(f),i##_end_=(t);i>=i##_end_;i--)
#define LL long long
#define INF 0x3f3f3f3f
#define N 1005
#define M 205
#define P 1000000007
using namespace std;
int n,m,k;
struct p10{// n<=500 m<=50
    string s1,s2;
    void solve(){
        cin>>s1>>s2;
        LL ans=0;
        REP(i,0,n-m)if(s1.substr(i,m)==s2)ans++;
        cout<struct p70{
    char s1[N],s2[M];
    LL dp[2][N][M][2];
    void solve(){
        scanf("%s%s",s1+1,s2+1);
        dp[0][0][0][0]=dp[1][0][0][0]=1;
        REP(i,1,n){
            int now=i&1;
            REP(j,1,min(i,m))
                REP(l,1,k){
                    dp[now][j][l][0]=(dp[now^1][j][l][0]+dp[now^1][j][l][1])%P;
                    if(s1[i]==s2[j])dp[now][j][l][1]=((dp[now^1][j-1][l-1][0]+dp[now^1][j-1][l-1][1])%P+dp[now^1][j-1][l][1])%P;
                    else dp[now][j][l][1]=0;
                }
        }
        printf("%lld",(dp[n&1][m][k][0]+dp[n&1][m][k][1])%P);
    }
}p70;
int main(){
//  freopen("substring.in","r",stdin);
//  freopen("substring.out","w",stdout);
    cin>>n>>m>>k;
    if(k==1)p10.solve();
    else p70.solve();
    return 0;
}

transport ——4129

사고방식: 2분의 답안, 나무 사슬을 나누거나 배로lca를 구한다. 그리고 나무의 차이점, 접두사와 약간의 dfs 순서가 있다.
풀기 1:

#include
#define REP(i,f,t ) for(int i=(f),i##_end_=(t);i<=i##_end_;i++)
#define DREP(i,f,t ) for(int i=(f),i##_end_=(t);i>=i##_end_;i--)
#define LL long long
#define INF 0x3f3f3f3f
#define N 300005
#define T 19
using namespace std;
int n,m,x,y,z,Max,cnm;
int D[N],dis[N],val[N],num[N],tmp[N],fa[N][T+5];
struct node{
    int x,y,lca,dis;
}Q[N];
struct Node{
    int to,cost;
};
vectorE[N];
void dfs(int x,int f){
    num[++cnm]=x;
    REP(i,1,T-1){
        if((D[x]-(1<1)break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    REP(i,0,E[x].size()-1){
        Node y=E[x][i];
        if(y.to==f)continue;
        fa[y.to][0]=x;
        D[y.to]=D[x]+1;
        dis[y.to]=dis[x]+y.cost;
        val[y.to]=y.cost;
        dfs(y.to,x);
    }
}
void Up(int &x,int step){
    DREP(i,T-1,0)if(step&(1<int Lca(int x,int y){
    if (D[x]>D[y])swap(x,y);
    Up(y,D[y]-D[x]);
    if(x==y)return x;
    DREP(i,T-1,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
bool check(int mid){
    int cnt=0,limit=0;
    memset(tmp,0,sizeof(tmp));
    REP(i,1,m)
        if (Q[i].dis>mid){
            ++tmp[Q[i].x];
            ++tmp[Q[i].y];
            tmp[Q[i].lca]-=2;
            limit=max(limit,Q[i].dis-mid);
            cnt++;
        }
    if(!cnt)return 1;
    DREP(i,n,2)tmp[fa[num[i]][0]]+=tmp[num[i]];
    REP(i,2,n)if(val[i]>=limit&&tmp[i]==cnt) return 1;
    return 0;
}
int main(){
//  freopen("transport.in","r",stdin);
//  freopen("transport.out","w",stdout);
    cin>>n>>m;
    int L=0,R=0,ans;
    REP(i,1,n-1){
        scanf("%d%d%d",&x,&y,&z);
        E[x].push_back((Node){y,z});
        E[y].push_back((Node){x,z});
        R+=z;
    }
    dfs(1,0);
    REP(i,1,m){
        scanf("%d%d",&Q[i].x,&Q[i].y);
        Q[i].lca=Lca(Q[i].x,Q[i].y);
        Q[i].dis=dis[Q[i].x]+dis[Q[i].y]-dis[Q[i].lca]*2;
    }
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid))ans=mid,R=mid-1;
        else L=mid+1;
    }
    cout<

풀이2:

#include
#define REP(i,f,t ) for(int i=(f),i##_end_=(t);i<=i##_end_;i++)
#define DREP(i,f,t ) for(int i=(f),i##_end_=(t);i>=i##_end_;i--)
#define LL long long
#define INF 0x3f3f3f3f
#define N 300005
#define M 19
using namespace std;
int n,m;

int D[N],fa[N],son[N],sz[N],top[N],dis[N];//shu pou
int val[N],sum[N],dp[N];
int Lt[N],Rt[N],List[N],T;//dfs xu

struct node{
    int to,cost;
};
vectorE[N];

struct Node{
    int from,to,lca,dis;
    bool operatorconst Node &a)const{
        return dis>a.dis;
    }
}Q[N];
void dfs1(int x,int f){
    D[x]=D[f]+1;
    fa[x]=f;
    sz[x]=1;
    REP(i,0,E[x].size()-1){
        node y=E[x][i];
        if(y.to==f)continue;
        dis[y.to]=dis[x]+y.cost;
        val[y.to]=y.cost;
        dfs1(y.to,x);
        sz[x]+=sz[y.to];
        if(sz[y.to]>sz[son[x]])son[x]=y.to;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    Lt[x]=++T;
    List[T]=val[x];
    if(!son[x])return;
    dfs2(son[x],tp);
    REP(i,0,E[x].size()-1){
        node y=E[x][i];
        if(y.to==fa[x] || y.to==son[x])continue;
        dfs2(y.to,y.to);
    }
    Rt[x]=T;
}
int Lca(int a,int b){
    while(top[a]!=top[b]){
        if(D[top[a]]return D[a]void solve(int a,int b){
    while(top[a]!=top[b]){
        if(D[top[a]]1]--;
        a=fa[top[a]]; 
    }
    if(a==b)return;
    if(D[a]>D[b])swap(a,b);
    sum[Lt[a]+1]++,sum[Lt[b]+1]--;
}
bool check(int mid){
    int Sz=0;
    while(Q[Sz+1].dis>mid)Sz++;
    if(dp[Sz])return Q[1].dis-dp[Sz]<=mid;
    memset(sum,0,sizeof(sum));
    REP(i,1,Sz)solve(Q[i].from,Q[i].to);
    int Mx=0,tot=0;
    REP(i,1,n){
        tot+=sum[i];
        if(tot==Sz)Mx=max(Mx,List[i]);
    }
    dp[Sz]=Mx;
    return Q[1].dis-dp[Sz]<=mid;
}
int main(){
//  freopen("transport.in","r",stdin);
//  freopen("transport.out","w",stdout);
    cin>>n>>m;
    REP(i,1,n-1){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        E[a].push_back((node){b,c});
        E[b].push_back((node){a,c});
    }
    dfs1(1,0);
    dfs2(1,1);
    REP(i,1,m){
        scanf("%d%d",&Q[i].from,&Q[i].to);
        Q[i].lca=Lca(Q[i].from,Q[i].to);
        Q[i].dis=dis[Q[i].from]+dis[Q[i].to]-dis[Q[i].lca]*2;
    }
    sort(Q+1,Q+1+m);
    int L=0,R=Q[1].dis,ans;
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid))ans=mid,R=mid-1;
        else L=mid+1;
    }
    cout<

소결: 두 번째 문제의 dp는 아직 좀 느리게 풀었어. 정의할 때 오래 걸렸어. 그래서 세 번째 문제는 급하게 쳤고 두 번 잘못 쳤어...