题目链接
https://vjudge.net/problem/Gym-102394E
题意
给定n个序列，给出方式有两种：直接给定m个数字作为序列si，或者给定j，k，使si=sj+sk。
对sn任意排序，最多能使多少个位置上的数字与之前不同？
思路
先记录输入，vector数组存储第一种方式给定的序列。
从后往前递推出每一个序列的使用次数并记录。
使用unordered_map统计出现次数最多的数字，并记录序列总长度
答案为min（len，2len-2cnt）
教训/收获
- map除了建立映射以外还保证了内部元素的有序，所以查询插入复杂度为logn，c++11支持hash原理的unordered_map查询插入复杂度为O(1)
- 善用vector可以节省很大的空间开销，1e8 int 数组约400M
- 有思路就写，做错好过什么都不做
代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<cstdlib>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=1005000;const int inf=0x3f3f3f3f;int n,m;ll cmd[maxn][3];vector<ll>v[maxn];ll need[maxn];queue<ll>q;unordered_map<ll,ll>mp;template <typename T>void read(T &x){
x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){
if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){
x=x*10+ch-48;ch=getchar();}x*=f;}signed main(){
int tn;read(tn);while(tn--){
read(n);for(int i=1;i<=n;i++){
read(cmd[i][0]);if(cmd[i][0]==1){
read(m);for(int j=0;j<m;j++){
ll tmp;read(tmp);v[i].push_back(tmp);}}else{
scanf("%lld%lld",&cmd[i][1],&cmd[i][2]);}}for(int i=0;i<=n;i++)need[i]=0;need[n]=1;for(int i=n;i>=1;i--){
if(cmd[i][0]==1)continue;need[cmd[i][1]]+=need[i];need[cmd[i][2]]+=need[i];}ll cnt=0,ma=-inf;for(int i=1;i<=n;i++){
if(need[i]){
for(auto j:v[i])mp[j]+=need[i];cnt+=need[i]*v[i].size();}}cout<<cnt<<endl;for(int i=1;i<=n;i++)v[i].clear();for(auto i:mp){
ma=max(i.second,ma); }mp.clear();if(2*ma<cnt){
printf("%lld\n",cnt);}else{
printf("%lld\n",2*cnt-2*ma);}} }