总结

这次竞赛题目不难，但是蛮久没刷数位DP了，还是花了一些时间去推导公式才解决$T4$，浪费了不少时间，排名不是很理想。

题目列表

1.字符串全排列

题目描述

对K个不同字符的全排列组成的数组, 面试官从中随机拿走了一个, 剩下的数组作为输入, 请帮忙找出这个被拿走的字符串? 比如[“ABC”, “ACB”, “BAC”, “CAB”, “CBA”] 返回 “BCA”

分析

全排列数组一共$n=k!$个排列，这意味着，任意一个字符出现在第$i$位的次数都是$n/k$，所以可以使用hash表统计出现在各个位置上的字符的次数，如果第$i$个位置上字符$x$出现的次数不是$n/k$，就说明被拿走的字符串的第$i$个位置就是$x$。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<char, int> m;
std::string solution(int n, std::vector<string>& vec) {
	string res;
	if(!n) return res;
	int k = vec[0].size();
	string s = vec[0];
	for(int i = 0; i < k; i++) m[s[i]] = i;
	int t = (n + 1) / k;
	for(int i = 0; i < k; i++) {
		vector<int> cnt(k, t);
		for(int j = 0; j < n; j++) {
			cnt[m[vec[j][i]]]--;
		}
		for(int j = 0; j < k; j++) {
			if(cnt[j]) {
				res += s[j];
				break;
			}
		}
	}
	return res;
}
int main() {
	int n;
	vector<string> vec;
	cin>>n;
	string x;
	for(int i = 0; i < n; i++) {
		cin>>x;
		vec.push_back(x);
	}
	std::string result = solution(n,vec);
	std::cout<<result<<std::endl;
	return 0;
}

2.小Q新式棋盘

题目描述

已知棋盘大小为n*n。 每个位置都有自己的权值q。 该棋盘中有多少对行权值和小于列权值和。

输入描述：

第一行输入整数n。(1<=n<=100)表示棋盘的大小
以下n行每行输入n个整数表示棋子的权值。(1<=a<=1000)

输出描述：

输出小Q的分值。

输入样例：

3
1 2 3
1 2 3
1 2 3

输出样例：

3

分析

本题相当于求出n个行权值和数组$row$和n个列权值和数组$col$后，对$row$中的每个元素，在$col$中找出大于它的元素个数，累加起来就是答案。分别对这两个数组排序，然后暴力枚举即可。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
const int N = 1005;
int g[N][N];
int row[N], col[N];
int main() {
	int n;
	cin>>n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin>>g[i][j];
			row[i] += g[i][j];
			col[j] += g[i][j];
		}
	}
	sort(row, row + n);
	sort(col, col + n);
	int res = 0;
	for(int i = 0; i < n; i++) {
		int x = row[i];
		int j = 0;
		while(j < n && col[j] <= x) j++;
		res += n - j;
	}
	cout<<res<<endl;
	return 0;
}

3. 因数-数字游戏

题目描述

小Q的柠檬汁做完了。 掏出了自己的数字卡牌。 想要和别人做数字游戏。 可是她又不想要输掉游戏。 她制定好规则，每 次每个人只能把这个牌换成它的因子的某个牌。 但是这个因子不能是1或者整数本身。 现在给出整数n。 两个人开始做游 戏，谁无法再给出因子牌则该人胜利，如果该整数无因子牌直接视为先手胜利，请判断先手在最优策略状态下能否必胜，

分析

本题考察博弈论。其实就是简单的数论题目。

• 如果初始的数字是1或者质数，则先手无法给出因子牌，先手获胜；
• 如果初始的数字有两个因子（不包括1和自身)，那么先手只能给出其中一个因子，后手拿到的就是质数，后手获胜；
• 如果初始数字有两个以上的因子，先手拿掉大部分因子，只留下包含两个因子的数字给后手，如此一来，后手面临的就是第二种情况，先手获胜。

因此，本题只需要求出初始数字的因子个数，因子个数是2则后手获胜，否则先手获胜。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
	ll n;
	std::cin>>n;
	int cnt = 0;
	for(ll i = 2; i <= n / i; i++) {
		if(n % i == 0) {
			ll x = n;
			while(x % i == 0) {
				cnt++;
				x /= i;
			}
			ll j = n / i;
			if (j != i) {
				x = n;
				while(x % j == 0) {
					cnt++;
					x /= j;
				}
			}
		}
	}
	if(cnt == 2) cout<<2<<endl;
	else cout<<1<<endl;
	return 0;
}

4.题目名称：编码

题目描述

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。 字母 表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的长度相同的单词放在 一起，按字典顺序排列（a…z，ab…az，bc…bz…）一个单词的编码就对应着它在整个序列中的位置。 你的任务就是对 于所给的单词，求出它的编码。

输入描述：

仅一行，被编码的单词。

输出描述：

仅一行，对应的编码。如果单词不在序列中，输出0。

输入样例：

ab

输出样例：

27

分析

如果将字母看成数字，本题就相当于定义了一种"升序数"，比如“456”，第1个升序数是0，第11个是12。给定一个升序数，求它的编号。这就是经典的数位DP问题了，数位DP问题一段时间不做就生疏了，这里再借助本题回忆下求解过程。

首先，定义基本的状态数组。$f[i][j]$表示以$j$为开头的$i$位数的数量，自然要加上限制条件，比如本题就是表示以$j$为开头的$i$位数的编码数量。

状态转移方程：$f[i][j]=f[i-1][j+1]+f[i-1][j+2]+...$，也就是说，只要$i-1$位数的首字符大于$j$，$j$追加上这个$i-1$位数都可以转移为以$j$开头的$i$位数的状态。再来看状态$f[i][j+1]$，$f[i][j+1]=f[i-1][j+2]+f[i-1][j+3]+...$，比较下两个状态的状态转移方程，可以得出

$$f[i][j]=f[i-1][j+1]+f[i][j+1]$$

状态边界是$f[1][j]=1$，表示以$j$为首字符的一位数编码个数是1。

上面的基本状态数组是数位DP中最容易的一部分，数位DP的难点在于按位遍历分类讨论。

以s= "$bdf$"为例，我们自右而左遍历：

• 遍历到$f$，由于s是三位数，所以所有的1位数都小于它，我们给最终的编号$res$加上一位数的编码$f[1][j]$，其中$0<=j<26$。然后再加上以$bd$开头的，小于$bdf$的三位数$bde$。
• 遍历到$d$，给$res$加上所有的两位数的编码$f[2][j]$，再加上以$b$开头，第二位数小于$d$的三位数，这就确定了第二位数是$c$，相当于加上$f[2][c]$就可以了。
• 遍历到$b$，最高只有三位，所以这里不需要加上所有的三位数了，只需要给$res$加上以小于$b$的字符开头的三位数的个数，即$f[3][a]$即可。

此时的$res$就是s前面编码的个数，那么s自身的编码就是$res+1$。

观察上面的遍历过程可以发现，所有小于"bdf"的编码，一位和两位数编码分布在前面的两轮遍历，剩下的编码我们通过固定前面字符的方式来进行状态划分：

• 遍历$f$，固定前面的$bd$，枚举第三位大于$d$小于$f$的状态；
• 遍历$d$，固定前面的$b$，枚举第二位大于$b$小于$d$的状态。
• 遍历$b$，枚举第一位小于$b$的三位数状态。

用数字表示更为直观，比如247，寻找小于它的升序数的个数。遍历7，枚举了所有的1位数（0到9），以及小于247的前两位是24的三位升序数（245，246）；遍历4，枚举了所有的两位升序数（12，13，…,23，…),以及小于247的首位是2的三位升序数（234，…,239,245,246）；遍历2，枚举所有首位小于2的三位升序数（123，123，…)。

数位DP之所以难，就是划分的状态多，求小于n位编码x的个数，需要划分状态为：1位数编码，2位数编码，…，n-1位数编码，第一位小于x的首位的n位数编码，第一位等于x的首位数且第二位小于x的第二位的n位数编码，…，前n-1位等于x的前n-1位且最后一位小于x的最后一位的n位数编码。

总结下数位DP的求解过程。

• 求解基本的状态数组f
• 遍历时加上小于n位数的状态
• 遍历时加上前面位数固定的状态

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
typedef long long ll;
ll f[7][30];
bool check(string &s) {
	int n = s.size();
	for(int i = 1; i < n; i++) {
		if(s[i] <= s[i-1]) return true;
	}
	return false;
}
int main() {
	string s;
	cin>>s;
	ll res = 0;
	int n = s.size();
	if(n > 6 || check(s)) cout<<0<<endl;
	else {
		for(int i = 0; i < 26; i++) f[1][i] = 1;
		for(int i = 2; i <= n; i++) {
			for(int j = 25; j >= 0; j--) {
				f[i][j] = f[i][j+1] + f[i-1][j+1];
			}
		}
		for(int i = n - 1; i >= 0; i--) {
			int x = s[i] - 'a';
			int last = 0;
			if(i) last = s[i - 1] - 'a' + 1;
			int k = n - i;
			for(int j = last; j < x; j++) res += f[k][j];
			if(i) {
                for(int j = 0;j < 26;j++) res += f[k][j];
			}
		}
		cout<<res + 1<<endl;
	}
	return 0;
}