CCPC-Wannafly Winter Camp Day8 Div2

Aqours

时间复杂度O(N)的题解:根据题目规定的条件,显然从每个叶子节点暴力往上面跳,并且在一路上记录从叶子节点到当前点的距离,直到找到一个已经被记录过的点,答案就是那个点上记录的值加上当前点到这个点的距离,并且在从那个点饭回来的路上要尝试用从那个点到这条路径的距离更新每个点记录的最近的叶子结点的距离。

#include <bits/stdc++.h>

const int MAXN = 3000005;

using namespace std;

int n,fa[MAXN],Min[MAXN],in[MAXN],tmp,ans;

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

void dfs(int x)
{
    if(Min[x]) {
        ans = tmp + Min[x];
        Min[x] = min(Min[x],tmp);
        return;
    }
    else Min[x] = tmp;
    if(x == 1) return;
    tmp++;
    dfs(fa[x]);
    Min[x] = min(Min[x],Min[fa[x]]+1);
}

int main()
{
    n = read();
    
    if(n == 1){
        printf("1 -1\n");
        return 0;
    } 
    
    for(int i = 2;i <= n;i++){
        fa[i] = read();
        in[fa[i]]++;        
    }
    
    for(int i = 2;i <= n;i++)
        if(!in[i]){
            tmp = 1;ans = 0;
            dfs(fa[i]);
            if(ans == 0) printf("%d -1\n",i);
            else printf("%d %d\n",i,ans);
            
        }
    
    return 0;
}

时间复杂度O($nlogn$)的题解:第一遍DFS找个到每个节点编号最小的叶子节点的编号,然后对每个节点按照叶子节点编号排序,第二遍DFS从根节点按照上述排序过后的顺序访问整棵树,并且在访问的过程总维护从最近的叶子节点到当前点的距离

#include <bits/stdc++.h>

const int MAXN = 3000005,MAXD = 22;

using namespace std;

int n,Max[MAXN],Min[MAXN],last,tmp,top;

vector<int>E[MAXN];

pair<int,int>ans[MAXN];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;    
}

inline void init()
{
    n = read();
    int u;
    for(int i = 2;i <= n;i++){
        u = read();
        E[u].push_back(i);
    }
    
}

void dfs1(int u){

    if(E[u].size() == 0){
        Max[u] = u;
        return;
    }
    else for(int i = 0;i < E[u].size();i++){
        int v = E[u][i];
        
        dfs1(v);
        if(!Max[u]) Max[u] = Max[v];
        else Max[u] = min(Max[v],Max[u]);
   
    }
}

void dfs2(int u)
{
    if(E[u].size() == 0){
        if(last == 0) {
            ans[++top].first = u;
            ans[top].second = -1;
            last = 1;
            tmp = 1;
        }
        else {
            ans[++top].first = u;
            ans[top].second = tmp;
            tmp = 1;        
        }
        return;
    }
    
    else for(int i = 0;i < E[u].size();i++){
        int v = E[u][i];
        if(Min[u]) tmp = min(tmp,Min[u]);
        tmp++;
        
        if(last) {//最重要的改动的地方,我们往下面走的时候要更新下面的点 来保证每个点的Min[u]都是正确的 
            if(Min[v]) Min[v] = min(Min[v],tmp);
            else Min[v] = tmp;
        }
        
        dfs2(v);
        if(Min[u]) Min[u] = min(Min[u],tmp);
        else if(last) Min[u] = tmp;
    }
    if(Min[u] && last) tmp = min(Min[u],tmp);//往上面走的时候要更新tmp 因为我们原来可能来过这个点 
    tmp++;
}

inline bool cmp(const int &A,const int &B){
    return Max[A] < Max[B];
}

int main()
{
    //freopen("input.txt","r",stdin); 
    init();
    //if(n == 1) return 0;
    dfs1(1);
    
    for(int i = 1;i <= n;i++)
        if(E[i].size())
            sort(E[i].begin(),E[i].end(),cmp);
    
    dfs2(1);
    
    /*for(int i = 1;i <= n;i++)
        printf("Min[%d]=%d\n",i,Min[i]);*/
    
    sort(ans+1,ans+top+1);
    
    for(int i = 1;i <= top;i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
            
    return 0;
}

吉良吉影的奇妙计划
题解:优化DFS,加打表,占个坑标准解答以后再写

#include <bits/stdc++.h>
using namespace std;

const int MOD=998244353;
int n;
int nu;
int ans=0;
int dfs(int i,int num0,int num1,int now){
    
    if((nu-i)<abs(num0-num1))
        return 0;
    
    
    if(i==nu){
        if(num0==num1){
            ans++;ans%=MOD;
        }    
        return 0;
    }
    if(i>nu)
        return 0;
    
    if(now==0){
        dfs(i+1,num0+1,num1,0);
        dfs(i+2,num0,num1,2);
    }
    if(now==1){
        dfs(i+1,num0,num1+1,1);
        dfs(i+2,num0,num1,2);        
    }
    if(now==2){
        dfs(i+1,num0+1,num1,0);
        dfs(i+1,num0,num1+1,1);
    }
    return 0;
}

int main()
{    
    scanf("%d",&n);
    
    switch(n){
        case 20: printf("149589348");return 0;
        case 19: printf("53341428");return 0;
        case 18: printf("19045612");return 0;
        case 17: printf("6810102");return 0;
    }
    
    nu=2*n;
    dfs(1,1,0,0);
    dfs(1,0,1,1);
    dfs(2,0,0,2);
    
    printf("%d",ans);
    
    return 0;
 }

穗乃果的考试
题解:我优秀的队友写的,占坑,待补

#include <bits/stdc++.h>
using namespace std;
int A[2222][2222];
const int MOD=998244353;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    char num;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        char N[2222];
        scanf("%s",N+1);
        
        for(int j=1;j<=m;j++)
        {
            char num=N[j];

            if(num=='1')
            {

                ans+=(long long)i*(n-i+1)%MOD*j%MOD*(m-j+1)%MOD;
                ans%=MOD;
            }
            
        }
    }
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    
    printf("%lld",ans);
    
    return 0;
 }
Last modification:January 29th, 2019 at 04:35 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment