目录
单词接龙
思路：数据范围很小，只需枚举所有可以接龙的情况，更新最大接龙长度即可，具体实现看代码。
算法：搜索回溯
时间复杂度：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> words;
int st[25];
int ans = 0;
// 看a是否可以接到b，且不能是子串关系
int find(string a, string b)
{
int lena = a.size(), lenb = b.size();
int mx = 0;
// 枚举a的后缀和b的前缀长度，min保证不会有子串关系
for (int i = 1; i < min(lena, lenb); i++)
if (a.substr(lena - i) == b.substr(0, i))
return i; // 能接直接返回
return 0;
}
void dfs(int u, int curlen)
{
ans = max(ans, curlen);
for (int i = 0; i < words.size(); i++)
{
if (st[i] > 1) continue; // 每个单词最多用两次
int k = find(words[u], words[i]);
if (k > 0) // 可以接龙
{
st[i]++;
// a = abcc b = cccdef lena = 4, lenb = 6, k = 1, curlen = 4+6-1
dfs(i, curlen + words[i].size() - k);
st[i]--;
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string x; cin >> x;
words.push_back(x);
}
char head;
cin >> head;
for (int i = 0; i < n; i++)
{
if (words[i][0] == head) // 以当前下标i的单词开始接龙
{
st[i]++;
dfs(i, words[i].size());
st[i]--;
}
}
cout << ans;
return 0;
}
小田的01变换
思路：
- 01，10无法变换
- 111100或者000011只需一次
- 111000需要两次
- 1111111 或 000000 不需要
统计1和0的个数，分类讨论即可：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, ans;
string s;
cin >> n >> s;
int cnt0 = count(s.begin(), s.end(), '0');
int cnt1 = count(s.begin(), s.end(), '1');
if (s == "01" || s == "10") ans = -1;
else if (cnt1 == 0 || cnt0 == 0) ans = 0;
else if (cnt1 > cnt0 || cnt0 > cnt1) ans = 1;
else if (cnt1 == cnt0) ans = 2;
cout << ans;
return 0;
}
Dota2参议院
思路：行使禁止权力肯定是用到下一个将要投票的敌对阵营的议员身上，这样可以让对方势力尽可能减弱。由于投票是按顺序一轮一轮进行，可以用两个队列q1，q2分别维护天辉R和夜魇D的投票过程。
- 若R投票，则R出队再入队，D出队，不入队，因为被禁止了
- 若D投票，则D出队再入队，R出队，不入队，因为被禁止了
最后看q1，q2谁先为空，说明当前阵营都被禁止掉了，对方阵营胜利。
时间复杂度：
// 数组模拟队列，hh队头，tt队尾，若不熟练请使用STL queue 实现
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int q1[2*N], q2[2*N], hh1=0, tt1=-1, hh2=0, tt2=-1;
int main()
{
int t; cin >> t;
while (t--)
{
string s;
cin >> s;
int n = s.size();
hh1=0, tt1=-1, hh2=0, tt2=-1;
for (int i = 0; i < n; i++)
{
if (s[i] == 'R') q1[++tt1] = i; // R 下标
else q2[++tt2] = i; // D 下标
}
while (hh1<=tt1 && hh2 <= tt2)
{
if (q1[hh1] < q2[hh2]) // R投，投完重新入队等待下一轮
q1[++tt1] = q1[hh1]+n;
else // D 投，投完重新入队等待下一轮
q2[++tt2] = q2[hh2]+n;
hh1++, hh2++; // 没投的那一方直接出队，等同于罢免权力
}
if (hh1 > tt1) cout << "Dire\n"; // q1先为空，D胜利
else cout << "Radiant\n"; // 否则R胜利
}
}
小田的01背包
思路：按位与运算只会越与越小，最好情况也是保持不变，假设我们要得到的价值是 x，则应该把所有w[i] == x的物品全选上，然后求选上之后的体积t，看是否满足k的限制。
由此得到了从大到小枚举价值，验证体积是否合法的思路。
时间复杂度：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n, k, v[N], w[N];
int main()
{
cin >> n >> k;
for (int i=1; i<=n; i++) cin >> v[i] >> w[i];
for (int res=4e4; res>=0; res--) // 由大到小枚举价值
{
int t = 0x7fffffff; // 0111...11111，位掩码的常用值，关于位掩码相关知识，自己查OIwiki
for (int i=1; i<=n; i++)
{
if ((w[i]&res) == res) // 选上所有"与"完后价值不变的物品
t &= v[i]; // 体积也 &
}
if (t <= k) // 若体积满足条件，输出res即为最大价值
{
cout << res;
return 0;
}
}
return 0;
}
互关
/*
很容易想到f[a][b] = 1 表示a关注了b
但是a和b范围1e9，没办法开这么大数组，回想学过的数据结构，显然这是一种映射关系
容易想到map哈希表，map[a] = b 似乎可行，但是a可以关注b，c，d...多个用户，所以
直接定义map<int,int>无法满足一对多的映射关系，要放弃了吗？没有其他办法了吗？
NO！不能在这里放弃，应该还有其它办法！如果定义哈希表为：
map<int, map<int,int>> 呢？没错，再套一层就可以了！
mp[a][b] = 1 表示a关注b，完美！
使用unordered_map，时间复杂度为O(Q)，看看空间是否够用：
Q最多2e5，也就是说map里面最多2e5个键值对，完全ok。
拓展：其它解法思路参考
N的范围很大，但是数据量实际只有2e5，可以考虑对所有用户Ai，Bi进行离散化处理，然后建立
邻接表来存储映射关系，假设Ai，Bi离散化后的值为ai，bi，H为表头数组，则H[ai]的链表中存在bi，说明
ai关注了bi。
*/
#include<bits/stdc++.h>
#define IO(name) freopen(name ".in","r",stdin),freopen(name ".out","w",stdout)
using namespace std;
unordered_map<int, unordered_map<int, bool>> follow; // follow v. 关注，跟随
void solve()
{
int t, a, b;
cin >> t >> a >> b;
if (t == 1) follow[a][b] = 1;
else if (t == 2) follow[a][b] = 0;
else
{
if (follow[a][b] && follow[b][a])
cout << "Yes\n";
else
cout << "No\n";
}
}
int main()
{
int n, q;
cin >> n >> q;
while (q--) solve();
return 0;
}
【离散化+邻接表版本】
此代码仅供对离散化和邻接表（链式前向星）的复习，实际在极端数据下（自己思考怎样的极端数据，可以在题目讨论中说明或者私聊我）是会超时的，本题也只能得部分分，若要按离散化思路拿满分，还要对链表进行排序，在查找和删除时使用二分进行定位，才可AC，纯数组去实现过于复杂，可以用set代替数组模拟的单链表。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10; // 离散化后节点数
const int M = 4e5 + 10; // 边数
int h[N], e[M], ne[M], idx;
int T[M], A[M], B[M];
vector<int> alls; // 待离散化数据Ai Bi
// 插入一条有向边 u -> v
void add(int u, int v)
{
e[idx] = v;
ne[idx] = h[u];
h[u] = idx++;
}
// 查找 u 是否关注 v
bool find_edge(int u, int v)
{
for(int i = h[u]; i != -1; i = ne[i])
if(e[i] == v) return true;
return false;
}
// 删除 u 对 v 的关注
void erase_edge(int u, int v)
{
int prev = -1;
for(int i = h[u]; i != -1; i = ne[i])
{
if(e[i] == v)
{
if(prev == -1) h[u] = ne[i];
else ne[prev] = ne[i];
return;
}
prev = i;
}
}
// 离散化查找编号（1-based）
int find(int x)
{
int l = 0, r = alls.size() - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for(int i=0; i<q; i++)
{
cin >> T[i] >> A[i] >> B[i];
alls.push_back(A[i]);
alls.push_back(B[i]);
}
// 离散化
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 初始化邻接表
memset(h, -1, sizeof h);
for(int i=0; i<q; i++)
{
int u = find(A[i]);
int v = find(B[i]);
if(T[i] == 1 && !find_edge(u, v)) add(u, v); // u->v
else if(T[i] == 2) erase_edge(u,v); // u取消关注v
else // T[i] == 3 查询互关
{
if(find_edge(u,v) && find_edge(v,u))
cout << "Yes\n";
else
cout << "No\n";
}
}
return 0;
}
全体赋值与单点加法
/*
给定一共长度为n的序列A，一共3种操作：
1 x，将序列所有元素改为x
2 i x，A[i] += x
3 i，输出 A[i]
操作2和3都是O(1)时间复杂度，但如果直接模拟操作1，时间复杂度将为O(n)
Q个查询，时间复杂度就是O(nQ)，铁超时，难道又要放弃了吗？肯定还有其它办法，
如何优化操作1呢？想不到了，要放弃了，真要放弃了吗？不能在这里放弃，再想一想！
bingo！操作1把所有元素改为x，没必要去真的改，直接用一个全局变量base维护，
再记录当前进行操作1的时间戳upd，以及每个a[i]更新的时间戳last_upd[i]就可以了。
更新逻辑如下：
初始化base = -1，表示还没有进行操作1全局赋值。
若 opt == 1，更新base = x，同时upd ++
若 opt == 2，检查base，若 base != -1 && last_upd[i] < upd，需要使用upd来更新 a[i]，并更新last_upd[i] = upd
否则直接 a[i] += x;
若 opt == 3，检查base，若 base != -1 && last_upd[i] < upd，需要输出upd，否则输出a[i]。
q组询问，每个操作都是O(1)，总时间复杂度：O(q)
注意：数据范围1e9，操作2有加法，q是2e5，最大和为2e14！
*/
#include<bits/stdc++.h>
#define IO(name) freopen(name ".in","r",stdin),freopen(name ".out","w",stdout)
using namespace std;
const int N = 2e5 + 10;
long long a[N];
int upd, last_upd[N]; // upd表示进行操作1的时间，last_upd[i]表示a[i]上一次更新的时间
int main()
{
int n, q, base = -1;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
while (q--)
{
int opt, i, x;
cin >> opt;
if (opt == 1)
{
cin >> x;
base = x;
upd ++;
}
else if (opt == 2)
{
cin >> i >> x;
if (base != -1 && last_upd[i] < upd)
a[i] = base + x, last_upd[i] = upd;
else
a[i] += x;
}
else
{
cin >> i;
if (base != -1 && last_upd[i] < upd)
cout << base << endl;
else
cout << a[i] << endl;
}
}
return 0;
}
删除多余括号
本题考查中缀表达式建树，与求中缀表达式的值类似，建好表达式树后进行dfs中序遍历，并比较左右子树和根的运算符优先级，判断是否需要添加括号，可以将多余括号进行删除。
添加括号的逻辑详见代码内部注释与图例。
后缀表达式建树之前讲过，可以点这里查看。
表达式树的建立与dfs搜索遍历是一项十分必要熟练掌握的基本功，对于搜索的理解和代码能力的提升有莫大的帮助，请同学们务必好好研究消化，而不是Ctrl + C/V 草草了之，即使下面的代码花上3天甚至一周去掌握也是值得的！
#include <bits/stdc++.h>
using namespace std;
char opt[300]; // 节点运算符
string val[300]; // 叶子节点值
int idx = 0; // 节点编号
stack<int> num; // 数字栈
stack<char> op_num; // 运算符栈
vector<int> tree[300]; // 邻接表存子节点
bool isleaf[300]; // 是否叶子节点
map<char,int> pr={{'+',1},{'-',1},{'*',2},{'/',2},{'(',0}}; // 运算符优先级
void eval()
{
char op_char = op_num.top(); op_num.pop(); // 弹出符号
int b = num.top(); num.pop(); // 弹出两个运算数的节点编号
int a = num.top(); num.pop();
int id = ++idx; // 以当前运算符作为根，a，b作为左右子树建树，id就是这个子树的节点
opt[id] = op_char;
isleaf[id] = false;
tree[id].push_back(a);
tree[id].push_back(b);
num.push(id); // 将这颗子树的节点编号重新入栈
}
// DFS 进行中序遍历扫描表达式树
string dfs(int u) {
if (isleaf[u]) return val[u]; // 叶子节点
int l = tree[u][0], r = tree[u][1];
string L = dfs(l), R = dfs(r); // L + opt[u] + R 为整个中缀表达式
/*
树长这样：
opt[u]
/ \
L = dfs(l) <-- l r --> R = dfs(r)
*/
// 左子树加括号条件：若左子树运算符优先级 < opt[u]，需要加括号
if (!isleaf[l] && pr[opt[l]] < pr[opt[u]]) L = "(" + L + ")";
/*
右子树加括号条件：1.优先级 < opt[u] 2.优先级相等，对于 '-' 和 '/' 遵循从左到右运算的结合性，也要加括号
举例： b-(a+c)，表达式树如下：
-
/ \
b +
/ \
a c
当opt[u] = '+' 时，dfs遍历左子树 L = b，右子树 R = a - c
此时 opt[u] = '-'，r 的优先级和 u 相同，但是右子树a+c应该先算，需要加上括号
*/
if (!isleaf[r])
{
if (pr[opt[r]] < pr[opt[u]]) R = "(" + R + ")";
else if (pr[opt[r]] == pr[opt[u]])
{
if (opt[u] == '-' || opt[u] == '/')
R = "(" + R + ")";
}
}
return L + opt[u] + R;
}
int main() {
string s;
getline(cin, s);
for(int i = 0; i < s.size(); i++) {
char ch = s[i];
if(ch >= 'a' && ch <= 'z') // 操作数
{
int id = ++idx;
val[id] = ch;
isleaf[id] = true;
num.push(id);
}
else if(ch == '(') op_num.push(ch);
else if(ch == ')')
{
while(!op_num.empty() && op_num.top() != '(') eval();
op_num.pop(); // 弹掉 '('
}
else // 运算符
{
while(!op_num.empty() && pr[op_num.top()] >= pr[ch]) eval();
op_num.push(ch);
}
}
while(!op_num.empty()) eval();
int root = num.top(); // 此时num栈顶即为表达式树根节点编号
cout << dfs(root) << endl;
return 0;
}
章节3
取走ABC
思路：直接遍历s查询子串并用erase进行删除时间复杂度太高，erase删除末尾 元素的时间复杂度是O(1)，所以将t对s进行逐个拼接和判定删除，时间复杂度O(N).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
string s, t;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
t += s[i];
if (t.size() >= 3 && t.substr(t.size()-3)=="ABC")
t.erase(t.size()-3);
}
cout << t;
return 0;
}
热水器
题意：给定若干个Si，Ti，在[Si, Ti) 区间加上Pi，最后统计整个区间[1,2e5]是否有超过W的值。
思路：很容易想到计数数组进行模拟，但是N个人，每个人区间长度最大2e5，时间复杂度O(n^2). 容易想到，上述问题其实是对区间进行快速修改的优化，符合差分的思想（前缀和的逆运算）。
差分的复习：http://www.turing-code.com/discuss/657b201777ed835db0da9735#1702567959391
【参考代码】
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
ll a[N], b[N]; // a是b的前缀和，b是a的差分
int main()
{
ll n, w;
cin >> n >> w;
for (int i = 1; i <= n; i++)
{
int s, t, p;
cin >> s >> t >> p;
b[s+1] += p; // s和t的范围是0~2e5,往右偏移1位方便求前缀和
b[t+1] -= p;
}
bool f = 1;
for (int i = 1; i <= N; i++)
{
a[i] = a[i-1] + b[i]; // 求b的前缀和a
if (a[i] > w)
{
f = 0;
break;
}
}
if (f) cout << "Yes";
else cout << "No";
return 0;
}
章节4
平均路径长度
全排列模板题
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool vis[10];
int ax[10], ay[10];
int ans[10], n;
double tot;
double getdis(double a, double b, double c, double d)
{
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int f(int n)
{
int p = 1;
for (int i = 1; i <= n; i++)
p *= i;
return p;
}
// 1 3 4 5 2
void dfs(int u)
{
if (u > n)
{
double res = 0;
for (int j = 1; j < n; j++)
{
int i = ans[j], k = ans[j+1];
int tx1 = ax[i], ty1 = ay[i];
int tx2 = ax[k], ty2 = ay[k];
res += getdis(tx1,ty1,tx2,ty2);
}
// res中计算出来了一条有效路径的总长
tot += res;
}
for (int i = 1; i <= n; i++)
{
if (vis[i]) continue;
ans[u] = i;
vis[i] = 1;
dfs(u + 1);
vis[i] = 0;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> ax[i] >> ay[i];
}
dfs(1);
cout << fixed << setprecision(6) << tot*1.0/f(n);
return 0;
}
章节5
传送装置
模拟即可，注意k很大的时候，需要找到循环节，用取模优化。
堆积如山的书
思路：前缀和+双指针，dp状态数太多存不下，但是可以提供思路，从暴力角度想的话，枚举A的前 i本与B的前j本，求最大的i+j，使得A1~Ai + B1~Bj <= k。区间和可以用前缀和优化，由于都是阅读时间都是 正整数，所以前缀和具备单调性，可以利用双指针或者二分进行求解满足条件的最大i+j。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int A[N], B[N];
int main(){
int n, m;
long long k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) cin >> A[i], A[i] += A[i-1];
for(int i = 1; i <= m; i++) cin >> B[i], B[i] += B[i-1];
int j = m;
long long ans = 0;
// 先把 B 取到最大
while (j > 0 && B[j] > k) j--;
ans = j;
// 枚举 A 取多少
for(int i = 1; i <= n; i++){
if (A[i] > k) break;
// 调整 B 的数量
while (j >= 0 && A[i] + B[j] > k) j--;
ans = max(ans, (long long)i + j);
}
cout << ans << "\n";
}
最小化绝对值1
思路，要使得 |ai - xi| 尽可能小，而xi ∈ [l, r], 只需要讨论ai和区间 [l,r]的关系即可：
（1）ai < l，xi取l （2）ai > r，xi取r （3）ai在[l,r]范围内，xi取ai可得0
最小化绝对值2
思路：要求|x^2 + y^2 - D| 的最小值，先从暴力想：枚举x和y的值，更新最小的ans，但是D很大，x和y枚举范围 太广，会超时。此时可以转换思路，只枚举x，因为x^2 和 y^2 都是正数，D也是正数，所以满足条件的x和y一定小于根号D， 即x的枚举范围缩小到1~sqrt(D)，y = sqrt(D - x^2)，ans = min({ans, y, y+1}。y和y+1分别对应上下取整最接近的整数，因为 y求出来是浮点数。
大于我的数之和
模拟即可