-->

杂题选讲

最近刷水题太多了 所以要做一点稍有思考难度的好题 然后记录下来分享给大家
(PS:简单的我就不贴代码了)


AtCoder Regular Contest 083 E

这道题一开始想偏了一点 首先不管所有点染成黑还是白 他的答案 只跟是否和孩子的颜色相同有关系
对于一个点来说 它的子树和它相同颜色的个数已经确定下来
因为要尽量可行 那么我们贪心 只需要和它颜色不同的个数要尽量的少
那么有

dp[i] 表示第i个点的子树中和i不同颜色的个数最小值

然后每个点都有一个二元组 $$(dp[i],X[i])$$ 就是子树内和它相同和不同的个数 直接背包就好了 时间复杂度O(5000N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=5010;
const int inf=0x3f3f3f3f;
struct node{int x,y,next;}edge[1010]; int len,first[1010];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int dp[1010]; int N; int X[1010]; int G[Maxn],F[1010][Maxn];
void Dfs(int x,int f)
{
int s=0; for(int k=first[x];k!=-1;k=edge[k].next)
{
int y=edge[k].y;
if(y==f) continue;
else s++;
}
if(s==0){dp[x]=0; return ;}
memset(F[x],63,sizeof(F[x])); F[x][0]=0; dp[x]=inf;
for(int k=first[x];k!=-1;k=edge[k].next)
{
int y=edge[k].y;
if(y==f) continue;
Dfs(y,x);
for(int i=0;i<=X[x];i++) G[i]=inf;
for(int i=0;i<=X[x];i++) if(F[x][i]<inf)
{
if(i+dp[y]<=X[x]) G[i+dp[y]]=min(G[i+dp[y]],F[x][i]+X[y]);
if(i+X[y]<=X[x]) G[i+X[y]]=min(G[i+X[y]],F[x][i]+dp[y]);
}
for(int i=0;i<=X[x];i++) F[x][i]=G[i];
}
for(int i=0;i<=X[x];i++) dp[x]=min(dp[x],F[x][i]);
}
int main()
{
scanf("%d",&N); len=0; memset(first,-1,sizeof(first));
for(int i=2;i<=N;i++){int x; scanf("%d",&x); ins(x,i);}
for(int i=1;i<=N;i++) scanf("%d",&X[i]);
Dfs(1,0);
if(dp[1]==inf) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
return 0;
}


bzoj4435: [Cerc2015]Juice Junctions

感觉好常规啊 但是我好像不是很会啊
解法:对于一对点来说
贡献为0的时候 就是这两个点不联通
1的时候 就是这两个点联通且不在一个边联通分量里面
2的时候 就是两个点联通且仅在一个边联通分量里面
3的时候 就是删掉任意一条边两个点仍然在一个边联通分量里面

为什么是边联通分量呢 因为每个点只会属于一个边联通分量 而会属于多个点联通分量
感觉这类题还不是很熟悉 以后要多做才行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stack>
using namespace std;
const int Maxn=10010;
const int bas=233;
struct node{int x,y,next;}edge[Maxn]; int len,first[Maxn];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int N,M; int fa[Maxn]; int Find(int x){return (x==fa[x])?x:fa[x]=Find(fa[x]);}
int dfn[Maxn],low[Maxn],belong[Maxn],cnt=0,id=0; stack<int>S;
void init()
{
id=cnt=0;
for(int i=1;i<=N;i++) dfn[i]=low[i]=-1,belong[i]=0;
while(!S.empty()) S.pop();
}
void Dfs(int x,int fa,int kk)
{
dfn[x]=low[x]=++id; S.push(x);
for(int k=first[x];k!=-1;k=edge[k].next)
{
int y=edge[k].y;
if(k==(kk^1) || k==kk || y==fa) continue;
if(dfn[y]==-1)
{
Dfs(y,x,kk);
low[x]=min(low[x],low[y]);
}
else low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
int i; cnt++;
do
{
i=S.top();
belong[i]=cnt;
S.pop();
}while(i!=x);
}
}
unsigned int H[Maxn];
int main()
{
scanf("%d%d",&N,&M); len=1; memset(first,-1,sizeof(first));
for(int i=1;i<=N;i++) fa[i]=i;
for(int i=1;i<=M;i++){int x,y; scanf("%d%d",&x,&y); ins(x,y); ins(y,x); fa[Find(x)]=Find(y);}
int ans=0;
init();
for(int i=1;i<=N;i++) if(dfn[i]=-1) Dfs(i,0,0);
for(int i=1;i<=N;i++)
{
for(int j=i+1;j<=N;j++) if(i!=j)
{
if(Find(i) == Find(j))
{
ans++;
if(belong[i]==belong[j]) ans++;
}
}
}
for(int j=2;j<=len;j+=2)
{
init();
for(int i=1;i<=N;i++) if(dfn[i]==-1) Dfs(i,0,j);
for(int i=1;i<=N;i++) H[i]=H[i]*bas+belong[i];
}
for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) if(i!=j && H[i]==H[j]) ans++;
return printf("%d\n",ans),0;
}


Codeforces Round #440 (Div. 2, based on Technocup 2018 Elimination Round 2) E

首先所有的点向四个方向连边
然后找出一个环的话 就有$$2^E$$的贡献 其中E为所有点所涉及的边数
否则所有的直线就不能同时出现 有$$2^E-1$$的贡献
考虑到代码实现的问题 我们可以把一个直线变成一个点 然后去找环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long LL;
const LL Mod=1e9+7;
LL two[1234567];
LL N; map<LL,vector<LL> >mp;
set<LL>S; LL V,E;
void Dfs(LL x)
{
V++; S.erase(x); E+=mp[x].size();
for(LL i=0;i<mp[x].size();i++)
{
LL y=mp[x][i];
if(S.count(y)) Dfs(y);
}
}
int main()
{
scanf("%lld",&N); S.clear();
two[0]=1; for(LL i=1;i<=2*N;i++) two[i]=two[i-1]*2%Mod;
for(LL i=1;i<=N;i++)
{
LL x,y; scanf("%lld%lld",&x,&y);
x=x<<1; y=(y<<1)+1;
mp[x].push_back(y);
mp[y].push_back(x);
S.insert(x); S.insert(y);
}
LL ans=1;
while(!S.empty())
{
LL x=*S.begin();
V=E=0; Dfs(x); E/=2;
if(V-1==E) (ans=ans*(two[V]-1))%=Mod;
else (ans=ans*two[V])%=Mod;
}
return printf("%lld\n",(ans+Mod)%Mod),0;
}


Codeforces Round #441 (Div. 2, by Moscow Team Olympiad)

和OZY一起做的比赛成绩还不错

主要是OZY手速太强啦
简单讲讲题

B

Description: 从N个数里面选K个数使得两两的差在mod M下相同
Solution: 两两差在mod M 下相同其实可以转换为所选的数在mod M下都相同 开个map跑一下就好了

D

Description: 题目看来了好久啊,就是每一轮放一个硬币 然后每次从前往后所有硬币都可以往后面去撞 然后问多少次后停止下来 答案+1
Solution: 发现在最后面的硬币是不用管的 管的是前面的硬币 前面的硬币每一次只会撞一个过来 那么答案就是
$$ Ans= 所有的硬币个数-最后面的连续一段硬币个数 $$

E

Description: 就是有N个序列字符集大小为M 然后每个序列长度为Li 你可以选择一些数字去打’
比如说1<2 当2被打’的时候 2’<1 就是被打’的数字的字典序变小
当然了也有 1’<2’ 问最少哪些数打’使得保持输入的字典序 不行输出No
Solution:其实这道题有点连边然后判断矛盾的意思
我们首先可以考虑2-sat 但是好像建出来的边不具有对称性(但不知道那些人是怎么过的)
在这里讲一下chenyushuo的做法

我们可以发现
对于原来的字典序 首先考虑第一种情况
a….
b….

那么这种情况 b’ -> a’
对于第二种情况
b….
a….

那么对于这种情况 b一定要打’ a不能打’

对于任意两个串 需要做上述操作的 只有可能在第一个位置不相同才做
但是这样就有O(N^2) 的连边 很不优美
考虑只有第一种情况打’的才连边 而第二种情况直接判断 这样就有一个优美的传递性
而且只会大的连到小的 没有环
然后按照DAG传递打’的信息就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int Maxn=200010;
vector<int> A[Maxn]; int N,M;
vector<int> G[Maxn]; int opp[Maxn];
bool vis[Maxn]; int ru[Maxn];
vector<int> V; queue<int>Q;
struct node{int x,y,next;}edge[Maxn]; int len,first[Maxn];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
bool tag[Maxn];
int main()
{
scanf("%d%d",&N,&M); len=0; memset(first,-1,sizeof(first));
for(int i=1;i<=N;i++)
{
int L; scanf("%d",&L);
for(int j=1;j<=L;j++){int x; scanf("%d",&x); A[i].push_back(x);}
}
memset(opp,-1,sizeof(opp)); memset(ru,0,sizeof(ru));
for(int i=2;i<=N;i++)
{
int o=min(A[i].size(),A[i-1].size()); bool bkk=false;
for(int j=0;j<o;j++)
{
if(A[i][j]==A[i-1][j]) continue;
else
{
if(A[i][j]<A[i-1][j])
{
if(opp[A[i][j]]==1){printf("No\n"); return 0;}
if(opp[A[i-1][j]]==0){printf("No\n"); return 0;}
opp[A[i-1][j]]=1; opp[A[i][j]]=0;
}
else if(A[i][j]>A[i-1][j])
{
ins(A[i][j],A[i-1][j]); ru[A[i-1][j]]++;
}
bkk=true; break;
}
}
if(bkk==false && A[i].size()<A[i-1].size()){printf("No\n"); return 0;}
}
for(int i=1;i<=M;i++) if(opp[i]==1) tag[i]=1;
for(int i=1;i<=M;i++) if(ru[i]==0) Q.push(i);
while(!Q.empty())
{
int x=Q.front();
for(int k=first[x];k!=-1;k=edge[k].next)
{
int y=edge[k].y;
tag[y]|=tag[x];
ru[y]--; if(ru[y]==0) Q.push(y);
}
Q.pop();
}
for(int i=1;i<=M;i++) if(opp[i]==0 && tag[i]){printf("No\n"); return 0;}
for(int i=1;i<=M;i++) if(tag[i]) V.push_back(i);
printf("Yes\n");
printf("%d\n",V.size());
for(int i=0;i<V.size();i++) printf("%d ",V[i]);
return 0;
}

F

Description:就问有多少对数 使得他们之间所有数or起来大于左右之间的最大数
Soluion:很明显的一个思路就是先找出最大数的范围 而不是做了之后再去找最大数
然后发现要or起来比最大数大 那肯定要找到最近左右两边最大数中为0的二进制位为1的位的位置
设这两个点l[i],r[i] 在最大数影响的范围里面 包含l[i]或者r[i]端点的区间即可
简单容斥一下得到答案 时间复杂度O(NlogN)


bzoj3612: [Heoi2014]平衡

好菜啊啊啊啊
就是整数划分的dp 没有接触过
$$ F[i][j] = F[i-j][j]+F[i-j][j-1] $$
意思大概就是 分最小为1 和最小不为1 的情况
最小不为1 的显然就是 F[i-j][j] 就是在之前j个下面都+1嘛
然后最小有一个的就是 F[i-j][j-1] 除了在之前的j-1个下面+1 还要多一个一新开一组
但是这样有一个问题 就是最大的题目中不能超过N
那么怎么办呢 因为每一次在之前的+1的时候 一个状态只有一个位是越界的 而且刚好是N+1
那么抹掉这个位的数 剩下的就是 F[i-(N+1)][j-1]
所以这道题总的dp方程就是:
$$ F[i][j] = F[i-j][j]+F[i-j][j-1]-F[i-(N+1)][j-1] $$
然后这道题就解决了


Codeforces Round #430 (Div. 2) D

心情烦躁随便开了一题
Description: 就是序列的每个元素每次xor x且不变回来 问序列的mex
Solution: 开个字典树嘛 对于x扔进去查找就好了啊 x这个位为1的就先走1方向 满了就自走0方向 x位为0的同理


bzoj5071:[Lydsy十月月赛]小A的数字

发现每次操作只改变两个前缀和 就直接用前缀和判断一下即可
读入要读入完 不能直接break了….


bzoj5072: [Lydsy十月月赛]小A的树

首先一个很好出来的状态定义:

F[i][j][k] 表示i子树内选j个点 恰好k个黑点是否可行

发现这样的状态要O(N^3)转移
但是 之前也试过这样错的定义

F[i][j][k] 表示i子树内选j个点 最多k个点可行

因为这样的状态k个点符合要求 k-1个点可能不符合要求

于是我们进一步发现 对于i子树内选j个点 符合要求的 肯定是一个区间内的黑点数量
所以限制上下界 然后转移就好了

值得一提的是 转移的时候 应该先用一个辅助数组 先把 siz[x] 和 siz[y] 合并
这样的复杂度是

$$ O(siz[x] * siz[y]) $$

而如果你先把这个背包变成 siz[x]+siz[y] 大小 然后再枚举 siz[y] 的大小 这样的合并时间会变大

$$ O((siz[x] + siz[y]) * siz[y]) $$

就变大了子树大小的平方 平均下来这个的极限数据会满一半

尽管两种都是

$$ O(N^2) $$


bzoj5073: [Lydsy十月月赛]小A的咒语

这道题题解是后缀数组??????
不管我只写了dp

F[i][j][op] 表示A串中前i个用了j次 最后1个匹不匹配 最多匹配了B串的多少

有一点值得注意的是 虽然我们是利用了贪心的想法 肯定是对于一个状态来说取越多越好
因为假设你取少点 以后去匹配 还不如我现在取完 以后不去匹配
而且以后取少点能匹配的 我当前状态取多点的也可以匹配
这就证明了这个状态的正确性

但是这样我们并不是说能匹配就一定要匹配 因为你这样可能要花费很多次分开的机会
可能后面有一大堆不用分开的 所以虽然能匹配也要记录当前不匹配的状态


bzoj5074: [Lydsy十月月赛]小B的数字

推一波式子:
$$2^{(k_1+k_2+\cdots+k_n ) | 2^{a_ik_i} } $$
$$k_1 + k_2 + \cdots + k_n \leq a_ik_i $$
我们考虑怎么处理这个式子 可以先变成
$$\frac{k_i}{k_1 + k_2 + \cdots + k_n} \leq \frac{1}{a_i} $$

这些式子相加 就变成了

$$\sum\limits_{i=1}^{n} \frac{1}{a_i} \leq 1$$

然后只要扩倍扩成3628800倍就好了
就是变成了

$$3628400 \geq \sum\limits_{i=1}^{n} \frac{3628400}{a_i} $$

这样就可以AC了 可是这样好像会有一个问题 就是下面的式子只满足上面的式子的必要性 而充分性无法证明 题解也没有详细的写


bzoj5076: [Lydsy十月月赛]小B的咒语

首先我们可以跳出一个子串内 最后面的-最前面的这个计算
比如一个子串:
2 3 3 2 3 2
其实是2的贡献是6-1 其实可以拆成(4-1)+(6-4)
那么就是相邻两个的贡献 我们熟悉的 就是用pre[i]来存与i相同的前一个数字也为i的位置
那么答案就变成了:

$$Ans = \sum\limits_{i=l,pre[i]\geq l}^{r} (i-pre[i])$$

这样我们看看部分分做法
30ftps: 就是在pre[i] 这个位置上面的主席树打上贡献 然后往后合并即可
50ftps: 不知道可不可以用待修改莫队搞一下?
80ftps: 综上所诉就是80分做法
100ftps :
我们可以再把式子变一变 我们希望l和r各是1维空间 方便我们用数据结构什么的维护 去掉下界的控制

$$\sum\limits_{i=1,pre[i]\geq l}^{r} (i-pre[i])$$
然后我们可以有三维序对来表示他们 分别是
$$ (T,pre[i],i) $$

其中T是时间戳 pre[i]就充当了L的成分 i就是充当了R的成分
就是在一个平面上 x坐标为pre[i] y坐标为i 然后在里面矩阵数点的问题

然后就是CDQ了