“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛) ADGI

点对最大值

题意

这里有一棵树，每个点和每条边都存在一个价值。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。
求这颗树上最大的点对价值为多少。点对至少需要两个点。

思路

典型树形dp，当时看题太快了，没注意到必须要两个点。
定义 $dp[i]$ 表示为 $i$ 的一条子链的的最大价值（只包含一个点权）。
显然转移方程为 $dp[u] = dp[v] + cost[u,v]$ 。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 2001110;
const int M = 1e9+7;
int n,ans;

int a[maxn];

int head[maxn],cost[maxn],to[maxn],Next[maxn],cnt = 2;

void add(int u,int v,int w)
{
    to[cnt] = v;cost[cnt] = w;Next[cnt] = head[u];head[u] = cnt;cnt++;
}

int dp[maxn];

//至少两个点

void dfs(int u,int pre)
{  
    dp[u] = a[u];
    for(int i = head[u]; i ; i = Next[i])
    {
        int v = to[i];
        if(v == pre) continue;
        dfs(v,u);
        ans = max(ans,dp[u]+dp[v]+cost[i]);
        dp[u] = max(dp[u],dp[v]+cost[i]);
    }
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 1; i <= n; i++)
        {
            head[i] = 0;
        }
        cnt=2;ans = -1000;
        for(int i = 2,x,y; i <= n; i++)
        {
            cin>>x>>y;
            add(i,x,y);add(x,i,y);
        }
        for(int i = 1; i <= n; i++)
        {
            cin>>a[i];
        }
        dfs(1,1);
        cout<<ans<<endl;
    }
    return 0;
}

扔硬币

题意

有n枚硬币，每枚硬币扔出来是正面和反面的概率各占50%。小明同时扔下了n枚硬币后，已知至少有m枚硬币是反面。请问恰好有k枚硬币是正面的概率是多少。

思路

比赛看了半天没看懂题意，就是抛硬币，会有许多情况，就是问在全部情况中（除去m枚以下硬币朝下的情况）恰好k枚硬币朝上的概率是多少？
我们可以用k枚朝上的样本数除以总的样本数

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,ok;

int inv[maxn];

void init()
{   
    inv[1] = 1;
    for(int i = 2; i < maxn; i++) 
    {
        inv[i] = (M-M/i)*inv[M%i]%M;
    }
}

int c(int x,int y) 
{   
    if(y > x) return 0;
    int res = 1;
    y = min(y,x-y);
    for(int i = 1; i <= y; i++) 
    {
        res = (res*(x-i+1)%M*inv[i])%M;
    }
    return res;
}

int ksm(int a,int b)
{
    int res = 1;
    while (b)
    {
        if(b&1) res = (res*a)%M;
        a = (a*a)%M;
        b /= 2;
    }
    return res%M;
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    init();
    while(T--)
    {
        cin>>n>>m>>k;
        int b = 1,a = 1;
        if(m+k > n) cout<<0<<endl;
        else
        {   
            int x = 1;
            for(int i = 1; i < m; i++) 
            {
                x = x*(n-i+1)%M*inv[i]%M;
                b = (b+x)%M;
            }
            b = (ksm(2,n)-b+M)%M;
            a = c(n,k);
            cout<<(a*ksm(b,M-2)%M)<<endl;
        }
    }
    return 0;
}

养花

题意

题目太长了，不说了，当你知道这题是用网络流来解决的时候你已经做出来了。
建一个虚拟起点，然后k点就是终点，跑最大流就行了

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 110;
const int maxm = 201110;
const int M = 1e9+7;
int n,m,s,t;

int a[maxn],b[maxn][maxn];

int head[maxn],cost[maxm],to[maxm],Next[maxm],cnt = 2;

void ad(int u,int v,int w)
{
    to[cnt] = v;cost[cnt] = w;Next[cnt] = head[u];head[u] = cnt;cnt++;
}

void add(int u,int v,int w)
{
    ad(u,v,w);ad(v,u,0);
}

int level[maxn];

int bfs()
{
    mem(level,0);
    level[s] = 1;
    queue<int> q;q.push(s);
    while(!q.empty())
    {
        int u = q.front();q.pop();
        for(int i = head[u]; i ; i = Next[i])
        {
            int v = to[i];
            if(cost[i] > 0 && level[v] == 0)
            {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t];
}

int dfs(int u,int flow)
{
    if(u == t) return flow;
    int res = flow;
    for(int i = head[u]; i ; i = Next[i])
    {
        if(res == 0) break;
        int v = to[i];
        if(cost[i] && level[v] == level[u]+1)
        {
            int k = dfs(v,min(res,cost[i]));
            res -= k;cost[i] -= k;cost[i^1] += k;
        }
    }
    return flow-res;
}

int dinic()
{
    int ans = 0;
    while(bfs())
    {
        ans += dfs(s,inf);
    }
    return ans;
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>t;s = 101;
        mem(a,0);mem(b,0);
        mem(head,0);cnt = 2;
        for(int i = 1,x; i <= n; i++) 
        {
            cin>>x;
            a[x]++;
        }
        for(int i = 1; i <= 100; i++) 
        {
            if(a[i]) add(s,i,a[i]);
        }
        int op,x;
        int a1,a2,b1,b2;
        while(m--)
        {
            cin>>op>>x;
            if(op == 1)
            {
                cin>>a1>>b1;
                b[a1][b1] += x;
            }
            else if(op == 2)
            {
                cin>>a1>>a2>>b1;
                for(int i = a1; i <= a2; i++) 
                {
                    b[i][b1] += x;
                }
            }
            else if(op == 3)
            {
                cin>>a1>>b1>>b2;
                for(int i = b1; i <= b2; i++) 
                {
                    b[a1][i] += x;
                }
            }
            else
            {
                cin>>a1>>a2>>b1>>b2;
                for(int i = a1; i <= a2; i++) 
                {
                    for(int j = b1; j <= b2; j++) 
                    {
                        b[i][j] += x;
                    }
                }
            }
        }
        for(int i = 1; i <= 100; i++) 
        {
            for(int j = 1; j <= 100; j++) 
            {
                if(b[i][j]) add(i,j,b[i][j]);
            }
        }
        cout<<dinic()<<endl;
    }
    return 0;
}

字典序

题意

小明遇到了一个问题希望你能帮他解决
现在有n个数字排成一列构成数组A，数组A中存在n个数a[i], 其中1<=i<=n。
数组sj为删除数组A中的第j个数后，剩余n-1个数构成的数组，其中1<=j<=n。
小明希望你把s1~sn的数组按照字典序大小排列起来，
若两个数组相等，则认为删除元素编号小的数组字典序更小

思路

我也是看了题解之后才想出来的，感觉很奇妙。 $if(a[i] == a[i+1)$ 说明删去 $i$ 或者 $i+1$ 的序列一模一样，不过删 $i$ 的字典序会更小 $if(a[i] < a[i+1)$ 说明删去 $i$ 的序列会比删去任何一个大于 $i$ 的序列的字典序大，因为删去 $i$ 的序列第 $i$ 位是 $a[i+1]$ ，而删去大于 $i$ 的序列第 $i$ 位是 $a[i]$ ，显然字典序会更小。
同理， $if(a[i] < a[i+1)$ 情况则相反

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,ok;

int a[maxn];

int ans[maxn];

struct node
{
    int id,x;
    bool operator < (const node tmp) const
    {
        if(x == tmp.x) return id < tmp.id;
        return x < tmp.x;
    }
}b[maxn];

int dfs(int i,int k)
{   
    if(i == n)
    {
        ans[i] = k;
        return ans[i];
    }
    if(a[i] == a[i+1])
    {
        ans[i] = dfs(i+1,k);
    }
    if(a[i] < a[i+1])
    {
        ans[i] = k+(n-i);
        dfs(i+1,k);
    }
    if(a[i] > a[i+1])
    {
        ans[i] = k;
        dfs(i+1,k+1);
    }
    return ans[i];
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 1; i <= n; i++) 
        {
            cin>>a[i];
        }
        dfs(1,1);
        for(int i = 1; i <= n; i++) 
        {
            //cout<<ans[i]<<' ';
            b[i].id = i;
            b[i].x = ans[i];
        }
        sort(b+1,b+1+n);
        for(int i = 1; i <= n; i++) 
        {
            cout<<b[i].id<<' ';
        }
        cout<<endl;
    }
    return 0;
}