比赛地址
Pro: 5/5/11
Rank: 56/1116
[B] Graph
题意
给出一棵树,每条边有一个非负边权.有两种操作,一种是添加一条边,如果构成了一个环的话,要求这个环的边权异或值为0;第二种操作是删除一条边,但是要保证删除后图仍然连通.
问经过一定次数的操作后,得到的新树的边权和最小是多少.
题解
神奇的结论题.
首先,根据题意,无论怎么操作,任意两点间的路径上的边的异或值不变(证明过于复杂,不再展开).朴素的想法是求出任意两点的路径异或值后,求一个最小生成树,时间复杂度O(n^2logn),会T.
转化下思路,先求出任意一个点到根的异或值,这样任意两点的路径的异或值就可以用他们到根的距离的异或值来表示.得到了n个异或值之后,接下来尝试重构出一棵树.先把这些异或值全部扔到Trie树上,然后在Trie树上从下往上DP.
假如说Trie树某个节点的两个子树都储存有异或值,就尝试从两个子树中各取出一个值,然后将它们的异或加到答案里,这个操作对应的是在两个点之间连边.这种贪心合并的思路显然是正确的.问题变成了如何从两堆数中各取出一个出来,使得它们的异或尽可能小.我的思路是启发式合并,把小的那一堆的每一个数全部拿出来,扔到Trie树的另一枝上往下暴力算最小异或值.然后将两堆启发式合并一下,继续往上DP.总的时间复杂度是O(30nlogn).
中间RE了几次,应该是Trie树开小了(虽然我感觉应该造不出接近理论上界的数据).
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x7f7f7f7f
using namespace std;
int n,i,x,y,z,lsum=1,root=1,cnt=1;
int p[35];
LL ans;
int head[N],f[N*25];
vector <int> Q[N*25];
struct Data{
int x,y,z;
}a[N];
struct Edge{
int t,next,l;
}e[N*4];
struct Trie{
int s[2];
int tag,d,v;
}t[N*25];
IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Add(int s,int t,int l){
e[lsum].t=t; e[lsum].l=l; e[lsum].next=head[s]; head[s]=lsum++;
}
IL void Insert(int x){
reg int i=0,now=root,son=0;
for (i=30;i>=0;i--){
son=(x&(p[i]));
if (son) son=1; else son=0;
if (t[now].s[son]) now=t[now].s[son];
else {
t[now].s[son]=++cnt; t[now].d=p[i];
now=cnt;
}
}
t[now].tag=x; t[now].v=1; Q[now].push_back(x);
}
IL void Dfs(int x,int fa,LL val){
reg int i=0;
Insert(val);
for (i=head[x];i;i=e[i].next){
if (e[i].t==fa) continue;
Dfs(e[i].t,x,val^e[i].l);
}
}
IL LL Find(int x,int val){
while (1){
if (t[x].v) return (t[x].tag^val);
if (val&t[x].d){
if (t[x].s[1]) x=t[x].s[1];
else x=t[x].s[0];
} else {
if (t[x].s[0]) x=t[x].s[0];
else x=t[x].s[1];
}
}
}
IL void DP(int x){
reg int i=0,l=0,r=0;
LL qq=INF;
f[x]=x;
if (t[x].tag) return;
if (t[x].s[0]==0 || t[x].s[1]==0){
if (t[x].s[0]) DP(t[x].s[0]),f[x]=f[t[x].s[0]];
if (t[x].s[1]) DP(t[x].s[1]),f[x]=f[t[x].s[1]];
return;
}
DP(t[x].s[0]); DP(t[x].s[1]);
l=t[x].s[0]; r=t[x].s[1];
if (Q[f[l]].size()<Q[f[r]].size()){
qq=INF;
for (auto j : Q[f[l]]){
qq=Min(qq,Find(r,j));
}
ans+=qq;
Q[f[r]].insert(Q[f[r]].end(),Q[f[l]].begin(),Q[f[l]].end());
Q[f[l]].clear();
f[x]=f[r];
} else {
qq=INF;
for (auto j : Q[f[r]]){
qq=Min(qq,Find(l,j));
}
ans+=qq;
Q[f[l]].insert(Q[f[l]].end(),Q[f[r]].begin(),Q[f[r]].end());
Q[f[r]].clear();
f[x]=f[l];
}
//cout<<qq<<endl;
//cout<<t[x].d<<" "<<ans<<endl;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=p[0]=1;i<=30;i++) p[i]=p[i-1]<<1;
for (i=1;i<=n-1;i++){
a[i].x=read()+1; a[i].y=read()+1; a[i].z=read();
Add(a[i].x,a[i].y,a[i].z); Add(a[i].y,a[i].x,a[i].z);
}
if (n==2){
cout<<a[1].z<<endl;
return 0;
}
if (n==3){
x=a[1].z; y=a[2].z; z=x^y;
cout<<x+y+z-Max(x,Max(y,z))<<endl;
return 0;
}
ans=0;
Dfs(1,0,0); DP(1);
cout<<ans<<endl;
return 0;
}
[D] Drop Voicing
题意
给出一个排列,有两种操作,第一种操作是将第一个数挪到序列的末尾.第二种是将倒数第二个数挪到序列的最前面.连续使用某一种操作视为一段.问最少用几段第二种操作,可以将序列排好序.
题解
推导后不难发现,一段第二种操作可以将一些相邻的数放到其最后的位置上.所以在环形序列上求一个LIS,序列长度减去LIS的长度就是答案.
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int s[1005];
int sta[1005];
int LIS(const int *a, const int n)
{
int top = 0;
sta[top++] = a[0];
for (int i=1; i<n; ++i)
{
if (a[i] >= sta[top-1])
sta[top++] = a[i];
else
*std::upper_bound(sta, sta+top, a[i]) = a[i];
}
return top;
}
int main() {
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &s[i]);
for (int t = 1; t <= n; t++) {
ans = max(ans, LIS(s, n));
s[n] = s[0];
for (int i = 0; i < n; i++) s[i] = s[i+1];
}
printf("%d\n", n - ans);
return 0;
}
[E] Bogo Sort
题意
给出一个排列,现在要对一个序列进行排序,排序的方式是按照这个给出的排列进行一次置换操作.如果没排好序就继续.问有几种序列,可以通过这个排列进行排序.
题解
求出序列的各个循环节,答案就是这些循环节长度的LCM.
Python大法好!
就是容易莫名RE,Python的栈空间是真的小,以后注意写非递归的
代码
from math import gcd
n=int(input())
p=list(map(int,input().split()))
v=[0 for i in range(n+10)]
ans=1
def Dfs(x,L):
if (v[x]):
return L
v[x]=1
while 1:
L+=1
x=p[x]-1
if (v[x]):
return L
else:
v[x]=1
for i in range(n):
if (v[i]):
continue
else:
v[i]=1
y=Dfs(p[i]-1,1)
g=gcd(ans,y)
ans=ans*y//g
print(ans)
[F] DPS
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
int d[N],s[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Print(int x){
reg int i=0;
putchar('+');
for (i=1;i<=s[x];i++) putchar('-');
putchar('+'); putchar(10);
putchar('|');
for (i=1;i<s[x];i++) putchar(' ');
if (d[x]==d[0]) putchar('*');
else if (s[x]) putchar(' ');
putchar('|');
printf("%d",d[x]);
putchar(10);
putchar('+');
for (i=1;i<=s[x];i++) putchar('-');
putchar('+'); putchar(10);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++) d[i]=read();
for (i=1;i<=n;i++) d[0]=Max(d[0],d[i]);
for (i=1;i<=n;i++){
s[i]=int(50.0*(1.0*d[i]/(1.0*d[0]))+0.999999);
}
for (i=1;i<=n;i++) Print(i);
//for (i=1;i<=n;i++) cout<<s[i]<<endl;
return 0;
}
[I] Hard Math Problem
题意&题解
签到题
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int main() {
printf("0.666667\n");
return 0;
}
总结
前期结论猜的很爽,连莽四道题,然后就在B题上卡死了.可能是觉得这场的结论题有点多,一开始总想通过一些骚操作过掉B,在用线性基尝试过后放弃了这个念头.
将异或值扔到Trie树上应该是一个经典手法,但是没有一上来就往这个方向去想.怎么在Trie树上DP也想了很久,按理说前几场刚刚写过启发式合并的题,不应该想这么慢的,思维灵活性有些欠缺.如果时间足够充裕的话应该可以推掉C和K,但是没有如果了,最后五题遗憾收尾.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第五场
本文地址: 2020牛客暑期多校第五场
