第 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<

相关内容

热门资讯

安卓系统音乐软件推荐,五大热门... 你有没有发现,手机里音乐软件那么多,挑一款适合自己的真心不容易啊!安卓系统上的音乐软件更是五花八门,...
安卓系统刷三星系统,轻松刷入最... 你有没有想过,你的安卓手机其实可以变身成三星的旗舰机呢?没错,就是那种屏幕大、性能强、系统流畅的旗舰...
塞班系统可以转为安卓,跨越时代... 你知道吗?现在科技的发展真是让人眼花缭乱,连我们曾经熟悉的塞班系统也能华丽转身,变成安卓系统呢!是不...
安卓系统如何录像剪辑,录像剪辑... 亲爱的手机控们,你是否有过这样的经历:在某个瞬间,你捕捉到了一段令人难忘的画面,却因为没来得及记录而...
安卓系统强行提高配置,配置提升... 最近你的安卓手机是不是感觉有点儿“发烧”了?没错,就是那种配置突然“升级”的感觉。你是不是也觉得,手...
安卓系统能做设计吗,探索安卓系... 你有没有想过,安卓系统竟然也能做设计?是的,你没听错,这个我们日常使用的手机操作系统,竟然也能成为设...
安卓系统几年后使用,探索多年使... 你有没有想过,那些陪伴我们多年的安卓手机,它们现在过得怎么样了呢?安卓系统,这个曾经让我们爱恨交加的...
平板安卓苹果双系统,安卓与苹果... 你有没有想过,拥有一台既能运行安卓系统,又能使用苹果系统的平板电脑,那该是多么酷炫的事情啊!想象一边...
嘉和病历系统安卓,便捷医疗信息... 你有没有听说过嘉和病历系统安卓版?这可是医疗行业的一大神器呢!想象医生们拿着手机就能轻松管理病历,患...
安卓10更改系统号,揭秘系统编... 你知道吗?最近安卓系统又来了一次大更新,安卓10正式上线了!这次更新可是带来了不少新功能,其中最引人...
小米墨水屏 安卓系统,融合科技... 你知道吗?在科技日新月异的今天,电子阅读器市场也迎来了新的活力。而小米,这个我们熟悉的品牌,最近推出...
系统软件最少的安卓系统,基于最... 你有没有想过,手机系统就像是我们生活的操作系统,有时候太复杂了,让人感觉头都大了。今天,我要给你介绍...
安卓系统关闭应用推荐,安卓系统... 你有没有发现,手机里的安卓系统最近有点儿“小情绪”,总是给你推荐一些你根本不感兴趣的应用?别急,今天...
车载安卓系统如何用,智能驾驶体... 你有没有想过,你的车载安卓系统其实是个隐藏的宝库呢?没错,就是那个你每天开车时几乎不离手的那个屏幕,...
安卓系统更新如何取消,```p... 你有没有遇到过这种情况:安卓手机的系统更新推送得让人有点头疼,有时候更新后的系统还各种不适应。别急,...
安卓系统源码修改练习,从零开始... 亲爱的技术爱好者,你是否曾梦想过深入安卓系统的内核,亲手修改源码,让手机变得更加个性化?那就让我们一...
安卓考勤系统论文,基于安卓平台... 你有没有想过,每天打卡上班,是不是也能变得有趣起来呢?没错,就是那个我们每天都要面对的安卓考勤系统。...
安卓系统哪家流畅度,安卓系统流... 手机里的安卓系统,就像是每个人的小世界,各有各的风采。但说到流畅度,这可是大家最关心的问题了。今天,...
安卓开不了定位系统,安卓设备定... 最近是不是发现你的安卓手机定位系统突然罢工了?别急,别慌,今天就来给你详细解析一下这个问题,让你轻松...
安卓系统怎么设置airpod,... 你有没有发现,自从AirPods问世以来,它就成为了科技界的宠儿?这款无线耳机不仅音质出众,而且连接...