Codeforces Round #792 (Div. 1 + Div. 2)

A. Digit Minimization

题目链接：Problem - A - Codeforces

样例输入： 

3
12
132
487456398

样例输出：

2
1
3

题意：给定一个长度小于10的字符串，Alice和Bob轮流操作，Alice每次可以选择将其中的两个字符交换位置，而Bob每次删除最后一个字符，最后剩下一个字符，问Alice最后能够得到的最小的字符是多少？

分析：其实模拟不难发现，Alice可以把最后想得到的字符一开始通过交换换至前面，然后就可以最后剩下这个字符，根据贪心我们肯定是剩下原串中最小的那个字符，但是需要注意的一点是Alice是必须要进行操作的，如果一开始是两个字符，那么Alice只能最后剩下第二个字符。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int x;
		scanf("%d",&x);
		if(x<100) printf("%d\n",x%10);
		else
		{
			int mi=9;
			while(x)
			{
				mi=min(mi,x%10);
				x/=10;
			}
			printf("%d\n",mi);
		}
	}
	return 0;
}

B. Z mod X = C

题目链接：Problem - B - Codeforces

样例输入： 

4
1 3 4
127 234 421
2 7 8
59 94 388

样例输出：

12 11 4
1063 234 1484
25 23 8
2221 94 2609

题意：给定一个a,b,c，让我们输出一组x，y，z满足xmody=a, ymodz=b, zmodx=c

分析：直接设x=k1*y+a,y=k2*z+b,z=k3*x+c，然后联立方程令k3=0，k1=k2=1即可解得x=a+b+c,y=b+c,z=c

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		printf("%d %d %d\n",a+b+c,b+c,c);
	}
	return 0;
} 

C. Column Swapping

题目链接：Problem - C - Codeforces

 样例输入：

5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2

样例输出：

1 1
-1
1 2
1 3
1 1

题意：我们定义一行数是好的当且仅当我们对某对(i,j)(i可以等于j)进行一次交换后可以使得这行数是非递减的，现在给定一个矩阵，问我们能否正好交换两列使得每一行都是好的

分析：这个题其实就是直接暴力找每一行需要交换的两个数的位置即可，如果出现两列需要交换的位置不一样就直接输出-1，否则输出这两列的编号，但是这道题细节比较多，下面给出两组容易出错的样例：

1 3

2 2 1

1 3

2 1 1

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N],n,m;
int find(int i,int j)
{
	return (i-1)*m+j;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&m);
		int l=0,r=0;
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			int tl=0,tr=0;
			for(int j=1;j<=m;j++)
			{
				scanf("%d",&a[find(i,j)]);
				if(j==1) continue;
				if(a[find(i,j)]<a[find(i,j-1)])
				{
					if(!tl)
						tl=j-1;
					else if(!tr)
						tr=j;
					else
						flag=false;
				}
			}
			if(tl&&(!tr)) tr=tl+1;
			while(tl>1&&(a[find(i,tl)]==a[find(i,tl-1)])) tl--;
			while(tr<m&&(a[find(i,tr)]==a[find(i,tr+1)])) tr++;
			if(!tl) continue;
			if(!(l||r)) l=tl,r=tr;
			else
			{
				if((l!=tl)||(r!=tr)) flag=false;
			}
		}
		for(int i=1;i<=n;i++)
		{
			swap(a[find(i,l)],a[find(i,r)]);
			for(int j=1;j<m;j++)
				if(a[find(i,j)]>a[find(i,j+1)]) flag=false;
		}
		if(flag) printf("%d %d\n",l>0?l:1,r>0?r:1);
		else puts("-1");
	}
	return 0;
}

D. Traps

题目链接：Problem - D - Codeforces

 样例输入：

5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1
7

样例输出：

0
21
9
6
0

题意：一开始有n个陷阱，每个陷阱都有一个损失值a[i]，我们有k次跳过陷阱的机会，但是我们每跳过一次陷阱那么后面所有的陷阱的损失值就会+1，问我们在经过n个陷阱后的最小损失。

分析：这道题我一开始写的是动态规划，设f[i][j]表示经过前i个陷阱使用了j次跳跃机会的最小损失，为了使得状态转移方程没有后效性，假如我们后面还有m个陷阱，还有k-j次跳跃机会，那么也就是说我们有m-(k-j)个陷阱都不能跳过，而且会因为本次的跳跃使得损失值+1，所以我们直接看作当前跳跃的代价即可，这样我们就能通过枚举第i个陷阱跳还是不跳来进行动态转移了。不过当时没细看数据范围，超时了，不过通过这个分析过程我找到了贪心的思路：

就是说，假如我们没有使用跳跃那么我们的损失值就是,假设当前是第i个陷阱，我们还有j次跳跃机会，那么如果当前使用跳跃机会我们的损失值会降低a[i]-(n-i-(j-1))，其中(n-i-(j-1))就是因为本次跳跃而导致的后续损失增加的值，那么我们就是选择m个a[i]使得最大，对于a[i]-(n-i-(j-1))变形发现等于a[i]+i-(n-j+1)，其中n-j+1是不会跟着我们所选择跳跃的位置变化而变化的，所以我们可以直接求出来，至于a[i]+i我们可以直接排序求一下最大的m个陷阱即可。细节见代码：

动态规划超时代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
long long f[2][N];
int a[N];
//f[i][j]表示前i个陷阱中用了j次跳跃后所受到的最小伤害
int main()
{
	int T;
	cin>>T;
	int n,m;
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		f[0][0]=0;
		for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			if(j==0)
			{
				f[i&1][j]=f[(i-1)&1][j]+a[i];
				continue;
			}
			f[i&1][j]=min(f[(i-1)&1][j]+a[i],f[(i-1)&1][j-1]+max(0,(n-i)-(m-j)));
		}
		printf("%lld\n",f[n&1][m]);
	}
	return 0;
} 

贪心代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int main()
{
	int T;
	cin>>T;
	int n,m;
	while(T--)
	{
		scanf("%d%d",&n,&m);
		long long ans=0;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]),ans+=a[i],b[i]=a[i]+i;
		for(int i=0;i<m;i++)
			ans+=n-i;
		sort(b+1,b+n+1);
		for(int i=n;i>n-m;i--)
			ans-=b[i];
		printf("%lld\n",ans);
	}
	return 0;
}