首页 > 其他分享 >【合集】实在太懒把模拟赛分开新建随笔了

【合集】实在太懒把模拟赛分开新建随笔了

时间:2023-10-08 14:57:18浏览次数:39  
标签:oo 随笔 int 质数 太懒 返祖 直接 合集 dp

B. 特

二分哈希找公共长度

C. 伯

考场上其实是有往正解那个奇怪的结合上想的

考虑 n很小的时候怎么做: 这时候可以用最小表示乘上排列数

形态为树的时候,会发现可以直接 dp ,k中颜色实际上都是相同的 所以直接设 \(dp[i]\) 表示 节点 i 每一种颜色的 ans

考虑结合两部分

将原图变为一个树和一些返祖边,我们可以定义每个返祖边指向的dfn更小的点为关键点,把返祖边的答案累积到关键点上

考虑暴力枚举关键点的最小表示 $ dp[u][i] $ 表示 u节点,颜色为 i 的ans,规定不是 最小表示中的颜色都为 0

dfs dp时,访问到一条返祖边,这条边的贡献是可以判断出来的 ,不是dif 就一定是sam ,这几可以直接累加到 dp[v][col[v]上,在回溯的时候直接继续算就好了

D. 雷

考虑倍增优化,不会证明,不是谁会证明给我讲讲

A. V

考场上打的另一种贪心

这里正解考虑对于一个正串 ( 做正贡献 ,一个反串 ( 做负贡献,所以我们要是想让 ( 尽可能做正贡献,不妨直接贪心选

最前面 n/4 个( 最后面 n/4 的) 组成正串,看看最后剩下的能不能构成反串

B. U

dp 是比较显然的,但实际上能转移的状态之间构成了DAG , 转移的时候可以分层枚举 ,学到了

C. T

并不是很明白证明,但是遇到这种情况大力分讨(分细一点)也许会很有用

A. 大

这个一看就很可以容斥,考场上尝试一步直接算出 h[i] 表示长度为 i 的不合法段个数,没意识到这道题可以直接枚举结尾元素 暴力再写一个 dp g[i][j] 我是傻叉

考虑容斥:f[i] 表示长度为 i的 合法串的个数

那么有: $ f[p] = \sum_{i=1}^{i} (-1)^{i-1} * f[p-i]*h[i] $

直接上 !

B. 豆

图论构造题,思路觉得很创新

考虑维护一个断点 使得断点左右两侧状态不同 ,每次插入考虑插入相同一侧的对面,维护新断点

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define mkp(oo,ooo) make_pair(oo,ooo)
#define w(o,oo) mp[mkp(o,oo)]
inline int read(){
    int x=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
    return x*f;
}int pre[N],nex[N],x,ed;
map<pair<int,int>,int> mp;
signed main(){
	int n=read(),m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		mp[mkp(x,y)]=mp[mkp(y,x)]=1;
	}if(n<=2||!m){
        for(int i=1;i<=n;i++) printf("%d ",i);
        printf("\n");
        return 0;
    }nex[1]=2; pre[2]=1; ed=2;
    for(int i=3;i<=n;i++){
        if(!x){
            nex[ed]=i; pre[i]=ed;
            if(w(ed,i)!=w(ed,pre[ed])) x=ed;
            ed=i;
            continue;
        }
        int a=pre[x],b=nex[x];
        if(w(x,a)==w(i,x)){
            nex[x]=i; nex[i]=b; 
            pre[i]=x; pre[b]=i;
            if(w(x,i)==w(i,b)) x=b; 
            else x=i;
            if(!pre[x]||!nex[x]) x=0;
        }else{
            nex[a]=i; nex[i]=x; 
            pre[i]=a; pre[x]=i;
            if(w(x,i)==w(i,a)) x=a; 
            else x=i;
            if(!pre[x]||!nex[x]) x=0;
        }
    }int p=1;
    while(p){printf("%d ",p);p=nex[p];}
    return 0;
}

C. 托

米奇妙妙题

A. 染色

质数分为奇质数和偶质数,2很特殊 ,相当于有奇偶两条链,除了2 的所有质数 只会连接 两条链,所以我们只要保证每一条链是形如

1 3 1 3 1 3

2 4 2 4 2 4
就可以了

B. 序列

三分,发现两项影响大概呈现单峰函数形式,直接三分到一个区间,暴力扫一遍

C. 树上询问

将询问存到点上,dfs 时直接动态维护 一个桶就好了

B. 点

dp 加 贪心 ,考场上应该能想出来的,还是自己不够强,一直在想贪心策略直接解决

这种只会对周围点造成影响的很明显可以树形 dp 呀,流泪,我是什么东西

C. 不

随机化扔两个点,两个点在的概率为0.25,直接多扔几次,暴力根号直接判断

不知道为什么> 900ms 停要写成

好像windos 和 linux 不一样,算了,记住好了

累了 写到CSP模拟44联测6 了,记一下

标签:oo,随笔,int,质数,太懒,返祖,直接,合集,dp
From: https://www.cnblogs.com/limingyun/p/17749040.html

相关文章

  • 2023中大厂Android面试八股文合集,GitHub,牛客,leetcode已爆火!
    前言金九银十已过半,不知道大家现在都到哪个阶段了,有没有已经找到心仪的工作的朋友?有没有还没准备好面试在各大平台找资料临时抱佛脚的朋友?或是现在在准备,想要明年金三银四跳槽的朋友?不管你是现在急切找工作还是找资料备战,我都非常推荐你看看我花2个多月从GitHub,牛客,leetcode上为大......
  • HTML+CSS随笔
    这是我的学习笔记,重点是我容易忘的内容,并不全面配合以下内容学习就很全面了黑马程序员pink老师前端入门教程HTMLHTML文件基础结构解析<!DOCTYPEhtml><htmllang="zh-han"><head><metacharset="UTF-8"><metaname="viewport"content="width=devic......
  • java——redis随笔——实战——短信登录
    前言: 此章节用到的知识点:mybatisPlus ;参考网址:https://www.bilibili.com/video/BV1Xu411A7tL?p=7&vd_source=79bbd5b76bfd74c2ef1501653cee29d6  正常新建一个接口: 再新建这个接口的实现类:  修改接口: 修改实现类:  然后就可以注入并使用了:   ......
  • java——redis随笔——基础
         层级模式:                                          11......
  • java——mysql随笔——运维——分库分表&MyCat
    分库分表:                    介绍:                    拆分方式:                                     ......
  • java——mysql随笔——运维——日志
    黑马:https://www.bilibili.com/video/BV1Kr4y1i7ru?p=154&vd_source=79bbd5b76bfd74c2ef1501653cee29d6 csdn:https://blog.csdn.net/weixin_44904239/article/details/130379510 ================================================================================......
  • 闭包随笔
    开始正式介绍之前先看一个比较有难度的关于闭包的面试题:functionfun(n,o){console.log(o)return{fun:function(m){returnfun(m,n);}};}......
  • java——mysql随笔——SQL优化&锁
               插入数据SQL优化:              主键优化:                                    order  by优化:       ......
  • 2023年9月随笔之摩托车驾考
    1. 回头看日更坚持了273天。读《SQL学习指南(第3版)》更新完成读《高性能MySQL(第4版)》持续更新学信息系统项目管理师第4版系列持续更新9月码字81307字,日均码字数2710字,累计码字451704字,累积日均码字1654字,月度码字量暴增。拿到了摩托车驾驶证(D照)。2. 感受2.1不......
  • 「闲话随笔」Yubai 数数
    「闲话随笔」Yubai数数点击查看目录目录「闲话随笔」Yubai数数AmazingCountingproblem!国庆快乐!可是已经开学了,奥赛生只配放7+3=2-.衡实初中部为啥没有集训啊?可能是因为以前机房在衡实只能去衡实集训,所以就把初中带上了吧,本来不会集训的.诶不对好像是不是初......