Educational Codeforces Round 79 (Rated for Div. 2) Finished （A-D）

如果最大值比剩余两个加起来的总和+1还大，就是NO，否则是YES

#include<bits/stdc++.h>

using namespace std;

int main(){

	int T;

	cin>>T;

	while(T--){

		vector<int> a(3);

		for(int i=0;i<3;i++)

			cin>>a[i];

		sort(a.begin(),a.end());

		if(a[2]>a[0]+a[1]+1) puts("No");

		else puts("Yes");

	}

}

　　

先不要去考虑跳过的问题，就让他一直向前走，并且一直减，并且记录途中遇到的礼物最大值，这样有两种情况

case1：直接走完，答案就是0

case2：停在某一个位置，我们一定会选择所有可能跳过的礼物中最大的，因为必须要放弃一个，肯定要放弃其中最大的

#include<bits/stdc++.h>

using namespace std;

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int n,sum;

		scanf("%d%d",&n,&sum);

		vector<int> a(n);

		for(int i=0;i<n;i++)

			scanf("%d",&a[i]);

		int pos=0;

		int i;

		for(i=0;i<n;i++){

			if(sum>=a[i]) {

				sum-=a[i];

			}

			else {

				if(a[pos]<a[i]) pos=i;

				break;

			}

			if(a[pos]<a[i]) pos=i;

		}

		if(i==n) printf("0\n");

		else{

			printf("%d\n",pos+1);

		}

	}

}

　　

对于被拿出来的，不需要去管他究竟是按什么放回去的，但是可以肯定的是必然有一种方案是最优的，使得如果不取更深的礼物的话花费一定是1

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

int a[maxn],b[maxn],pos[maxn];

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int n,m;

		scanf("%d%d",&n,&m);

		for(int i=0;i<n;i++)

			scanf("%d",&a[i]),pos[a[i]]=n-i;

		for(int i=0;i<m;i++)

			scanf("%d",&b[i]);

		int in=n,out=0;

		long long ans=0;

		for(int i=0;i<m;i++){

			if(pos[b[i]]<=in) {

				ans+=2*(in-pos[b[i]]+out)+1;

				in=pos[b[i]]-1;

				out=n-i-1-in;

			}

			else ans++,out--;

		}

		printf("%lld\n",ans);

	}

}

　　

遍历每一个礼物，很容易算出每一个礼物被选中的概率，然后考虑有多少个人需要这个礼物，假设为cnt，这个可以预处理出来，选中这些人的概率为cnt/n

两个相乘即可，所有的情况加起来即可

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+5;

const int P=998244353;

int add(int a,int b){

	int ans=a+b;

	if(ans>=P) ans-=P;

	return ans;

}

int mul(int a,int b){

	return 1ll*a*b%P;

}

int qpow(int a,int n){

	int ans=1;

	for(;n;n>>=1,a=1ll*a*a%P)

		if(n&1) ans=1ll*ans*a%P;

	return ans;

}

vector<int> a[maxn];

int inv[maxn];

int main(){

	int n;

	scanf("%d",&n);

	vector<int> cnt(maxn,0);

	for(int i=0;i<n;i++){

		int x;

		scanf("%d",&x);

		a[i].resize(x);

		for(int j=0;j<x;j++)

			scanf("%d",&a[i][j]);

		for(int j=0;j<x;j++)

			cnt[a[i][j]]++;

	}

	for(int i=0;i<maxn;i++)

		inv[i]=qpow(i,P-2);

	int ans=0;

	for(int i=0;i<n;i++){

		for(int j=0;j<a[i].size();j++){

			ans=add(ans,mul(mul(inv[n],inv[a[i].size()]),mul(inv[n],cnt[a[i][j]])));

		}

	}

	printf("%d\n",ans);

}