首页 > 其他分享 >[NOIP2024]遗失的赋值

[NOIP2024]遗失的赋值

时间:2024-12-05 15:01:32浏览次数:7  
标签:www cn 遗失 luogu https com NOIP2024 赋值

https://www.luogu.com.cn/problem/P11362

参考:https://www.luogu.com/article/9pagx8eg

由于 \(v>1\),所以对于 (2,3) 或 (3,4) 的关系,必定能够确保至少存在一种赋值(只要 \(x_2\neq x_3\) 即可),无需考虑。

只需考虑关系链 \(3\sim 6\)。

因为 \(x_3=a_3\),从这里出发一直推导,可以发现 \(x_6\) 需要与 \(b_5\) 相等,要让他失效,就要保证二者不等,而除了首尾中间相当于架桥,任意取值,头部固定,尾部可以取除了 \(x_6\) 以外的其他值。

https://www.luogu.com.cn/record/192597873

标签:www,cn,遗失,luogu,https,com,NOIP2024,赋值
From: https://www.cnblogs.com/wscqwq/p/18588614

相关文章

  • NOIP2024 游记
    比赛历程保持以往的策略,先将每一道题都想一遍。T1想了一个贪心,简单地证明感受了一下正确性。接着T2想了一个计数DP,感觉上它是对的。然后T3还是计数,一样简单地推了一个DP然后去看T4。这时莫名的感觉时间有点紧,于是没有想多,想了一个可以拿到不错的分数的暴力就开始打代码......
  • NOIP2024 简要题解
    T1编辑字符串(edit)考虑求出\(x\)表示两个串最多能匹配多少对\(0\)。设两个串\(0\)的个数加起来为\(s\),那么会发现恰好有\(s-2x\)个位置是不匹配的,我们只需要最小化\(s-2x\)即最大化\(x\)即可。可以直接贪心求解,枚举每个位置判断是否能匹配一对\(0\),处理出两个......
  • 题解:P11362 [NOIP2024] 遗失的赋值
    这里写一个我在考场上差点想出来的、比较另类的做法。若\(\existsc_i=c_j(i\nej),d_i\ned_j\),则答案显然为\(0\)。否则,我们可以将序列\(x\)中的数分为已确定和未确定两类。设\(f_0(i)\)为当\(x_i\)未确定时前\(i-1\)个二元限制的方案数,\(f_1(i)\)为当\(x_i\)确......
  • NOIP2024回忆
    day-联赛的备考从暑假就开始了期间我们的一些学长回来给我们讲过一些课,比如GLR的好题选讲,树分块(没怎么听懂),生成函数,阈值分治等。他们都有光明的未来,而我们即将走上他们曾走过的道路。开学后到了新的年级,新的老师,感觉还是更加适应原来的老师。国庆后开始全面停课,但是在医院住......
  • [luoguP11361/NOIP2024] 编辑字符串
    题意给出两个0/1字符串,每个字符串有一些位置被标记,无法交换。求通过任意多次的交换相邻元素操作能够使两个字符串最多多少位置相同。sol一道贪心题。显然交换相邻的操作可以使该字符串可以交换的一段任意排列。由于不同位置的贡献最大只为\(1\),因此在任何位置贡献都没有区......
  • noip2024 vp 复盘总结
    考试过程原定13:30开的比赛晚点9min。顺序开题。看T1,一开始感觉是个dp。看了数据范围是\(10^5\)。这时发现我区间好像都不会写。旁边扯了一张纸一根笔,写写写画画画。画了类似这样的东西。想转最后一个。那我就要\(f[i][j][k][0/1][0/1]\)。保留上下区间的失配数和......
  • [Tricks-00005][NOIp2024]树上查询 思维方式还是要数形结合!
    题目链接。有一个经典结论是,在\(l<r\)的时候,\(dep_{\operatorname{LCA}(l,l+1,\dots,r)}=\min\limits_{i=l}^{r-1}dep_{\operatorname{LCA}(i,i+1)}\),证明也十分容易。特判掉\(k=1\)的特殊情况后,问题则可以转化成:有一个序列\(d_i=dep_{\operatorname{LCA}(i,i+1)}\),求\(\m......
  • NOIP2024游记
    本文根据真实事件改编,如有雷同纯属巧合。前情提要:我说丝薄,csp300出头的丝薄,所以这次noip特别虚day0上午随便切了两个题,背了下板。下午看考场,环境很好,键盘也不错,评测姬异常优秀(埋下伏笔)晚上回去[数据删除]啊,应该什么都不想的。day1上午六点半就起来了,七点出门,开车过去七点......
  • NOIP2024游记
    NOIP2024游记第三次参加NOIP了,但是是第一次正式参加。Day0考前一天我们三点半就放学了,然后打了两个小时排球,回去很累了,摆了一晚上。然后快要睡觉了,我又突然想起来打了个网络流的板子。最后差不多在22:40睡觉了,睡眠质量还不错。Day1早上6:30就醒了,但是由于比较紧张,后......
  • NOIp2024游记
    Day998244852打板子,发现不会板子。Day0开考,看t1,开始写,假掉了,急急急。然后重新想,继续写,还是过不了样例,急急急。。怎么感觉在写Div2D?1h过了t1,感觉要完蛋了。。开t2,怎么逝计数啊,稍微观察一下,怎么这么唐,10:00过了。开t3,不太会啊,如果枚举开始的边好像会重复很多啊。。......