文章目录
Day3
T1 传送 portal (※建图，最短路)
最开始想着 DP ，后来发现访问每一行的顺序不能确定，于是以时间为阶段，当前所在行为状态，将 DP 加载到队列上进行转移，本质上就是跑最短路，但是不知道为什么超时。
事实上，我们可以定义三元组
(
x
,
y
,
w
)
(x,y,w)
(x,y,w) 作为从第
x
x
x 行到第
y
y
y 行的一条路径，
w
w
w 为这条路径的费用，根据输入的
01
01
01 矩阵建图，然后跑一遍从
1
1
1 到
n
n
n 的最短路即可。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
const int inf = 0xffffff;
int n,ty,map[305][305];
int f[305],tmp;
bool vis[305];
string s;
int head[305],cnt;
struct edge{
int nxt;
int val;
int to;
}e[90005];
void addedge(int from,int to,int cost)
{
cnt ++;
e[cnt].nxt = head[from];
e[cnt].val = cost;
e[cnt].to = to;
head[from] = cnt;
return ;
}
void SPFA()
{
queue<int > q;
for(int i = 1;i <= n;i ++) f[i] = inf;
f[1] = 0;vis[1] = 1;q.push(1);
int v = 0;int u =0;
while(!q.empty())
{
u = q.front();
q.pop();
if(u == n) continue;
vis[u] = 0;
for(int i = head[u];i ;i = e[i].nxt)
{
v = e[i].to;
if(f[v] > f[u] + e[i].val)
{
f[v] = f[u] + e[i].val;
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&ty);
for(int i = 1;i <= n;i ++)
{
cin >> s;
for(int j = 0;j < n;j ++)
map[i][j+1] = s[j]-'0';
}
for(int i = 1;i < n;i ++)
{
tmp = 0;
for(int j = 1;j <= n;j ++)
{
tmp += map[i][j];
if(i == j) continue;
if(map[i][j] == 1)
{
if(tmp == 1) addedge(i,j,0);
else if(ty == 2 || ty == 3) addedge(i,j,tmp-1);
}
else
{
if(tmp == 0 && (ty == 1 || ty == 3)) addedge(i,j,1);
else if(ty == 3) addedge(i,j,tmp+1);
}
}
}
SPFA();
if(f[n] == inf) printf("-1");
else printf("%d",f[n]);
return 0;
}
T2 图计数 graph (计数DP，组合数学，※状态优化设计)
#6497. 「雅礼集训 2018 Day1」图
（注：一个点本身算作一条交错路径；路径可以包含多条连接连续若干个结点的连续同向有向边）
对于计数问题，可以考虑使用动态规划解决。
一般来说，用动态规划求符合题意的对象的方案数，要设计能体现题意、表达对象特征的状态，然后计数，最后筛选出合法状态的方案数作为答案。
发现性质
为了设计一个易表达易计数的状态，我们不妨先观察图的构造规则，发现一些有用的性质。
首先，
i
i
i 与
j
j
j 连边的条件是
i
<
j
i<j
i<j，这给我们提供了十分简单的构造顺序，我们可以考虑从
1
1
1 到
n
n
n 逐个完善并统计对它们的连边。
然后，题目要求统计交错路径为偶数或者奇数的图的构造方案数，我们要知道：偶数+偶数=偶数；偶数+奇数=奇数；奇数+奇数=偶数；奇数个奇数相加为奇数，偶数个奇数相加为偶数；无论多少个偶数相加仍是偶数。
接下来，考虑在实践中发现规律，我们根据前面的性质，可以考虑新加入一个点并新加一些连边对交错路径的奇偶性的影响。
最后我们可以发现：
- 对于一个作为奇数条交错路径的终点结点 i i i ，如果有一个与它不同颜色的结点 j j j 与它连边，那么全图除它本身以外将增加奇数条交错路径。
- 对于一个作为偶数条交错路径的终点结点 i i i，如果有一个与它不同颜色的结点 j j j 与它连边，那么全图除它本身以外将增加偶数条交错路径。
- 对于一个作为奇数条交错路径的终点结点 i i i ，如果有一个与它同颜色的结点 j j j 与它连边，那么全图除它本身以外将增加 0 0 0 条（即偶数条）交错路径。
- 对于一个作为奇数条交错路径的终点结点 i i i ，如果有一个与它同颜色的结点 j j j 与它连边，那么全图除它本身以外将增加 0 0 0 条（即偶数条）交错路径。
从上性质我们可以发现，除去它本身增加的交错路径，只有第一种情况是增加奇数条交错路的，结合奇数偶数的运算规律，我们可以知道作为奇数条交错路径的终点的结点是一个比较重要的状态。
设计状态与状态转移
由于我们知道我们并不关心交错路径的具体数目，所以我们针对交错路径的奇偶性进行状态设计。
我们先从简单朴素的状态入手，结合上述性质，我们可以设
f
(
i
,
j
,
x
,
y
)
f(i,j,x,y)
f(i,j,x,y) 表示有
i
i
i 个白点，
j
j
j 个黑点，
x
x
x 个奇数交错路径结尾的白点，
y
y
y 个奇数交错路径结尾的黑点的图的方案数。由奇偶数的运算规律我们知道，当
x
+
y
x+y
x+y 为奇数时，全图的交错路径为奇数，否则为偶数。
然后设计状态的转移，根据题目规则得到的连边顺序，我们考虑将一个新的结点
p
p
p 加入由前
p
?
1
p-1
p?1 个点组成的图中。根据我们发现的性质，我们以
p
p
p 为白点为例得到：
f
(
i
,
j
,
x
,
y
)
=
f
(
i
?
1
,
j
,
x
?
1
,
y
)
×
∑
k
=
2
a
,
a
∈
N
k
?
y
(
y
k
)
×
2
i
+
j
?
y
?
1
+
f
(
i
?
1
,
j
,
x
,
y
)
×
∑
k
=
2
a
+
1
,
a
∈
N
k
?
y
(
y
k
)
×
2
i
+
j
?
y
?
1
f(i,j,x,y) = f(i-1,j,x-1,y)\times\sum_{k = 2a,a\in \mathbb{N}}^{k\leqslant y}{\binom{y}{k}}\times2^{i+j-y-1}+ f(i-1,j,x,y)\times\sum_{k = 2a+1,a\in \mathbb{N}}^{k\leqslant y}{\binom{y}{k}}\times2^{i+j-y-1}
f(i,j,x,y)=f(i?1,j,x?1,y)×k=2a,a∈N∑k?y?(ky?)×2i+j?y?1+f(i?1,j,x,y)×k=2a+1,a∈N∑k?y?(ky?)×2i+j?y?1
同理可得黑点与未知点的状态转移方程。时间复杂度
O
(
n
5
)
O(n^5)
O(n5)。
最初步优化：
i
,
j
i,j
i,j 实际上对方程的影响不大，考虑合并
i
,
j
i,j
i,j ，用总点数
i
i
i 代替这两个变量。
f
(
i
,
x
,
y
)
=
f
(
i
?
1
,
x
?
1
,
y
)
×
∑
k
=
2
a
,
a
∈
N
k
?
y
(
y
k
)
×
2
i
?
y
?
1
+
f
(
i
?
1
,
x
,
y
)
×
∑
k
=
2
a
+
1
,
a
∈
N
k
?
y
(
y
k
)
×
2
i
?
y
?
1
f(i,x,y) = f(i-1,x-1,y)\times\sum_{k = 2a,a\in \mathbb{N}}^{k\leqslant y}{\binom{y}{k}}\times2^{i-y-1}+ f(i-1,x,y)\times\sum_{k = 2a+1,a\in \mathbb{N}}^{k\leqslant y}{\binom{y}{k}}\times2^{i-y-1}
f(i,x,y)=f(i?1,x?1,y)×k=2a,a∈N∑k?y?(ky?)×2i?y?1+f(i?1,x,y)×k=2a+1,a∈N∑k?y?(ky?)×2i?y?1
时间复杂度
O
(
n
4
)
O(n^4)
O(n4)
#include<iostream>
#include<cstdio>
using namespace std;
const long long modn = 998244353;
typedef long long ll;
int n,p,col[505],min_white[505],max_white[505];
ll f[400][400][400],c[400][400],pow2[400];
ll ans;
void preComb()
{
c[0][0] = 1;
for(int i = 1;i <= 399;i ++) c[i][0] = 1;
for(int i = 1;i <= 399;i ++)
for(int j = 1;j <= i;j ++)
c[i][j] = (c[i-1][j]%modn + c[i-1][j-1]%modn)%modn;
return ;
}
int main()
{
preComb();
scanf("%d%d",&n,&p);
for(int i = 1;i <= n;i ++)
{
scanf("%d",&col[i]);
min_white[i] = min_white[i-1];max_white[i] = max_white[i-1];
if(col[i] == 0) min_white[i] ++,max_white[i] ++;
if(col[i] == -1) max_white[i] ++;
}
pow2[0] = 1;
for(int i = 1;i <= 399;i ++) pow2[i] = (pow2[i-1]<<1)%modn;
if(col[1] == -1) f[1][1][0] = f[1][0][1] = 1;
else
{
if(col[1] == 1) f[1][0][1] = 1;
else f[1][1][0] = 1;
}
for(int i = 2; i <= n;i ++)
{
for(int x = 0;x <= max_white[i];x ++)
for(int y = 0;y <= min(i-min_white[i],i-x);y ++)
{
if(col[i] == -1 || col[i] == 0)
{
if(x > 0) for(int k = 0;k <= y;k += 2) f[i][x][y] = (f[i][x][y]%modn + ((f[i-1][x-1][y]*c[y][k])%modn*pow2[i-1-y]%modn)%modn)%modn;
for(int k = 1;k <= y;k += 2) f[i][x][y] = (f[i][x][y]%modn + ((f[i-1][x][y]*c[y][k])%modn*pow2[i-1-y]%modn)%modn)%modn;
}
if(col[i] == -1 || col[i] == 1)
{
if(y > 0) for(int k = 0;k <= x;k += 2) f[i][x][y] = (f[i][x][y]%modn + ((f[i-1][x][y-1]*c[x][k])%modn*pow2[i-1-x]%modn)%modn)%modn;
for(int k = 1;k <= x;k += 2) f[i][x][y] = (f[i][x][y]%modn + ((f[i-1][x][y]*c[x][k])%modn*pow2[i-1-x]%modn)%modn)%modn;
}
if((i == n) && ((p == 1 && (x+y)%2 == 1) || (p == 0 && (x+y)%2 == 0))) ans = (ans%modn + f[i][x][y]%modn)%modn;
}
}
printf("%lld",ans);
return 0;
}
优化非变量带来的时空复杂度
方程中的组合数与
2
2
2 次幂的运算增加了我们程序运行的时空复杂度，考虑对二者进行预处理，在转移过程中避免计算。同时可以考虑将第一维进行滚动处理，减少空间复杂度。
接下来，我们将发现：
∑
k
=
2
a
,
a
∈
N
k
?
n
(
n
k
)
=
∑
k
=
2
a
+
1
,
a
∈
N
k
?
n
(
n
k
)
(
n
>
0
)
\sum_{k = 2a,a\in \mathbb{N}}^{k\leqslant n}{\binom{n}{k}}=\sum_{k = 2a+1,a\in \mathbb{N}}^{k\leqslant n}{\binom{n}{k}}(n>0)
k=2a,a∈N∑k?n?(kn?)=k=2a+1,a∈N∑k?n?(kn?)(n>0)
初步运用这个性质，实现初步优化。时间复杂度
O
(
n
3
)
O(n^3)
O(n3)，核心部分如下。
f[i%2][x][y] = 0;
if(col[i] == -1 || col[i] == 0)
{
if(x > 0) f[i%2][x][y] = (f[i%2][x][y]%modn + ((f[(i-1)%2][x-1][y]*c2[y])%modn*pow2[i-1-y]%modn)%modn)%modn;
if(y > 0) f[i%2][x][y] = (f[i%2][x][y]%modn + ((f[(i-1)%2][x][y]*c2[y])%modn*pow2[i-1-y]%modn)%modn)%modn;
}
if(col[i] == -1 || col[i] == 1)
{
if(y > 0) f[i%2][x][y] = (f[i%2][x][y]%modn + ((f[(i-1)%2][x][y-1]*c2[x])%modn*pow2[i-1-x]%modn)%modn)%modn;
if(x > 0) f[i%2][x][y] = (f[i%2][x][y]%modn + ((f[(i-1)%2][x][y]*c2[x])%modn*pow2[i-1-x]%modn)%modn)%modn;
}
优化状态设计
最后我们希望使程序运行更为优秀，那么我们需要发现：
∑
k
=
2
a
,
a
∈
N
k
?
n
(
n
k
)
=
∑
k
=
2
a
+
1
,
a
∈
N
k
?
n
(
n
k
)
=
2
n
?
1
(
n
>
0
)
\sum_{k = 2a,a\in \mathbb{N}}^{k\leqslant n}{\binom{n}{k}}=\sum_{k = 2a+1,a\in \mathbb{N}}^{k\leqslant n}{\binom{n}{k}} = 2^{n-1}(n>0)
k=2a,a∈N∑k?n?(kn?)=k=2a+1,a∈N∑k?n?(kn?)=2n?1(n>0)
由此可得：
f
(
i
,
x
,
y
)
=
f
(
i
?
1
,
x
?
1
,
y
)
×
2
i
?
2
+
f
(
i
?
1
,
x
,
y
)
×
2
i
?
2
f(i,x,y) = f(i-1,x-1,y)\times2^{i-2}+ f(i-1,x,y)\times2^{i-2}
f(i,x,y)=f(i?1,x?1,y)×2i?2+f(i?1,x,y)×2i?2
又可以进一步优化了，但是仍然不足够。
由上一步的优化可以发现，对于白点的这个方程，无论从什么状态转移而来，如果
x
>
0
x > 0
x>0 转移的方案数一定是
2
i
?
2
2^{i-2}
2i?2 ，如果
x
=
0
x = 0
x=0 则单独讨论即可，同理可以推广到剩余的方程 ，那么我们实际上只需要关注是否存在作为奇数条交错路径终点的结点。
设
f
(
i
,
0
/
1
,
0
/
1
,
0
/
1
)
f(i,0/1,0/1,0/1)
f(i,0/1,0/1,0/1) 表示前
i
i
i 个点组成的图中，是否有白色奇点，是否有黑色奇点，交错路径是否奇偶的方案数，转移方程很多，整个过程及其意义要弄清楚
才能写出来，此时时间复杂度
O
(
n
)
O(n)
O(n)
#include<iostream>
#include<cstdio>
using namespace std;
const long long modn = 998244353;
typedef long long ll;
int n,p,col[200005];
ll f[200005][2][2][2],pow2[200005];
ll ans;
bool firx,firy;
int main()
{
scanf("%d%d",&n,&p);
for(int i = 1;i <= n;i ++)
{
scanf("%d",&col[i]);
}
pow2[0] = 1;
for(int i = 1;i <= 200000;i ++) pow2[i] = (pow2[i-1]*2)%modn;
f[0][0][0][0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 0;j <= 1;j ++)
for(int k = 0;k <= 1;k ++)
for(int t = 0;t <= 1;t ++)
{
if(!f[i-1][j][k][t]) continue;
if(col[i] != 1)
{
if(k)
{
f[i][j][k][t] = (f[i][j][k][t] + f[i-1][j][k][t]*pow2[i-2]%modn)%modn;
f[i][j|1][k][t^1] = (f[i][j|1][k][t^1] + f[i-1][j][k][t]*pow2[i-2]%modn) %modn;
}
else f[i][j|1][k][t^1] = (f[i][j|1][k][t^1] + f[i-1][j][k][t]*pow2[i-1]%modn)%modn;
}
if(col[i])
{
if(j)
{
f[i][j][k][t] = (f[i][j][k][t] + f[i-1][j][k][t]*pow2[i-2]%modn)%modn;
f[i][j][k|1][t^1] = (f[i][j][k|1][t^1] + f[i-1][j][k][t]*pow2[i-2]%modn)%modn;
}
else f[i][j][k|1][t^1] = (f[i][j][k|1][t^1] + f[i-1][j][k][t]*pow2[i-1]%modn)%modn;
}
}
for(int i = 0;i <= 1;i ++)
for(int j = 0;j <= 1;j ++)
ans = (ans + f[n][i][j][p]%modn)%modn;
printf("%lld",ans%modn);
return 0;
}
Day 4
T1 翻翻翻 reverse （最短路，宽度搜索，set介绍）
通过观察容易知道，可以将其转换成为最短路的模型，直接跑最短路。但是毒瘤数据连 Dijkstra 加堆优化都卡掉了
20
20
20 分，所以考虑进一步发掘性质。
于是就有性质：从一个点出发，能够到达的点一定是一个区间内的所有奇数位置或者所有偶数位置。
然后可以将全部未访问的奇数位置和偶数位置记下来，并且在翻转的时候查询在当前位置的可行区间内所有可到达的位置，然后快速遍历。题解说拿两个set，分奇偶数维护当前所有的未访问点。每次用
x
x
x 点更新答案时，则寻找一个区间内
的所有未访问的奇数点或者偶数点，如果能找到则加入队列继续更新。
时间复杂度
O
(
n
log
?
n
)
O(n\log n)
O(nlogn)
于是开始学用 set：
set内部采用红黑树实现，是一种平衡二叉树，用于快速查询。
- 插入元素：
insert(val)或者insert(beg,end)，是其成员函数，插入 val 元素或插入 beg 到 end 区间的元素
set<int > s;
s.insert(1);
s.insert(5,8);
- 迭代器：
set<int >::iterator，定义一个迭代器可以用于遍历set，如果要访问其中的元素则要调用其指针。
set<int > s;
for(int i = 1;i <= n;i ++) s.insert(a[i]);
set<int >::iterator it;
for(it = s.begin();it != s.end();it ++) cout << *it << ' ';
- 删除元素：
erase(val)或erase(pos)删除 val 元素或删除指针 pos 指向的元素，并返回下一个元素迭代器。
s.earse(7);
lower_bound(val)返回第一个 >=val 元素的迭代器，如果没有返回 s.end()。upper_bound(val)返回第一个 >val 元素的迭代器，如果没有返回 s.end()。find(val)返回指向 val 元素的指针，如果没有返回 s.end()，如果多个返回第一个。
参考自学长SC的STL笔记。
#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
const int N = 1e5 + 5;
int n,k,m,s;
int ans[N],x;
bool ban[N];
set<int > odd,even;
void bfs()
{
memset(ans,-1,sizeof(ans));
queue<int > q;
set<int>::iterator iter;
ans[s] = 0;q.push(s);
while(!q.empty())
{
int now = q.front();
q.pop();
int lt = max(1, now - k + 1); int rt = min(n , now + k - 1);
lt = lt + (lt + k - 1) - now;
rt = rt + (rt - k + 1) - now;
set<int > &p = lt & 1 ? odd : even;
for(iter = p.lower_bound(lt);iter != p.end() && *iter <= rt;p.erase(iter ++))
{
ans[*iter] = ans[now] + 1;
q.push(*iter);
}
}
return ;
}
int main()
{
scanf("%d%d%d%d",&n,&k,&m,&s);
for(int i = 1;i <= m;i ++)
{
scanf("%d",&x);
ban[x] = 1;
}
for(int i = 1;i <= n;i ++)
if(!ban[i] && i != s)
{
if(i & 1) odd.insert(i);
else even.insert(i);
}
bfs();
for(int i = 1;i <= n;i ++) printf("%d ",ans[i]);
return 0;
}
T2 商人 merchant （利用单调性二分求解，nth_element()函数介绍）
可以发现，每个物品的价值都是关于时间的一次函数。选择
m
m
m 个物品就相当于选择了
m
m
m 条直线，我们可以发现，对于这
m
m
m 条直线
l
1
:
y
=
k
1
x
+
b
1
,
l
2
:
y
=
k
2
x
+
b
2
?
l
m
:
y
=
k
m
x
+
b
m
l_1:y=k_1x+b_1,l_2:y=k_2x+b_2\cdots l_m:y=k_mx+b_m
l1?:y=k1?x+b1?,l2?:y=k2?x+b2??lm?:y=km?x+bm? 之和等价于 直线
l
′
:
y
=
∑
k
i
x
+
∑
b
i
l':y=\sum k_ix+\sum b_i
l′:y=∑ki?x+∑bi?，其仍是一次函数，具有单调性，故本题考虑用二分的方法求解。
不过在这些物品当中，有的
k
?
0
k \geqslant 0
k?0 ，有的
k
<
0
k < 0
k<0，不妨先分开考虑。
对于
k
<
0
k < 0
k<0 的物品，其在
t
t
t 范围内的最大值必然在
t
=
0
t=0
t=0 时取得，此后函数值递减，故如果全部物品都满足
k
<
0
k < 0
k<0 ，则我们只需判断
t
=
0
t=0
t=0 时
∑
b
i
\sum b_i
∑bi? 是否大于等于
S
S
S 即可。复杂度
O
(
1
)
O(1)
O(1)。
对于
k
>
0
k > 0
k>0 的物品，可以二分
t
t
t ，然后算出所有函数值，排序后暴力判断前
m
m
m 个物品是否满足
∑
k
i
+
∑
b
i
?
S
\sum k_i + \sum b_i \geqslant S
∑ki?+∑bi??S 即可。复杂度
O
(
(
n
log
?
n
+
m
)
log
?
1
0
9
)
O((n\log n + m)\log 10^9)
O((nlogn+m)log109)。
现将两种情况综合考虑，我们发现两种情况可以兼容，所以我们要在
t
=
0
t = 0
t=0 时判断一下，然后开始二分，这时仍然算出所有函数值，但是要注意，遇到
k
i
x
+
b
i
<
0
k_ix+b_i<0
ki?x+bi?<0 的就不选，因为题目说选择不超过
m
m
m 个物品即可，所以不要让负值影响我们判断，也可以每选一个物品判断一次，避免受到负值影响。
发现瓶颈在于每次找出前
m
m
m 大的元素，我们有下列方法可以快速找出：
- 使用 STL 的
nth_element()函数。传入左指针，右指针和你希望求出的第 m m m 大之后，函数会
的将第 m m m 大的元素放在第 m m m 个位置，并将比这个元素小的放在左边，比它大的放在右边。 - 手写快排，每次随机一个元素后即可知道第
m
m
m 大的是在左边还是右边，只需要向一边递归即可。由
于每层长度期望减小一半，这个算法的复杂度也是 O ( n ) O(n) O(n) 的（事实上 STL 就是这样实现的）
由此时间复杂度降为
O
(
n
log
?
1
0
9
)
O(n\log 10^9)
O(nlog109)
在algorithm头文件下 nth_element(beg,it,end,cmp)找到 beg 到end区间内按照 cmp 排序后在it这个地方的元素，并将这个元素放在 it（it是指针）的位置，比他小的放左边，大的放右边，没有返回值。参考自学长SC的 STL 笔记。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 1e9 + 19;
ll n,m,S,sum,lt,rt,mid,sumk,sumb,maxt,val[10000005],ans;
struct func{
ll k;
ll b;
}f[1000005];
bool calc(ll x)
{
for(int i = 1;i <= n;i ++) val[i] = f[i].k * x + f[i].b;
nth_element(val + 1,val + m ,val + 1 + n,greater<ll>());
sum = 0;
for(int i = 1;i <= m;i ++)
{
if(sum >= S) return 1;
if(val[i] > 0) sum += val[i];
}
return sum >= S;
}
void Bisearch()
{
ans = inf;
lt = 1;rt = 1e9;
while(lt < rt)
{
mid = (lt + rt)/2;
if(calc(mid)) rt = mid;
else lt = mid + 1;
}
ans = lt;
return ;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&S);
for(int i = 1;i <= n;i ++)
scanf("%lld%lld",&f[i].k,&f[i].b);
if(calc(0))
{
printf("0");
return 0;
}
maxt = 1e9;
Bisearch();
printf("%lld",ans);
return 0;
}