[2019南京网络赛D题]Robots

2019.9.2更新

第二天睡醒想了想发现好像搜一遍就可以过，赛时写的花里胡哨的还错了，太菜了QAQ

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 3e5 + ;

 struct node {

     int s, e, next;

 }edge[maxn];

 int head[maxn], len;

 void init() {

     memset(head, -, sizeof(head));

     len = ;

 }

 void add(int s, int e) {

     edge[len].s = s;

     edge[len].e = e;

     edge[len].next = head[s];

     head[s] = len++;

 }

 double dp[maxn], dp2[maxn];

 int vis[maxn],n;

 void dfs(int x) {

     if (vis[x])

         return;

     vis[x] = ;

     dp[x] = dp2[x] = ;

     if (x == n)

         return;

     int num = ;

     for (int i = head[x]; i != -; i = edge[i].next) {

         int y = edge[i].e;

         dfs(y);

         dp[x] += dp[y];

         dp2[x] += dp2[y];

         num++;

     }

     dp[x] += num + , dp[x] /= num;

     dp2[x] += (num + )*dp[x], dp2[x] /= num;

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int  m, x, y;

         init();

         scanf("%d%d", &n, &m);

         for (int i = ; i <= m; i++)

             scanf("%d%d", &x, &y), add(x, y);

         memset(vis, , sizeof(vis));

         dfs();

         printf("%.2f\n", dp2[]);

     }

 }

原文

绝望ing!!!

搞了3个小时的D,到最后也没过，吃饭的时候突然想到错了，改一改就过了Orz.

遗憾!!错在求了拓扑序,要用a[n]->a[1],结果用成了n->1。要被队友骂死了QAQ

而且样例刚好1-n是拓扑序(

题意是说，在DAG中从1到n，每次有x/(x+1)的概率到相连的点，1/(x+1)的概率原地不动，(x为相连的点的个数)。每次移动需要一天，每次移动会消耗当前天数数值那么多的能量，求到达n点的期望能量消耗。

一开始就蛮有感觉的，DAG上跑期望dp，先跑期望天数，再跑期望能量，设dp[i]为i点到n点的期望天数，则初始dp[n]=0,转移为$dp[i]=\tfrac{1}{x+1}*\sum dp[j]+\tfrac{1}{x+1}*dp[i]+1$ i->j有边。

然后再跑期望能量，dp2[i]为i到n点的期望能量，初始为dp2[n]=0,转移为$dp2[i]=\tfrac{1}{x+1}*\sum dp2[j]+\tfrac{1}{x+1}*dp2[i]+dp[i]$ i->j有边。

代码极度丑陋，望见谅。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 4e5 + ;

 struct node {

     int s, e, next;

 }edge[maxn], edge2[maxn];

 int head[maxn], head2[maxn], len, len2;

 void init() {

     memset(head, -, sizeof(head));

     memset(head2, -, sizeof(head2));

     len = len2 = ;

 }

 void add(int s, int e) {

     edge[len].s = s;

     edge[len].e = e;

     edge[len].next = head[s];

     head[s] = len++;

 }

 void add2(int s, int e) {

     edge2[len2].s = s;

     edge2[len2].e = e;

     edge2[len2].next = head2[s];

     head2[s] = len2++;

 }

 double dp[maxn], dp2[maxn];

 int in[maxn], a[maxn], num[maxn];

 void solve(int n) {

     int lens = ;

     queue<int>q;

     for (int i = ; i <= n; i++)

         if (in[i] == ) q.push(i);

     while (!q.empty()) {

         int p = q.front(); q.pop();

         a[++lens] = p;

         for (int i = head[p]; i != -; i = edge[i].next) {

             int y = edge[i].e;

             in[y]--;

             if (in[y] == )

                 q.push(y);

         }

     }

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n, m, x, y;

         scanf("%d%d", &n, &m);

         init();

         for (int i = ; i <= n; i++)

             in[i] = , num[i] = , dp2[i] = dp[i] = ;

         for (int i = ; i <= m; i++)

             scanf("%d%d", &x, &y), add(x, y), add2(y, x), in[y]++;//正向反向各存一图，正向跑拓扑，反向求期望

         solve(n);//求拓扑序

         dp[a[n]] = ;

         for (int x = n; x >= ; x--) {//期望dp日常倒推

             if (a[x] != n) dp[a[x]] += num[a[x]] + , dp[a[x]] /= num[a[x]];//num[i]为与i点相连的点数

             num[a[x]] = ;

             for (int i = head2[a[x]]; i != -; i = edge2[i].next) {

                 int y = edge2[i].e;

                 dp[y] += dp[a[x]];

                 num[y]++;

             }

         }

         dp2[n] = ;

         for (int x = n; x >= ; x--) {

             if (a[x] != n) dp2[a[x]] += (num[a[x]] + ) * dp[a[x]], dp2[a[x]] /= num[a[x]];

             for (int i = head2[a[x]]; i != -; i = edge2[i].next) {

                 int y = edge2[i].e;

                 dp2[y] += dp2[a[x]];

                 num[y]++;

             }

         }

         printf("%.2lf\n", dp2[]);

     }

 }

巴特西

[2019南京网络赛D题]Robots

最新文章

热门文章