题目链接
Problem - E - Codeforces
题目大意
有两种操作 第一种是列出一个序列 第二种是合并之前出现的序列生成一个新的序列
问你最后序列的快乐值是多少
快乐值定义是 将序列随意排序后最大的与之前位置不同的元素个数
题目思路
经过观察发现
最大快乐值
数量最多的元素数量=maxv
总元素数量=tot
当maxv<tot/2时 快乐值=tot
否则快乐值 =tot-（maxv-（tot-maxv））
列出如下之图可看得更明白
有上图到下图 明显不快乐值为 最大的数量5 -剩余数量4=1
快乐值=9-1=8
问题是如何找到各个元素数量
由于每个操作2可以吸收两个序列
可以很容易想到拓补
但是该题有一个条件就是2操作的对象序号小于 i
那么该题就不需要拓扑了 直接从n到1线性求解
设置num【n】=1
若该点是操作2则将操作对象的num+=num【i】
若该点是操作1则该点包含所有的点的数量+=num【i】
若某一个点num【i】==0 就跳过
这样的时间复杂度是O（N+K）
但由于读入数量级的问题 很容易T
因此我用了一个超级快读（注意该快读无法读入其他类型）
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{register int x(0);register char c(gc);while(c<'0'||c>'9')c=gc;while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;return x;
}题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int t,n,m,T,q,x,y;int lef[maxn],inlj[maxn];
ll num[maxn];
ll tot,maxv;
unordered_map<int ,ll >mp;
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{register int x(0);register char c(gc);while(c<'0'||c>'9')c=gc;while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;return x;
}
//void dfs(int floor)
//{
// if(lef[floor])
// for(int i=0;i<e[floor];i++)
// {
//
// }
//}
vector<int >v[maxn];
int main()
{T=read();while(T--){n=read();mp.clear();tot=maxv=0;for(int i=1;i<=n;i++){t=read();v[i].clear();lef[i]=num[i]=0;if(t==1){q=read();for(int j=0;j<q;j++){x=read();v[i].push_back(x);} }else if(t==2){x=read();y=read();v[i].push_back(x);v[i].push_back(y);lef[i]=1;}} num[n]=1;if(lef[n]){//dfs(n);for(int i=n;i>=1;i--){if(num[i]==0)continue;int floor=i;if(lef[floor]==1){num[v[floor][0]]+=num[i];num[v[floor][1]]+=num[i];}else {for(int j=0;j<v[floor].size();j++){int y=v[floor][j];mp[y]+=num[i];maxv=max(maxv,mp[y]);tot+=num[i];}}} }else {int floor=1;for(int j=0;j<v[floor].size();j++){int y=v[floor][j];mp[y]+=num[floor];maxv=max(maxv,mp[y]);tot+=num[floor];}}if(maxv<=(tot)/2){printf("%lld\n",tot);}else {ll tmp=maxv-(tot-maxv);printf("%lld\n",tot-tmp);}}return 0;
}