A

每次可以选一个子区间，复制其中所有元素，那其实我们可以用这个操作把初始元素变成任意多个，但是我们不能凭空变出来一个元素。那么给出操作后的数组，其中每一段连续相同元素，一定是初始数组中至少一个该种元素操作得来的。因此把每一段连续相同元素缩成一个该种元素，就是最小的初始数组

void solve(){
	cin>>n;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	int ans=1;
	rep(i,2,n){
		if(a[i]!=a[i-1]){
			ans++;	
		}
	}
	cout<<ans<<'\n';
}

B

经典子序列+状态机dp

给一个序列，定义只有两个数都不减才是合法的，可以交换一个元素的xy，也可以删除一个元素，问使序列合法的最小代价。

注意数据，支持我们，那可以写一个朴素转移的子序列dp，表示得到以为结尾的合法子序列的最小代价，枚举上一个位置，只要满足和上一个位置的元素满足前面说的合法条件，就可以转移，中间的元素都删掉。

然后还有一个交换xy的操作，那么我们可以加一个维度表示这个状态是否反转了最后一个元素

然而这个状态设计还是有一点问题，因为是默认最后一个元素必须选的，那如果返回实际上选上了第n个元素，但是最优方案可能不选第n个元素。可能是把一段后缀删掉了。

这里我选择的解决方式是类似哨兵的思想，加了一个第n+1个元素，然后这个元素的xy都很大，可以从前面任何一个位置转移过来，那么这时就可以包含删除一个后缀的情况了

void solve(){
	int x,y;
	cin>>n>>x>>y;
	vi a(n+2),b(n+2);
	rep(i,1,n)cin>>a[i]>>b[i];
	a[n+1]=b[n+1]=2e9;
	vvi dp(n+2,vi(2,1e15));
	dp[1][0]=0;
	dp[1][1]=y;
	rep(i,2,n+1){
		rep(j,1,i-1){
			rep(p,0,1){
				int a1=a[j],b1=b[j];
				if(p)swap(a1,b1);
				rep(q,0,1){
					int a2=a[i],b2=b[i];
					if(q)swap(a2,b2);
					if(a1<=a2&&b1<=b2){
						dp[i][p]=min(dp[i][p],dp[j][q]+p*y+x*(i-j-1));
					}
				}
			}
		}
		dp[i][0]=min(dp[i][0],(i-1)*x);
		dp[i][1]=min(dp[i][1],(i-1)*x+y);
		//cout<<dp[i][0]<<' '<<dp[i][1]<<'\n';
	}
	cout<<min(dp[n+1][0],dp[n+1][1])<<'\n';
}

C

数列题不会都可以考虑打表。

这题打表发现出现的数很多，然后发现只有少数几个数不出现，且4，8，16都没出现，那么转而对不出现的元素打表，发现从4开始的2的幂都不出现。

那么问第k小元素，可以二分，检查一个小于x的数的个数-小于x的2的幂的个数，是否小于k。直接求也可以，但是要讨论，感觉有点麻烦

void solve(){
	cin>>n;
	int l=1,r=2e18;
	auto check=[&](int x)->bool{
		int cnt=x-1;
		int p=4;
		while(p<2*x){
			cnt--;
			p*=2;
		}
		return cnt<n;
	};
	while(l<=r){
		int m=l+r>>1;
		if(check(m))l=m+1;
		else r=m-1;
	}
	cout<<r*2<<'\n';
}

D

贡献法+期望

代码很短，思路很长。

首先为什么要贡献法？对于这种有很多个方案，然后求每个方案的某个函数值之和的问题，枚举方案然后加起来会超时，但是每个方案包含的基本元素并不多，那么可以转而枚举每个基本元素，然后计算每个基本元素的贡献，也就是它会被多少个方案所包含，这样会快的多，也好想。

然后对于这个题，我们要用贡献法，首先要找到基本元素，一个比较显然的元素是连通块，但是连通块并不容易枚举，那么有什么和连通块等价的东西吗，我们枚举他们也行？

手玩/推理可以发现每个连通块里有且只有一个边，同时是的最小边。可以反证：如果一个连通块有两个这样的边，不妨设，那么根据选边的规则，b会选呃e1，u会选e2，那么bu就不不会联通了，这就不是一个连通块了，矛盾。

那么连通块和这种边是等价的，那么求连通块的期望，就是求这样的边的个数的期望，这又等价于，每条边成为这样的边的方案数的期望的和。

那么我们可以枚举边，然后算每条边的期望然后求和。每条边都是他所连接的两个点的所有边中的一条，在边权赋值完全随机的情况下，他成为最小边的概率就是，他成为最小边的方案数的期望也是。

然后每条边的期望都是这样算的，一共条边，因此答案就是

void solve(){
	mint x;
	cin>>x;
	cout<<x*(x-1)/(4*x-6)<<'\n';
}

E

单调栈+暴力

保证数据随机是个很好的性质，在这个条件下很多东西的期望复杂度都并不大，因此可以用偏暴力的方法来做，似乎去年鸡哥也出了类似的东西。

对于本题，随机生成的一个序列，相同的段数的期望是的，因此我们可以单调栈记录每个变化的分界点，然后对枚举分界点形成的区间，统计答案。这里的具体实现是用set存所有分界点，然后枚举就行了，可能有重复点，但是区间长度为0，对答案贡献也是0，不影响。

我们统计了每种的值的出现次数，最后答案问的是大于某个值的区间个数，因此我们还需要对这个值求个后缀和，然后每次查询就直接二分就可以了。这里求后缀和需要倒序遍历，可以枚举迭代器，这里学了一个新写法，先用，然后用，可以直接倒序遍历

void solve(){
	cin>>n>>m>>k;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	stack<int>s1,s2;
	multiset<int>s;
	map<int,int>ans;
	rep(i,1,n){
		while(s1.size()&&a[i]>=a[s1.top()])s.erase(s.find(s1.top())),s1.pop();
		while(s2.size()&&a[i]<=a[s2.top()])s.erase(s.find(s2.top())),s2.pop();
        if(!s1.size())s.insert(0);
        if(!s2.size())s.insert(0);
        s1.push(i);
        s2.push(i);
		s.insert(i);
		s.insert(i);
		int mx=0,mn=1e9;
		for(auto p=next(s.rbegin());p!=s.rend();++p){
			int pre=*prev(p);
			int cur=*p;
			mx=max(mx,a[pre]);
			mn=min(mn,a[pre]);
			ans[mn*mx]+=pre-cur;
		}
	}
	debug(ans);
	ans[1e18]=0;
	int sum=0;
	for(auto &[k,v]:ans|views::reverse){
		sum+=v;
		v=sum;
	}
	rep(i,1,k){
		int x;
		cin>>x;
		cout<<ans.lower_bound(x)->second<<'\n';
	}
}

F

贪心，最害怕的一集。还是好几个贪心拼在一起的

首先注意到我们能取的答案就是在里取的，因此我们可以把排序，然后枚举最后取到的最大的a+b，然后检验这个值能不能通过优化面试顺序取到。那么对于前面更小的a+b，我们要安排他们的顺序，让能获得的offer尽量大，如果最后能大于当前，就能取到当前。

如果不大于，那么说明当前a比前面的所有都更大，那么我们可以把这个放到最开头，这样就能取到前面最大的。

void solve(){
	cin>>n;
	vi a(n+1),b(n+1);
	rep(i,1,n)cin>>a[i]>>b[i];
	vvi c;
	rep(i,1,n){
		c.push_back({a[i]+b[i],a[i]});
	}
	sort(c.begin(),c.end());
	vi ans(n+1),mx(n+1);
	rep(i,1,n){
		ans[i]=ans[i-1];
		if(ans[i-1]>=c[i-1][1]){//如果前面最大的大于当前a，取到a+b
			ans[i]=max(ans[i],c[i-1][0]);
		}
		else{//如果不大于，把这个a安排到第一个，取到前缀最大a+b
			ans[i]=max(ans[i],mx[i-1]);
		}
		ans[i]=max(ans[i],c[i-1][1]);//a肯定能取到
		mx[i]=max(mx[i-1],c[i-1][0]);//最大的a+b
	}
	cout<<ans[n]<<'\n';
}

H

构造，根本想不到，就当开拓眼界了

首先如果所有区间大小是偶数，那直接就可以。如果是奇数，可能出现区间中点的数排序之后位置没变，不能用这个方案了。

那把这个问题一般化一点，想染所有长度为奇数的区间排序后都变了，这个每个奇数区间在排序前都必须是个错排，也就是没有一个元素是在排序后的位置上的，这样排序一下的新位置都会和排序前不同。

然后所有奇数大小的区间，都是由最小的奇数区间，也就是长为3的区间构成的（长为1显然没意义），那么我们只要保证每个长度为3的区间都是错排，就能保证所有长为奇数的区间都是错排了。

注意到长为3的错排有两种，而且他们的前后缀还是连着的。那其实就可以按这样的模式构造，注意这里的数字是他们在长度为3的子数组中的相对大小。

这个思路的实现有一种简单的方法，就是把每两个交换一下，例如

void solve(){
    cin>>n>>m;
    vi a(n+1);
    rep(i,1,n)a[i]=n-i+1;
    rep(i,1,m){
        int l,r,c;
        cin>>l>>r>>c;
        k=(r-l+1)%2;
    }
    if(k%2){
        for(int i=1;i<n;i+=2){
            swap(a[i],a[i+1]);
        }
    }
    rep(i,1,n)cout<<a[i]<<' ';
    cout<<'\n';
}

I

离线+线段树或者在线+主席树

我们要求一个区间内的一个元素，排序后是不是还在这个位置，实际上就是求这个区间内小于这个元素的个数，这个东西很容易联想到主席树，但是主席树板子是求第k打的元素是几，这个是求小于k的元素的个数，略有区别，那么可以去修改一下查询方式，或者仍然使用查第k大的板子，外面套个二分，第二种方法是的，会爆。

离线就比较好做。查一个区间内小于K的元素个数，我们可以把询问按K大小离线，然后每次查的时候，ds里只有小于当前K的元素，那就直接查区间内元素个数就行了。

也可以注意到内小于K的元素个数，是等于的结果的，那么我们可以把询问拆开，然后从左到右把元素加入ds，到了一个位置，处理所有有一个端点在的所有询问，如果是就减，是就加。这只需要一个求小于K的元素个数的ds，可以是权值线段树，也可以是treap。

void solve(){
	cin>>n>>m;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	vvi b[n+1];
	vi ans(m+1);
	rep(i,1,m){
		int l,r,c;
		cin>>l>>r>>c;
		ans[i]+=l-1;
		b[l-1].push_back({i,a[c],-1});
		b[r].push_back({i,a[c],1});
	}
	RedBlackTree tr;
	rep(i,1,n){
		tr.insert(a[i]);
		for(auto &q:b[i]){
			int id=q[0],v=q[1],sym=q[2];
			int cnt=tr.countLessEqual(v);
			ans[id]+=sym*cnt;
		}
	}
	rep(i,1,m)cout<<ans[i]<<'\n';
}

J

枚举+贪心

首先注意到这个过程一定是先只磨刀，然后又磨又打。如果磨一会，打一会，肯定是不如先把刀磨到较高攻击力再打要划算的。

然后注意到磨刀石不多，也就是只磨不打的可能时长不多，那么可以枚举只磨不打的阶段的时长，然后剩下的时间先有磨又打，磨刀石没了就只打。对每种情况取max即可。

然后这题似乎可以三分，因为这个总伤害似乎是凸函数，这样就可以做了

void solve(){
	int x,y;
	cin>>n>>x>>y;
	int ans=0;
	rep(i,0,min(y,n)){
		int mx=x+i;
		int t1=min(n,y)-i,t2=min(n-t1-i,mx);
		int cur=t1*(mx+1);
		cur+=(mx+mx-t2+1)*t2/2;
		ans=max(ans,cur);
	}
	cout<<ans<<'\n';
}

K

注意到翻一页，两页之和+4，那么就看目标和和当前的两页的和模4是否同余

void solve(){
	cin>>n>>m;
	if(m%4==(2*n+1)%4){
		cout<<"YES\n";
	}
	else{
		cout<<"NO\n";
	}
}

L

每次都删两个不同元素，可以在任意位置，问能不能剩下一个给定字符串。

首先这个字符串必须是初始串的子串。然后非字符串中的必须都删了，而且每次只能删两个不同的，那这其实就转化成经典贪心，不同元素两两配对，问能不能把所有元素都配对。

这需要看出现次数最多的元素，出现次数超不超过总数的一半，不超过就可以，超过则不行。

void solve(){
	cin>>n;
	string s;
	cin>>s;
	s=' '+s;
	string t="CHICKEN";
	int pos=0;
	rep(i,1,n){
		if(pos<7&&s[i]==t[pos]){
			pos++;
		}
	}
	if(pos!=7){
		cout<<"NO\n";
	}
	else if((n-7)%2==1){
		cout<<"NO\n";
	}
	else{
		map<char,int>mp;
		rep(i,1,n){
			mp[s[i]]++;
		}
		rep(i,0,6){
			mp[t[i]]--;
		}
		int mx=0;
		for(auto &[k,v]:mp){
			mx=max(mx,v);
		}
		if(mx>(n-7)/2){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\n";
		}
	}
}