2020-09-03 考试题解
Hobson's Trains
题目大意
给出一个图，保证每个点有且仅有一个出边，对于每个点把它走 (k) 步这条路径上的所有的点答案加 1 ，问最后每个点的答案。
(nle 5 imes 10^5)
思路
考试的时候 sb 了，没想出来怎么做。
首先你可以发现这其实是个基环树森林，对于不在环上的点，它答案其实就是子树内深度与它相差不超过 (k) 的点的数量。考虑在环上的点，显然它们还要考虑环上其他点对该点产生的贡献。
具体实现的话我们可以断开一条边使得变成森林，然后求点的数量可以用树状数组解决，然后如果每次都需要清空的话时间复杂度就会降到 (Theta(n^2)) ，所以我们可以只考虑增长量。时间复杂度 (Theta(nlog n)) 。
( exttt{Code})
vector <int> E[MAXN];
int n,k,cutu,cutv,f[MAXN],sum[MAXN],vis[MAXN],lim[MAXN],ans[MAXN];
int lowbit (int x){return x & (-x);}
void modify (int x){for (Int i = x;i <= n;i += lowbit (i)) sum[i] ++;}
int query (int x){int res = 0;for (Int i = min (n,x);i;i -= lowbit (i)) res += sum[i];return res;}
void dfs (int u,int dep){
vis[u] = 1,ans[u] -= query (dep + k) - query (lim[u]),modify (dep);
for (int v : E[u]) if (u != cutu || v != cutv) dfs (v,dep + 1);
ans[u] += query (dep + k) - query (lim[u]);
}
signed main(){
read (n,k);
for (Int i = 1;i <= n;++ i) read (f[i]),E[f[i]].push_back (i);
for (Int i = 1;i <= n;++ i){
if (vis[i]) continue;
int u = i,v;
while (!vis[u]) vis[u] = 1,u = f[u];
v = f[u],cutu = v,cutv = u;
for (Int len = k;v != u;v = f[v],len --) lim[v] = max (0,len);
for (v = f[u];v != u;v = f[v]) ans[v] -= query (lim[v]);
dfs (u,1);
for (v = f[u];v != u;v = f[v]) ans[v] += query (lim[v]);
}
for (Int i = 1;i <= n;++ i) write (ans[i]),putchar ('
');
return 0;
}
拯救小矮人
题目大意
一开始有 (n) 个点，每个点都两个权值 (a,b) ，如果存在集合 (s) 使得对于 (k) 存在 (a_i{iin s}+b_kge h) ，那么我们就可以把答案加 1，但是后面的集合就不能包含该点。
问答案的最大可能值。(nle 2 imes 10^5)
思路
考试的时候像个弱智一样，写了一个伪贪心，然后写了一个平衡树，结果只把后面比较水的数据骗过去了，还没有乱搞得的分多。。。
正解其实是个反悔贪心，我们按照 (a+b) 排序，然后你发现如果我们把满足的点存下来，每次如果当前点可以那么，那就直接加进去，否则就把最强的拉下来，把这个救上去。
时间复杂度 (Theta(nlog n)) 。
( exttt{Code})
int n,H,ans;ll suma;
priority_queue <int> q;
struct node{
int a,b;
bool operator < (const node &p)const{return a + b < p.a + p.b;}
}peo[MAXN];
signed main(){
read (n);
for (Int i = 1;i <= n;++ i) read (peo[i].a,peo[i].b),suma += peo[i].a;
sort (peo + 1,peo + n + 1),read (H);
for (Int i = 1;i <= n;++ i){
q.push (peo[i].a);
if (suma + peo[i].b >= H) ans ++;
else suma += q.top(),q.pop ();
suma -= peo[i].a;
}
write (ans),putchar ('
');
return 0;
}
Easy
题目大意
定义 ({a}) 合法，当且仅当 (sum_{i=1}^{k}a_i=n)，定义 ({b}) 合法，当且仅当 (sum_{i=1}^{k}b_i=m)，定义 ({a,b}) 的权值为 (prod_{i=1}^{k}min(a_i,b_i))，问所有合法 ({a,b}) 的权值之和。
有 (t) 次查询，每次给出 (n,m,k) 。(tle 100,n,m,kle 5 imes 10^5)
思路
考试的时候随便推了一下，骗了 (60) 分就没有想了，主要是因为没想到二元生成函数，想到了之后就很简单了，直接推式子就可以了。
你发现，其实答案就是 :
证明显然。
然后你把上面那个东西写出来，你发现其实就是：
然后你用等差比公式推一下发现其实就等价于：
然后求这个东西的 ([x^ny^m]) 可以直接用隔板法，具体来说就是枚举 (xy) 的次数。
时间复杂度 (Theta(tn)) （假设 (n,m) 同阶）。
( exttt{Code})
read (N,M,K);
int ans = 0;
for (Int i = 0;i <= N - K && i <= M - K;++ i)
ans = add (ans,mul (binom (K + i - 1,i),mul (binom (N - i - 1,N - K - i),binom (M - i - 1,M - K - i))));
write (ans),putchar ('
');
2020-09-04 考试题解
尝试了头铁打法然后爆炸了。。。
express
题目大意
给出一个 (n) 个点，(m) 条带权边的图，需要依次访问 (2k) 个点，你有两个传送门，传送门放置时必须保证为当前位置，传送门之间可以瞬间传送，问访问完所有点的最小路径长度。
(nle 300,mle 4000,kle 300)
思路
考试的时候猜到了一个显然的结论结果没想到用 dp ，然后。。。
首先有一个显然的结论，就是说有一个传送门肯定就在我的脚下，然后我们可以设 (dp[i][j]) 表示访问了前 (i) 个点，另外一个传送门在 (j) 的最小路径长度。显然，(dp[0][1]=0)。转移式的话我们可以想到肯定只会在 (dp[i-1][k]) 之间转移，其中 (k) 是上一次的传送门的位置，然后你枚举一下情况就可以得到转移式了，具体见代码。
( exttt{Code})
dp[0][1] = 0,a[0] = 1;
for (Int i = 1;i <= k * 2;++ i){
for (Int j = 1;j <= n;++ j){
for (Int K = 1;K <= n;++ K)
dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][j] + dist[K][a[i]]),
dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][j] + dist[j][a[i]]),
dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][a[i]] + dist[K][j]),
dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[K][j] + dist[j][a[i]]);
}
}
int ans = dp[k * 2][1];
for (Int i = 1;i <= n;++ i) ans = min (ans,dp[k * 2][i]);
write (ans),putchar ('
');
Graph
题目大意
有一个 (n) 个点的边带权的树，你每次可以加边或者删边，但需要保证任意时刻存在的环上的权值异或之值为 (0)。问最后 (n-1) 条边的最小边权之和。
(nle 10^5)
思路
被wxk和llsw骗了，实际上这道题目没有很难（也有可能是因为自己没做）
我们可以发现如果两个点之间要加边，那么，边权一定是固定的，因为如果构成的环上的不管怎么变边权都是相同的（异或值为 (0)），可以想到如果定义 (p[u]) 表示 (1 o u) 的路径异或值，那么 (u,v) 之间的边权就是 (p[u]otimes p[v])。于是我们就可以对 (n^2) 条边做最小生成树。
但是这样显然很慢。我们可以想到，如果从高到低位考虑，那么对于当前位而言，我们应该尽量边相邻两点该位分别为 (0,1) 的边的数量最少，那显然就只连 (1) 条边，而且这里很方便的是不需要考虑不连通的问题（有 (n^2) 条边）。那我们可以直接分治，每次把该位为 (0) 的分治构成一棵树，该位为 (1) 的构成一棵树，然后两棵树之间连一条边权最小的边。于是问题就是如何找到边权最小的边，然后你发现这个东西直接用 01trie 树解决就好了。
时间复杂度 (Theta(nlog^2 n))
( exttt{Code})
ll ans;
int n,tot,p[MAXN],rt[MAXN],cnt[MAXN * 31],son[MAXN * 31][2];
void ins (int a,int b,int t,int x)
{
if (t < 0) return ;
int i = x >> t & 1;
son[a][i] = ++ tot;
son[a][i ^ 1] = son[b][i ^ 1];
cnt[son[a][i]] = cnt[son[b][i]] + 1;
ins (son[a][i],son[b][i],t - 1,x);
}
int query (int a,int b,int t,int x)
{
if (t < 0) return 0;
int i = x >> t & 1;
if (cnt[son[b][i]] > cnt[son[a][i]]) return query (son[a][i],son[b][i],t - 1,x);
else return (1 << t) + query (son[a][i ^ 1],son[b][i ^ 1],t - 1,x);
}
int toop = 1,to[MAXN << 1],wei[MAXN << 1],nxt[MAXN << 1],head[MAXN];
void Add_Edge (int u,int v,int w){
to[++ toop] = v,wei[toop] = w,nxt[toop] = head[u],head[u] = toop;
to[++ toop] = u,wei[toop] = w,nxt[toop] = head[v],head[v] = toop;
}
void dfs (int u,int fa){
for (Int i = head[u];i;i = nxt[i]){
int v = to[i],w = wei[i];
if (v == fa) continue;
p[v] = p[u] ^ w,dfs (v,u);
}
}
void dfs (int t,int l,int r){
if (l >= r || t < 0) return ;
int pos = r + 1,tmp = INF;
for (Int i = l;i <= r;++ i) if (p[i] >> t & 1){pos = i;break;}
dfs (t - 1,l,pos - 1),dfs (t - 1,pos,r);
if (pos - 1 >= l && pos <= r){
for (Int i = pos;i <= r;++ i) tmp = min (tmp,query (rt[l - 1],rt[pos - 1],29,p[i]));
ans += tmp,tot = 0;
}
}
signed main(){
read (n);
for (Int i = 2,u,v,w;i <= n;++ i) read (u,v,w),u ++,v ++,Add_Edge (u,v,w);
dfs (1,0),sort (p + 1,p + n + 1);
for (Int i = 1;i <= n;++ i) ins (rt[i] = ++ tot,rt[i - 1],29,p[i]);dfs (29,1,n);
write (ans),putchar ('
');
return 0;
}