魔幻的题目
魔幻的我
按个人主观难度排序，原题见题单
[T2]
可做题随人心态改变而改变，在心态崩的时候任何题都是不可做题。
考虑把需要选的数放在 bfs序 上看，然后就会发现要选的数是一段。
当然这只是一个性质，我们真正需要的并不是这一点，而是：
任意的两段一定是要么包含，要么不交。
而对于包含关系，真正起作用的是内层，外层一点用都没有。
也就是：对于一个数的增减，它每次最多只会对 一段 要选的数起作用。
于是双指针维护，复杂度 O(m) + O(n log n) ，瓶颈在于双指针前的排序。
具体实现见代码：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 200005;
int n, m;
vector<int> G[N], pos[N];
vector<PII> rq[N];
int mark[N], id[N];
void dfs(int u, int d)
{
if (mark[d])
{
id[u] = mark[d];
pos[mark[d]].push_back(u);
}
for (auto i : rq[u])
{
pos[mark[i.first + d]].push_back(0);
mark[i.first + d] = i.second;
}
for (int j : G[u])dfs(j, d + 1);
for (auto i : rq[u])mark[i.first + d] = 0;
}
int main()
{
freopen("lirililarila.in", "r", stdin);
freopen("lirililarila.out", "w", stdout);
scanf("%d", &n);
for (int i = 2, p; i <= n; i ++)
{
scanf("%d", &p);
G[p].push_back(i);
}
scanf("%d", &m);
for (int i = 1; i <= m; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
rq[x].push_back({y, i});
}
dfs(1, 1);
int L = 1, R = n, r = 0;
for (int i = 1; i <= m; i ++)
{
sort(pos[i].begin(), pos[i].end());
reverse(pos[i].begin(), pos[i].end());
//for (auto j : pos[i])printf("%d ", j);
//puts("");
r = max(r, pos[i].back());
}
for (int l = 1; l <= n; l ++)
{
if (R - L + 1 > r - l + 1)
{
L = l;
R = r;
}
if(id[l] && pos[id[l]].back())
{
pos[id[l]].pop_back();
if (pos[id[l]].size())r = max(r, pos[id[l]].back());
else break;
}
}
printf("%d %d\n", L, R);
return 0;
}
[T4]
状压，但三进制。
怎么那么喜欢欧拉回路。
0 -> 不与 1 联通
1 -> 与 1 联通情况下度数为奇
2 -> 与 1 联通情况下度数为偶
转移由于会来来回回，因此用SPFA转移。
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 2000005, K = 10005, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int n, k, m, sum, st[M];
int d[N], dist[N][N];
vector<int> G[N];
int f[M], g[K], power[N];
void init()
{
memset(dist, 0x3f, sizeof dist);
power[0] = 1;
for (int i = 1; i <= n; i ++)
{
power[i] = power[i - 1] * 3;
dist[i][i] = 0;
}
}
void SPFA()
{
queue<int> q;
memset(f, 0x3f, sizeof f);
f[2] = 0;
st[2] = 1;
q.push(2);
while (q.size())
{
int S = q.front();
q.pop();
st[S] = 0;
for (int i = 0; i < n; i ++)
{
if ((S / power[i]) % 3)
{
for (auto j : G[i])
{
if (!((S / power[j]) % 3))
{
int T = S + power[j] * 2;
if (f[T] > f[S])
{
f[T] = f[S];
if (!st[T])
{
q.push(T);
st[T] = 1;
}
}
}
}
}
}
for (int i = 0; i < n; i ++)
{
if ((S / power[i]) % 3)
{
for (int j = 0; j < n; j ++)
{
if (!((S / power[j]) % 3))
{
int T = S + power[j];
if ((S / power[i]) % 3 == 1)T += power[i];
else T -= power[i];
if (f[T] > f[S] + dist[i][j])
{
f[T] = f[S] + dist[i][j];
if (!st[T])
{
q.push(T);
st[T] = 1;
}
}
}
}
}
}
}
}
void get()
{
memset(g, 0x3f, sizeof g);
g[0] = 0;
for (int S = 0; S < (1 << n); S ++)
{
for (int i = 0; i < n; i ++)
{
if (!(S >> i & 1))
{
for (int j = i + 1; j < n; j ++)
{
if (!(S >> j & 1))
{
int T = S + (1 << i) + (1 << j);
g[T] = min(g[T], g[S] + dist[i][j]);
}
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &k);
init();
for (int i = 0, a, b, c; i < k; i ++)
{
scanf("%d%d%d", &a, &b, &c);
a --, b --;
dist[a][b] = dist[b][a] = min(dist[a][b], c);
G[a].push_back(b);
G[b].push_back(a);
d[a] ++, d[b] ++, sum += c;
}
scanf("%d", &m);
for (int i = 0, a, b, c; i < m; i ++)
{
scanf("%d%d%d", &a, &b, &c);
a --, b --;
dist[a][b] = dist[b][a] = min(dist[a][b], c);
}
for (int k = 0; k < n; k ++)
{
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < n; j ++)dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
SPFA();
get();
int res = INF;
for (int S = 0; S < power[n]; S ++)
{
int flag = 1;
for (int i = 0; i < n; i ++)
{
if (G[i].size() && !((S / power[i]) % 3))
{
flag = 0;
break;
}
}
if (!flag)continue;
int fS = S;
for(int i = 0; i < n; i ++)
{
if (d[i] & 1)
{
if ((S / power[i]) % 3 == 1)fS += power[i];
else fS -= power[i];
}
}
int T = 0;
for(int i = 0; i < n; i ++)
{
if((fS / power[i]) % 3 == 1)T += (1 << i);
}
res = min(res, f[S] + g[T]);
}
printf("%d", res + sum);
return 0;
}
[T1]
啊我不知道应该是一个树形DP的东西但是来不及了，明天再补
[T3]
博弈论之后数论分块套数论分块（点头