T1
考场用时：\(40\) min
期望得分：\(100\) pts
实际得分：\(100\) pts
这题以前做过。
首先显然的一点是小 Y 行走的路径是一棵树，这题可以分两部分来做，首先对于每一个节点按照节点编号对于每一个终点升序排序。
然后对于 \(m=n-1\) 的部分是一棵树，直接 dfs 一遍即可，对于 \(m=n\) 的部分是一棵基环树，直接 dfs 找出这个环，然后枚举环上不走的那条边即可，复杂度 \(O(n^2)\) 可以接受。
#include<bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;
const int MAX=5e3+10;
const int MOD=998244353;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
vector<int> s[MAX];
int vis[MAX],fa[MAX],dfn[MAX],cnt,huan[MAX],tot,mn=1,res=1e9;
int cut1,cut2,ans[MAX],a[MAX],cnt2,n,m;
void dfs(int f,int k){
a[++cnt2]=k;
for(int v:s[k]){
if(v==f||((k==cut1&&v==cut2)||k==cut2&&v==cut1)) continue;
dfs(k,v);
}
return ;
}
void fid(int f,int k){
dfn[k]=++cnt;fa[k]=f;
for(int v:s[k]){
if(v==f) continue;
if(dfn[v]){
if(dfn[v]<dfn[k]) continue;
huan[++tot]=v;
for(;k!=v;v=fa[v])
huan[++tot]=fa[v];
// for(int i=1;i<=tot;i++) cout<<huan[i]<<" ";
return ;
}
fid(k,v);
}
return ;
}
bool check(){
for(int i=1;i<=n;i++){
if(a[i]<ans[i]) return true;
if(a[i]>ans[i]) return false;
}
return false;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) ans[i]=n-i+1;
for(int i=1;i<=m;i++){
int u=read(),v=read();
s[u].push_back(v);
s[v].push_back(u);
}
for(int i=1;i<=n;i++) sort(s[i].begin(),s[i].end());
if(m==n){
fid(0,1);
for(int i=1;i<tot;i++){
cut1=huan[i];
cut2=huan[i+1];
dfs(0,1);
if(check()) for(int j=1;j<=n;j++) ans[j]=a[j];
cnt2=0;
}
cut1=huan[tot],cut2=huan[1];
dfs(0,1);
if(check())
{
for(int i=1;i<=n;i++) ans[i]=a[i];
cnt2=0;
}
}
else{
dfs(0,1);
for(int i=1;i<=n;i++) ans[i]=a[i];
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
T2
考场用时：\(2。5\) h
期望得分：\(20\) pts
实际得分：\(20\) pts
这 \(2.5\) 小时其中有两个小时是本地挂暴力打表的，考场写了一个 \(O(2^{nm}C_{n+m}^n)\) 的大暴力，本地跑了两小时跑出了 \(6\times 6\) 的除 \((6,6)\) 以外的所有答案，得到了这20pts。
T3
考场用时：\(1.5\) h
期望得分：\(44\) pts
实际得分：\(44\) pts
直接暴力 dp，\(dp[i][0/1]\) 表示满足/不满足第 \(i\) 个国王的要求时的最小开销，那么 \(dp[i][0]=\sum dp[son[i]][1]\)，\(dp[i][1]=c[i]+\sum \min(dp[son[i]][0],dp[son[i]][1])\)。
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int MAX=1e5+10;
const int MOD=998244353;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int cnt,val[MAX],dp[MAX][2],head[MAX];
struct node{int u,v,next;}edge[MAX<<1];
void add(int u,int v){
edge[++cnt]=(node){u,v,head[u]};
head[u]=cnt;
return ;
}
int n,m;string s;
void dfs(int now,int fa){
dp[now][1]+=val[now];
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
dfs(v,now);
dp[now][0]+=dp[v][1];
dp[now][1]+=min(dp[v][0],dp[v][1]);
}
}
signed main(){
n=read(),m=read();
cin>>s;
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
while(m--){
memset(dp,0,sizeof(dp));
int a=read(),x=read(),b=read(),y=read();
if(x==1) dp[a][0]=1e18;
else dp[a][1]=1e18;
if(y==1) dp[b][0]=1e18;
else dp[b][1]=1e18;
dfs(1,0);
if(min(dp[1][0],dp[1][1])>=1e18) puts("-1");
else cout<<min(dp[1][1],dp[1][0])<<endl;
}
return 0;
}