友汇网站建设管理后台,微信官方网站 - 百度-百度,论坛网站开发demo,京东电器商城网上购物华为杯武汉大学21级新生程序设计竞赛
比赛传送门 u p d : 2022.4.8 upd:2022.4.8 upd:2022.4.8 补了 I I I题。
B题待补。
A - 仓鼠快速签到
给了10道选择题#xff0c;输出10个选择题的答案。 首先通过度娘得知第9题和第10题的答案是C。 然后接下来前8个题目…华为杯武汉大学21级新生程序设计竞赛
比赛传送门 u p d : 2022.4.8 upd:2022.4.8 upd:2022.4.8 补了 I I I题。
B题待补。
A - 仓鼠快速签到
给了10道选择题输出10个选择题的答案。 首先通过度娘得知第9题和第10题的答案是C。 然后接下来前8个题目手算的话会非常难顶所以方法是写一个暴力枚举剩下的8个题目的所有可能答案然后对每一个答案进行checkcheck的方法就是是否符合所有题目的要求。会发现可能的答案只有一种所以直接把那个答案输出出来就行。
#includebits/stdc.h
using namespace std;
typedef long long LL;int main() {cout CBABBACCCC;return 0;
}B - 二维弹球
还没做捏
C - osu!catch
期望DP题目。 期望DP题目通常从结果往初始状态转移。 这道题目我们设 d p t , i dp_{t,i} dpt,i表示时间为 t t t位置为 i i i时可以捡到水果数量的最大期望。我们考虑可能的三种操作通过这三种操作来求得转移方程。 ①不动。此时 d p t , i max { d p t , i , d p t 1 , i } dp_{t,i}\max \{dp_{t,i}, dp_{t1,i} \} dpt,imax{dpt,i,dpt1,i}。 ②向左或向右移动一格。此时 d p t , i max { d p t , i , d p t 1 , i 1 , d p t 1 , i − 1 } dp_{t,i}\max \{dp_{t,i}, dp_{t1,i1}, dp_{t1,i-1} \} dpt,imax{dpt,i,dpt1,i1,dpt1,i−1}。 如果在最左端和最右端分别只有向右移动一格和向左移动一格一种移动方式 ③向左或向右冲刺。我们设向左、向右可以获得的期望分别是 s u m l , s u m r sum_l,sum_r suml,sumr。此时 d p t , i max { d p t , i , s u m l , s u m r } dp_{t,i}\max \{dp_{t,i}, sum_l, sum_r \} dpt,imax{dpt,i,suml,sumr}。 接下来求 s u m i , s u m r sum_i,sum_r sumi,sumr。 如果我们对于每一个 t t t的每一个 i i i都从 i − k i-k i−k到 i k ik ik进行一次求和那么时间复杂度就变成了 O ( t m k ) O(tmk) O(tmk)是很不能接受的。所以我们要考虑优化。因为有很多次加法都是重复操作所以为了避免重复操作我们可以对于每一个 t t t预处理期望前缀和然后对于每一个 i i i我们 O ( 1 ) O(1) O(1)求得 s u m l , s u m r sum_l,sum_r suml,sumr。 由于我们有向左和向右两个方向所以我们要对于每一个算好的 t t t时刻的期望从左到右算一次前缀和用于计算向左冲刺的期望和从右到左算一次前缀和用于计算向右冲刺的期望和。对于每一个 t t t我们算的都是 t 1 t1 t1时刻的前缀和。我们通过前缀和数组分别算出 i i i处左右侧 k k k个格子的前缀和最后分别除以 k k k所得结果即为 s u m l , s u m r sum_l,sum_r suml,sumr。要注意的是可能左边或右边不足 k k k个格子此时统计缺少的格子的数量然后将端点值的期望和缺少格子的数量的乘积求出来加入期望和。 最后的答案就是 1 1 1时刻最大的期望值即 max { d p 1 , i } \max \{dp_{1,i} \} max{dp1,i}。 可以用滚动数组来节省空间的开销。
#includebits/stdc.h
using namespace std;
typedef long long LL;int n, m, k, mt;
int pos[10050];
double dp[2][1050], sum[1050][2];int main() {scanf(%d%d%d, n, m, k);mt 0;for (int i 1; i n; i) {int tt, pp;scanf(%d%d, tt, pp);mt max(mt, tt);pos[tt] pp;}int cur 0;for (int i 0; i m 1; i) {dp[0][i] dp[1][i] 0.0;}for (int t mt; t 1; --t) {for (int i 1; i m; i) {dp[cur][i] dp[cur ^ 1][i];if (i 1) dp[cur][i] max(dp[cur][i], dp[cur ^ 1][i - 1]);if (i m) dp[cur][i] max(dp[cur][i], dp[cur ^ 1][i 1]);double e_l, e_r; int delta;if (i - k 1) {e_l sum[i - 1][0] - sum[i - k - 1][0];} else {delta k - i 1;e_l sum[i - 1][0] delta * sum[1][0];}if (i k m) {e_r sum[i 1][1] - sum[i k 1][1];}else {delta k i - m;e_r sum[i 1][1] delta * sum[m][1];}dp[cur][i] max({dp[cur][i], e_l / (double)k, e_r / (double)k});if (pos[t] i) dp[cur][i] 1.0;}sum[0][0] sum[m 1][1] 0.0;for (int i 1; i m; i) {sum[i][0] sum[i - 1][0] dp[cur][i];}for (int i m; i 1; --i) {sum[i][1] sum[i 1][1] dp[cur][i];}cur ^ 1;}double ans 0.0;for (int i 1; i m; i) {ans max(ans, dp[cur ^ 1][i]);}printf(%.8lf, ans);return 0;
}D - 和谐之树
当前节点为 x x x其左儿子为 2 x 2x 2x右儿子为 2 x 1 2x1 2x1。用这种方式来建一棵根节点区间为 [ 1 , n ] [1,n] [1,n]的线段树最大的编号是多少 不难想到最大的编号一定在这棵线段树的最深一层。对于最深的一层这个节点一定在这一层的最右侧。考虑数据范围理想的复杂度下我们每一次查询可以接受 O ( n l o g n ) O(nlogn) O(nlogn)。那就是从根节点开始一直向着所谓的最大编号结点移动每次向左移动就是编号乘 2 2 2向右移动就是编号乘 2 2 2加 1 1 1。 现在的问题是怎么向最大编号的结点前进 在移动的过程中假设我们走在表示 [ l , r ] [l,r] [l,r]区间的结点上。我们先考虑这个区间所表示的区间长短是奇数还是偶数。如果是偶数的话那么左右两个儿子结点的形状是完全一样的那么他们的深度就是完全一样的这个时候我们向右移动目标是向着最深一层的右半区域移动。 如果是奇数那么根据 m i d ( l r ) / 2 mid (l r) / 2 mid(lr)/2可以看出左右儿子的区间长度一个是奇数一个是偶数。当左儿子长度是偶数右儿子长度是奇数时左边的偶数大于右边的奇数这个时候两边的深度相同那么就向右儿子前进。当左儿子长度是奇数右儿子长度是偶数时此时左儿子大于右儿子。随便画几个线段树就会发现当这个时候偶数是二的幂次时较大的奇数的子树一定是更深的此时就往左儿子走。 综上当左儿子区间长度是奇数、右儿子区间长度是偶数且右儿子区间长度大小是二的幂次时向左儿子走其他情况都向右儿子走。
#includebits/stdc.h
using namespace std;
typedef long long LL;LL n;
LL id, l, r, ti 0;
LL two[100];void main2() {cin n;if (n 1) {cout 1 \n;return;}l 1; r n; id 1;while (1) {LL mid (l r) 1ll;if (r - l 1 1) break;if ((r - l 1) % 2 0) {l mid 1; id id * 2 1;continue;}LL idd lower_bound(two 1, two ti 1, r - mid) - two;if (two[idd] r - mid) {r mid; id id * 2;}else {l mid 1; id id * 2 1;}}cout id \n;
}int main() {LL _; cin _;LL xxx 1;while (xxx 1e18) {two[ti] xxx;xxx 1ll;}while (_--) main2();return 0;
}E - 和谐之树·改
D题的强化版但是跟D题的思路基本没什么关系是个打表找规律题目。 用D题的代码输出 n n n从 1 1 1到 200 200 200大概就可以看出来一点规律。 我们发现随着 n n n不断变大答案是不断变大的而且同样的答案会重复循环一定的次数之后才变到下一个数而且答案全部都是奇数。 表格中 a × b a\times b a×b表示 a a a答案连续出现 b b b次。 我们注意到连续出现的次数 b b b的变化也是有规律的每一列都是先从一个 1 1 1开始然后是 1 , 2 , 4 , 8 , ⋯ 1,2,4,8,\cdots 1,2,4,8,⋯随着轮数的增加而周期越来越长。 那么数值上有什么规律呢 我们发现第二行即每一轮的第二个数值都是第一个数值 2 2 2。对于第三行从第三轮开始每次增加的量是 4 , 8 , 16 , 32 , ⋯ 4,8,16,32,\cdots 4,8,16,32,⋯。然后每一轮从第四轮开始增加量每次除以 2 2 2如第六轮从第三行开始的增加量是 32 , 16 , 8 , 4 , ⋯ 32,16,8,4,\cdots 32,16,8,4,⋯。 我们还可以发现对于第 i i i轮我们走过 2 i − 1 2^{i-1} 2i−1个数。 回到题目本身我们怎么来求 [ l , r ] [l,r] [l,r]的答案 我们可以先考虑求得 [ 1 , x ] [1,x] [1,x]的答案。先求到每一轮为止所获得的答案前缀和。然后通过数量的规律可以知道当前要求的 x x x在哪一轮然后在这一轮上暴力模拟求得这一轮到 x x x为止的答案然后加上上一轮的答案的前缀和即可。 会求 [ 1 , x ] [1,x] [1,x]的答案之后我们就可以求 [ 1 , l − 1 ] [1,l-1] [1,l−1] [ 1 , r ] [1,r] [1,r]的答案然后一减就可以了。 前缀和可以提前打好表。
#includebits/stdc.h
using namespace std;
typedef long long LL;
const LL p 998244353;LL psum[64] {0, 1, 8, 42, 198, 878, 3742, 15550, 63614, 257790, 1038846, 4172798, 16730110, 67006462, 268214270, 75022333, 300974074, 207552493, 834273210, 351010539, 424147889, 737144521, 35633959, 314502306, 620475021, 242141751, 549136608, 493659009, 833785346, 592066557, 950591451, 119766833, 403569739, 70774826, 400539280, 259978726, 192663195, 753870820, 347896164, 770807568, 289782507, 454402150, 190044624, 63567169, 983346219, 651941185, 541100752, 35811355, 893779119, 117952595, 611174067, 858896898, 527912782, 817126786, 736909845, 994080617, 299010500, 290495304, 270110074, 136898165, 340908710, 0, };LL sum(LL x) {if (x 0) return 0;else if (x 1) return 1;LL tot 1, ret 0;while (1) {if ((1ll tot) - 1 x) {return psum[tot];}else if ((1ll tot) - 1 x) {ret psum[tot - 1];break;}tot;}x - ((1ll (tot - 1)) - 1);LL v (1ll tot) - 1;ret (ret v % p) % p; --x;if (!x) return ret;v 2;ret (ret v % p) % p; --x;if (!x) return ret;LL del (1ll (tot - 1)), s 1;while (1) {s 1ll; v (v del % p) % p; del 1ll;if (s x) {ret (ret (x % p) * v % p) % p;return ret;}else {ret (ret (s % p) * v % p) % p;x - s;}}return 0;
}int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);LL _; cin _;for (LL i 1; i 62; i) {psum[i] (psum[i - 1] psum[i]) % p;}while (_--) {LL x, y;cin x y;LL ans sum(y) - sum(x - 1);cout (ans % p p) % p \n;}
}F - 仓鼠与炸弹
给一个只包含 a b ab ab的字符串要求找两个互不相交的长度为 k k k的子串要求这两个串是对称的。问可以找到多少对符合条件的两个串。 我们如果通过字符串逐位比较是否相等那么时间开销就有点太大了。我们发现要比较的字符串长度是固定的那么我们可以考虑字符串哈希。我们可以提前预处理每一个位置开始长度为 k k k的字串的字符串哈希值然后在构建一个颠倒过来的字符串再求一下颠倒过来的字符串的每个点开始长度为 k k k的字符串哈希值然后我们只需要比较哈希值是否相同即可。采用双哈希不容易被卡。 比较字符串是否对称的方法有了接下来就是考虑计数的问题了。 我们先用map存储倒序字符串中的所有哈希值。然后我们从左到右遍历正序字符串看不重复的位置里map里有多少和自己相同的哈希值倒序里相同正序里就是对称。相同的数量加入ans当中。然后我们每次在正序字符串上移动的过程中每次移动都会导致map里的一些字符串会被覆盖这个时候我们只需要在倒序字符串上加一个从右往左的pointer每次因为正序字符串向右查询而导致的倒序字符串的被覆盖的哈希值被覆盖就是如果采用就会跟正序的那个子串产生重合删除的顺序一定是倒序串上从右往左所以用pointer整个过程中从右往左删即可。这样一轮走下来得到的ans就是最终结果。 整个做法的时间复杂度中哈希、遍历、删除串是 O ( n ) O(n) O(n)的行为只不过后面两个用map维护会多一个 l o g log log所以整体时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)级别的。
#includebits/stdc.h
using namespace std;
typedef long long LL;LL n, m;
LL a, b;
string s;
pairLL, LL h1[100050], h2[100050];
const LL p1 998244353, p2 1e9 7;
LL b1, b2;
const LL bse 19260817;
mappairLL, LL, int mp;int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;cin s;a b 0;b1 b2 1;for (LL i 1; i m; i) {b1 b1 * bse % p1;b2 b2 * bse % p2;}for (LL i 0; i n; i) {a (a * bse s[i]) % p1;b (b * bse s[i]) % p2;if (i m) {a (a - (s[i - m] * b1)) % p1;b (b - (s[i - m] * b2)) % p2;a (a % p1 p1) % p1;b (b % p2 p2) % p2;}h1[i 1] {a, b};}reverse(s.begin(), s.end());a b 0;for (LL i 0; i n; i) {a (a * bse s[i]) % p1;b (b * bse s[i]) % p2;if (i m) {a (a - (s[i - m] * b1)) % p1;b (b - (s[i - m] * b2)) % p2;a (a % p1 p1) % p1;b (b % p2 p2) % p2;}h2[i 1] {a, b};}for (LL i m; i n - m; i) {mp[h2[i]];}LL ans 0;for (LL i m; i n - m; i) {ans mp[h1[i]];--mp[h2[n - i]];}cout ans;return 0;
}G - 寄寄子的生日
这道题首先开始口胡 对于任意的正整数 a , b ( 1 a b ≤ 1000 ) , b − a 1 a,b(1ab \leq 1000),b-a1 a,b(1ab≤1000),b−a1我们必定可以找到一个正整数 c ∈ ( a , b ) c∈(a,b) c∈(a,b)使得 c c c与 a , b a,b a,b均互质。 但是我不会证明。可以写一个代码暴力验证 我们现在来看题目。题目中的 2 n 2n 2n次操作是解决这道题目的突破口。 2 n 2n 2n可以看作是对每一个数都进行了 2 2 2次操作。那么操作是怎么样捏 大体的想法是从左到右让数字归位即先让 2 2 2回到第一个位置然后让 3 3 3回到第二个位置以此类推。这个想法可以保证每次只需要往后看前面已经是排好的就不用再往前看了。 假设我们已经搞完了前 x − 1 x-1 x−1个位置现在开始搞第 x x x个位置第 x x x个位置应当是 x − 1 x-1 x−1但是 x − 1 x-1 x−1现在在第 y y y个位置上显然 x y xy xy那么我们先来看如果 x , y x,y x,y位置上的数是互质的那么我们可以一步操作直接换好。 现在的问题是如果这两个数字不互质那怎么办我们可以从第 x 1 x1 x1个位置到第 n − 1 n-1 n−1个位置枚举看看有哪一个位置的数和第 x , y x,y x,y位置的数都互质根据我们的口胡一定可以找到一个位置 z z z符合这个条件。那么我们进行以下两个操作 ①将 x , z x,z x,z位置上的数字互换。 ②将 x , y x,y x,y位置上的数字互换。 在草纸上试了试然后发现这样一定是可行的而且只进行了两次操作。这样哪怕每一个数都需要找一个 z z z也可以在 2 n 2n 2n的次数内解决实际情况远比这个要好。 于是这道题目做完了。
#includebits/stdc.h
using namespace std;
typedef long long LL;int a[1050], mp[1050];
int n;
int b[1050];
vectorpairint, int ans;int main() {cin n; --n;for (int i 1; i n; i) {cin a[i]; b[i] a[i];mp[a[i]] i;}for (int i 1; i n; i) {if (a[i] i 1) continue;int id mp[i 1];if (__gcd(i 1, a[i]) 1) {ans.push_back({i, id});mp[i 1] i;mp[a[i]] id;swap(a[i], a[id]);}else {for (int j i 1; j n; j) {if (__gcd(a[i], a[j]) 1 and __gcd(a[id], a[j]) 1) {ans.push_back({i, j}); mp[a[j]] i; mp[a[i]] j;swap(a[i], a[j]);ans.push_back({i, id});mp[a[i]] id; mp[i 1] i;swap(a[i], a[id]);break;}}}}cout ans.size() \n;if (ans.size() 2 * (n 1)) {cout INF;return 0;}for (auto [x, y]: ans) {cout x y \n;}return 0;
}H - wwhhuu
不难发现三个字母的数量越平均越好然后相同字母放在一起一定是最优的因为没有类似逆序对的东西导致结果的浪费。假如说长度是 5 5 5那就 5 2 2 1 5221 5221。
#includebits/stdc.h
using namespace std;
typedef long long LL;int n;int main() {cin n;int d n % 3; n - d;int a, b, c;a b c n / 3;if (d 1) a 1;else if (d 2) {a 1; b 1;}cout a * b * c;return 0;
}I - 异度之刃
学习了shyyhs的做法 因为数据量很大在线去做非常困难所以我们考虑离线。 我们首先考虑假如不会出现重复的连续数列比如说 1 , 2 , 4 , 5 , 6 , 9 , 10 1,2,4,5,6,9,10 1,2,4,5,6,9,10。这种情况下的答案该怎么计算呢 我们发现我们可以对这些数进行分组即将连续在一起的数字做一个同样的标记比如说上面这串数列我们把每一组数标记最小的那个下标即标记成了 1 , 1 , 3 , 3 , 3 , 6 , 6 1,1,3,3,3,6,6 1,1,3,3,3,6,6。其实这标记的也是连续的数列的最开始的数字的位置。设这个标记是pre[i]。为什么要标记这个这样方便我们从任意一个数算出到这个数为止连续上升数列的位置和长度。 那么答案怎么计算对于每一个数 i i i答案的贡献就是 [ p r e [ i ] , i ] [pre[i],i] [pre[i],i]区间上所有数贡献 1 1 1。这就很有线段树的味道了。 我们发现我们遍历序列时对于遍历到的数算出的贡献只与左侧有关与右侧无关。那么我们对于所有查询的区间对右端点排序然后从左到右遍历这个序列假设遍历到第 i i i个序列那么先计算贡献然后更新线段树然后在线段树上查询所有区间为 [ x , i ] [x,i] [x,i]的区间的答案。 如果有重复怎么办 我们可以通过对上面的那个方法进行一个改进。我们发现如果有重复我们只需要保住最后面那一段重复的连续序列即可。这样固定右端点查询左端点时不管怎样都不会发生少区间、多区间的情况。现在的问题就是考虑如何去掉重复的贡献。 首先我们在序列中假设已经遍历到第 i i i个数了。如果原来序列中也存在过相同的数值 a [ x ] a [ i ] a[x] a[i] a[x]a[i]下标为 x x x那么我们看对于那个 a [ i ] a[i] a[i]他所在的最长连续区间和当前第 i i i个数的最长连续区间长度关系即比较 x − p r e [ x ] x-pre[x] x−pre[x]和 i − p r e [ i ] i-pre[i] i−pre[i]的大小关系。 如果 x − p r e [ x ] ≤ i − p r e [ i ] x-pre[x]\leq i-pre[i] x−pre[x]≤i−pre[i]这意味着前面这个 x − p r e [ x ] x-pre[x] x−pre[x]这段区间完全被我这个新的区间覆盖了也就是说前面这段区间就不需要了直接把他们的贡献清除。然后再往前看有没有其他的 a [ x ] a [ i ] a[x] a[i] a[x]a[i]。因为我们不能保证刚刚删掉的那个 a [ x ] a[x] a[x]所在的区间对于前面来说是完全覆盖还是部分覆盖注意要删除的区间可能之前有被之前删除过所以我们要先把他恢复成正常的样子再统一删去。然后因为对于这个 a [ i ] a[i] a[i]的贡献完全从 x x x的位置到了 i i i所以以后再有相同的数值时就不需要再考虑这个 x x x的位置了。 如果 x − p r e [ x ] ≥ i − p r e [ i ] x-pre[x]\geq i-pre[i] x−pre[x]≥i−pre[i]这意味着前面这个区间比当前这个区间的长度大。前面的区间要做到部分删除。和前一种情况一样要先把这个区间恢复成原来的样子然后再把适配到 i − p r e [ i ] i-pre[i] i−pre[i]的长度的区间删除。这种情况找到一个然后删除之后就可以不用再往下找了理由是我们找到的这个连续的区间已经比我们当前的区间长了 那么再往后找的一定已经被我们删掉的这个区间覆盖掉了所以可以直接break。 然后删除过后把当前这个数记录下来留作后续遍历时按照条件删除。
#includebits/stdc.h
using namespace std;
typedef long long LL;
const LL N 1000050;struct Tree {LL l, r, sum, tag;
}t[N * 4];void build_tree(int ni, LL l, LL r) {t[ni].l l; t[ni].r r; t[ni].sum t[ni].tag 0;if (l r) {return;}LL mid (l r) 1;build_tree(ni 1, l, mid);build_tree((ni 1) 1, mid 1, r);
}void pd(int ni) {if (t[ni].tag 0) return;t[ni 1].sum (t[ni].tag * (t[ni 1].r - t[ni 1].l 1));t[ni 1 | 1].sum (t[ni].tag * (t[ni 1 | 1].r - t[ni 1 | 1].l 1));t[ni 1].tag t[ni].tag;t[ni 1 | 1].tag t[ni].tag;t[ni].tag 0;
}void pu(int ni) {t[ni].sum t[ni 1].sum t[ni 1 | 1].sum;
}void add(int ni, LL l, LL r, LL x) {if (l t[ni].l and t[ni].r r) {t[ni].tag x;t[ni].sum (x * (t[ni].r - t[ni].l 1));return;}LL mid (t[ni].l t[ni].r) 1;pd(ni);if (l mid) add(ni 1, l, r, x);if (mid r) add(ni 1 | 1, l, r, x);pu(ni);
}LL query(int ni, LL l, LL r) {if (l t[ni].l and t[ni].r r) {return t[ni].sum;}LL mid (t[ni].l t[ni].r) 1;pd(ni);LL ret 0;if (l mid) ret query(ni 1, l, r);if (mid r) ret query(ni 1 | 1, l, r);return ret;
}LL n, m;
LL a[N], pre[N], del[N], ans[N];
vectorpairLL, LL q[N];
vectorLL w[N];int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;build_tree(1, 1, n);for (LL i 1; i n; i) {cin a[i];}pre[1] 1;for (LL i 2; i n; i) {pre[i] ((a[i] a[i - 1] 1) ? pre[i - 1] : i);}for (LL i 1; i n; i) {del[i] ans[i] 0;}for (LL i 1; i m; i) {LL x, y;cin x y;q[y].push_back({x, i});}for (LL i 1; i n; i) {add(1, pre[i], i, 1);while (w[a[i]].size()) {LL x w[a[i]].back();if (del[x]) {add(1, del[x], x, 1); del[x] 0;}if (x - pre[x] i - pre[i]) {add(1, pre[x], x, -1);w[a[i]].pop_back();}else {LL st x - (i - pre[i] 1) 1;add(1, st, x, -1);del[x] st;break;}}w[a[i]].push_back(i);for (auto [x, y]: q[i]) {ans[y] query(1, x, i);}}for (LL i 1; i m; i) {cout ans[i] \n;}return 0;
}J - 传闻档案
给一个DAG每个点的答案是这个点通过一定路径可以达到的点权最大值。求所有点的答案和。 可以发现对于一个环而言他们的答案一定是一样的假设他们的答案不一样一定可以通过路径将答案小的点的答案调整成跟大数一样。 于是可以考虑缩点然后在缩点之后的图上跑一个dfs每次更新答案即可。
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int N 100050;
const int M 300050;int n, m, en 0, nen 0;
int front[N], nfront[N];
int dfn[N], bel[N], low[N], ins[N], stk[N];
int a[N], b[N];
int tp[N], ind[N];
int di, ti, si;
int vis[N];
int cnt 0;inline LL read() {LL x 0, y 1; char c getchar(); while (c 9 || c 0) { if (c -) y -1; c getchar(); }while (c0c9) { xx*10c-0;cgetchar(); } return x*y;
}struct Edge {int u, v, next;
}e[M * 3], ne[M * 3];void addEdge(int u, int v) {e[en] {u, v, front[u]};front[u] en;
} void naddEdge(int u, int v) {ne[nen] {u, v, nfront[u]};nfront[u] nen;
}void tarjan(int x)
{dfn[x] low[x] di;stk[si] x; ins[x] 1;for (int i front[x]; i; i e[i].next) {int v e[i].v;if (!dfn[v]) {tarjan(v);low[x] min(low[x], low[v]);}else if (ins[v]) {low[x] min(low[x], dfn[v]);}}if (dfn[x] low[x]) {int y 0;cnt;do {y stk[si--];ins[y] 0;bel[y] cnt; } while (y ! x);}
}void dfs(int u) {if (vis[u]) return;vis[u] 1;for (int i nfront[u]; i; i ne[i].next) {int v ne[i].v;dfs(v);b[u] max(b[u], b[v]);}
}int main() {n read(); m read();for (int i 1; i n; i) {front[i] nfront[i] vis[i] b[i] 0;}for (int i 1; i n; i) {a[i] read();}en nen 0;for (int i 1; i m; i) {int x read(), y read();addEdge(x, y);}for (int i 1; i n; i) {if (!dfn[i]) tarjan(i);}for (int i 1; i m; i) {int u e[i].u, v e[i].v;if (bel[u] ! bel[v]) {naddEdge(bel[u], bel[v]);}}for (int i 1; i n; i) {b[bel[i]] max(b[bel[i]], a[i]);}for (int i 1; i cnt; i) {if (!vis[i]) dfs(i);}LL sum 0;for (int i 1; i n; i) {sum b[bel[i]];}printf(%lld, sum);return 0;
}
