转盘锁
可以把序列看出一个个元素, + 1, - 1 看成转移, 这就成了一个 bfs
还可以发现, \(a_0, a_1, a_2, a_3 \to b_0, b_1, b_2, b_3 = 0, 0, 0, 0 \to b_0 - a_0, b_1 - a_1, b_2 - a_2, b_3 - a_3\)
状态数只有 \(10^4\)
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int>dist;
unordered_map<string, bool>vis;
queue<string>q;
string t, s;
int a[10], b[10], T;
char c;
void C(string t, int x){
for(auto &c : t){
if(c < '0'){
c += 10;
}
if(c > '9'){
c -= 10;
}
}
if(vis[t]){
return;
}
vis[t] = 1;
dist[t] = x;
q.push(t);
}
void bfs(){
C("0000", 0);
while(q.size()){
s = q.front();
q.pop();
for(int l = 0; l < 4; ++l){
t = s;
for(int r = l; r < 4; ++r){
t[r]--;
C(t, dist[s] + 1);
}
t = s;
for(int r = l; r < 4; ++r){
t[r]++;
C(t, dist[s] + 1);
}
}
}
}
void S(){
for(int i = 1; i <= 4; i++){
cin >> c;
a[i] = c - '0';
}
s = "";
for(int i = 1; i <= 4; ++i){
cin >> c;
b[i] = c - '0';
s += char((b[i] - a[i] + 10) % 10 + '0');
}
cout << dist[s] << '\n';
}
int main(){
freopen("lock.in", "r", stdin);
freopen("lock.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
bfs();
for(cin >> T; T--; S()){
}
return 0;
}
时间复杂度 \(O(10^4 \cdot !4 \cdot 4 + 4T)\)
空间复杂度 \(O(10^4 \cdot !4 \cdot 4)\)
多姿多彩
对于每一个 \(i\), 所有的字符都会和其它匹配。
所以只需要统计所有字符出现次数 \(cnt_i\), 每个字符代价为 \(cnt_i \dots (n - cnt_i)\)
#include<bits/stdc++.h>
using namespace std;
long long ans;
int n, cnt[30];
char c;
int main(){
freopen("diverse.in", "r", stdin);
freopen("diverse.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> c;
cnt[c - 'a']++;
}
for(int i = 0; i < 26; ++i){
ans += 1ll * cnt[i] * (n - cnt[i]);
}
cout << ans * n;
return 0;
}
时间复杂度 \(O(n)\)
空间复杂度 \(O(26)\)
黑白树
树形 DP
状态 \((i, j, sum)\) 表示在 \(i\) 的子树内做 \(\bmod 2 = j\) 次操作的黑节点最大值为 \(sum\)
合并子树
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, c[N], dp[N][4], u, v, f[4];
vector<int>g[N];
void dfs(int x, int fa){
if(!(g[x].size() - (x != 1))){
dp[x][1] = !c[x];
dp[x][0] = c[x];
}
else{
dp[x][0] = -1e9;
dp[x][1] = -1e9;
}
for(auto v : g[x]){
if(v != fa){
dfs(v, x);
f[0] = dp[v][0], f[1] = dp[v][1];
for(int i = 0; i <= 1; ++i){
for(int j = 0; j <= 1; ++j){
f[i ^ j] = max(f[i ^ j], dp[x][i] + dp[v][j]);
}
}
dp[x][0] = f[0], dp[x][1] = f[1];
}
}
if((g[x].size() - (x != 1))){
dp[x][0] += c[x], dp[x][1] += !c[x];
}
}
int main(){
freopen("mono.in", "r", stdin);
freopen("mono.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> c[i];
}
for(int i = 1; i < n; ++i){
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << max(dp[1][1], dp[1][0]);
return 0;
}
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
苟延残喘
一开始极差为 \(a_n - a_1\)
第二次极差最大为 \(a_n - a_1\)
\(\dots\)
所以极差 \(\le 10^9\)
若最小值 \(\ge 10^9 + 7\), 整体减 \(10^9 + 7\), 即能保值不爆 long long, 又等价于取模, 还是对的。
#include<bits/stdc++.h>
using namespace std;
const int N = 3005, mod = 1e9 + 7;
struct Node{
long long x;
int i, j;
};
struct cmp{
bool operator()(const Node &i, const Node &j){
return i.x > j.x;
}
};
priority_queue<Node, vector<Node>, cmp>pq;
int n, sum, flag;
long long a[N], b[N], minx;
int main(){
freopen("weak.in", "r", stdin);
freopen("weak.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
for(int i = n; i > 1; --i){
for(; pq.size(); pq.pop()){
}
for(int k = 1; k < n; ++k){
pq.push({a[k] + a[k + 1], k, k + 1});
}
minx = 1e9;
for(int k = 1; k < n; ++k){
auto [sum, id, j] = pq.top();
pq.pop();
b[k] = sum;
if(j != n){
j++;
pq.push({a[id] + a[j], id, j});
}
minx = min(minx, b[k] / mod);
}
n--;
for(int k = 1; k <= n; ++k){
a[k] = b[k] - minx * mod;
}
}
cout << a[n];
return 0;
}
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)