首页 > 其他分享 >【题解】CodeForces-1913

【题解】CodeForces-1913

时间:2023-12-19 10:36:37浏览次数:39  
标签:Submission 题解 sum CodeForces 最小值 提交 区间 1913

Page Views Count

CodeForces-1913A Rating Increase

依题意模拟。

提交记录:Submission - CodeForces

CodeForces-1913B Swap and Delete

交换免费就是能任意重排,从头开始尽量填相反的,剩下只能删去了。

提交记录:Submission - CodeForces

CodeForces-1913C Game with Multiset

从大到小能减则减一定更优。

提交记录:Submission - CodeForces

CodeForces-1913D Array Collapse

认为两次操作覆盖到同一元素是操作有交,发现这等价于取并区间操作一次,没有被操作的可以视作对自己操作,那么就是划分若干区间,每个区间只保留最小值,求本质不同方案数。

设 \(f_i\) 表示以 \(i\) 为最后一个区间的最小值的方案数,枚举上一个区间的最小值 \(j\),充要条件是 \(\min(p_i,p_j)=\min_{k=j}^i \{p_k\}\)。

若 \(p_i<p_j\),即 \(pos_i\) 为序列中第一个小于 \(i\) 的位置,则 \(j\in [pos_i+1,i-1]\),可以前缀和转移。

若 \(p_i>p_j\),那么 \(p_j\) 是 \([j,i]\) 的最小值,发现这就是当前单调栈内所有元素,维护一个和即可。

提交记录:Submission - CodeForces

CodeForces-1913E Matrix Problem

首先 \(\sum A_i=\sum B_j\),考虑左部点为行,右部点为列的二分图,假设先把所有 \(1\) 翻成 \(0\),这样这些位置翻成 \(0\) 的费用是 \(-1\),其他位置是 \(1\),跑一个最小费用最大流即可。

如果担心出负圈可以权值都加 \(1\),最后答案再减去最大流。注意无解也要靠最大流是否等于 \(\sum A_i\) 判断。

提交记录:Submission - CodeForces

CodeForces-1913F Palindromic Problem

标签:Submission,题解,sum,CodeForces,最小值,提交,区间,1913
From: https://www.cnblogs.com/SoyTony/p/Solution_on_CodeForces-1913.html

相关文章

  • 【题解】CodeForces-1905
    CodeForces-1905AConstructiveProblems发现沿着对角线放就行了,答案是\(\max(n+m)\)。提交记录:Submission-CodeForcesCodeForces-1905BBegginer'sZelda最优操作每次删两个叶子(除了最后一次只剩两个节点),所以答案是叶子个数除以二上取整。提交记录:Submission-CodeForc......
  • Java面向对象程序设计(上海交通大学出版社)12章及以后的课后问题解析
    1)Map集合和Collection集合的区别是什么? Map集合和Collection集合都是Java集合框架中的接口,它们之间有一些关键的区别:元素存储方式:Collection:用于存储单一元素的集合接口。它继承自Iterable接口,包含常见的子接口如List、Set。Map:用于存储键值对(key-value......
  • Cesium开发遇到的问题解决
    问题1:后台缓存收回进程无法释放上下文[/BUSINESS的缓存的[10]%-请考虑增加缓存的最大大小。原因:出现该问题是Tomcat启动时,占用的缓存较大,Tomcat默认的缓存是10000KB.解决:需要调整Tomcat目录下\conf\context.xml文件中的缓存的最大值,需要添加在<Context></Context>标签内,添加项如......
  • 题解 LGP7294【[USACO21JAN] Minimum Cost Paths P】/ accoders::NOI 5696【棋子】
    problemFarmerJohn的牧草地可以看作是一个\(N×M\)(\(2≤N≤10^9,2≤M≤2⋅10^5\))的正方形方格组成的二维方阵(想象一个巨大的棋盘)。对于\(x∈[1,N],y∈[1,M]\),从上往下第\(x\)行、从左往右第\(y\)列的方格记为\((x,y)\)。此外,对于每一个\(y∈[1,M]\),第\(y\)列拥有一个......
  • JOISC2020题解
    \(\text{ByDaiRuiChen007}\)ContestLinkA.Building4ProblemLink题目大意给\(2n\)个数对\((a_i,b_i)\),构造一个非降序列\(c_i\)满足\(\forall1\lei\len,c_i\in\{a_i,b_i\}\),且\(c_i=a_i\)的位置恰好有\(n\)个。数据范围:\(n\le5\times10^5\)。思路......
  • Codeforces Round 834 (Div. 3)
    CodeforcesRound834(Div.3)A.Yes-Yes?题意:就是Y后面跟e,e后面跟s,s后面跟Y#include<iostream>usingnamespacestd;voidsolve(){stringx;cin>>x;intl=x.size();if(l==1){if(x[0]!='Y'&&x[0]!='e&#......
  • Codeforces Round 839 (Div. 3)
    CodeforcesRound839(Div.3)A.A+B?跳过太水了、、、、、#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){inta,b;scanf("%d+%d",&a,&b);cout<<a+......
  • boost beast http::read 一直阻塞不返回,问题解决, 使用parser对象的skip(true) 来解
    用beast作为客户端发送http请求后读web服务端返回的数据,遇到了http::read或http::async_read一直阻塞着,不返回,直到连接过期后被强制网络断开后read函数才返回。看了官方文档,文档里这么描述的,read要一直等到end_of_stream时才回退出阻塞状态。也就是连接失效后才行。但我们的......
  • 【POJ 2388】Who‘s in the Middle 题解(nth_element)
    描述FJ正在调查他的牛群,寻找最普通的奶牛。他想知道这头“中位数”奶牛产奶量:一半奶牛产奶的量与中位数相同或更多;一半的人给予同样多或更少。给定奇数头奶牛N(1<=N<10000)和它们的牛奶产量(1…1000000),求出所给牛奶的中位数,使至少一半奶牛所给的牛奶量相同或更多,至少一半奶牛的牛奶......
  • MySQL 8 手动安装后无法启动的问题解决
    首先的自我检讨与自我批评,最近有点懒,知识的更新慢,最近在更换系统到ubuntu22.04,废弃centos ,同时MYSQL都在8以上,之前MySQL都是在CENTOS7.5上安装,并且也都自动化安装,基本上没有问题,但到了ubuntu22.04基于对于系统的不熟悉,产生很多的问题。今天就梳理一下,转换了系统对于M......