Day 9
Day 9
nt欢乐赛
T1
直接暴力 next_permutation 或者暴力搜索即可, 需要模拟一个简单的表达式解析。
时间复杂度 \(O(n!)\)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
int t,n,m;
ll v[55];
map<char, int> num;
char fk[1145];
int fkcnt;
int pro(char op)
{
switch(op)
{
case '+':
return 1;
case '-':
return 1;
case '*':
return 2;
default: return 0;
}
}
string solve1(string S)
{
stack<char> st;
string lf;
int l = S.length();
for(int i = 0; i < l; ++ i)
{
if(isdigit(S[i]) || isalpha(S[i]))lf += S[i];
else if(S[i] == '(')st.push(S[i]);
else if(S[i] == ')')
{
while(st.size() && st.top() != '(')
{
lf += st.top();
st.pop();
}
st.pop();
}
else
{
while(st.size() && pro(st.top()) >= pro(S[i]))
{
lf += st.top();
st.pop();
}
st.push(S[i]);
}
}
while (st.size())
{
lf += st.top();
st.pop();
}
return lf;
}
int solve2(string lf)
{
stack<int> st;
int l = lf.length();
for(int i = 0; i < l; ++ i)
{
if(isdigit(lf[i])) st.push(lf[i] - '0');
else if(isalpha(lf[i])) st.push(num[lf[i]]);
else
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
switch(lf[i])
{
case '+':
st.push(a + b);
break;
case '-':
st.push(b - a);
break;
case '*':
st.push(a * b);
break;
}
}
}
return st.top();
}
int main()
{
//freopen("sample_2.in","r",stdin);
//freopen("sample_2.out","w",stdout);
t = read();
string s;
while(t --)
{
fkcnt = 0;
n = read();
for(int i = 1; i <= n; ++ i)v[i] = read();
sort(v + 1, v + n + 1);
m = read();
cin >> s;
int l = s.length();
for(int i = 0; i < l ; ++ i)
if(s[i] >= 'a' && s[i] <= 'z')
fk[++ fkcnt] = s[i];
int flag = 0;
do
{
num.clear();
for(int i = 1; i <= n; ++ i)
num[fk[i]] = v[i];
string fkp = solve1(s);
ll ans = solve2(fkp);
if(ans == m)
{
puts("YES");
flag = 1;
break;
}
}while(next_permutation(v + 1, v + n + 1));
if(!flag)
puts("NO");
}
return 0;
}
T2
考虑直接暴力搜索每个位置放了或者没有放, 可能的优化:
- 如果某一行/某一列超过限制了或者全选了也不够，直接剪枝
- 从最后一行/最后一列开始搜索，因为权值大能够对后面有比较大的影响。
时间复杂度 \(O(能过)\)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
int t, n, m;
int h[16], l[16], ans[16][16];
void dfs(int x, int y)
{
int bj = 0;
if(y == 0)
{
if(h[x])return;
else y = m, -- x;
}
if((y + 1) * y / 2 < h[x])
return;
if(x == 0)
{
for(int i = 1 ; i <= m; -- i)if(l[i]) return;
bj = 1;
return;
}
if(x * (x - 1) / 2 >= h[y])ans[x][y] = 0,dfs(x, y - 1);
if(h[x] >=y && l[y] >= x)
{
if(x != 1 || !(l[y] - x))
{
h[x] -= y, l[y] -= x;
ans[x][y] = 1;
dfs(x, y - 1);
if(bj)return;
h[x] += y, l[y] += x;
}
}
}
int main(){
ct = read();
while(t --)
{
n = read(), m = read();
for(int i = 1; i<= n; ++ i) h[i] = read();
for(int i = 1;i <= m; ++ i) l[i] = read();
dfs(n, m);
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; ++ j) cout << ans[i][j] << ' ';
cout << '\n';
}
}
return 0;
}
T3
我们本质上就是需要构造一个有向图，我们可以把重边的重数看成边权，同时上面的字母是不重要的。考虑怎么通过搜索构造这个有向图。
我们需要确定的东西: 终点集合，边权。
整体搜索的想法就是一个一个点的加上，搜索连边情况剪掉不用的状态
- 如果某个时刻能够接受的状态已经超过了，剪枝
- 限制每条边的边权上界
- 在估计某个时刻能够接受的状态的时候加上不能走到终点的点的贡献，因为这些点一定在之后的某个时刻能够走到终点。
- ...
最后通过限制我们发现所有点都在 \(n\le 4\) 有解，在限制了边权上界为 \(4\) 能够很快的求解出答案。
时间复杂度 \(O(能过)\)
打表即可 \(O(1)\)
耻辱代码。不发了（
T4
考虑搜索平方之前的数, 我们可以发现如果确定了一个后缀那么平方之后的一个后缀也确定了，同时如果确定了一个前缀，平方之后的前缀也能规范到一个区间里面。
于是我们就可以按照后面一个数前面一个数的顺序进行搜索，如果某个时刻确定的后缀没有办法匹配当前的前缀区间就剪枝。
这种做法可以在一个小时之内算出所有平方前 \(10^{17}\) 的答案，也就是数据范围里的 \(k\le 485\).
同样耻辱打表
题目选讲
CF 912E
给定 \(n\) 个质数 \(p_1, p_2, ... ,p_n\), 求出第 $k $ 小的质因数全在给定质数内的数，保证此树 \(\le 10^{18}\)
\(n \le 16, p_i \le 100\)
meet in middle + 二分
考虑将质因数分为两个集合 \(A, B\) 分别预处理集合内的质因数能构成的集合，二分最后答案，枚举其中一个集合里的因数， 双指针计算另一集合内因数上限计算方数。
如果我们按照小一半大一半来划分集合的话会造成一个集合过大，所以我们可以吧排序后按照奇偶位置划分。
Cf 483E
如果一个数在十进制表示下每个数码要么比左右都小要么比左右
都大，那么我们就称这个数是 \(wavy\) 的。
求第 \(k\) 小的是 \(n\) 倍数的 \(wavy\) 数, 如果这个数大于 \(10^{14}\) 你只需
要输出 \(−1\).
\(n, k ≤ 10^{14}\)
观察数据范围, 我们没法直接暴力枚举，考虑 \(meet-in-middle\) 折半搜索
预处理左一半和右一半满足 \(wavy\) 条件的数同时记录模 \(n\) 的余数。
我们在合并的时候不仅需要保证左右的 \(wavy\) 性质还需要保证中间合并点的性质,
那么需要我们在预处理分类的时候将端点值以及端点的大小关系也记进去。
\(O(\sqrt{n})\)
code
Luogu P3230 [HNOI2013] 比赛
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联赛共 \(N\) 支球队参加，比赛规则如下：
-
每两支球队之间踢一场比赛；
-
若平局，两支球队各得 \(1\) 分；
-
否则胜利的球队得 \(3\) 分，败者不得分。 尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分， 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有 \(3\) 支球队，每支球队最后均积 \(3\) 分，那么有两种可能的情况：
可能性 \(1\) and 可能性 \(2\)
| 球队 | \(A\) | \(B\) | \(C\) | 得分 | 球队 | \(A\) | \(B\) | \(C\) | 得分 |
|---|---|---|---|---|---|---|---|---|---|
| \(A\) | - | \(3\) | \(0\) | \(3\) | \(A\) | - | \(0\) | \(3\) | \(3\) |
| \(B\) | \(0\) | - | \(3\) | \(3\) | \(B\) | \(3\) | - | \(0\) | \(3\) |
| \(C\) | \(3\) | \(0\) | - | \(3\) | \(C\) | \(0\) | \(3\) | - | \(3\) |
但沫沫发现当球队较多时，计算工作量将非常大，所以这个任务就交给你了。请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对 \(10^9+7\) 取模的结果。
\(100\%\) 的数据满足 \(3≤N≤10\) 且至少存在一组解。
搜索剪枝
每个人每个时刻的当前得分不能超过总分。
如果某个时刻赢下剩下所有的比赛都不够总分就剪枝。
由于总分和总场数是确定的，同时胜场贡献 3 分，平场贡献 2 分可以确定胜、平的总场数。
最后剩余人数很少的时候可以记忆化。
可能的对称性剪枝。
Gym 100503B
如下图你需要完成一个 \(kakuro\) 拼图, 每个白色的格子需要填入
一个 \(1\) 到 \(9\) 的数字, 每个 \(run\) 里面每个数字最多使用一次，黑色
格子上写着数字和的一些限制。
\((n, m ≤ 6)\)
搜索。
每个位置最多属于两个 \(run\), 在搜索的过程中记录每个 \(run\)。
使用的数字集合以及当前的和。
如果某个时刻一个 \(run\) 剩余没有填的元素都按照最小的去填仍然超过，或者都按照最大的去填仍然到不了就剪枝。
爬山算法
搜索中所有状态集合 \(S\) ,那么搜索算法相当于以某种方式便利整个状态集合同时统计是否合法/合法个数/最优解。
在搜索过程中我们可以去定义两个状态的” 相邻”，比如: 两个二
进制串 (或任意字符串) 差正好一位的串, 棋盘上再下一步, ...
那么同时我们每个状态会有一个属性, 在最优化问题中这个属性
就是最优化的值, 在合法性问题中这个属性需要我们去给定, 可
以是对当前局面的一个评分, 也可以是当前局面能到达的最好局
面 (估算) 的评分。
那么爬山算法可以描述为从某个初始状态开始, 每次选择最好的
走到一个相邻状态直到当前状态的任意相邻状态都会变差停止。
我们可以发现这种算法会在一个局部极值停止不一定会是全局的
最值。
那么一种优化方法就是执行算法若干次每次随机一个不同
的起点，这样增加了停在全局最值的概率。
在凸函数上爬山算法是有正确性保证的，但在一般函数上正确性
无法保证。
爬山算法一般应用于已知的 NP-Complete 问题或者
常规算法较难求解的问题，多数情况下能取得比较不错的解。
模拟退火算法是基于爬山算法的一种优化, 同样是使用某种方式
对状态集合进行搜索。
简单的说，爬山算法只能接受更优 (非更劣) 的状, 而模拟退火算
法可以以某种概率走向更劣的解, 当然损失的权值越大概率越小，
同时随着迭代次数 (时间) 的推移概率越小。当 \(t → ∞\) 的时候模
拟退火算法就是爬山算法。
算法流程:
- 初始随机状态 \(s = s_0\), 温度 \(t = t_0\)
- 随机一个相邻状态 \(s'\)
, 计算目标函数差值 \(∆C = C(s′) − C(s)\) - 以 \(min(1.0, exp(\frac{∆C}{t}))\) 的概率 \(s ← s'\)
- \(t ← γ t\), 其中 \(γ\) 为温度衰减系数, 一般为 \(1 − [10^{−7}, 10^{−3}]\)
- goto 2 (从第 \(2\) 步开始循环)
JOISC2020 �説の�子職人
您面前有一个 \(R \times C\) 的网格，每一个格子里有一个团子，您可以横向，竖向，斜向地将三个连续的团子按顺序串起来，按顺序指可以串上中下，下中上之类的，但是不能串中下上，上下中之类的。
如果一串团子的颜色为绿，白，粉或者粉，白，绿，那么称这串团子叫 AK IOI 串。
求串最多 AK IOI 串的方法（我坚信做了几个 AK IOI 串就会 AK 几次 IOI）。
输入格式
第一行两个整数 \(R,C\) 代表网格大小。
接下来 \(R\) 行每行 \(C\) 个字符代表网格：
P代表粉色团子W代表白色团子G代表绿色团子
一共有 \(6\) 组数据，保证 \(3 \le R,C \le 500\)
考虑将每一个合法的串子建一个点，如果两串共用了团子就连一
条边，那么这个问题就抽象成了一般图最大独立集问题，这显然
是一个目前无法在多项式时间内解决的 \(NP-complete\) 问题。
考虑贪心的做法，按照某个顺序加点，直到没有点能加为止。
那么状态的相邻可以描述为:
选择一个有冲突的串子加进去然后删掉有矛盾的串子，目标函数就是串子的个数。使用爬山或者模拟退火解决。
总结
剪枝:
- 可行性剪枝
- 最优性剪枝
- 对称性剪枝
记搜 (寄搜)
折半 \(meet-in-middle\)
A星 \(A^*\)
爬山，模拟退退火