Aug.Day07 8.13总结
#A.乘方
本题最初的思路可以想到用一个快速幂求出幂的值后判断是否大于 。
int qmi_m (int a, int b)
{/*....*/}
int main ()
{
//...
if (qmi_m (a, b) > 1e9) cout << -1;
else cout << qmi_m (a, b);
}
但是由于 ，那么求出来的幂值最大是 ，连 __int128 都装不下，所以不能先求出幂值再判断。
进一步思考，既然如果最后的值大于 ，那么在求快速幂时就会有一个时间点，在这个时间点，res 的值会超过 ，所以可以在快速幂里边算边求。
细节：不能直接每次判断 res，应该判断每次更新的底数，并且最后还要再判一次 res。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
void qmi_m (int bs, int ex)
{
int res = 1;
while (ex)
{
if (bs > 1e9)
{
cout << -1;
return;
}
if (ex & 1) res *= bs;
bs *= bs;
ex >>= 1;
}
if (res > 1e9) cout << -1;
else cout << res;
}
signed main ()
{
Fio ("cf");
cin >> a >> b;
qmi_m (a, b);
return 0;
}
感受与学习：无（ 过于简单 ）。
错误原因：无。
#B.解密
本题是一道数学题，有两种思路较接近的写法。
写法1.二分
二分的思路十分简单，比第二种做法的思考量稍微少一些。首先可以想到先将 这个式子展开，方便后续操作（为方便，下文省去各个变量的下标 ）：
$$e \times d=(p-1)(q-1)+1 \\ =p(q-1)-(q-1)+1 \\ =pq-p-q+2$$得到这个式子以后，再结合 这个式子，那么需要尽量得到 的值来二分，接下来将 代入式子，通过 展开得到：
$$n-ed \\ =pq-(pq-p-q+2) \\ =pq-pq+p+q-2 \\ =p+q-2 \\ \rightarrow \\ n-ed=p+q-2 \\ p+q-2+2=n-ed+2 \\ n-ed+2=p+q$$emmmmm...其实就是题目给你的 ，将其带入即可。
那么接下来可以开始二分了，开始 l 初始化为 ，r 初始化为 （因为用 的话， 之前就会枚举到所有可能）。用二分去枚举 ，则 就是 或 ，用第一套模版的话，r 变量往左移的条件为如果发现 p * (m - p) >= n，否则 l 往左移。最后检验答案并输出。
Code:
#include <bits/stdc++.h>
#define int unsigned long long int
using namespace std;
int k;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
bool Check (int p, int n, int ml)
{
int q = n - ml + 2 - p;
if (p * q >= n) return true;
return false;
}
signed main ()
{
Fio ("decode");
cin >> k;
while (k --)
{
int n, d, e; cin >> n >> d >> e;
int m = n + 2 - e * d;
int l = 1, r = sqrt (n);
while (l < r)
{
int mid = l + r >> 1;
if (Check (mid, n, d * e)) r = mid;
else l = mid + 1;
}
if (l * (m - l) == n) cout << l << ' ' << m - l << '\n';
else cout << "NO\n";
}
return 0;
}
做法2.纯数学
根据上面得出 的式子，可以得出：
$$n=pq \\ m=p+q \\ (p+q)^2=p^2+q^2+2pq \\ (p-q)^2=p^2+q^2-2pq \\ (p+q)^2-4pq=p^2+q^2-2pq \\ (p+q)^2-4pq=(p-q)^2 \\ \sqrt{m^2-4n}=p-q \\ \rightarrow \\ m=p+q \\ \sqrt{m^2-4n}=p-q \\ \because (p+q+p-q) \div 2=p \\ \because (p+q-p+q) \div 2=q \\ ∴ (m+ \sqrt{m^2-4n}) \div 2=p \\ ∴ (m- \sqrt{m^2-4n}) \div 2=q$$所以最终只需求出 m = n - e * d + 2，那么即可求出 p = (m + sqrt (m * m - 4 * n)) / 2, q = (m - sqrt (m * m - 4 * n)) / 2。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
signed main ()
{
Fio ("decode");
cin >> k;
while (k --)
{
int n, d, e; cin >> n >> d >> e;
int m = n - e * d + 2;
int p = (m + sqrt (m * m - 4 * n)) / 2, q = (m - sqrt (m * m - 4 * n)) / 2;
if (p * q == n) cout << min (p, q) << ' ' << max (p, q) << '\n';
else cout << "NO\n";
}
return 0;
}
感受与学习：本题我想到了二分解法，但是没有考虑全，离正解只有非常细微的差距了qwq，应该从深层思路方面想。
错误原因：二分条件没考虑全，没有仔细检查，也没有仔细思考自己思路的正确性。
#C.逻辑表达式
本题是一道表达式求值与深搜结合的一道题。
本题的难点在于如何处理短路的情况，这时我们就可以从表达式求值的根本——表达式树去想。如果一个非叶子结点（符号节点）为符号与且左子树的值为 ，那么构成一个短路，或运算亦同。根据树的递归性质，可以用深搜求解。
首先，符号栈不变，但是要准备好三个数组来建立一棵树，并且数字栈里的元素改为所有数字节点在表达式树里的编号（为后面建树时确定左右节点），用一个变量 idx 表示节点编号。wt[i] 代表当前第 i 个节点的值，lson[i] 和 rson[i] 代表第 i 个节点的左右节点编号，在读取到 '0' 或 '1' 字符时先将这个字符在 wt 里新建一个节点，再将当前节点的编号压入数字栈中。其他则按正常写，最大的不同就是原模版的 calc_m 函数改了，将计算改为了建树。
而搜索的过程就是不停的遍历左右子树，如果当前 wt[flo] == '&' || wt[flo] == '|'，这时就可以判断左子树的结果，符合短路条件就将对应 cnt ++。而边界就是当 wt[flo] 为 '1' 或 '0'，则 return 1 或 0。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int lson[N], rson[N], cta, cto, idx;
stack <char> opt;
stack <int> num;
char wt[N];
string s;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
int jg_m (char op)
{
if (op == '&') return 2;
return 1;
}
void calc_m ()
{
int y = num.top (); num.pop ();
int x = num.top (); num.pop ();
wt[++ idx] = opt.top (); opt.pop ();
lson[idx] = x, rson[idx] = y;
num.push (idx);
}
int DFSexpr (int flo)
{
if (wt[flo] == '0') return 0;
if (wt[flo] == '1') return 1;
if (wt[flo] == '&')
{
if (DFSexpr (lson[flo]) == 0)
{
cta ++;
return 0;
}
if (DFSexpr (rson[flo]) == 1) return 1;
return 0;
}
if (wt[flo] == '|')
{
if (DFSexpr (lson[flo]) == 1)
{
cto ++;
return 1;
}
if (DFSexpr (rson[flo]) == 0) return 0;
return 1;
}
}
int main ()
{
Fio ("expr");
cin >> s;
for (int i = 0, oi = 0; i < s.size (); i ++, oi ++)
{
if (isdigit (s[i]))
{
wt[++ idx] = s[i];
num.push (idx);
}
else if (s[i] == '(') opt.push (s[i]);
else if (s[i] == ')')
{
while (opt.top () != '(') calc_m ();
opt.pop ();
}
else
{
while (opt.size () && opt.top () != '(' && jg_m (opt.top ()) >= jg_m (s[i]))
calc_m ();
opt.push (s[i]);
}
}
while (opt.size ()) calc_m ();
int res = DFSexpr (idx);
cout << res << '\n' << cta << ' ' << cto;
return 0;
}
感受与学习：本题就是一个对表达式求值的综合应用，须多加练习表达式求值运用。
错误原因：没有想到短路的更好的处理方式，没有想到表达式的根本——表达式树。
#D.上升点列
本题又是一道 ₯ 题qwq。
观察数据，发现 时本题就是一个最长上升子序列，能拿 分：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int n, k, f[N];
template <typename _ft, typename _st>
struct biny
{
_ft x;
_st y;
};
vector <biny <int, int> > ps;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
bool CmpP (biny <int, int> a, biny <int, int> b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool Check (int o, int t)
{
int sx = ps[t].x - ps[o].x, sy = ps[t].y - ps[o].y;
if ((sx == 1 && sy == 0) || (sx == 0 && sy == 1)) return true;
return false;
}
int main ()
{
Fio ("point");
cin >> n >> k;
for (int i = 0; i < n; i ++)
{
int x, y; cin >> x >> y;
ps.push_back ({x, y});
f[i] = 1;
}
sort (ps.begin (), ps.end (), CmpP);
// for (auto itr : ps) cout << itr.x << ' ' << itr.y << '\n';
for (int i = 0; i < ps.size (); i ++)
{
for (int j = 0; j < i; j ++)
if (Check (j, i)) f[i] = max (f[i], f[j] + 1);
}
int mxu = 1;
for (int i = 0; i < ps.size (); i ++)
mxu = max (mxu, f[i]);
cout << mxu + k;
return 0;
}
那么，如何更新为能加 个， 个 ... 个点的数组呢？首先，要将 增加一维，从 变为 ， 表示以第 个节点结束（已经按曼哈顿距离排了序）且用了 个自己增加的点的最长序列长度，那么可以思考：
初始化每个点结束时，增加 个点的距离为 （f[i][0] = 1）。枚举每一个点 ，这就是本次循环要用 个点到达的终点，再枚举 为从 的所有节点，就是循环中从第 个点到第 个点需要更新，随后先算出从 点至 点的曼哈顿距离 dis，这就是我们从 走至 点的需要加的点个数，不过需要判断，如果 的 坐标或 坐标有一个比 的对应坐标大，说明从 走不到 ，直接 continue；如果 dis > k，说明用 k 个点也走不到，也 continue，不过记住，两端的点都不要算，所以 dis 还要减 。
接下来枚举需要加的点数 从 个点枚举，每次更新能用的 为 ，也就是在原来的值与更新后的值取最大值，更新后的值也就是从 出发到 点，多花了 个点，而之间的长度又多了 ，不过由于 一开始减了一个 ，所以还要加上 。
最后答案为 $\max \{f_{i, j}+(k-j)\} \ (i \in [0,n-1],j \in [0,k])$。
伪代码：
for i in 0 to n
begin
for j in 0 to i - 1
begin
var dis = manhaton_distance (i, j) - 1 : int;
if ps[j].x > ps[i].x or ps[j].y > ps[i].y or dis > k then next -> j;
for l in dis to k
begin
f[i][l] = max (f[i][l], f[j][l - dis] + dis + 1);
end.
end.
end.
var maxinium = 1 : int;
for i in 0 to n
begin
for j in 0 to k
begin
maxinium = max (maxinium, f[i][j] + k - j);
end.
end.
write (maxinium);
Code:
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e3 + 10;
int n, k, f[N][N];
vector <pair <int, int> > ps;
void Fio (string iofile)
{
string ifl = iofile + ".in", ofl = iofile + ".out";
freopen (ifl.c_str (), "r", stdin);
freopen (ofl.c_str (), "w", stdout);
}
int mahtn_m (int f, int t)
{
int sx = abs (ps[t].x - ps[f].x);
int sy = abs (ps[t].y - ps[f].y);
return sx + sy;
}
int main ()
{
Fio ("point");
cin >> n >> k;
for (int i = 0; i < n; i ++)
{
int x, y; cin >> x >> y;
ps.push_back ({x, y});
f[i][0] = 1;
}
sort (ps.begin (), ps.end ());
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < i; j ++)
{
int dis = mahtn_m (i, j) - 1;
if (ps[j].x > ps[i].x || ps[j].y > ps[i].y || dis > k) continue;
for (int l = dis; l <= k; l ++)
f[i][l] = max (f[i][l], f[j][l - dis] + dis + 1);
}
}
int mxu = 1;
for (int i = 0; i < n; i ++)
for (int j = 0; j <= k; j ++)
mxu = max (mxu, f[i][j] + k - j);
cout << mxu;
return 0;
}
感受与学习：本题是一道标准的 线性₯ 题，以后遇到这种题应该多想 状态表示 和计算。
错误原因：没有一点头绪，但是是一道很好的 ₯ 题（ 使我头脑旋转 ）。
