pts:105
T1: 100
T2: 5
T3: 0
T1
[NOIP2018 提高组] 旅行
贪心，搜索，DFS
solution
subtask1 60'
(m = n - 1) emm，没错，是一棵树，因为树上没有反悔的机会，所以直接随便选一个树根，每次贪心选择与它相邻的标号最小的没有走过的点，走完一遍就是答案哇
感觉用 (vector) 存图排序比较方便 /cy
code
namespace subtask1{//暴力跑
int vis[MAXN], Ans[MAXN], tot;
void dfs(int u, int fa) {
if(vis[u]) return ;
Ans[++tot] = u;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if(v == fa) continue;
dfs(v, u);
}
}
int main(){
for (int i = 1; i <= n; i++)sort(a[i].begin(), a[i].end());//贪心选最小的
dfs(1, 0);
for(int i = 1; i <= n; i++) printf("%lld ", Ans[i]);
}
}
subtask2 m = n
-
solution 1 ( (n^2))：
基环树，那就枚举断开哪一条边呗，然后跑一遍看是否答案更优就好了
怎么删边？？
直接枚举这条边，记录出这条边的两个端点，跑路的时候保证不连续走过这两个点就好啦 (if((u == from~{&&}~v == to) || (v == from~{&&}~u == to)) continue;)
code
int vis[MAXN], Ans[MAXN], tot, tmp[MAXN];
void dfs(int u, int fa) {
if(vis[u]) return; vis[u] = 1;
tmp[++tot] = u;
for(int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if(v == fa) continue;
if((u == from && v == to) || (v == from && u == to)) continue;
dfs(v, u);
}
}
bool check(){
for(int i = 1; i <= n; i++) {
if(tmp[i] == Ans[i]) continue;
return tmp[i] > Ans[i] ? 0 : 1;
}
}
void clear(){memset(vis, 0, sizeof vis);tot = 0;}
void update(){memcpy(Ans, tmp, sizeof Ans);}
int main() {
for (int i = 1; i <= n; i++) sort(a[i].begin(), a[i].end());
for (int i = 1; i <= cnt; i += 2) {
from = e[i].u, to = e[i].v;
clear(), dfs(1, 0);
if(tot < n) continue;
if(!Ans[n]) update();
else if(check()) update();
}
for (int i = 1; i <= n; i++) printf("%lld ", Ans[i]);
}
- solution2
参考题解：The_World_exe
首先一个环可以分成两部分，先走到一个点，然后再回溯，走剩下的部分
(tarjan) 判环，找出在环上的点，以及环的起始节点；
-
对于不在环上的点，直接按照树走就好了
-
对于在环上的点
只有环上的点有反悔的机会 emm
(start) 为环的开端
对 (start) 连的环上的两个点，第二小的标为 mn，然后走最小的
回溯的条件：
-
当 (dfs) 到环上的一个点的时候，
-
(i+1=e[x].size())，即当前出边 (i) 是 (x) 点的最后一条有效边（(tot) 是与 (x) 直接相连的编号最大的点）（若当前出边 (i) 是 (x) 点的倒数第二条出边，但最后一条出边指向的是上一个访问的节点满足该条件）
-
(mn < v) ，即之前找到的 (mn) 的编号比 (tot) 的字典序小
-
(already=0) ，即之前从未回溯过
如果已经回溯过了直接继续走就好哩（环上只有一次回溯机会）
走到一个点，如果有支链，并且这条支链没有走过，那么回溯标记一定打在这条支链上，但选择的支链权值尽可能小
code
/*
work by:Ariel_
tmiao 又是贪心 = =
cao, vector 不会用，挨着把函数试了个遍 qwq
8:00 写过了树，环的跑不出来？
n^2 暴力的断环跑一遍？？？
9:15 过了大样例 wc （感觉会 T /kk）
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 5000 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m, from, to;
struct edge{int u, v, nxt;}e[MAXN << 1];
int head[MAXN], cnt;
void add_edge(int u, int v){
e[++cnt] = (edge){u, v, head[u]};
head[u] = cnt;
}
vector <int> a[MAXN];
namespace subtask1{//暴力跑
int vis[MAXN], Ans[MAXN], tot;
void dfs(int u, int fa) {
if(vis[u]) return ;
Ans[++tot] = u;
for (int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if(v == fa) continue;
dfs(v, u);
}
}
int main(){
for (int i = 1; i <= n; i++)sort(a[i].begin(), a[i].end());//贪心选最小的
dfs(1, 0);
for(int i = 1; i <= n; i++) printf("%lld ", Ans[i]);
}
}
namespace subtask2{//断环为树，emm
int vis[MAXN], Ans[MAXN], tot, tmp[MAXN];
void dfs(int u, int fa) {
if(vis[u]) return; vis[u] = 1;
tmp[++tot] = u;
for(int i = 0; i < a[u].size(); i++) {
int v = a[u][i];
if(v == fa) continue;
if((u == from && v == to) || (v == from && u == to)) continue;
dfs(v, u);
}
}
bool check(){
for(int i = 1; i <= n; i++) {
if(tmp[i] == Ans[i]) continue;
return tmp[i] > Ans[i] ? 0 : 1;
}
}
void clear(){memset(vis, 0, sizeof vis);tot = 0;}
void update(){memcpy(Ans, tmp, sizeof Ans);}
int main() {
for (int i = 1; i <= n; i++) sort(a[i].begin(), a[i].end());
for (int i = 1; i <= cnt; i += 2) {
from = e[i].u, to = e[i].v;
clear(), dfs(1, 0);
if(tot < n) continue;
if(!Ans[n]) update();
else if(check()) update();
//for(int i = 1; i <= n; i++) cout<<Ans[i]<<" ";
//puts(" ");
}
for (int i = 1; i <= n; i++) printf("%lld ", Ans[i]);
}
}
namespace subtask3{
int dfn[MAXN], low[MAXN], tot, opt, start, fag[MAXN], vis[MAXN], already, id, mn;
stack<int> s;
void tarjan(int x, int fa) {
dfn[x] = low[x] = ++tot;
s.push(x);
vis[x] = 1;
for (int i = 0; i < a[x].size(); i++) {
int v = a[x][i];
if(v == fa) continue;
if (vis[v] == 1) {
low[x] = min(low[x], dfn[v]);
opt = 1;
start = v;
}
else{
tarjan(v, x);
low[x] = min(low[x], low[v]);
}
if(opt == 1) return;
}
if(dfn[x] == low[x]) s.pop(), vis[x] = 0;
}
void get_fag() {
int x;
while(x != start && s.empty() != 1) {
x = s.top(), s.pop(), fag[x] = 1;
}
fag[start] = 1;
}
void dfs(int x, int fa) {
printf("%d ", x);
vis[x] = 1;
if(fag[x] == 0 || already == 1) {
for(int i = 0; i < a[x].size(); i++) {
int v = a[x][i];
if(!vis[v]) dfs(v, x);
}
}
else if(fag[x] == 1){//找环中第二大的点
if(x == start){
for(int i = 0; i < a[x].size(); i++) {
int v = a[x][i];
if(vis[v]) continue;
if(fag[v] == 1) {
id = v, mn = a[x][i + 1];
break;
}
}
}
for (int i = 0; i < a[x].size(); i++) {
int v = a[x][i];
if(vis[v])continue;
if(!already && mn < v && fag[v] == 1 &&(i + 1 == a[x].size() || (i + 2 == a[x].size() && a[x][i + 1] == fa))){//该反悔了
already = 1;
dfs(mn, x);
}
else if(already == 1) dfs(v, x);//已经回溯过了就不用了
else if(fag[v] == 1) {
int tmp = i + 1;
while(vis[a[x][tmp]] == 1)tmp++;
if(a[x][tmp] != 0) mn = a[x][tmp];
dfs(v, x);
}
else dfs(v, x);
}
}
}
int main(){
for(int i = 1; i <= n; i++) sort(a[i].begin(), a[i].end());
tarjan(1, 0);
get_fag();
memset(vis, 0, sizeof vis);
dfs(1, 1);
}
}
signed main(){
//freopen("travel.in", "r", stdin);
//freopen("travel.out", "w", stdout);
n = read(), m = read();
for (int i = 1, u, v; i <= m; i++) {
u = read(), v = read();
add_edge(u, v), add_edge(v, u);
a[u].push_back(v), a[v].push_back(u);
}
if(m == n - 1)subtask1::main();
//else if(m == n)subtask2::main();
else if(m == n) subtask3::main();
puts("");
return 0;
}
/*
树
6 5
1 3
2 3
2 5
3 4
4 6
1 3 2 5 4 6
基环树
6 6
1 3
2 3
2 5
3 4
4 5
4 6
1 3 2 4 5 6
*/
T2
[NOIP2018 提高组] 填数游戏
dp，数论， 打表？！
输出样例 15 分 /kk
solution
subtask 1
枚举所有的情况，同时路径判断
时间复杂度: (O(2^{mn}*C_{n + m}^{n}))
subtask 2
(f_{x,y}(max, min)) 表示以 ((x,y)) 为起点，到达终点的最大值和最小值
如果一个点向右走的最小值小于向下走的最大值，不合法，这个点就不能经过了
每次枚举完一行就判断一次，不行就不枚举了
肯定会T，那就大表找规律 ！！ = =
规律
-
当 (m>n+1) 且 (n>1) 时, (ans_{n,m}=ans_{n,m-1} * 3)
-
当 (n=1) 时, (ans_{n,m}=2^m)
-
当 (m>3) 时, (ans_{n,n+1}=ans_{n,n}*3− 3 ∗ 2^n)
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include<cmath>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m;
int a[10][10]={
{0,0,0,0,0,0,0},
{0,2,4},
{0,0,12,36},
{0,0,0,112,336},
{0,0,0,0,912,2688},
{0,0,0,0,0,7136,21312},
{0,0,0,0,0,0,56768,170112},
{0,0,0,0,0,0,0,453504,1360128},
{0,0,0,0,0,0,0,0,3626752,10879488}
};
int qpow(int a, int b) {
int ans = 1;
while(b) {if(b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}
return ans;
}
signed main(){
n = read(), m = read();
if(n < m) swap(n, m);
if(n == 1) printf("%lld
",qpow(2,m));
else{
if (n == m||n + 1 == m){
printf("%d
", a[n][m]);
}
else{
printf("%lld
",a[n][n + 1] * qpow(3,m - n - 1) % mod);
}
}
}
T3
[NOIP2018 提高组] 保卫王国
dp，倍增，树链剖分
solution
状态：
T 表示整棵树
(dp[i][0/1]) 表示以 (i) 为根的子树，(i) 点选或者不选的最小代价
(g[i][0/1]) 表示 ( (T) - 以 (i) 为根的子树)，(i) 选或者不选的最小代价
(dp) 数组应该会树形 (dp) 滴都会吧 = =
关于 (g) 数组
转移式
(g[v][0] = g[x][1] + f[x][1] - min(f[v][0], f[v][1]))
(g[v][1] = min(g[x][0] + f[x][0] - f[v][1],~~g[v][0]))
假设现在 (x) 为 2 号点，(v) 为 3 号点
(g[v][0]) 显然就是 1，2，4，5 所在的子树
同时因为 3 不选所以 2 必须选，所以就有了 $g[x][1] + f[x][1] - min(f[v][0], f[v][1]) $
把后两项看成一起，也就是让 (f[x][1]) 减去由 (v) 转移过来的贡献，这样就做到了不考虑 (v) 为根的子树
(g[v][1]) 时，2 选不选就都可以了，可以直接等于上面 2 选的情况，也可以不选
(g[v][1] = min(g[x][0] + f[x][0] - f[v][1],~~g[v][0]))
(f[i][j][0/1][0/1]) 表示 (i) 选(不选) ， (2^j) 选(不选)的，节点 (i) 到节点 (2^j) 路径上的最小花费
注意：路径上的最小花费包括它的支链的花费
可以理解为以 (i) 的 (2^j) 为根的子树的最小花费减去以 (i) 为根的子树的最小花费
关于 (f) 数组的转移
因为它的状态是连续的，所以考虑倍增优化转移
首先对 (f) 初始化 = =
for(int i = 1; i <= n; i++) {
f[i][0][0][0] = INF;
f[i][0][0][1] = dp[fa[i][0]][1] - min(dp[i][0], dp[i][1]);
f[i][0][1][1] = dp[fa[i][0]][1] - min(dp[i][0], dp[i][1]);
f[i][0][1][0] = dp[fa[i][0]][0] - dp[i][1];
}
然后直接倍增枚举点的状态转移就好了
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= n; i++) {
for (int u = 0; u <= 1; u++) {
for (int v = 0; v <= 1; v++) {
f[i][j][u][v] = INF;
for (int w = 0; w <= 1; w++)
f[i][j][u][v] = min(f[i][j][u][v], f[i][j - 1][u][w] + f[fa[i][j - 1]][j - 1][w][v]);
}
}
}
}
弄这些状态有啥用捏 ？
如果我们不考虑特殊要求的话，就是“没有上司的舞会”
因为限制，所以有些状态就不成立了，所以就把禁止选的 (dp) 数组都改为 (INF) (建议开大点= =)，其余的没有影响
- 如果 (a) 是 (b) 的父亲的话
直接让 (b) 向上跳，和合并 (f) 数组一样转移
- 否则的话就让 (a, b) 同时跳到它们 (LCA) 的儿子那儿，枚举这两个儿子选还是不选进行转移
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int INF = 42949672900;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m, val[N];
struct edge{int v, nxt;}e[N << 1];
int cnt, head[N];
void add_edge(int u, int v) {
e[++cnt] = (edge){v, head[u]};
head[u] = cnt;
}
int dep[N], fa[N][30];
int g[N][2];
int f[N][30][2][2];
int dp[N][2];
void dfs(int x, int f) { //处理 dp 数组
fa[x][0] = f, dep[x] = dep[f] + 1;
dp[x][1] = val[x];
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v == f) continue;
dfs(v, x);
dp[x][0] += dp[v][1], dp[x][1] += min(dp[v][1], dp[v][0]);
}
}
void dfs2(int x) {
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v == fa[x][0]) continue;
g[v][0] = g[x][1] + dp[x][1] - min(dp[v][1], dp[v][0]);
g[v][1] = min(g[v][0], g[x][0] + dp[x][0] - dp[v][1]);
dfs2(v);
}
}
int solve(int a,int x,int b,int y){
if(dep[a] > dep[b]) swap(a, b), swap(x, y);
int ta[2] = {INF, INF}, tb[2] = {INF, INF};
int na[2], nb[2];
ta[x] = dp[a][x], tb[y] = dp[b][y];
for (int i = 20; i >= 0; i--) {
if(dep[fa[b][i]] >= dep[a]) {
nb[0] = INF, nb[1] = INF;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 1; k++) {
nb[j] = min(nb[j], tb[k] + f[b][i][k][j]);
}
}
tb[0] = nb[0], tb[1] = nb[1], b = fa[b][i];
}
}
if(a == b) return tb[x] + g[b][x];
for (int i = 20; i >= 0; i--) {
if(fa[a][i] != fa[b][i]){
na[0] = na[1] = INF;
nb[0] = nb[1] = INF;
for (int j = 0; j <= 1; j++) {
for(int k = 0; k <= 1; k++) {
nb[j] = min(nb[j], tb[k] + f[b][i][k][j]);
na[j] = min(na[j], ta[k] + f[a][i][k][j]);
}
}
ta[1] = na[1], ta[0] = na[0];
tb[1] = nb[1], tb[0] = nb[0];
a = fa[a][i], b = fa[b][i];
}
}
int lca = fa[a][0];
int now1 = dp[lca][0] - dp[a][1] - dp[b][1] + ta[1] + tb[1] + g[lca][0];
int now2 = dp[lca][1] - min(dp[a][1], dp[a][0]) - min(dp[b][0], dp[b][1]) + min(ta[0], ta[1]) + min(tb[0], tb[1]) + g[lca][1];
return min(now1, now2);
}
char s[10];
signed main(){
//freopen("defense.in", "r", stdin);
//freopen("defense.out", "w", stdout);
n = read(), m = read();
cin>>s;
for (int i = 1; i <= n; i++) val[i] = read();
for (int i = 1, u, v; i < n; i++) {
u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
dfs(1, 0);
for (int j = 1; j <= 20; j++)
for(int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
dfs2(1);
for(int i = 1; i <= n; i++) {
f[i][0][0][0] = INF;
f[i][0][0][1] = dp[fa[i][0]][1] - min(dp[i][0], dp[i][1]);
f[i][0][1][1] = dp[fa[i][0]][1] - min(dp[i][0], dp[i][1]);
f[i][0][1][0] = dp[fa[i][0]][0] - dp[i][1];
}
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= n; i++) {
for (int u = 0; u <= 1; u++) {
for (int v = 0; v <= 1; v++) {
f[i][j][u][v] = INF;
for (int w = 0; w <= 1; w++)
f[i][j][u][v] = min(f[i][j][u][v], f[i][j - 1][u][w] + f[fa[i][j - 1]][j - 1][w][v]);
}
}
}
}
for (int i = 1; i <= m; i++) {
int a = read(), x = read(), b = read(), y = read();
int ans = solve(a, x, b, y);
if(ans >= INF) printf("-1
");
else printf("%lld
", ans);
}
puts("");
return 0;
}