题目连接：http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1524

牛客题目链接：2019牛客国庆集训派对day1

可补题：B、G

前三个题我就不写题解了，前三个题水题。

F题

是一个排列的问题吧，依次分配即可。先将n往左，0次往上。然后n-1次往左，1次往上。。以此类推，直到0次往左，n次往上。

 

其他三个也是如此，单独一个象限内来看，其实就是一个等差数列。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    ll n,a,b,c,d;
    while(~scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d))
    {
        ll m=n;
        --n;
        ll a1=a,d1=a;
        ll s1=(n*a%mod+n*(n-1)/2%mod*a%mod)%mod*b%mod;
        ll s2=(n*a%mod+n*(n-1)/2%mod*a%mod)%mod*d%mod;
        a1=c,d1=c;
        ll s3=(n*c%mod+n*(n-1)/2%mod*c%mod)%mod*b%mod;
        ll s4=(n*c%mod+n*(n-1)/2%mod*c%mod)%mod*d%mod;
        ll ans=s1+s2+s3+s4%mod;
        ll t=m*a%mod+m*b%mod+m*c%mod+m*d%mod;
        printf("%lld\n",(ans+t+1)%mod);
    }
}

I 题

补了沈阳网络赛那题来写这题简直分分钟就秒了。

设dp[u][j]为u节点到子树中某个节点距离模2019等于j的数量。

那么转移方程就是dp[u][(j+w)%2019]+=dp[son][j]，dp[u][w]++

dp[u][w]++,因为u到v节点距离为w，产生一个距离w

 

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
vector<int>G[N],val[N];
int n,u,v,w;
int dp[N][2300];
void dfs(int u,int fa)
{
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        int w=val[u][i];
        if(v==fa) continue;
        dfs(v,u);
        dp[u][w]++;
        for(int j=0;j<2019;++j)
        {
            dp[u][(j+w)%2019]+=dp[v][j];
        }
    }
}
int ans;
void dfs2(int u,int fa)
{
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        int w=val[u][i];
        if(v==fa) continue;
        int t[2300];
        for(int j=0;j<2019;++j)
        {
            t[(j+w)%2019]=dp[u][(j+w)%2019]-dp[v][j];
        }
        t[w]--;

        dp[v][w]++;
        for(int j=0;j<2019;++j)
        {
            dp[v][(j+w)%2019]+=t[j];
        }
        ans+=dp[v][0];
        dfs2(v,u);
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;++i) {
            G[i].clear(),val[i].clear();
            for(int j=0;j<2019;++j) dp[i][j]=0;
        }
        ans=0;
        for(int i=1;i<n;++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(v);
            G[v].push_back(u);
            val[u].push_back(w);
            val[v].push_back(w);
        }
        dfs(1,-1);
        ans+=dp[1][0];
        dfs2(1,-1);
        printf("%d\n",ans/2);
    }
}

 

另一个有意思的换根过程：

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
vector<int>G[N],val[N];
int n,u,v,w;
int dp[N][2300];
void dfs(int u,int fa)
{
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        int w=val[u][i];
        if(v==fa) continue;
        dfs(v,u);
        dp[u][w]++;
        for(int j=0;j<2019;++j)
        {
            dp[u][(j+w)%2019]+=dp[v][j];
        }
    }
}
int ans;
void dfs2(int u,int fa)
{
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        int w=val[u][i];
        if(v==fa) continue;
        //printf("v:%d\n",v);
        int t[2300];
        for(int j=0;j<2019;++j) t[j]=dp[u][j];//保存之前的信息
        
        dp[u][w]--;///开始退化dp
        for(int j=0;j<2019;++j)
            dp[u][(j+w)%2019]-=dp[v][j];


        dp[v][w]++;//换根dp开始
        for(int j=0;j<2019;++j)
            dp[v][(j+w)%2019]+=dp[u][j];
            
        ans+=dp[v][0];
        dfs2(v,u);
        for(int j=0;j<2019;++j) dp[u][j]=t[j];//还原

    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;++i) G[i].clear(),val[i].clear();
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<2019;++j) dp[i][j]=0;
        }

        ans=0;
        for(int i=1;i<n;++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(v);
            G[v].push_back(u);
            val[u].push_back(w);
            val[v].push_back(w);
        }
        dfs(1,-1);
        ans+=dp[1][0];
        dfs2(1,-1);
        printf("%d\n",ans/2);
    }
}

K 双向链表

很久没写双向链表了，我看到这题就抵触了，交给队友搞，没搞出来。

下午花了两节课，问了中南的大佬好多问题才勉强A的。

我一直纠结于链表内next和pre指针乱了怎么办，其实不用管他，乱就乱我只要判断 p->next->next!=p 那么p->next->next就是往下走就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    int x;
    node *next;
    node *pre;
    node(){}
};
vector<int>ans;
struct edge
{
    node *it;
}head[N],tail[N];
int n,m;
 
void init()
{
    for(int i=1;i<=n;++i)
    {
        head[i].it=new node();
        tail[i].it=new node();
        node *p;p=new node();
        p->x=i;
        head[i].it->next=p;
        p->pre=head[i].it;
        p->next=tail[i].it;
        tail[i].it->pre=p;
        head[i].it->pre=NULL;
        tail[i].it->next=NULL;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=m;++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            if(head[u].it==NULL&&head[v].it!=NULL)
            {
                head[u].it=tail[v].it;
                tail[u].it=head[v].it;
                head[v].it=NULL;
                tail[v].it=NULL;
                continue;
            }
            else if(head[v].it==NULL&&head[u].it!=NULL)
            {
                swap(head[u].it,tail[u].it);
                continue;
            }
            else if(head[v].it==NULL&&head[u].it==NULL)
            {
                continue;
            }
 
            node *p1,*p2;
            if(tail[u].it->next!=NULL)p1=tail[u].it->next;
            else p1=tail[u].it->pre;
 
            if(head[v].it->next!=NULL)p2=head[v].it->next;
            else p2=head[v].it->pre;
 
            if(p1->next==tail[u].it) p1->next=p2;
            else p1->pre=p2;
            if(p2->next==head[v].it) p2->next=p1;
            else p2->pre=p1;
 
            tail[u].it=head[u].it;
            head[u].it=tail[v].it;
 
            head[v].it=NULL;
            tail[v].it=NULL;
        }
        node *p=head[1].it;
        if(p==NULL)
        {
            printf("0\n");
            continue;
        }
        node *pr=p;
        if(p->next!=NULL) p=p->next;
        else p=p->pre;
        ans.clear();
        while(p!=tail[1].it){
            ans.push_back(p->x);
            if(p->next!=pr)
            {
                pr=p;
                p=p->next;
            }
            else {
                pr=p;
                p=p->pre;
            }
        }
        printf("%d ",ans.size());
        for(int v:ans) printf("%d ",v);
        puts("");
        for(int i=1;i<=n;++i) free(head[i].it),free(tail[i].it);
    }
}