A – F & B – Acrostic

过水 QWQ…

C – Ordinary Beauty

思路:
一道比较巧妙的数学题。我们其实只需要考虑一位的期望,然后整个序列的期望就是这个的m+1倍。

然后我们考虑如何计算期望。一共是有$n*n$种情况(只考虑一位),如果$d==0$时,显然是有$n$种情况符合要求,如果$d!=0$那么就有$(n-d)*2$种情况符合要求,所以分类讨论一下就好。还有一点就是要注意精度,不要一下除$n*n$,精度损失比较大。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstring>
#define LL long long
using namespace std;

LL n, m, d;

int main()
{
    scanf("%lld%lld%lld", &n, &m, &d);
    double temp;
    if(d==0) temp=n;
    else temp=(n-d)*2;
    printf("%.10lf\n", (double)(m-1)/n*temp/n);
}

D – Saving Snuuk

思路:
比较水的一道图论题,只是题目好难看懂啊。。。其实就是给你一张无向图,每条边有两种权值,然后求在每个点切换权值的最短路。

不难想到建两张图,分别从起点,终点跑SPFA。每个点切换权值的最短路就是到起点,终点的距离之和。
代码:

#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 100005

LL min(LL x, LL y) {if(x<y) return x; return y;}

int n, m, s, t, u, v;
LL a, b, f=1e15, ans[MAXN];

struct Graph
{
    int cnt, head[MAXN], vis[MAXN];
    LL dis[MAXN];

    struct Edge {int next, to; LL dis;} edge[MAXN*2];

    std::queue<int> q;

    void addedge(int from, int to, LL dis)
    {
        edge[++cnt].next=head[from];
        edge[cnt].to=to;
        edge[cnt].dis=dis;
        head[from]=cnt;
    }

    void spfa(int s)
    {
        for(int i=1; i<=n; i++) dis[i]=INF;
        memset(vis, 0, sizeof(vis));
        q.push(s); vis[s]=1; dis[s]=0;
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            vis[x]=0;
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]>dis[x]+edge[i].dis)
                {
                    dis[to]=dis[x]+edge[i].dis;
                    if(!vis[to]) q.push(to), vis[to]=1;
                }
            }
        }
    }
} g1, g2;

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%lld%lld", &u, &v, &a, &b);
        g1.addedge(u, v, a); g1.addedge(v, u, a);
        g2.addedge(v, u, b); g2.addedge(u, v, b);
    }
    g1.spfa(s);  g2.spfa(t);
    ans[n+1]=INF;
    for(int i=n; i>=1; i--) ans[i]=min(ans[i+1], g1.dis[i]+g2.dis[i]);
    for(int i=1; i<=n; i++) printf("%lld\n", f-ans[i]);
}

E – + Graph

思路:
思维难度不大,只是超级考验码力,我比赛时调了超级久还是没有写出QWQ。

我们设节点1的值为x,然后其它所有点的值都可以用$w_1-x$或$w_2+x$表示(w可以根据题目条件推出来)。先bfs一遍处理出每个节点$w_1,w_2$,储存在f数组里,然后统一进行判断。

限制条件有很多,不要漏了。首先要判断是否有正整数解,还要判断解的范围,还要判断解是否在范围内。详细的看代码好了。

代码:

#include <bits/stdc++.h>
#define MAXN 1000005
#define INF 1e18
#define LL long long

int n, m, cnt, head[MAXN], vis[MAXN];
LL l=1, r=INF, root=-1, f[MAXN][5];

LL min(LL x, LL y) {if(x>y) return y; return x;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

struct Edge{int next, to; LL dis;} edge[MAXN];

std::queue<int> q;

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int x)
{
    vis[x]=1; q.push(x);
    f[x][0]=1; f[x][1]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            f[to][0]=-f[x][0];
            f[to][1]=edge[i].dis-f[x][1];
            vis[to]=1; q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int u, v, s;
        scanf("%d%d%d", &u, &v, &s);
        addedge(u, v, s);
        addedge(v, u, s);
    }
    bfs(1);
    for(int i=1; i<=n; i++)
    {
        if(f[i][0]==1) l=max(l, 1-f[i][1]);
        else r=min(r, f[i][1]-1);
        for(int j=head[i]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            LL x=f[i][0]+f[to][0];
            LL y=f[i][1]+f[to][1];
            if(x==0 && y!=edge[j].dis) {printf("0\n"); return 0;}
            if(x!=0)
            {
                LL temp=edge[j].dis-y;
                if(temp%2 || temp/x<=0) {printf("0\n"); return 0;}
                if(root==-1) root=temp/x;
                if(root!=temp/x) {printf("0\n"); return 0;}
            }
        }
    }
    if(root==-1) printf("%lld\n", max(0, r-l+1));
    else printf("%d", (root>=l && root<=r));
}

发表评论

邮箱地址不会被公开。 必填项已用*标注