2018-2019 ACM-ICPC, Asia East Continent Finals Solution

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

D. Deja vu of … Go Players

签。

 #include <bits/stdc++.h>

 using namespace std;

 int t, n, m;

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

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

         for (int i = ; i <= n + m; ++i) scanf("%*d");

         puts(n <= m ? "Yes" : "No");

     }

     return ;

 }

I. Misunderstood … Missing

题意：

$有n轮游戏，每一轮有三个参数a_i, b_i, c_i$

初始攻击力为$A = 0, 成长值为D = 0$

每一轮的开头 $A = A + D$

接着三种操作选一个

造成$A + a_i点伤害$
$D = D + b_i$
$A = A + c_i$

求造成的最大伤害和是多少

思路：

倒着$dp, dp[i][j][k] 表示当前处于第i轮，在后面的轮数中要进行j次攻击，时间点之和为k$

那么到当前点，我们就可以

通过$k\;来算出如果当前点选择第二种操作的贡献$

$dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k] + c[i] * j)$

$通过j\;来算出如果当前点选择第三种操作的贡献$

$dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k] + (k - i * j) * b[i])$

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 110

 #define M 6010

 int t, n;

 ll dp[][N][M], a[N], b[N], c[N];

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n);

         for (int i = ; i <= n; ++i) scanf("%lld%lld%lld", a + i, b + i, c + i);

         for (int i = ; i < ; ++i) for (int j = ; j <= n; ++j) for (int k = ; k <= ; ++k) dp[i][j][k] = -;

         dp[n &  ^ ][][] = ;

         for (int i = n; i >= ; --i)

         {

             for (int j = ; j <= n; ++j) for (int k = ; k <= ; ++k) if (dp[i &  ^ ][j][k] != -)

             {

                 dp[i & ][j + ][k + i] = max(dp[i & ][j + ][k + i], dp[i &  ^ ][j][k] + a[i]);

                 dp[i & ][j][k] = max(dp[i & ][j][k], dp[i &  ^ ][j][k] + 1ll * j * c[i]);

                 dp[i & ][j][k] = max(dp[i & ][j][k], dp[i &  ^ ][j][k] + 1ll * (k - j * i) * b[i]);

             }

         }

         ll res = ;

         for (int i = ; i <= n; ++i) for (int j = ; j <= ; ++j) res = max(res, dp[][i][j]);

         printf("%lld\n", res);

     }

     return ;

 }

L. Eventual … Journey

题意：

有两个阵营，阵营之间的人可以两两之间通过花费1来相互到达

不同阵营之间如果有直接边也可以直接相互到达，如果没有直接边，可以通过间接到达

即先到达一个有边连到对方阵营的同阵营的人，再过去

思路：

考虑花费一共有三种情况

1：同阵营之间的相互到达，不同阵营之间有边可以直接到达

2：不同阵营之间没有直接边，但是有一方有直接边连向对方阵营

3：两个属于不同阵营，且都没有直接边连向对方阵营

要注意m = 0的时候，不同阵营之间不可达

还有它给出的公共边可能有相同阵营的

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, m;

 int cnt[], zero[], degree[N], vis[N];

 int main()

 {

     while (scanf("%d%d", &n, &m) != EOF)

     {

         memset(degree, , sizeof degree);

         cnt[] = cnt[] = ;

         zero[] = zero[] = ;

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

         {

             scanf("%d", vis + i);

             ++cnt[vis[i]];

         }

         if (m == )

         {

             for (int i = ; i <= n; ++i) printf("%d%c", cnt[vis[i]] - , " \n"[i == n]);

             continue;

         }

         for (int i = , u, v; i <= m; ++i)

         {

             scanf("%d%d", &u, &v);

             if (vis[u] == vis[v]) continue;

             ++degree[u];

             ++degree[v];

         }

         for (int i = ; i <= n; ++i) if (!degree[i])

             ++zero[vis[i]];

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

         {

             int res = ;

             if (degree[i]) res = cnt[vis[i]] -  + degree[i] + (cnt[vis[i] ^ ] - degree[i]) * ;

             else res = cnt[vis[i]] -  + cnt[vis[i] ^ ] *  + zero[vis[i] ^ ];

             printf("%d%c", res, " \n"[i == n]);

         }

     }

     return ;

 }