【CF #792 Div1+Div2】A-E

题目

每次操作先交换两个数再删去尾端的数，使最后剩余的数最小。

直接判断这个数大于100，每次操作都可以把最小的数留到最后，只有两位数的话只能是个位的数。

#include
#define pb push_back
#define ll long long
#define guanliu ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);

int main() 
{
	guanliu;
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n/100==0)
		{
			int a=n/10;
			int b=n%10;
			cout< 
B. Z mod X = C 
题目
 
分析 
给出a,b,c，找出满足x mod y = a ,y mod z = b ,z mod x = c;的x,y,z。
 
之前做过类似的题，先做出式子代换，代换为假设z的k为0，其余两个k相同，即可推出x和y的值。
 
注意：x,y,z的值需要开long long。
 
代码 
#include
#define pb push_back
#define ll long long
#define guanliu ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);

int main() 
{
	guanliu;
	int t;
	cin>>t;
	while(t--)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		ll x,y,z;
		z=c;
		for(int i=0;i<=1e5;i++)
		{
			y=i*c+b;
			x=i*y+a;;
			if(x%y==a&&y%z==b&&z%x==c) break;
		}
		cout< 
C. Column Swapping 
题目
 
分析 
只能选择一次两列数，交换他们，使每一行的数都是非递减的。
 
设需要交换的列的数量为cnt：
 
当cnt=0，无需交换，可以直接选择交换1 1;
 当cnt<=2时，尝试交换两列，并判断交换后，每行的这两列位置的数字是否已与排序后的该位置的数字相等;
 当cnt>2时，那么需要交换的次数是大于1的，故无法满足要求;
 
这题自己手太弱了，赛时一直调不出来，赛后重写了一遍才过。
 
注意：数组大小2e5，数组存会爆，可以采用vector存。
 
代码 
#include
#define pb push_back
#define ll long long
#define guanliu ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
vector v[maxn],vv[maxn];
int n,m;

int check(int i,int j)
{
	for(int k=0;k>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=0;i>x;
				v[i].pb(x);
			}
			vv[i]=v[i];
			sort(vv[i].begin(),vv[i].end());
		}
		int ansi=-1,ansj=-1;
		int f=1;
		for(int i=0;i 
D. Traps 
题目
 
分析 
需要经过n个陷阱，每个陷阱的伤害是a[i]，有k次跳过陷阱的机会，但是一旦跳过一个陷阱之后，这个陷阱之后的每一个陷阱的伤害+1，求通过n个陷阱受到的最小伤害值。
 
先记录每个陷阱被跳过对总值的影响（不考虑跳过陷阱之间的影响）a[i]-(n-i)。再考虑跳过陷阱之后对其他陷阱的伤害值的影响，跳过m个陷阱，会使伤害减少m（因为跳过一个会让之后的陷阱伤害+1，并且我计算影响时计算了这个值，这个时候跳过，需要减去这个值）。
 
计算出每个独立跳过的伤害值，并从大到小跳过陷阱，再比较这个值与跳过陷阱个数，考虑继不继续跳过陷阱，一旦这个值小于，即不跳过任何陷阱，即此时伤害最小。
 
代码 
#include
#define pb push_back
#define ll long long
#define guanliu ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
ll a[maxn];

bool cmp(ll a,ll b)
{
	return a>b;
}

int main() 
{
	guanliu;
	int t;
	cin>>t;
	while(t--)
	{
		ll sum=0;
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sum+=a[i];
			a[i]=a[i]-(n-i);
		}
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<=k;i++)
		{
			if(a[i]>-i)
			{
				sum-=a[i]+i-1;
			}
			else break;
		}
		cout< 
E. MEX vs DIFF 
题目
 
分析 
一个数组a，经过最多k次将a[i]换为任意的非负整数，求最小的DIFF-MEX值。
 
DIFF：数组中不同数的个数。
 
MEX：数组中没有出现的最小的数。
 
为使最后差值最小，考虑使MEX值最大，令大于mex的不同数的个数尽量小：muitiset维护一下，让大于mex的数中，数量较少的数优先进行改变操作。
 
附上本题参考的题解
 
代码 
#include
#define pb push_back
#define ll long long
#define guanliu ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll maxn=1e5+10;
const ll mod=1e9+7;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
int a[maxn];
int n,k;
map mp,dmp;

int main() 
{
	guanliu;
	int t;
	cin>>t;
	while(t--)
	{
		mp.clear();
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			mp[a[i]]++;
		}
		dmp=mp;
		sort(a+1,a+1+n);
		int mex=0;
		while(mp[mex])
		{
			mex++;
		}
		for(int i=n,j=k;i&&j;i--,j--)
		{
			if(a[i] s;
		for(auto i : dmp)
		{
			if(i.first>mex) 
			{
				s.insert(i.second);
			}
		}
		int dif=mex;
		for(auto i : s)
		{
			if(k>=i) k-=i;
			else dif++;
		}
		cout<