首页 > 其他分享 >AtCoder Grand Contest 001

AtCoder Grand Contest 001

时间:2024-05-05 18:12:48浏览次数:25  
标签:AtCoder DAG 奇数 Contest 构造 001 条边 考虑 回文

D. Arrays and Palindrome

如果两个字符要求相同就给它们连边,对于一个长度为 \(x\) 的回文串,\(x\) 是偶数会连 \(x/2\) 条边,奇数会连 \(x/2 - 0.5\) 条边。

\(a\) 和 \(b\) 两个序列总和为 \(2n\),要让 \(n\) 个字符相同至少连 \(n - 1\) 条边,也就是奇数个数超过 \(2\) 时一定无解。

考虑如何构造,手玩应该会发现有一种左右横跳的构造,对于单个回文串,发现构造一个 \(x - 1/x + 1\) 的回文串就能把这个回文串串起来,\(+1/-1\) 可以用来拼接相邻两个回文串,这样能构造出 \(m = 2\) 的情况:

\(m > 2\) 可以考虑中间的串长度不变直接错位,这在偶数的情况下能达到同样的效果,但是奇数就不行了,所以直接把最多两个奇数放到序列的两端上。

E. BBQ Hard

去掉 \(i < j\) 的限制。

考虑格路计数,转换成求每对 \((i, j)\),从 \((-a_i, -b_i)\) 到 \((a_j, b_j)\) 的方案数之和。

值域很小,\(O(V^2)\) 递推就行了。

F. Wide Swap

显然从值域入手好做,因为,交换操作变成相邻的了。(即在逆排列 \(q\) 上考虑)

然后考虑相对顺序 \(i < j\),如果 \(|q_i - q_j| < K\),那么 \(q_i\) 一定在 \(q_j\) 前面,相当于建立了一个 DAG 的限制关系。

在 \(q\) 上怎么贪呢,如果没有限制,我们首先希望 \(q_i = 1\) 挪到越前面越好,然后是 \(q_i = 2\)。那在 DAG 上拓扑,用优先队列维护就好了。

这个 DAG 只需要找到每个 \(q_i\) 最大的 \(j < i\) 满足 \(|q_i - q_j| < K\) 且 \(q_j > q_i\) 就好了,因为 \(q_j < q_i\) 本身就会先决策,\(< j\) 的会和 \(j\) 串起来。

线段树维护即可。

标签:AtCoder,DAG,奇数,Contest,构造,001,条边,考虑,回文
From: https://www.cnblogs.com/zlxFTH/p/18173520

相关文章

  • AtCoder Beginner Contest 352题解
    AtCoderBeginnerContest352Time:2024-05-04(Sat)20:00-2024-05-04(Sat)21:40AAtCoderLine问题陈述AtCoder铁路线有$N$个车站,编号为$1,2,\ldots,N$。在这条线路上,有趟进站列车从$1$站出发,依次停靠$2,3,\ldots,N$站,有趟出站列车从$N$站出发,依次停......
  • AtCoder Beginner Contest 352 考试总结
    前言正常发挥。属于是\(4\)个月没搞OI,复健成功了!得分明细:ABCDEFGTotal√√√√√××1475改题明细:ABCDEFG√√√√√××第一次正式rated打AT,行吧!A.AtCoderLineProblemAtCoder铁路线有\(N\)个车站,编号为\(1......
  • AtCoder abc352
    EProblemStatementYouaregivenaweightedundirectedgraph$G$with$N$vertices,numbered$1$to$N$.Initially,$G$hasnoedges.Youwillperform$M$operationstoaddedgesto$G$.The$i$-thoperation$$(1\leqi\leqM)$$isasfollows:Youar......
  • P1028 [NOIP2001 普及组] 数的计算
    题目链接:观察样例。当输入\(n=6\)时,6本身算一个。当6后加的数为1时只有一个。6后加的数为2时有62,621两个。6后加的数为3时有63、631两个。可以看到,我们往\(n\)后加的每一个不超过\(\dfrac{n}{2}\)的数都可以继续延伸。考虑递推。\(f[i]\)表示以\(i......
  • AtCoder Beginner Contest 351
    A-Thebottomoftheninth(abc351A)题目大意给定\(9\)个\(a_i\)和\(8\)个\(b_i\),问最后一个\(b_9\)是多少,使得\(\suma_i<\sumb_i\)。解题思路答案就是\(\suma_i-\sumb_i+1\)。神奇的代码a=sum(map(int,input().split()))b=sum(map(int,input().......
  • [oeasy]python0015_键盘改造_将esc和capslock对调_hjkl_移动_双手正位
    键盘改造......
  • [atcoder]【LCR114] [
    importjava.util.*;classSolution{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();Stringstr=solution.alienOrder(newString[]{"wrt","wrf","er","e......
  • P2024 [NOI2001] 食物链
    原题链接题解带权并查集的应用,普通的并查集只能表示结点间的一种关系(如同一集合中的都是朋友)。而带权并查集的结点权值表示该结点与根结点的关系。相对应,带权并查集的路径压缩也复杂了一点。code #include<bits/stdc++.h>usingnamespacestd;constintN=5e4+5;intn,k......
  • Django Error: [WinError 10013] An attempt was made to access a socket in a way f
      D:\06softw-dev-202306\manage.pyrunserverWatchingforfilechangeswithStatReloaderPerformingsystemchecks...Systemcheckidentifiednoissues(0silenced).May03,2024-10:02:12Djangoversion3.2.18,usingsettings'MPDB.settings......
  • 001量化项目总结 --01获取实时价格
    一、获取实时价格deftdxgetprice(self,scode):#取实时价格price=0.0pmarkcode=0sip=''sport=0time_now=datetime.now().minuteif(scode[0]=='0'andscode[1]=='0')orscode[0]=='3&......