J.Justifying the Conjecture—思维+签到

题意：将给出的数表示为由一个素数和一个合数，不能输出 -1

思路：特判 n<=5 时无解，其他的数都可以。如果 n 是偶数就分解为 2 和 n-2，奇数就分解为 3 和 n-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n;
		if(n<=5)cout<<-1<<endl;
		else if(n&1) cout<<3<<' '<<n-3<<endl;
		else cout<<2<<' '<<n-2<<endl;
	}
	//system("pause");
	return 0;
}

K. Keeping Rabbits—签到

题意：现在有 n 个兔子抢胡萝卜，n 个兔子初始质量分别为 wi，每次会有一个兔子胜出，然后它吃一个萝卜质量 w+1，每回合第 i 个兔子生出的概率为 $\frac{w_{i}}{\sum_{j=1}^{n}w_{j}} $

现在求 k 天后兔子体重的期望值

思路：容易发现不管经过了多少天，概率分布都不会改变。考虑 k 天增长的体重总量为 k，所以第 k 只兔子的体重期望为 wi+kwi∑j=1nwjw_{i}+k\frac{w_{i}}{\sum_{j=1}^{n}w_{j}} \boldsymbol{}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k;
int a[100005];

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>k;
		ll sum=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum+=a[i];
		}
		for(int i=1;i<=n;i++)
			cout<<fixed<<setprecision(6)<<a[i]+a[i]*1.0*k/sum<<' ';
		cout<<endl;
	}
	return 0;
}

F.Fixing Banners—DFS+set容器

题意：从六个字符串中分别找出一个字符，问能否组成 harbin 字符串

思路：对于每个字符串，开一个set容器存所有字符串所有的 harbin 的字符的序号，然后用 DFS 每个字符串存储的序号寻找是否可以找到答案。

题解中说直接 6! 暴力枚举也可以过，或者用状压DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool flag;
string s[10];
string str="harbin";
set<int> seta[10];
bool vis[10];

void init(){
	for(int i=0;i<6;i++)seta[i].clear();
	flag=0;
	memset(vis,0,sizeof vis);
}

void dfs(int step){
	if(step>=6){
		flag=1;
		return ;
	}

	for(auto it=seta[step].begin();it!=seta[step].end();++it){
		if(vis[*it]==0){
			vis[*it]=1;
			dfs(step+1);
			vis[*it]=0;//回溯尝试拿下一个点
		}
	}
}

void solve(){
	int len;
	for(int i=0;i<6;i++){
		cin>>s[i];
		len=s[i].length();
		for(int j=0;j<len;j++){
			for(int k=0;k<6;k++){
				if(s[i][j]==str[k]){
					seta[i].insert(k);
					break;
				}
			}
		}
	}
	
	dfs(0);

	if(flag)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--){
		init();
		solve();
	}
	//system("pause");
	return 0;
}

I.Interesting Permutation—构造+思维

题意：定义 fi 为前 i 个数的最大值，gi 为前 i 个数的最小值，hi = fi - gi。现在告诉你每个位置的 hi，问有多少种 1~n 的排列满足这些 hi

思路：首先特判不成立的数据：首先特判 h1 ̸= 0，hn ≥ n ，hi<i-1 以及 hi > hi+1 的情况，这些情况答案都是 0。否则至少存在一个成立的情况，然后依次考虑 h2，h3，…，hn。如果 hi > hi−1，那么 ai 既可以是前 i 个数的最大值，也可以是前 i 个数的最小值，所以将答案数翻倍，同时新增中间 hi−hi−1−1 个空位没填，如果 hi = hi−1， 那么需要消耗一个空位，并将答案乘以空位数（组合数）。这里面从 h2 往后考虑的都是每个元素的相对大小关系，所以当选择最大值或者最小值越界的时候就可以通过更改 h1 维护答案的正确

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;

int n;
int a[100005];

bool check(){//不能生成序列
	if(a[1]!=0)return 0;
	for(int i=2;i<=n;i++){
		if(a[i]<a[i-1])return 0;
        if(a[i]<i-1)return 0;
		if(a[n]>=n)return 0;
	}
	return 1;
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	if(check()==0){
		cout<<0<<endl;
		return ;
	}
	
	ll ans=1,cnt=0;//记录答案和最大值与最小之间预留的空位
	for(int i=2;i<=n;i++){
		if(a[i]>a[i-1]){//a[i]既可以是前i个数的最大值也可以是前i个数的最小值
			ans=(ans*2)%mod;
			cnt+=a[i]-a[i-1]-1;
		}
		if(a[i]==a[i-1])ans=(ans*(cnt--))%mod;
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

E.Exchanging Gifts—拓扑+map容器

题意：一个序列经过多次重新排列后如果当前位初始的数字和排列后的数字不同快乐值就+1，因为序列最长是 1e18，不同的数最多是 1e6 ，所以题目采用以下操作给出：有 n 行数据

  • 操作一：给出一段长为 k 的序列
  • 操作二：将第 x 行和第 y 行给出的序列合并

求最后第 n 行作为最终序列给出的序列的最大欢乐值

思路：题解参考 记最终合并的序列中出现次数最多的字符为 x ，出现的次数为 occ(x) ,最终序列的长度为 len，若是大于序列长度的一半，那么答案是不难得出是 2*len-2*occ(x)，否则就是 len。那么关键在于怎么在 1000ms 内求出最长长度可以到 1e18 序列中出现次数最多的字符的数量。最直接的思路是用 map 桶记录每个数出在最终序列中出现的次数，但是直接暴力遍历每个序列 TLE。优化思路——因为最终合并的序列不一定将之前的序列都用到，也就是说有些序列内的数没必要统计。我们可以用先反向 bfs 找出形成最终序列有贡献的边的入度，然后在根据入度求拓扑图，只在中间合并这些序列统计。

bfs找贡献边前

bfs找贡献边后

这时我们会 TLE5 ,因为这题对于 O(nlogn) 卡常比较紧，将平民版快读改为读入挂直接降低一半时间成功 AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
#pragma GCC optimize(2)//防卡常新姿势，开启O(2)优化
using namespace std;
typedef long long ll;
const int maxn=1e6+10;

inline char nc() {
	static char buf[1000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

template <typename _Tp> inline void read(_Tp&sum) {
	char ch = nc(); sum = 0;
	while (!(ch >= '0'&&ch <= '9')) ch = nc();
	while (ch >= '0'&&ch <= '9') sum = (sum << 3) + (sum << 1) + (ch - 48), ch = nc();
}

struct node{
    ll l,r;
    node() {}
	node(ll l, ll r) :l(l), r(r) {}
};

/*
如果是存入操作，G[l]用来记录数列包含的数列数量
如果用于合并操作，l,r分别用于记录合并的两个数列编号
*/

int t,n;
node G[maxn];
map<ll,ll> mp;//相当于桶数组统计数列中每个数出现的次数
vector<vector<ll> > vec;
ll vis[maxn],cnt[maxn],in[maxn];//find_in用到的标记数组

inline void init(){
    vec.clear();
    mp.clear();
    for(int i=0;i<n;++i){
        cnt[i]=0;
        vis[i]=0;
        in[i]=0;
    }
}

void find_in(ll s){//寻找生成最后一个字符串所用的字符串的入度
    queue<ll> que;
    que.push(s);//最后一个是最终序列入度肯定是0
    vis[s]=1;
    while(que.size()){
        ll t=que.front();
        que.pop();
        if(G[t].r!=-1){//说明是合并操作
            ll l=G[t].l,r=G[t].r;
            ++in[l],++in[r];//说明当前两个字符串参与组成最后的字符串，入度+1说明使用它合并一次

            //没有存入过标记入队
            if(!vis[l]) que.push(l),vis[l]=1;
            if(!vis[r]) que.push(r),vis[r]=1;
        }
    }
}

void topsort(ll s){
    queue<ll> que;
    cnt[s]=1;//从最后一个最终序列拓扑,往下寻找的深度即是这个序列的重用次数
    que.push(s);
    while(que.size()){
        ll t=que.front();
        que.pop();
        if(G[t].r!=-1){//说明是合并操作
            ll l=G[t].l,r=G[t].r;
            cnt[l]+=cnt[t],cnt[r]+=cnt[t];
            //入度为0入队
            if(--in[l]==0) que.push(l);
            if(--in[r]==0) que.push(r);
        }
        else{
            for(ll &x:vec[G[t].l])
            mp[x]+=cnt[t];//每一次合并两个序列我们只需要更新一下map的数字出现的次数
        }
    }
}

void solve(){
    for(register int i=0;i<n;++i){//n个操作
        int opt;read(opt);
        if(opt==1){
            int len;read(len);
            G[i].l=vec.size();
            G[i].r=-1;
            vec.resize(vec.size()+1);//新开一个一维数组用来存当前数列的数
            int x;
            for(register int j=0;j<len;++j){
                read(x);
                vec.back().emplace_back(x);//将数存入新开的数组
            }
        }
        else{
            ll x,y;
            read(x),read(y);
            //从0编号开始
            G[i].l=x-1;
            G[i].r=y-1;
        }
    }

    find_in(n-1);//先用n个操作找有用的序列及其入度
    topsort(n-1);//将找到的序列进行拓扑排序

    ll ans=0,num=0;//数列中出现次数最多的次数，数列总的数量
    for(auto &x:mp){
        num+=x.second;
        ans=max(ans,x.second);
    }
    printf("%lld\n",ans>num/2? 2*num-2*ans:num);
}

signed main()
{
    int t;read(t);
    while(t--){
        read(n);
        init();
        solve();
    }
    return 0;
}