慈溪企业网站博客网站排名大全

慈溪企业网站,博客网站排名大全,崇明集团网站建设,登录页面设计代码最近手感差的很#xff0c;A能WA两发写20min#xff0c;D调不出来#xff0c;不过看别人的AC代码dp思路跟自己也不太一样…还是自己太菜了#xff0c;加训div2了。 A. Operations with Inversions Given an array a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​. In o…最近手感差的很A能WA两发写20minD调不出来不过看别人的AC代码dp思路跟自己也不太一样…还是自己太菜了加训div2了。A. Operations with InversionsGiven an arraya1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​. In one operation, you can choose a pair of indicesi,ji, ji,jsuch that1≤ij≤n1 \le i j \le n1≤ij≤n,aiaja_i a_jai​aj​, and remove the element at indexjjjfrom the array. After that, the size of the array will decrease by111, and the relative order of the elements will not change.Determine the maximum number of operations that can be performed on the array if they are applied optimally.真是糖丸了第一遍读错题了后来发现思路错了应该直接O(n2)O(n^2)O(n2)扫的。voidsolve(){intn;cinn;vectorinta(n1);for(inti1;in;i)cina[i];intans0;vectorintst(n1);for(inti1;in;i){for(intji1;jn;j){if(a[i]a[j]){st[j]1;}}}coutaccumulate(range(st),0LL)endl;}B. Optimal ShiftsYou are given a binary strings1s2…sns_1s_2 \ldots s_ns1​s2​…sn​, containing at least one 1. You want to obtain a binary string of the same length, consisting only of 1s. To do this, you can perform the following operation any number of times:Choose a numberddd(1≤d≤n1 \le d \le n1≤d≤n) and consider the stringtttas a cyclic right shift of the stringsssbyddd, or, more formally,tsn−d1…sns1…sn−dt s_{n - d 1} \ldots s_{n}s_{1} \ldots s_{n - d}tsn−d1​…sn​s1​…sn−d​. After that, for alljjjfor whichtj1t_j 1tj​1, performsj:1s_j : 1sj​:1. The described operation costsdddcoins, wheredddis the chosen shift amount.Note that the positionsjjjin the stringsss, where initiallysj1s_j1sj​1, remain equal to111even iftj0t_j0tj​0.You need to determine the minimum number of coins that can be spent so that the stringsssconsists only of 1s after all operations.看成一个环首位相接直接找相邻两个 1 中间有多少个 0;也唐了第一遍双指针没有更新 i 的位置TLE了…voidsolve(){intn;string s;cinns;inti0;intcnt10,cnt20;while(s[i]0in)cnt1,i;in-1;while(s[i]0i0)cnt2,i--;intanscnt1cnt2;for(inti0;in;i){if(s[i]0){intji1;while(jns[j]0)j;j--;ansmax(ans,j-i1);ij;}}coutansendl;}C. Odd ProcessYou havennncoins with denominationsa1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​and a natural numberkkk. You also have a bag, which is initially empty, where you can place coins. You need to perform exactlykkkactions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin.At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment.Let your score be the sum of the denominations of the coins in the bag. Your task is to performkkkactions such that your final score is maximized. Find the answer for all1≤k≤n1 \le k \le n1≤k≤n.简单来讲得发现首先选一个奇数接着一直选偶数这样才能保证最后的结果最优。但是如果偶数个数加上奇数的 1也就是 num_even 1 k则还需要一些别的操作来抵消多余的 k可以发现需要的抵消奇数个数等于(k - num_even - 1 1) / 2 * 2然后就是再判断一堆边界问题有点小麻烦。。voidsolve(){intn;cinn;vectorinta(n1);vectorvectorintvec(2,vectorint(1,0));for(inti1;in;i){cina[i];vec[a[i]1].push_back(a[i]);}autoprevec;sort(range_(vec[1]));sort(range_(vec[0]));intnovec[1].size()-1,nevec[0].size()-1;for(inti1;ino;i){pre[1][i]pre[1][i-1]vec[1][i];}for(inti1;ine;i){pre[0][i]pre[0][i-1]vec[0][i];}for(intk1;kn;k){intans;if(ne1k){intnum((k-ne-11)/2)*2;intk_k-num;// evenif(numno){ans0;}else{ansvec[1].back();intimax(0LL,k_-1);if(ine||k_0){ans(k1)?vec[1].back():0;}else{anspre[0][ne]-pre[0][ne-(i)];}}}else{if(no0){ans0;}else{ansvec[1].back();intik-1;anspre[0][ne]-pre[0][ne-(i)];}}coutans ;}coutendl;}D. Fibonacci PathsYou are given adirected graphconsisting ofnnnvertices andmmmedges. Each vertexvvvcorresponds to a positive numberava_vav​. Count the number of distinctsimple paths∗^{\text{∗}}∗consisting of at least two vertices, such that the sequence of numbers written at the vertices along the path forms a generalized Fibonacci sequence.In this problem, we will consider that the sequence of numbersx0,x1,…,xkx_0, x_1, \ldots, x_kx0​,x1​,…,xk​forms a generalized Fibonacci sequence if:x0,x1x_0, x_1x0​,x1​are arbitrary natural numbers.xixi−2xi−1x_i x_{i - 2} x_{i - 1}xi​xi−2​xi−1​for all2≤i≤k2 \le i \le k2≤i≤k.Note that a generalized Fibonacci sequence consists of at least two numbers.Since the answer may be large, output it modulo998 244 353998\,244\,353998244353.∗^{\text{∗}}∗A simple path in a directed graph is a sequence of verticesv1,v2,…,vkv_1, v_2, \ldots, v_kv1​,v2​,…,vk​such that each vertex in the graph appears in the path at most once and there is a directed edge fromviv_ivi​tovi1v_{i1}vi1​for alliki kik.挺好的一道题目可惜没写出来。对于图上的DP问题我们往往不知道怎么下手说白了就是不知道怎么设置初始状态因为图上往往有环对于这道题我们其实可以看成一种类似拓扑的结构因为斐波那契一定是递增的所以我们可以从最小的一批元素下手再从它们进行扩展。这里借助SPFA来写记f[u][val]表示以u为节点拓展到下一个数列需要val的方案数是多少f[u][val] 表示以u为节点拓展到下一个数列需要val的方案数是多少f[u][val]表示以u为节点拓展到下一个数列需要val的方案数是多少可以有转移v为u的出点u→v当vala[v]的时候f[v][a[u]a[v]]f[u][val]v为u的出点u →v当val a[v]的时候f[v][a[u] a[v]] f[u][val]v为u的出点u→v当vala[v]的时候f[v][a[u]a[v]]f[u][val]这里用 mapint, int 来记录值因为每个值的范围都是 long long但是数量又很少同时 建边的逻辑为e[u][val]表示从 u 出边下一个值为 val 的点的集合。注意这里不存在一个点只更新一次的情况所以我们只用一个 st 记录某个状态是否在 heap 中不在的话就加入否则不加入。不能按照 Dijkstra 的逻辑来不然是错误的。voidsolve(){intn,m;cinnm;vectorinta(n1);for(inti1;in;i)cina[i];priority_queuePII,vectorPII,greaterPIIheap;vectormapint,vectorinte(n1);vectormapint,intf(n1);mapPII,boolst;for(inti0;im;i){intu,v;cinuv;e[u][a[v]].push_back(v);f[v][a[u]a[v]];if(st[make_pair(a[u]a[v],v)]0){st[make_pair(a[u]a[v],v)]1;heap.push({a[u]a[v],v});}}intans0;while(heap.size()){auto[ne,u]heap.top();heap.pop();for(autov:e[u][ne]){if(st[make_pair(a[u]a[v],v)]0){st[make_pair(a[u]a[v],v)]1;heap.push({a[u]a[v],v});}(f[v][a[u]a[v]]f[u][ne])%mod;}}for(inti1;in;i){for(auto[_,c]:f[i]){(ansc)%mod;}}coutans%modendl;}F. Omega NumbersFor a given numbernnn, consider the functionω(n)\omega(n)ω(n), which is equal to the number of unique prime numbers in the prime factorization of the numbernnn.For example,ω(12)ω(22⋅3)2\omega (12) \omega (2^2 \cdot 3) 2ω(12)ω(22⋅3)2. Andω(120)ω(23⋅3⋅5)3\omega (120) \omega (2^3 \cdot 3 \cdot 5) 3ω(120)ω(23⋅3⋅5)3.For an array of natural numbersaaaand a natural numberkkk, we definef⁡(a,k)∑ijω(ai⋅aj)k\operatorname{f}(a, k) \sum_{i j} \omega(a_i \cdot a_j)^kf(a,k)∑ij​ω(ai​⋅aj​)kfor alliji jij.You are given an array of natural numbersaaaof lengthnnnand a natural numberkkk. Calculatef⁡(a,k)\operatorname{f}(a, k)f(a,k)modulo998 244 353998\,244\,353998244353.很麻烦的一题。首先要发现一个重要的性质即ω(x⋅y)ω(x)ω(y)−ω(gcd⁡(x,y))\omega(x \cdot y) \omega(x) \omega(y) - \omega(\operatorname{gcd}(x,y))ω(x⋅y)ω(x)ω(y)−ω(gcd(x,y))同时对于[1,2∗105][1, 2*10^5][1,2∗105]这个范围内的整数所有数字拥有质因子的个数都不会超过 7发现上述性质之后我们可以将问题转化为按照 gcd 分类统计 “恰好 gcdg 且ω(ai)ω(aj)Sω(a_i)ω(a_j)Sω(ai​)ω(aj​)S” 的对数然后它们的贡献就是(S−ω(g))k×对数(S−ω(g))^k×对数(S−ω(g))k×对数。这样按组分开计算的方式会使得复杂度大大降低可以通过题目的时间限制。那么怎么分组呢官方题解中给了如下做法cnt[x][len]:表示 数组中有多少个数 A满足A 能被 x 整除且 ω(A) len。注意len 指的就是 ω(A)不同质因子个数。cnt[x] 是对“能被 x 整除”的那些数组元素按 ω 值的分布统计。为什么要这么统计因为如果gcd(ai,aj)ggcd(a_i, a_j) ggcd(ai​,aj​)g那么aia_iai​和aja_jaj​都可以被ggg整除。我们先统计“都能被 g 整除的数”的分布这就是cnt[g]cnt[g]cnt[g]再用这些数配对计算候选对数最后用筛去掉 gcd 更大倍数的部分得到 “恰好 gcdg” 的对。怎么统计呢就是直接暴力枚举按照调和级数和质因子的个数枚举。dp[g][sumlen]:临时的 dp[g][sumlen] 最终表示恰好 gcd(ai,aj) g 且 ω(ai)ω(aj) sumlen 的 无序对数量i j 的对数。怎么得到呢先用 cnt[g] 计算“被 g 同时整除的数之间的所有配对数”并按 sumlen ω(ai)ω(aj) 累加到 dp[g][sumlen]这是包含了 gcd 可能为 g 的所有对也包括 gcd 更大倍数的情况。如果 len1 ! len2贡献是 cnt[g][len1] * cnt[g][len2]这些是有序配对数实际我们只要无序对所以在代码里枚举 len1 len2 用乘积。如果 len1 len2贡献是 cnt[g][len] * (cnt[g][len] - 1) / 2组合数保证 ij。然后用筛法从大到小枚举 g减去 dp[multiple_of_g][sumlen]把那些 gcd 实际上是 2g, 3g, … 的对去掉剩下的就是 gcd 恰好 等于 g 的对数。最后由公式 ω(ai * aj) sumlen - ω(g)就可以直接分组算贡献了ANS dp[g][sumlen] * pow(sumlen - ω(g), k);大致思路如上下面是代码consti64 mod998244353;intdx[4]{0,1,0,-1},dy[4]{1,0,-1,0};intqpow(inta,intk){a%mod;i64 res1%mod;while(k){if(k1)res(i64)res*a%mod;a(i64)a*a%mod;k1;}returnres;}intinv(intx){returnqpow(x,mod-2);}staticconstexprintMAX_N1e7;std::vectorintminp,primes;voidsieve(intn){minp.assign(n1,0);primes.clear();for(inti2;in;i){if(minp[i]0){minp[i]i;primes.push_back(i);}for(autop:primes){if(i*pn){break;}minp[i*p]p;if(pminp[i]){break;}}}}boolisprime(intn){returnminp[n]n;}voidsolve(){intn,k,Maxa;cinnk;vectorinta(n1),w(n1);for(inti1;in;i)cina[i];Maxa*max_element(range_(a));vectorvectorintcnt(Maxa1,vectorint(10,0));for(inti1;in;i){intxa[i];intc0;while(x1){intpminp[x];w[i];while(x%p0)x/p;}cnt[a[i]][w[i]];}for(intx1;xMaxa;x){for(inti2;i*xMaxa;i){for(intlen0;len8;len){(cnt[x][len]cnt[i*x][len])%mod;}}}vectorvectorintf(Maxa1,vectorint(17,0));for(intx1;xMaxa;x){for(intsumlen1;sumlen16;sumlen){for(intlen10;len18;len1){intlen2sumlen-len1;if(len20||len28)continue;if(len1len2)continue;if(len1len2){(f[x][sumlen]((cnt[x][len1]*(cnt[x][len2]-1)%mod)*inv(2)%mod))%mod;}else{(f[x][sumlen]cnt[x][len1]*cnt[x][len2]%mod)%mod;}}}}for(intxMaxa;x1;x--){for(inti2;i*xMaxa;i){for(intlen0;len16;len){((f[x][len]-f[x*i][len])mod)%mod;}}}w.clear();for(intg1;gMaxa;g){intxg;intcnt0;while(x1){intpminp[x];cnt;while(x%p0)x/p;}w[g]cnt;}intans0;for(intx1;xMaxa;x){for(intlen1;len16;len){(ans((qpow((len-w[x]mod)%mod,k)%mod)*f[x][len])%mod)%mod;}}coutansendl;}signedmain(){cin.tie(nullptr)-ios::sync_with_stdio(false);intT1;sieve(2e510);cinT;while(T--)solve();return0;}