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