模拟赛好题分享

@
目录

• 山茶花
  
  
  
  • 100pts
    
  
  
• T1区间逆序对
  
  
  
  • 60pts
    
  • 100pts 区间操作固定套路，转化为前缀操作
    
  
  
• dream
  
  
  
  • 20pts 神奇分块
    
  
  
• 杭州:转化题意，正难则反
  
  
  
  • 正难则反(或者对于这种有删边操作的题)， 我们看成反向加边
    
  
  
• 看题：构造
  
• 坐飞机:斜率优化DP
  
• 抓颓 : 启发式合并 + stl大杂烩
  
• 讨厌的线段树
  
• Foo Fighters ：构造
  
  
  
  • 乱搞一：大胆随机化
    
  • 正解:位运算 -> 基本套路 按位考虑
    
  
  
• Hack it! ： 构造
  
• 光之剑：计数DP
  
  
  
  • 正解:正难则反，取补集
    
  
  
• Divide
  
• 正解:科技-Stern-Brocot树  法里树
  
  
  
  • Stern-Brocot树
    
    
    
    • 性质1 单调性
      
    • 性质2 SB Tree的所产生的分数都是最简分数
      
    • 证明
      
    
    
  • 法里树
    
  
  
• 醒幸：正难则反
  
  
  
  • 相似题目:杭州
    
  • 正解:转化题意, 二分
    
  
  
• ABC321F :退背包
  
  
  
  • 正解:性质题
    
  
  
• 农场道路修建 : 问题转化
  
  
  
  • 正解 ：问题转化
    
  • 方法一 :
    
  • 方法二 :
    
  
  
• 密码锁：优化DP
  
  
  
  • 25ptsP
    
  • 55pts：区间DP+线段树优化
    
  
  
• 100pts：问题转化+性质
  
• 魔法是变化之神
  
  
  
  • 60pts:背包,求补集
    
  • 100pts：考虑随机数据
    
  
  
• 奶牛的数学题:单位贡献
  
  
  
  • 正解
    
  
  
• 路遇矩阵
  
• 奶牛的括号匹配:状压
  
• 润不掉了：转化点对问题
  
  
  
  • 40pts
    
  • 100pts 子树贡献转化
    
  
  
• 美好的查询:神奇主席树
  
  
  
  • 80pts：分块+并查集
    
  • 100pts:神奇主席树，多看看
    
  
  
• 新涂色游戏:操作反做
  
• 新-滑动窗口简单差分
  
• 小明去旅游 锅
  
• Heavy and Frail：分治优化重复操作
  
  
  
  • 
    
    
    
    • 35pts，二进制分组背包暴力跑
      
    • 80pts 背包合并
      
    • 100pts
      
    
    
  
  
• chess：根据题意分析
  
• glass：简单装呀
  
• card：组合意义的DP
  
• godnumber:锅
  
• meirin：暴力化简式子
  
• sakuya:期望树形DP好题
  
• 交换消消乐:简单性质题
  
• [ABC232H] King's Tour：构造，锅
  
• Road of the King：神奇DP
  
• 醉醉疯疯渺渺空空换根dp
  
• F - Robot Rotation 不能随机化的折半搜索
  
• E - Revenge of "The Salary of AtCoder Inc." 期望
  
• A. 1031模拟赛-A进步科学 状压DP
  
• B. 1031模拟赛-B吉吉没急 差分约束
  
• C. 1031模拟赛-C老杰克哒  动态DP
  
• 排座位 - 题目 - Daimayuan Online Judge] DP
  
• A. 方块游戏 - 题目 - 多校信息学训练题库
  
• B. 雪球 - 题目 - 多校信息学训练题库
  
• D. 不要FQ - 题目 - 多校信息学训练题库 动态DP
  
• 23zr提高day9-美人鱼 - 题目 - Zhengrui Online Judge (zhengruioi.com)
  

山茶花

性质推导题：  如果没有+1操作， 那么最后的答案一定为恒定的ans
考虑+1操作对什么时候会产生影响

<strong>不难发现，如果后缀为k个1, 则+1操作等效于 $ans ^ (1  i & 1) {                if(b) X ^= b;                        else {                        b = X;//                        printf("b[%d] %lld\n", i, b);                        return ;                 }        }}bool check(int X) {        LL NOW = 0;        for(int i = 0; i > i & 1) != (i != X)) {                        if(b) NOW ^= b;                        else return 0;                        }        }        return 1;}int main() {//        freopen("shuju.in","r",stdin);//        freopen("mine.out","w",stdout);         scanf("%d", &n);        for(int i = 1; i 1$的段和一段$