【csp模拟赛1】T1 心有灵犀

【题目描述】

爱玩游戏的小 Z 最近又换了一个新的游戏。这个游戏有点特别，需要两位玩家心有灵犀通力合作才能拿到高分。游戏开始时，两位玩家会得到同一个数字 N，假设这个数字共有 t 位数码，然后两位玩家可以分别对这个数字的 t 位数码进行 K 次交换，但要求每次交换后得到的数字不能有前导 0，最后游戏得分为两位玩家的最终数字的差的绝对值。小 Z 想知道，对于给定的数字，最大得分是多少。

【输入格式】

第一行为测试数据组数 T（1≤T≤10）。每组测试数据仅一行，包含两个整数 N 和 K，含义见题面。

【输出格式】

对于每组数据输出仅一行，包含一个整数，表示最大得分。

【样例输入】

12 1

213 2

998244353 1

998244353 2

998244353 3

【样例输出】

198

699599970

759599973

764599473

【样例解释】

第一个数据中，变换后可得到 21 与 12，差值是 9；第二个数据中，变换后可得到 321 与 123，差值是 198；后三个数据，变换 1/2/3 次分别可得到 998544323 与 298944353，998544332 与 238944359，998544332 与 233944859，差值分别为 699599970，759599973 与 764599473。

思路：

这道题贪心错误，不能直接找后面靠后的比他大的位和他交换，989244343可以hack掉，或者别的数据都可以，直接爆搜，从高位到低位，注意求最小值时要特判前导零 + dfs。

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define INF 999999999

using namespace std;

inline int read() {

	int x = 0,f = 1; char s = getchar();

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

	return x * f;

}

int T;

int n,m;

int A,B,tot;

int num[12],cnt;

int a[12],b[12];

inline void dfs_min(int k,int opt) {

	if(k <= 0 || opt >= tot) {

		int sum = 0;

		for(int i = 1;i <= tot;i ++) sum = sum * 10 + a[i];

		A = min(A,sum);

		return ;

	}

	if(opt == 1) {

		for(int i = opt + 1;i <= tot;i ++)

			if(a[i] <= a[opt] && a[i] != 0) {

				swap(a[i],a[opt]);

				dfs_min(k - 1,opt + 1);

				swap(a[i],a[opt]);

			}

	}

	else {

		for(int i = opt + 1;i <= tot;i ++)

			if(a[i] <= a[opt]) {

				swap(a[i],a[opt]);

				dfs_min(k - 1,opt + 1);

				swap(a[i],a[opt]);

			}

	}

	dfs_min(k,opt + 1);

}

inline void dfs_max(int k,int opt) {

	if(k <= 0 || opt >= tot) {

		int sum = 0;

		for(int i = 1;i <= tot;i ++) sum = sum * 10 + b[i];

		B = max(B,sum);

		return ;

	}

	for(int i = opt + 1;i <= tot;i ++)

		if(b[i] >= b[opt]) {

			swap(b[i],b[opt]);

			dfs_max(k - 1,opt + 1);

			swap(b[i],b[opt]);

		}

	dfs_max(k,opt + 1);

}

inline void Work() {

	memset(a,0,sizeof(a));

	memset(b,0,sizeof(b));

	memset(num,0,sizeof(num));

	cnt = tot = 0;

	n = read(),m = read();

	A = INF,B = 0;

	while(n) num[++ cnt] = n % 10,n /= 10;

	for(int i = cnt;i;i --)

		a[++ tot] = num[i],b[tot] = num[i];

	dfs_min(m,1); dfs_max(m,1);

	cout << B - A << endl;;

}

int main() {

	freopen("cooperate.in","r",stdin);

	freopen("cooperate.out","w",stdout);

	T = read();

	while(T --) Work();

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

【csp模拟赛1】T1 心有灵犀

最新文章

热门文章