首页 > 其他分享 >Educational Codeforces Round 151

Educational Codeforces Round 151

时间:2023-08-05 16:35:40浏览次数:55  
标签:151 Educational sum Codeforces 操作 Round

Educational Codeforces Round 151

T1

就是大水题但写了很长时间

构造题。首先分类讨论:

  1. 当 \(x\ne1\) 时我们构造的序列长度就为 \(n\) ,序列就是 \(n\) 个 \(1\) 。
  2. 当 \(x= 1\) 时,
    1. 当 \(n\) 为偶数,我们就枚举 \(1\sim k\) 且 \(i \ne x\) ,只要 \(n\) 能整除 \(i\) ,长度为 \(n \div i\) 每个数即为 \(i\) 。
    2. 当 \(n\) 为奇数,跟偶数差不多,只需要将 \(a\) 的第一项改为 \(3\) 即可。

T2

一眼题

本题的思路就是将一个二维的坐标系转换为两个一维的线段,能计算公共部分的前提显然是b、c基于点a的偏移量的正负性相同,那么分别计算两个一维线段的贡献即可。赛时10minAC。(比T1快了 \(7\) 倍)。

T3

这题没什么时间,看完题目以后以为是 数位dp ,没想出来转移方程。题解发现就是个暴力

用两个指针 \(i\) 和 \(j\) ,其中 \(i\) 指向 \(s\) , \(j\) 指向 \(t\) 。在 \(i\) 遍历的同时,判断当前的 \(s_i\) 是否将当前的 \(t_j\) 所有可能性全都试过。如果全都试过了,代表 \(l_j\) 到 \(r_j\) 的所有可能性都会是字符串 \(s\) 子序列的一部分,再往后看下一个 \(t_j\) 即可。如果没全都试过,将当前出现的 \(s_i\) 标记。

若是当前的 \(j\) 超过了 \(m\),说明字符串 \(t\) 的所有可能性都是字符串 \(s\) 的一部分,即构造不出符合要求的字符串 \(t\)。

T4

这题主要是思路。

这题我们要先记 \(sum_i\) 为前 \(i\) 个数的前缀和。那么很显然 \(k\) 的一种取值为 \(sum_i\) ,其中 \(1\le i \le n\) 。那么我们考虑进行了前 \(i\) 次操作且 \(x\ge k\) 成立后,进行第 \(i + 1\) 到 \(n\) 此操作对 \(s\) 产生的影响。那么在不考虑 \(k\) 的保底作用下,\(x + sum_n-sum_i\) 就为最终的答案,且这个数会小于真实的答案。接着我们考虑真是答案,当 \(x\) 达到了某个极大值刚好达到 \(k\) ,后面的若干次操作使它在保底作用下不小于 \(k\) ,最后可能有若干次操作使其增长,其中 \(x\) 一直不小于 \(k\) 。那么既然我们已经在最后的若干次操作中拜托了 \(k\) 的限制,我们就枚举这个摆脱限制的起始位置。那么第 \(i\) 次操作中 \(sum_i\) 的最大值,这个最大值就是 \(k\) 。此时在 \(x\) 达到最大值 \(k\) 后,经历第 \(i\) 次操作后,\(s=k\) 。(代码特别好实现)

T5

​ 不会

T6

​ 不会

标签:151,Educational,sum,Codeforces,操作,Round
From: https://www.cnblogs.com/messiljk/p/17608123.html

相关文章

  • Practice on Codeforces and Atcoder in August
    EducationalCodeforcesRound151A~ECodeforcesRound#879Div.2CodeforcesRound#882Div.2CodeforcesRound#873Div.2......
  • Educational Codeforces Round 151 (Rated for Div. 2) 题解
    A.ForbiddenInteger显然,当\(x\not=1\)时,直接输出\(n\)个\(1\)即可否则,如果\(n\)为奇数,那就输出\(\lfloor\frac{n}{2}\rfloor-1\)个\(2\)和\(3\);如果\(n\)为偶数,那就输出\(\frac{n}{2}\)个\(2\)(要看一下\(k\)的大小)B.ComeTogether因为Bob和Carol都......
  • Codeforces Round 882 (Div. 2)
    link题号:CF1847A~FA题意:给定一个数组\(\{x_1,x_2,\cdots,x_n\}\)和一个整数\(k\),记\(f(l,r)=\sum_{i=0}^{i<r-l}|x_{l+i}-x_{l+i+1}|\),求将数组划分为\(k\)个部分的划分方案,使得对每个部分的\(f(l,r)\)之和最小.题解:简单题,首先我们注意到,如果将\(l,l+1\)隔开,那......
  • Codeforces Round 424 (Div. 1)D. Singer House
    传送门显然要自底向上进行\(dp\)深度相同的子树结构相同所以可以利用深度来代表子树。那么就应该统计出有向路径的个数。考虑路径由链所拼成。那么状态里应该有有向链的条数。设\(f_{i,j}\)表示深度为\(i\)链条数为\(j\)的方案数。不选当前的节点则\(f_{i,j}=f_{i+1,k}\cdot......
  • Codeforces 1855B:Longest Divisors Interval 最长的连续约数区间
    1855B.LongestDivisorsIntervalDescription:对于一个整数\(n\)\((1\leqn\leq10^{18})\),找到一段最长的区间\([l,r]\),使得区间内所有数均为\(n\)的约数。Analysis:如果\(n\)是一个奇数(非\(2\)的倍数),由于\(odd=odd\timesodd\),则不可能有连续的两个整数均为......
  • Codeforces Round 449 (Div. 1) D. Nephren Runs a Cinema 卡特兰数
    luogu链接题意不再赘述。优先枚举的应该是\(VIP\)用户,枚举范围应该是\([0,n-l]\)之后总客户数为\(s=n-i\)再考虑枚举\(100\)的总人数为\(x\)则要求\(s-2x\in[l,r]\)这部分方案数应该为从\((0,0)\)到达\((s-x,x)\)且不越过\(y=x\)的方案数。利用折线法求出方案数为\(C(s,x)......
  • Educational 151 DIV2 T3 strong password
    T3strongpassword就是对于输入的每一个\(l,r\),我们遍历\(s[l]~s[r]\),对于每次遍历,我们设置一个临时指针\(cur\),然后通过指针右移寻找所需要的值在外面我们弄两个指针,分别代表每次遍历\([l,r]\)的区间的指针\(nmx\)和全局指针\(mx\)我们用临时指针更新单次区间的......
  • Educational Codeforces Round 38 C- F
    EducationalCodeforcesRound38C-Fhttps://codeforces.com/contest/938今天写出了三题ovoC.ConstructingTests多画几个图就能发现,对于\(n\timesn\)的正方形来说,要使得\(m\timesm\)的子正方形至少有一个\(0\),则最少的\(0\)个数为\(\lfloor\frac{n}{m}\rfloo......
  • Educational Codeforces Round 104
    https://codeforces.com/contest/1487A.Arena统计与最小值不同的数字数量。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintM=(1<<15)-1;voidsolve(){intn;cin>>n;vector<int>a(n);for(......
  • Educational Codeforces Round 88
    A.BerlandPoker先尽可能的吧小丑给一个人,在把剩下的小丑尽可能的平分,最后计算差值即可。#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,m,k,t;cin>>n>>m>>k,t=n/k;inta=min(m,t);m-=a,k--;intb=(m......