首页
关于
Search
1
Codeforces Round 930 (Div. 2)
14 阅读
2
Codeforces Round 931 (Div. 2)
9 阅读
3
测试页面
6 阅读
4
Codeforces Round 922 (Div. 2)
6 阅读
5
Codeforces Round 926 (Div. 2)
6 阅读
默认分类
codeforces
登录
Search
算法小何
累计撰写
87
篇文章
累计收到
1
条评论
首页
栏目
默认分类
codeforces
页面
关于
搜索到
86
篇与
的结果
2024-08-26
Educational Codeforces Round 147 (Rated for Div. 2)
A.Matching算法本质思维题目大意给定由数组和?组成的字符串,?可以变为任意数字字符,输出其能表示的不存在前导0的数字个数。思路推演显然?在第一位就有9种可能,其他位置有10种可能。但是需要考虑自带前导0的字符串,这种字符串的答案为0。B.Sort the Subarray算法本质思维题目大意给定长度为n的数组a[] b[],其中b[]是由a[]对自身某个区间元素升序排序后的结果。(保证a[] b[]有所不同)输出长度最大的区间l r。思路推演显然,未排序的地方元素一定相同,排序的区域不一定相同。且元素不相同的地方一定属于排序区域。所以通过对比元素是否相同,确定最小的排序区域。对于在排序区域,但是位置不变的元素,左边的为最小值,右边的为最大值。按照这个规律扩展即可。C.Tear It Apart算法本质思维题目大意给定由小写字母组成的字符串s,进行尽可能少的以下操作,使得s变成由单一字符组成选择任意互不相邻的下标,删除下标元素,剩余字符按序重连输出最小化的操作次数。思路推演显然,最后的可能情况为26字母中的某个。假设剩下的字符传为c,则需要删除c之间的所有字符,发现十分简单,即其log2函数(向上取整)。同时,不删除任何c显然是最优解。D.Black Cells算法本质思维题目大意在一行无限长的方格地图上,存在n个不相连的区间。你操控一只画笔,想要涂(已知)k个格子,但仅能在区间中涂写,并且遵守以下规则:每个回合只能选择选择一个操作:右移一格、笔尖下放、笔尖提起当完成一次笔尖下方、笔尖提起后,画笔在中间所在的方格会被涂色(意思是最后必须笔尖提起)输出最小化回合数。思路推演显然,这题的矛盾点在于,如果我们考虑少走路,就尽可能地用前面的的区间。但是如果前面的区域比较小,则我们的下放、提起所损耗比较多。我们定性分析一下:对于一个长度x的区间若取收益为x,成本为x+2若不取收益为0,成本为x如果我们想在后面捞x收益回来的话,至少需要x的成本所以可知,若x>=2,则这个区间一定是要取的。对于x=1的区间,则存在取或不取2种可能。于是我们枚举最后走到的区间。前面大于1的区间都必取,先加起来,变量名pre若pre>k则continue若pre<=k先用当前区间补一下,若不够补再用之前的1区间补。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int l[maxn], r[maxn]; inline void solve() { //init cin>>n>>k; rep(i,1,n) cin>>l[i]; rep(i,1,n) cin>>r[i]; //cal int ans=1e18; int sum=0, sum2=0, cnt2=0; // sum表示前面区间的总和,sum2表示前面区间>1的总和,cnt2表示前面区间>1的个数 for (int i=1; i<=n; i++) { sum += r[i]-l[i]+1; if (sum >= k) // 当前存在解决方案 { if (sum2 > k) // 说明当前+之后的方案都不是最优方案 break; int cha = k-sum2; // 还差的格子数 int bu = min(cha, r[i]-l[i]+1); // 当前区间尽可能补格子数 int pos = l[i] + bu - 1; // 最后停留下来的位置 int res = pos + (cnt2 + 1 + cha-bu)*2; // 计算这个方案的成本 ans = min(ans, res); } // 善后 if (r[i]-l[i]+1 > 1) sum2 += r[i]-l[i]+1, cnt2++; } if (ans==1e18) ans=-1; cout<<ans<<endl; return; }E.Rearrange Brackets算法本质思维题目大意题意稍微难懂,细心阅读称括号字符串为规则的,当满足以下条件:其可分割为若干子序列,每个子序列都是()定义规则括号字符串的属性成本值:可以进行任意次以下操作:选择两个相邻的字符组成的(),删去他们,成本为右边括号字符数。多次操作的成本之和的最小值,为成本值现给定规则括号字符串s和整数k,可以进行k次以下操作,得到一个新的规则括号字符串。任意调整某个字符位置(即半个括号)输出最小化得到的规则括号字符串的成本值。思路推演成本值是这题的关键属性,我们先模拟一下,如何求解一个括号字符串的成本值。其最优解显然是从右边开始,有点类似剥洋葱——但是从内部剥开。随后允许调整单个字符,再模拟找最优解。这个也非常显然,(调整单个字符的)最优解为把最大洋葱的外皮剥开。思路和代码相当简单,完全不符合2100的题目难度。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>k>>s; stack<int> st; vector<int> v; for (int i=0; i<s.length(); i++) { if (s[i]=='(') st.push(i); else { int l=st.top(); int r=i; // 找到对应的括号对 st.pop(); v.push_back((r-l-1)/2); // 每个括号对对成本的贡献值 } } sort(v.begin(), v.end()); k = min(k, (int)v.size()); int ans = accumulate(v.begin(), v.end()-k, 0ll); // 丢掉最后k个最大值 cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 145 (Rated for Div. 2)
A.Garland算法本质思维题目大意给定长度为4、由数字组成的字符串s,表示有4个灯,不同的数字表示不同的灯。最初灯都是关闭状态,尽量少的进行以下操作,使得灯最后全部为打开状态:(不行输出-1)选择与上次操作选择不同种类的灯,改变其状态思路推演如果全部灯都是同一种类,理所当然不能全部打开。如果有3个灯一样,手动模拟一下发现至少需要6次。其他情况都不需要反复开关,4次就好。B.Points on Plane算法本质思维、二分题目大意给定n,需要我们在一个网格状的无限大棋盘上,需要放置n个棋子:棋子只能放在整数坐标上必须保证所有棋子之间的距离大于1定义最终棋盘的成本为:棋子与(0,0)的曼哈顿距离最大值。输出可以最小化的成本。思路推演很显然的二分答案,所以我们去找成本 --> 最多棋子的函数。手动模拟一下,就可以发现放置棋子有2种方式,一种是(0,0)放棋子的,一种是(0,0)不放棋子的。对于第一种方式:0~1 3~1+8 5~1+8+16……这是一个简单的等差数列(抛开第一个点)对于第二种方式:1~4 3~4+12 5~4+12+20……同样是一个简单的等差数列于是就简单地拿到了方程,二分即可。如果进一步检查的话,其实可以发现,当成本为x时,最多放置的棋子个数是x^2,可以进一步简化函数。但是请注意,自带的sqrt()在数字过大的时候有精度问题,1e18相当大,肯定有精度问题,需要自己手写。C.Sum on Subarrays算法本质题目大意对于长度为n的数组a[]来说,满足下列条件拥有魅力值:元素范围[-1e3 ~ 1e3]任意[l,r]范围内元素之和不等于0对于拥有魅力值的a[]来说,其魅力值的具体计算为:其中[l,r]范围内元素之和 > 0 的数目现在需要你构造出一个长度为n、魅力值为k的数组。n <= 30 t <= 5e3思路推演对于任何区间+个数的题,首先想到的就是固定某一端点。此题也是一样,假如固定左端点l后,能使得所有[l, ?]的元素和都大于0,则可以很轻松的凑出k来。显然这理论上可行。选择固定右端点:先将k分为若干个<=n且各不相同的数字,设为集合Q。历便右端点,当r 属于 Q时,表示[?, r]的元素和都需要大于0——相反不属于时,都需要小于0。对于当前右端点r如果r 属于 Q:找到[?, r-1]元素和的最小值,让a[r] = 最小值+1,保证[?, r]元素和都大于0如果r 不属于 Q:找到[?, r-1]元素和的最大值,让a[r] = 最大值-1,保证[?, r]元素和都小于0同时这个做法,显然是:保证所用元素绝对值尽量小为前提。此题做法很多,可以多看看开拓思路。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 D.Binary String Sorting算法本质思维、dp题目大意给定01字符串s,进行以下操作使得s变成一个非递减字符串:1e12元:交换2个相邻字符1e12+1元:去掉一个字符输出最小化花费。s.length <= 3e5思路推演-1这个价格,表达的意思是:尽可能减少操作次数如果操作次数一致,尽可能使用交换操作手动模拟一下就知道,去掉操作是显然优于交换操作(即交换一定可以用去掉代替、去掉不一定用交换代替)。所以就想到,可以先思考去掉操作,找到最小操作值,然后再琢磨把其中的部分换成交换。历便s最后01的分界线,前导1+后导0,就可以找到最少的去掉操作次数。随后发现,当人为设定[1, l-1]全为0、[l, n]全为1的情况时,只有s[l-1]=1 && s[l]=0的情况,交换替换去掉才可以降低成本。所以我们只需要历便的时候,人为检测一下即可。思路推演-2还可以思考一下dp方向,操作简单+不递减的特点,是可以构成前后区间的联系的。定义dp[x]表示第s[1~x]变成不递减字符串的最少花费。当我们想要扩展到dp[x+1]时:如果s[1~x]末尾没有1很高兴,不用花钱,不管s[x+1]是1还是0,都可以直接放进去如果s[1~x]末尾有1个1如果s[x+1]是0,可以用交换,最省钱如果s[1~x]末尾有多个1如果s[x+1]是0,那还是去掉最省钱。可以看到,我们简化为了3个状态,可行。(具体的状态转变不详述了,看代码)ac核心代码-1头文件、宏定义、快读模板、常见变量、常见变量等略。 int pre[2][maxn]; int que(int l,int r,int x) { return pre[x][r]-pre[x][l-1]; } inline void solve() { //init cin>>s; n=s.length(); s=" "+s+" "; //可能会访问s[0]和s[n+1] //cal 预处理前缀和 for (int i=1; i<=n; i++) { pre[0][i]=pre[0][i-1]; pre[1][i]=pre[1][i-1]; pre[s[i]-'0'][i]++; } //cal 2 int qu=INF, huan=INF; for (int i=1; i<=n+1; i++) //[1, i-1]为0,[i, n]为1 { int n_qu = que(1, i-1, 1) + que(i, n, 0); //全去掉操作 if (qu + huan > n_qu) // 更新答案 { qu = n_qu; huan = 0; } if (s[i]=='0' && s[i-1]=='1') // 如果可以用1个交换替换2个去掉 { n_qu-=2; int n_huan=1; if (qu+huan > n_qu+n_huan) //重新更新答案 { qu = n_qu; huan = n_huan; } else if (qu+huan==n_qu+n_huan && huan<n_huan) { qu = n_qu; huan = n_huan; } } } //out int ans = qu*((int)1e12+1) + huan*(int)1e12; // 奇葩错误:double前12位准的,这里超了,最后的那个+1在转int的时候会被舍弃 cout<<ans<<endl; return; }ac核心代码-2int dp[3][maxn]; //dp[i][j]:i表示状态,j表示s[1~j]的最小成本 inline void solve() { //init cin>>s; n=s.length(); s=" "+s; //cal int price[2]; price[0] = 1000000000000 + 1; // 去掉的花费 price[1] = 1000000000000; // 交换的花费 for (int i=1; i<=n; i++) { if (s[i]=='1') { dp[0][i] = dp[0][i-1] + price[0]; dp[1][i] = min(dp[0][i-1], dp[1][i-1]+price[0]); dp[2][i] = min(dp[1][i-1], dp[2][i-1]); } else if (s[i]=='0') { dp[0][i] = dp[0][i-1]; dp[1][i] = dp[1][i-1]+price[1]; //dp[1][i]有可能由dp[2][i-1]去掉操作转化而来,但是保证那个不是最优解,且会破坏状态,所以不写 dp[2][i] = dp[2][i-1] + price[0]; } } //out int ans = min(dp[0][n], min(dp[1][n], dp[2][n])); cout<<ans<<endl; return; }
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 144 (Div. 2)
A.Typical Interview Problem算法本质思维题目大意使i顺序历遍[l, r]如果i%3==0则输出F(先判断)如果i%5==0则输出B现在给出一个string,判断是否存在如此的[l r]。思路推演模3模5,直接就想到循环节。找最小公倍数15,可知肯定15个数字为一个循环节。手动模拟1~15:FBFFBFFB因为担心首尾相连的情况和考虑到string的长度,将FBFFBFFB乘3,然后用自带的find方法判断是否可行。B.Asterisk-Minor Template算法本质思维、模拟题目大意(改)*可以表示任意长度的任意字符串(包括空字符串)。现在给出a b两个字母组成字符串,请设计一个字符串满足以下:可以使用*包含a b两种情况*的个数小于等于字符串长度的一半可以请输出此字符串,不行则输出No。思路推演需要尽量找到a b相同的字母来平衡*的数目。手动模拟一下即可发现,首尾其一字母相同即可。其他则需要中间有2个字母连着相同。重点在于要上手模拟一下,规律就很容易看出。C.Maximum Set算法本质思维题目大意给定一对l r,用[l, r]范围的数字建立一个集合(数字不重复)。若集合内数字两两为可整除关系,则称之为美丽集合(只有一个数字的集合也美丽)。集合的数字个数为集合的长度。找到所有美丽集合最长的集合,输出其长度,并且求出有多少个同样长度的美丽集合(%mod)。思路推演这类题乍一看比较唬人,都是些新鲜玩意。实际做题的时候不要怕,都是纸老虎!既然没怎么见过,就按照其要求先模拟一下。要求最长和美丽,首先可以想到的就是从l出发,每次*2计算。如此很快就可以得到最大长度。此时思考其他同长的美丽集合。有2个方向:从l+i出发最远的可行地方,可以用r向下除2来获得,这里称之为l_max将其中的*2改成*3 *4...可以很容易发现,最多将其中一个*2改为*3已知[l, l_max]都是可以通过*2来完成美丽集合的。其中能否将*2换成*3需要判断,因为单调性,所以可以二分判断。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init int l, r; cin>>l>>r; int len=0, x=l; while (x<=r) { x*=2; len++; } int ci=len-1, l_max = r; while (ci--) l_max/=2; //cal int ans=l_max-l+1; //全部都可以*2变成美丽集合 int ll=l, rr=l_max; int res=l-1; //最后res-ll+1表示有这么多个数字可以将*2替换成*3 while (ll<=rr) { int mid=(ll+rr)/2, max_val=mid; if (len-2>0) //len个数字就应该有len-1个*2,换一个*3,还有len-2个 max_val = mid*qpow(2, len-2); max_val *= 3; if (max_val > r) //说明不行 rr = mid-1; else { res = mid; ll = mid+1; } } ans += (res-l+1) * (len-1) % mod; //加上可以替换*3变成美丽集合的 ans %= mod; //out cout<<len<<" "<<ans<<endl; return; }D.Maximum Subarray *算法本质思维题目大意给定数组a[],你需要选择其中k个不同下标使其+val,其他下标都会-val。完成操作后选择最大子段和,报告其最大值。注:val可能是负值。n <= 2e5 k <= 20思路推演此题很容易让人想到最大子段和。最大字段和的复杂度是O(n),此题的k也相对小,感觉上是最大字段和的变种。观察其中的规律,当val>0可以很明显的发现其+val的下标要在子段内。同时将val<0情况转化为val=-val, k=n-k,方便统一思考。发现+val有聚集的倾向,直接人为规定所有的+val都必须要贴在一起。并且规定子段一定贴在+val的边缘当+val的长度为n-k时,其存在的可能就及其有限(k种):枚举所有的n-k长度的+val情况,人为设定子段贴边,用前缀和可以快速暴力出答案当+val的长度为n时同样枚举所有的k长度的+val的情况,但是两边采用最大子段和预处理,同样nk暴力出答案。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 140 (Rated for Div. 2)
A.Cut the Triangle算法本质模拟题目大意给定一个面积不为0的三角形,需要你判断是否可以通过竖切or横切分成2个面积不为0的三角形。思路推演只要保证不是水平+竖直方向的直角就好了。B.Block Towers算法本质思维题目大意有n个“塔”,每个塔由a[]的积木堆成,只有积木严格多余的塔之间可以传递积木(每次传递一块)。请问第一个塔最多可以有多少个积木。思路推演优先用较少的积木,贪心处理。title算法本质题目大意思路推演$i + 1\sim j $ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 D.Playoff算法本质思维题目大意有2^n个人,其id各不相同,并且集合是一个排列。现在任意调整他们的位置,其每天会两两战斗,淘汰一半的人,总共战斗n天决出胜者。现在给出一个字符串S,其s[i]=1表示第i天,id值更大的人会获胜,反之亦然。请输出:可以通过调整位置最后胜出的id。思路推演假设当前人id为x。如果当前轮id大的胜就需要制造一个和x一模一样境遇的点,然后放在x下面,假设为y。小于y的值一定小于x,大于y的值无法判断。所以小于x的值的个数*2+1了如果当前轮id小的胜同理,大于y的值的个数*2+1了ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>s; s = " " + s; //cal int da=0, xiao=0; for (int i=1; i<=n; i++) { if (s[i]=='1') xiao = xiao*2+1; else if (s[i]=='0') da = da*2+1; } //out for (int i=xiao+1; i<=qpow(2,n)-da; i++) cout<<i<<" "; cout<<endl; return; }
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 139 (Rated for Div. 2)
A.Extremely Round算法本质模拟题目大意给定一个n,求1~n中美丽的数字个数。美丽:数字十进制中,有且仅有1个位数字不为0:如1、7、100、4000。思路推演以十进制的位为单位,第一位、第二位……实际做的时候,为了抢时间,考虑可以打表,写了一个暴力打表预处理。B.Notepad#算法本质模拟题目大意给出一个长度为n的字符串s,现在需要判断能否用至多n-1次操作制造出字符串t,其等于s。每次操作可以:向t末尾加入任意一个字符复制t的某个子字符,在末尾粘贴思路推演至多n-1次,考虑能不能有一次复制粘贴相当于多次加字符。将t中所有长度为2的子字符串放入set,添加新字符的时候检测。C.Hamiltonian Wall算法本质模拟题目大意给出一个2*m的格子,格子只有黑白两种颜色。可否找到一个路径走遍所有的黑色格子(不准重复走)。思路推演因为只有2行,从左向右推进即可。对于每一列,只有数种情况:上下都黑可以通过,方位改变。某一格黑方位是否一致,一致可以通过无黑不可通过D.Lucky Chains算法本质思维题目大意给定一对x y(x<y),对于答案k来说,任意的0 <= val < k,都满足gcd(x+val, y+val)==1的情况。输出最大化k。(无限大请输出-1)思路推演可以发现,x y的差是不变的,而根据基本的数学定理可知,当gcd(x+v, y-x)==1时,x+v y+v也互质。所以说本质上,就是y-x分解的各种素数,会像拦路虎一样拦截逐渐增大的x+val。这个计算是相当简单的,但是可能会T,请用注意下面的优化:先用埃式处理素数,用已经获得的素数集分解质因数用int别用long long(可能是为了卡掉普通的质因数分解方法,时间卡的比较紧)E.Decomposition算法本质思维、状压dp题目大意给出长度为n的数组a[],所有元素范围在0~3。对于某个a[]的连续子数组依,其中元素次放入分组器使得其分为若干组:(设放入a[i]时已经存在k组)依次讲元素尝试放入前k组,若a[i]与当前组的末尾元素值按位和大于0,则将a[i]放入当前组的末尾若当前k组能无法接受a[i],则新开编号为++k组,放入a[i]每个a[]的连续子数组对ans的贡献是其最后的组数(k值)。计算所有的a[]连续子数组的k值和——ans。n <= 3e5思路推演按位和、0~3的小大……毫无疑问,需要先找到规则的特征。0值在任意时候都会单独成立一组除去0值,其他元素最多成立3组这是一个想到有效的结论,如果抛去0值,我们的状态数最多存在3*4*4=48种,如果满足前后缀的转移,则毫无疑问,使用状压dp的复杂度是ok的。事实如此。代码思路dp(状态, pos)表示:目前状态经历了a[pos]的值 + 经历了a[pos~pos+1]的值 + 经历了a[pos~n]的值。状态用vector<int>来表示。我们固定左边界l,对于每个左边界,都ans += dp(全0状态, l)。dp(当前状态, i) = dp(经历i后的状态, i+1) + 贡献值(经历i后的状态的元素个数)这里有一些问题的是,对于0,理论上我们也需要开一个新组,但是这样会导致内存爆掉。所以我们可以统一记录当前0值的贡献,假设我们固定的左值下标为l,当前0值下标为i,在r取i~n时都会具有1的贡献,所以直接加上n-i+1的值即可。其实其他值也可以,我们可以针对每一个导致开新组的元素,如果其下标为i,则直接加上n-i+1的值。不过为了便于理解,还是挨个加。思路推演-2(未ac)同时因为状态足够少,我们可以推出新组数变化的特征:(暂时自动忽略0)1组-->2组出现1 2或者2 12组-->3组若前面有1 2,则是3 2 2 ... 2 2 1若前面有2 1,则是3 1 1 ... 1 1 2所以搜索所有特征区间,这4种特征分别放入4个队列,可以叫做q12 q21 q321 q312。保证左边界较小的在前。(顺序历便的话自动就是左边界小的在前)随后枚举l = 1~n。详细看代码,但是WA16,不知道哪错了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; map<vector<int>, int> dp[maxn]; vector<int> go(vector<int> tai, int pos) { int val=a[pos]; if (val==0) return tai; // 默认状态不添加0 else { bool f=0; for (int i=0; i<tai.size() && f==0; i++) if ((tai[i]&val) > 0) { f=1; // f==1表示不需要新加组,更新状态,但是此点贡献为0 tai[i] = val; // 更新状态 } if (f==0) // 说明需要加组 tai.push_back(val); return tai; } } int f(vector<int> tai, int pos) //记录状态、当前pos { if (pos == n+1) return 0; if (dp[pos].count(tai)) return dp[pos][tai]; //记忆化 auto nxt=go(tai, pos); //tai经历a[pos]后的状态 int res = nxt.size() + f(nxt, pos+1); //当前贡献值 + 之后的贡献值 if (a[pos]==0) res+=n-pos+1; //0值的贡献值单独计算 return dp[pos][tai]=res; } inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; //cal int ans=0; for (int l=1; l<=n; l++) //枚举固定左边界 ans += f(vector<int>(0), l); //out cout<<ans<<endl; return; }
2024年08月26日
0 阅读
0 评论
0 点赞
1
...
10
11
12
...
18