首页 > 其他分享 >9.22 NOIP 模拟赛 R7

9.22 NOIP 模拟赛 R7

时间:2024-09-22 19:50:16浏览次数:9  
标签:9.22 R7 NOIP T4 dp 性质

省流:高一 rk6,整体 rk10。

考场上直接用前几天学的 map 优化 dp 优化我 T2 的 \(O(n^4)\) 代码,然后过了 \(4000\)!

感觉后面 dp 的优化是比较好想的,如果想到填表法的话。还要注意处理大小依赖关系,故从小到大加入的 trick。

T4 最后几分钟极限过样例,random_shuffle 过 \(200\)!(其实当时已经把性质什么都推出来了的,主要是一开始没有发现只选 1 个的性质,可能再多几分钟就能把 80pts 的 dp 打出来了,不过有 60 已经很理想了)

T4 到了最后本质上就是求 5 组物品的多重背包(或者叫分组?),然后每一层可以选不同个,价值递增。注意这玩意有决策单调性,所以就可以单次线对转移。(还是要枚举 \(V \mod i\))

T3 猜测每条边只操作一次打的暴力,结果错了。其实结论在考场上猜到了一些,但是只能说没有想到必要条件居然还是充分的,亏大了,应该分 Sub 打一下特殊性质的。只能说构造确实很妙。

感觉以后有些图上面的性质题都可以尝试分成:二分图奇环来考虑。

然后 T1 更是有点傻了,先是看错了题去打数形 dp。然后又打了个很正确但是很难写的分讨,大概花了 50min 还没写完,然而兔子在厕所告诉我直接暴搜合法答案就可以了……。

标签:9.22,R7,NOIP,T4,dp,性质
From: https://www.cnblogs.com/LCat90/p/18425767

相关文章

  • [NOIP2013 提高组] 转圈游戏
    [NOIP2013提高组]转圈游戏\(n\)个小伙伴(编号从\(0\)到\(n-1\))围坐一圈玩游戏。按照顺时针方向给\(n\)个位置编号,从\(0\)到\(n-1\)。最初,第\(0\)号小伙伴在第\(0\)号位置,第\(1\)号小伙伴在第\(1\)号位置,……,依此类推。游戏规则如下:每一轮第\(0\)号位置上的小......
  • noip2014联合权值
    noip2014联合权值题目描述无向连通图G有n个点,n-1条边。点从1到n依次编号,编号为i的点的权值为Wi,每条边的长度均为1。图上两点(u,v)的距离定义为u点到v点的最短距离。对于图G上的点对(u,v),若它们的距离为2,则它们之间会产生Wu×Wv的联合权值。请问图G上所有可产生......
  • 【题解】「Public NOIP Round #2」找零
    【题解】「PublicNOIPRound#2」找零[官解](PublicNOIPRound#2题解-博客-Qingyu的博客(pjudge.ac))Tag:背包、dp凸优化决策点单调触碰到知识点盲区了,所以来写几笔。首先,由于我们只关心最终状态下\(1\)的最多个数,其实有用的面值只有\(5,1\)(其她的可以当成若干......
  • 【题解】【枚举】—— [NOIP2014 普及组] 比例简化
    【题解】【枚举】——[NOIP2014普及组]比例简化[NOIP2014普及组]比例简化题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.思路解析2.AC代码[NOIP2014普及组]比例简化通往洛谷的传送门题目背景NOIP2014普及组T2题目描述在社交媒体......
  • NOIP2024模拟赛7 总结
    NOIP2024模拟赛7总结A.恰钱没啥好说的。赛场就过了。比较难蚌的是,第一遍本地测的时候没有写spj,导致我们很多人T1都直接挂零了。不过后来配上重测了。B.排序由于某种神秘原因,导致线段树build写的范围是\(1\simn+1\),update的时候写的也是\(1\simn+1\),然而que......
  • 【2024潇湘夜雨】WIN 11_Pro_24H2.26120.1843软件选装纯净特别版9.22
    【系统简介】=============================================================1.本次更新母盘来自WIN11_Pro_24H2.26120.1843.2.全程离线精简、无人值守调用优化处理制作。部分优化适配系统可能要重启几次,即使显示适配失败也不要在意,可能部分优化不适用。3.OS版本号为26120.1843。......
  • 【蓝桥杯】2024.9.22算法赛——灵魂问题\全栈项目小组(C++)
    一、灵魂问题题目灵魂问题题目分析1.要求输出一个整数2.题目在玩脑筋急转弯,关键句子标出来了——糖什么的根本不重要。所以咖啡不加糖,答案是0!!!代码#include<iostream>usingnamespacestd;intmain(){ cout<<0; return0;}二、全栈项目小组题目全栈项目小组......
  • 2024.9.22 扩展 centos7的文件系统空间
    从lsblk的输出可以看出,你的磁盘/dev/sda的总大小是30G,但sda3分区只使用了17.7G。要扩展/dev/sda3分区,使其利用整个磁盘上的可用空间,你可以按照以下步骤进行。扩展/dev/sda3分区备份数据在操作分区之前,建议你备份重要数据。进入fdisk调整分区使用fdisk工......
  • P1056 [NOIP2008 普及组] 排座椅(模拟)
    1.用x,y数组存放切了几对学生,用数组的下标记录切的位置2.按照题目要求k和l依次取出最大的数组的值,并将其变为-1,再次循环取出第二大的值,之后所有下标为-1的的下标就是切的学生对多的3.切的意思是把两个学生分开#include<bits/stdc++.h>usingnamespacestd;intx[1005],......
  • 2024.9.22 计划
    项目部分搞清楚声音信号怎么转化为热力图形式如果有时间就搞一下怎么将热力图和光学图或者视频怎么叠加个人学习部分多重背包问题III庆功会总结如果得到了声音的信号,可以经过处理用python绘制出来对应位置的热力图,这里采用随机生成的声音信号,代码如下:importnump......