WorkApplication是一家日企，主要办公地在东京、新加坡、上海等地。
第一题：n的全排列中有多少个排列逆序数为k
输入两个数字n，k，两个数字的范围都是[1,1000]。
输出：n的全排列中有多少个数字的逆序数等于k。
Example
输入4 1
输出3
有以下三种情况：
1 2 4 3；
2 1 3 4；
1 3 2 4
这道题一猜就是动态规划。在前n-1个数字已经排好了的情况下，将第n个数字插入进去。这第n个数字特别大，所以把它插入不同位置，会增加不同的逆序数：
f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,max(k-n+1,0))
最后一项的意思是：将第n个数字插入到前n-1个数字中，最多使得逆序数增加n-1，所以第n个数字插入之前，前面n-1个数字的逆序数必须为k-(n-1)。
化简一下可以得到f(n,k)更简单的递推关系：
由f(n,k)=f(n-1,k)+f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,max(k-n+1,0))，
f(n,k-1)=f(n-1,k-1)+f(n-1,k-2)+...+f(n-1,max(k-(n-1)+1,0))，
得到：
- 当k<n时，f(n,k)=f(n-1,k-1)+f(n,k-1)
- 当k>=n时，f(n,k)=f(n-1,k-1)+f(n,k-1)-f(n-1,k-n)
如果照着上面的思路没想通，可以打表、找规律。打表必须打表到6才能发现规律。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int a[10];
int cnt[30];
void visit(int n){
int s = 0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (a[i]>a[j])s++;
}
}
cnt[s]++;
}
void go(int n, int ind){
if (ind == n - 1){
visit(n);
return;
}
for (int i = ind; i < n; i++){
swap(a[i], a[ind]);
go(n, ind + 1);
swap(a[i], a[ind]);
}
}
int main(){
freopen("in.txt", "r", stdin);
for (int i = 0; i < 7; i++){
memset(cnt, 0, sizeof(cnt));
for (int j = 0; j < i; j++)a[j] = j;
go(i, 0);
for (int j = 0; j < 30; j++){
printf("%d ", cnt[j]);
}
puts("");
}
return 0;
}
终于拿下了这道题：
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
int n, k;
const int N = 1007;
int a[N][N];
int main(){
freopen("in.txt", "r", stdin);
memset(a, 0, sizeof(a));
cin >> n >> k;
for (int i = 1; i <= n; i++)a[i][0] = 1;
for (int i = 2; i <= n; i++){
for (int j = 1; j <= k; j++){
a[i][j] = a[i][j-1] + a[i-1][j];
if (j >= i){
a[i][j] -= a[i - 1][j - i];
}
a[i][j] = (a[i][j]%1000+1000)%10000;
}
}
cout << a[n][k] << endl;
return 0;
}
第二题：给定数组a[n]，选取若干数字求和，能否使得被m整除
输入：第一行两个数字n和m，第二行n个数字表示数组a[n]的内容。n的取值范围[1,30]，m的取值范围[1,1e6],a[n]中的数字取值范围为[1,1e9]
输出：Yes或者No，表示能否从a[n]中找到几个数字，使得它们的和为m的倍数。
解决思路：建立一个数组b[N]，b[i]表示第i个数字有没有被访问过。在当前b[N]的基础上，加上一个数字a[i]得到新的b[N]，就看最后能不能够到达0。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 1e6 + 7;
int n, m;
int a[37];
int b[N];
int main(){
freopen("in.txt", "r", stdin);
cin >> n >> m;
bool hasAns = 0;
for (int i = 0; i < n; i++){
cin >> a[i];
a[i] %= m;
if (a[i] == 0)hasAns = 1;
}
if (hasAns)goto over;
memset(b, 0, sizeof(b));
b[0] = 1;
for (int i = 1; i < n; i++){
for (int j = 0; j <= m; j++){
if (b[j] && b[j] != i + 2){//表示j数字不是本轮产生的
int id = (j + a[i]) % m;
if (b[id] == 0||id==0){//如果id未访问过，或者id=0即将game over
b[id] = i + 2;//表示id是由i产生的
if (id == 0){
hasAns = true;
goto over;
}
}
}
}
}
over:cout << (hasAns ? "Yes" : "No") << endl;
return 0;
}