首页 > 其他分享 >agc032 A~E 题解

agc032 A~E 题解

时间:2024-11-09 17:30:21浏览次数:4  
标签:度数 max 匹配 一个 题解 蓝线 度点 agc032

a

倒推,每次删掉最后一个b[i]=i的即可

b

一开始发现可以构造完全二分图,使两边和同为S,这样每个点的和=对面二分图点的和=S,然后n=6和为奇数

进一步发现可以直接分成A组组内和为B的组,然后组之间连边,此时S=(A-1)B,有AB=n(n+1)/2

当n为奇数时取A=(n+1)/2,B=n,n单独一组其他大匹配小;n为偶数时A=n/2,B=n+1,直接大匹配小

c

图连通,显然不能有奇数度数

可以一眼盯真发现最大度数=2时只有一个环,No

最大度数>=6时,取最大度数点作为起点,每次出-进作为一个环,那么至少有3个环,Yes

最大度数=4且有>=3个4度点时,任意取3个4度点xyz,从其中一个4度点出发,除了x-y-z-x-y-z-x只能走出2个环以外其他都是至少3个环
手玩一下,发现x-y-z-x-y-z-x这样x,y,z之间都有2条路,所以存在x-y-x-y-z-y-x的走法,这样也有至少3个环,所以都是Yes

当最大度数=4且有1个4度点时是两个环+一个交点,No

最后剩下最大度数=4且有2个4度点,此时可能是2个环相交两次,也可能是3个环按顺序相交。删掉其中一个4度点,连通是前者,不连通是后者

d

由于A操作可以任意选区间,所以等于把任何一个数往后移;B操作等于前移

考虑序列2 5 1 4 7 3 6 8,选择2468不动,其间大的左移小的右移;所有的方案都可以这样表示,变成选一个上升子序列不动,其他的左/右(不用严格保证两项之间无再选,少选了更劣)

所以直接dp,\(f[i][j]\)表示考虑完1..i怎么动,最后一个不动的大小为j,j单调递增

加入一个小于j的只能左移,加入一个大于j的可以右移或者留下作为j'
在序列前加一个0,初值为\(f[0][0]=0\)

非常简单(

e

重要结论(from 小粉兔):

证一下右边3个:

旧蓝线(a,b)>=新蓝线,并且旧蓝线和新红线之间有公共元素b,所以新红线为(b,c)

此时旧蓝线=a+b,新红线=b+c-m=(c-m)+b,a>=0>c-m,所以旧蓝线>=新红线

因此旧max>=旧蓝线>=新max,所以会变小


然后合法的分界点序列(偶数位置)是一段区间,过左会让右边最小的匹配对小于m,过右会让左边的大于等于m
(最大匹配最小实际是max最小,min最大的匹配方式),且一定存在至少一个合法分界(初始任意连,然后自然调整得到一种方案)

而且分界越往左答案越小,所以二分找到第一个满足右侧合法性的即可

f(不会)

没想明白转化的正确性(

标签:度数,max,匹配,一个,题解,蓝线,度点,agc032
From: https://www.cnblogs.com/gmh77/p/18537012

相关文章

  • NOIP集训 P11071 「QMSOI R1」 Distorted Fate 题解
    题解:P11071「QMSOIR1」DistortedFate给定一个长度为\(n\)的数组\(A\),你需要完成以下\(q\)次操作。1.1lrx将\(A_i(l\lei\ler)\)异或上\(x\)。2.2lr求:\[(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}\]其中\(\bigcup\)表示按位或。Input第一行输入......
  • [COCI2022-2023#5] Slastičarnica 题解
    前言题目链接:洛谷。题意简述一个长为\(n\)的序列\(\{a_n\}\)和\(q\)次操作,第\(i\)次操作中,你可以删除序列长为\(d_i\)的前缀或后缀,并需要保证删除的所有数\(\geqs_i\)。每次操作前,你可以选择任意长度的前缀或后缀,并将其删除,也可以不操作。请问,在你不能进行下一次操......
  • CodeforceTon Round 4 div1 + div2 题解
    题解A-EDreamissofar~A.BeautifulSequence检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上,遍历即可#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){ intn; cin>>n; vector<int>a......
  • CF607B Zuma 题解
    CF607BZuma不知道为什么你谷会评蓝,这不是很基础的区间DP吗。Problem-607B-Codeforces题意简述消除回文子串的最小次数。思路对于区间\([i,j]\),如果它是回文的,那么消除它所需的次数是\(1\)。如果它不是回文的,但是\(a[i]==a[j]\),那么当区间\([i+1,j-1]\)被消除到只剩下......
  • [ARC158C] All Pair Digit Sums 题解
    C-AllPairDigitSums题意:设\(f(x)\)为\(x\)的数字和。例如\(f(158)=1+5+8=14\)。给定一个长度为\(N\)的正整数序列\(A\),求\(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。分析:首先明确\(f(x)\)为\(x\)的数位和。举例情况:若有两个数分别为:\(12,21\)。\[f(......
  • QT中大量数据存储至excel的问题解决
            因为这个问题困扰了我很久,所以在这里记录一下,顺便给可能会遇到类似问题的人提供一点帮助。        在qt中,如果用C++处理数据保存到excel,正常来说在pro文件中添加axcontainer 然后就能够调用到excel,但是这只能适用于数量级没那么大时的需求。  ......
  • ffmpeg问题解决:Unrecognized option 'preset'. Error splitting the argument list: O
    来到这里,十有八九是手动编译安装的ffmpeg,在跑视频流程序或命令时出现这个问题。跟这个报错:ffmpeg:errorwhileloadingsharedlibraries:libx264.so.164:cannotopensharedobjectfile:Nosuchfileordirectory的错误本质是一样的,都是由于ffmpeg时使用到了libx264,而在......
  • 讲座の题解
    讲座配套题单的题解喵每题的文字解释会逐渐补充,如果有疑问直接私信喵目录讲座配套题单的题解喵目录A-看看你会不会用电脑B-求求你不要用内置函数C-GPAD-minE-for循环大神F-居然有人说这个是线性代数G-高三同学秒了H-无穷级数I-不要用内置函数......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......
  • [USACO23FEB] Problem Setting P 题解
    [USACO23FEB]ProblemSettingP题目说的很绕,意思就是所有验题人都认为题目难度顺序单增。发现\(m\)很小,很容易想到状压。把H看作\(\tt1\),E看作\(\tt0\),则我们得到\(m\)个长度为\(n\)的\(\tt01\)串,这就是每道题的“状态”。发现状态相同的题没有本质区别,所以我们......