第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南),签到题2题
admin
2024-04-07 21:44:10
0

文章目录

      • K.Search For Mafuyu
      • C.Optimal Strategy

补题链接:https://pintia.cn/market/item/1459833348620926976

K.Search For Mafuyu

K
Search For Mafuyu
(300分)
Mafuyu has hidden in Sekai, and Kanade is searching for her.

In Sekai, there is nothing but a lot of rooms. There are n rooms in Sekai, numbered from 1 to n. Besides, n−1 pairs of rooms are directly connected by corridors, such that it is possible to move from one room to any other one, using one or more corridors. In other words, rooms in Sekai form a tree.

Kanade is at room 1, and she knows that Mafuyu may hide in any room except room 1, with uniform probability. In one second, Kanade can move to a room adjacent to the room she is currently in. Once Kanade is in the same room with Mafuyu, she immediately finds her. What is the minimum expected time for Kanade to find Mafuyu, if Kanade is taking the optimal strategy?

Input
The first line contains an integer t (1≤t≤1000) — the number of test cases.

The first line in each test case contains an integer n (2≤n≤100) — the number of rooms.

Each of the following n−1 lines contains two integers a
i

, b
i

(1≤a
i

,b
i

≤n) — the rooms connected by the i-th corridor. It is guaranteed that it is possible to move from one room to any other one, using one or more corridors.

Output
Output t real numbers. For each test case, output the minimum expected time. Your answer is considered correct if the absolute or relative error is less than 10
−9
.

Sample Input
4
2
1 2
5
1 2
2 3
3 4
1 5
7
1 2
1 3
2 4
2 5
3 6
3 7
10
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
Output
1.0000000000
3.2500000000
5.3333333333
8.0000000000

题意:

  • T组数据(1000),每次给出一个n个点(100)的树,A和B走迷宫,A在1号点,B藏在某个树中某个点。
  • 求A找到B的最短期望时间。

思路:

  • 最短期望时间,即最优查找策略肯定是先走大小小的子树,再依次走大小大的。所以先跑一遍dfs记录每个节点子树的大小。
  • 然后再跑一遍dfs,对于遇到的节点x,按照子树大小从小往大的走。开个变量维护当前走的步数tim,每次遇到一个点就累加到ans上去,最后除掉n-1即可。
#include
using namespace std;
typedef long long LL;
const int maxn = 550;vectorG[maxn];
int siz[maxn];
void dfs(int x, int fa){siz[x] = 1;for(int to : G[x]){if(to!=fa){dfs(to,x);siz[x] += siz[to];}}
}bool cmp(int x, int y){return siz[x]res += tim;sort(G[x].begin(),G[x].end(),cmp);for(int to : G[x]){if(to!=fa){tim++;dfs2(to, x);tim++;}}
}int main(){int T;  cin>>T;while(T--){memset(siz,0,sizeof(siz));int n;  cin>>n;for(int i = 0; i <= n; i++)G[i].clear();for(int i = 1; i < n; i++){int u, v;  cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);res = tim = 0;dfs2(1,0);printf("%.11lf\n", res*1.0/(n-1));}return 0;
}

C.Optimal Strategy

C
Optimal Strategy
(300分)
Ena and Mizuki are playing a game.

There are n items in front of them, numbered from 1 to n. The value of the i-th item is a
i

. Ena and Mizuki take turns to move, while Ena moves first. In a move, the player chooses an item that has not been taken and takes it away. The game ends when all items are taken away. The goal of either player is to maximize the sum of values of items they have taken away.

Given that both players move optimally, how many possible game processes are there? Since the number may be too large, you should output it modulo 998244353.

Two processes are considered different if there exists some integer i(1≤i≤n) such that the indices of items taken away in the i-th move are different.

Input
The first line contains an integer n (1≤n≤10
6
).

The second line contains n integers a
1

,a
2

,…,a
n

(1≤a
i

≤n).

Output
Output the answer.

Sample Input 1
3
1 2 2
Sample Output 1
4
Sample Input 2
6
1 3 2 2 3 1
Sample Output 2
120
Sample Input 3
12
1 1 4 5 1 4 1 9 1 9 8 10
Sample Output 3
28800
Explanations
In the first example, there are four possible processes:

[1,2,3].
[1,3,2].
[2,3,1].
[3,2,1].
Here [a,b,c] means that in the first move Ena takes away the a-th item, in the second move Mizuki takes away the b-th item, and in the final move Ena takes away the c-th item.

Note that [2,1,3] is not a possible process, since the second move is not optimal for Mizuki.

题意:

  • 给定n个物品,每个物品有一个价值。 Ena和Mizuki轮流取物品,每个人的得分是其所取物品的价值总和。
  • Ena先手,每个人取的都是当前的最优解,问结束时中间有多少种不同的取法。答案模998244353。
  • 如果存在一些整数相等,但是下标不同,算为两种方式。

思路:

  • 要让和最大,自然想到每个数都不能太小。若直接贪心每次双方都取最大第一个样例都解释不通。
    再模拟样例二发现暗示比较明显,每个数都出现偶数次,样例三便是奇偶出现次数都有。

  • 首先考虑当前最大值,如果是偶数个,那么会每次被两个两个的取;如果是奇数个,那么会被先手立刻取走一个,变成偶数的情况。
  • 开个桶数组维护每个数字的出现次数,第 i 个数出现 c[i] 次。
    对于奇数次的数,先手必然取走最大的一个数,后手取走次大的出现的奇数次的数,对结果不产生影响。
    对于偶数次的数,双方轮流从大到小拿,一方拿走一个另一方会立刻拿走相同的数,取当前数时有c[i]/2种方案。
  • 从小到大考虑每个数的出现次数,当前数的可选方案为c[i]/2。比当前数小的数的出现次数和sum可直接作为总和选取(因为是从小到大遍历,现在自己取了能取的最小值,之前的数是都不符合贪心策略的,因为它们都比最小值小,只有后面的数要符合贪心,因此前面的数在前面的过程中可以按照任意顺序取)
    大数一定可在小数之前被选,所以每个数的方案为C(c[i]/2+sum,c[i]/2),每个数内部排列方案数为 c[i]!。
  • 组合数需要预处理,不然会T。
  • 参考https://blog.csdn.net/m0_57050876/article/details/121356251

#include
using namespace std;
typedef long long LL;
const LL maxn = 1e6+10, mod = 998244353;//预处理阶乘和逆元求组合数
LL fac[maxn], inv[maxn];
LL mpow(LL a, LL x) { if(x==0)return 1; LL t = mpow(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; }
LL init(LL _n){fac[0]=inv[0]=1;for(int i = 1; i < _n; i++){fac[i]=fac[i-1]*i%mod; inv[i]=mpow(fac[i],mod-2);}return 0;
}
LL C(LL x, LL y) {if(y<0 || y>x)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}LL c[maxn], mx, res = 1;int main(){init(maxn-1);LL n;  cin>>n;  for(int i = 1; i <= n; i++){LL x;  cin>>x;  c[x]++;  mx = max(mx, x);}LL sum = 0;for(int i = 1; i <= mx; i++){if(c[i]==0)continue;LL up = floor(c[i]/2), down = up+sum;res = res*fac[c[i]]%mod*C(down, up)%mod;sum += c[i];}cout<

相关内容

热门资讯

安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...
安卓系统怎么删除相片,照片删除... 手机里的相片越来越多,是不是感觉内存都要不够用了?别急,今天就来教你怎么在安卓系统里轻松删除那些不再...
什么安卓机系统最好,安卓系统最... 你有没有想过,手机里那个默默无闻的系统,其实才是决定你手机体验好坏的关键呢?没错,说的就是安卓机系统...
小米手环8安卓系统,智能生活新... 你有没有注意到,最近小米手环8安卓系统成了大家热议的话题呢?这款智能手环自从上市以来,就凭借其强大的...
虹膜系统怎么换为安卓,技术革新... 你有没有想过,你的虹膜系统怎么换为安卓呢?这可是个挺酷的话题,不是吗?想象你的手机上装了个高科技的虹...
安卓刷苹果mac系统,探索跨平... 你有没有想过,你的安卓手机竟然能变身成为苹果Mac系统的超级战士?没错,这就是今天我要跟你分享的神奇...
安卓系统不模仿苹果,不模仿苹果... 你知道吗?在科技圈里,有一场关于操作系统的大戏正在上演。没错,就是安卓系统和苹果iOS系统之间的较量...
安卓系统计步开启,开启健康生活... 你有没有发现,最近你的手机里多了一个小助手——计步器?没错,就是那个默默记录你每一步的小家伙。今天,...
怎么备份安卓系统 recove... 你有没有想过,如果你的安卓手机突然间像顽皮的小猫一样,把你的照片、视频和重要文件都给“藏”了起来?别...
安卓系统同步功能停用,安卓系统... 最近发现了一个让人有点小郁闷的消息——安卓系统的同步功能竟然被停用了!这可真是让人有点措手不及呢。想...
安卓系统的平板重装系统,轻松恢... 你那安卓平板是不是突然间卡得跟蜗牛似的,系统反应慢得跟乌龟赛跑似的?别急,今天就来给你支个招,教你怎...
安卓操作系统语言,引领智能时代... 你知道吗?在手机世界里,有一个超级厉害的操作系统,它就是安卓!这个操作系统可是全球最流行的,几乎每个...
安卓系统声音录音软件,声音记录... 你有没有想过,在安卓手机上,那些美妙的旋律、有趣的对话或者重要的会议内容,如何变成你随时可以回顾的宝...
coloros系统和安卓9,创... 你知道吗?最近手机圈里可是热闹非凡呢!一款名为ColorOS的系统,还有那个大家熟悉的安卓9,它们俩...
安卓个推系统搭建,基于个推系统... 你有没有想过,自己的手机里那些推送消息是怎么悄无声息地出现在你眼前的?没错,就是安卓个推系统在默默为...
设置系统时间app安卓,安卓时... 你有没有想过,手机里那个默默无闻的系统时间,竟然能通过一个小巧的App变得如此有趣和个性化?没错,今...
安卓系统输出开关量,安卓系统开... 你有没有想过,你的安卓手机里竟然隐藏着这么一个神奇的开关量输出功能?没错,就是那个你可能从未留意过的...
安卓系统音乐软件推荐,五大热门... 你有没有发现,手机里音乐软件那么多,挑一款适合自己的真心不容易啊!安卓系统上的音乐软件更是五花八门,...