今天学了莫比乌斯反演，竟然破天荒的自己推出来了一个题目！有关莫比乌斯反演的题解，和上次的01分数规划的题解明天再写吧~~~
学长们都在刷面试题，我也去试了试，120分钟，写出6题要有一点熟练度才行。先填上水题咯~·~~，4题可以进面试了，还是可以去面试的啦，开心~~~
多线程协作打印（完美世界2017秋招真题）
建立m个线程，每个线程只能打印一种字符，要求线程同时运行，交替打印n次字符。
比如: n=3 m=2打印字符为A和B。要求线程1打印3次A，线程2打印3次B，在屏幕输出ABABAB
注意: 需要检查输入有效性，遇到错误输入时，请打印error并安全退出
输入 打印次数n和字符序列。比如：2 ABC(三个字符需要三个打印线程) | 样例输入 2 ABC |
输出 每个线程打印n次字符，交替打印。在屏幕上输出n次字符序列 | 样例输出 ABCABC |
时间限制 C/C++语言：1000MS 其他语言：3000MS | 内存限制 C/C++语言：65536KB 其他语言：589824KB |
#include <bits/stdc++.h> using namespace std; int main()
{
int n;
char str[];
scanf("%d%s",&n,str);
if(n<) {
puts("error");
return ;
} for(int i = ; i < n; i++) {
printf("%s",str);
}
puts(""); return ;
}
2.编程题
按序找到数组中最小的k个数（完美世界2017秋招真题）
对于一个无序数组，数组中元素为互不相同的整数，请返回其中最小的k个数，顺序与原数组中元素顺序一致。
输入 第一行为数组的长度n，需要返回的数目k，n >= k 接下来n行为数组的n个元素，每行为一个整数 | 样例输入 4 2 1 2 3 4 |
输出 输出为k行，每行为一个整数 | 样例输出 1 2 |
时间限制 C/C++语言：100MS 其他语言：2100MS | 内存限制 C/C++语言：10KB 其他语言：524298KB |
排序两次即可！
最短最优升级路径（完美世界2017秋招真题）
游戏网站提供若干升级补丁，每个补丁大小不一，玩家要升级到最新版，如何选择下载哪些补丁下载量最小。
输入 第一行输入 第一个数为用户版本 第二个数为最新版本，空格分开 接着输入N行补丁数据 第一个数补丁开始版本 第二个数为补丁结束版本 第三个数为补丁大小，空格分开 | 样例输入 1000 1050 1000 1020 50 1000 1030 70 1020 1030 15 1020 1040 30 1030 1050 40 1040 1050 20 |
输出 对于每个测试实例，输出一个升级路径以及最后实际升级的大小 | 样例输出 1000->1020->1040->1050(100) |
时间限制 C/C++语言：1000MS 其他语言：3000MS | 内存限制 C/C++语言：65536KB 其他语言：589824KB |
最短路记录路径即可！
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int maxn = ;
const ll inf = 9876543212345678LL; struct Edge {
int from,to;
ll dist;
}; struct HeapNode {
ll d;
int u;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
}; bool broken[][]; struct Dij {
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
ll d[maxn];
int p[maxn]; void AddEdge(int from,int to,ll dist) {
edges.push_back((Edge){from,to,dist});
m = edges.size();
G[from].push_back(m-);
} long long dij(int s,int t) {
priority_queue<HeapNode> Q;
for(int i = ; i < n; i++)
d[i] = inf;
d[s] = ;
memset(done,,sizeof(done));
Q.push((HeapNode){,s});
while(!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = ; i <(int)G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if(d[e.to]>d[u]+e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
} return d[t];
} }sol; map<int,int> mp; int main()
{
freopen("in.txt","r",stdin);
int s,t;
scanf("%d%d",&s,&t); int cnt = ;
mp[s] = ;
mp[t] = ; int u,v,c;
while(scanf("%d%d%d",&u,&v,&c)!=EOF) {
if(mp.count(u)==)
mp[u] = cnt++;
if(mp.count(v)==)
mp[v] = cnt++; u = mp[u];
v = mp[v];
sol.AddEdge(u,v,c);
} printf("%I64d\n",sol.dij(,)); return ;
}
孪生质数（完美世界2017秋招真题）
数学中有很多奇特的现象，孪生质数就是一种(孪生素数就是指相差2的质数对，例如3和5，5和7，11和13…)，现在要求输出所有在m和n范围内的孪生质数。
输入 输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999） | 样例输入 100 150 |
输出 对于每个测试实例，要求输出所有在给定范围内孪生质数，就是说，输出的孪生质数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开 ; 如果给定的范围内不存在孪生指数，则输出 “no” ; 每个测试实例的输出占一行。 | 样例输出 101 103 107 109 137 139 |
时间限制 C/C++语言：1000MS 其他语言：3000MS | 内存限制 C/C++语言：65536KB 其他语言：589824KB |
即时战略游戏编队（完美世界2017秋招真题）
题目描述
你正在玩一个RST（即时战略）游戏。此时你已经有很多队士兵，每一队里的士兵战队力相同。该游戏士兵种类以战斗力区分，既战斗力一样的士兵算作一种。你想重新调整编队，将现有的队列合并成战斗力相同的两队，请想出有多少种编队方法吧。
比如：你现在有两队士兵，第一队有4个士兵，每个士兵战斗力都是1，第二队有2个士兵，每个士兵战斗力都是2. 这时你有三种编队方法，可以将这些士兵合并成战斗力相同的两个队伍：
方法一：队伍1有4个战斗力为1的士兵，队伍2有2个战斗力为2的士兵，两队的战斗力都是4
方法二：队伍1有2个战斗力为2的士兵，队伍2有4个战斗力为1的士兵，两队的战斗力都是4
方法三：队伍1有2个战斗力为1的士兵和1个战斗力为2的士兵，队伍2有2个战斗力为1的士兵和1个战斗力为2的士兵，两队的战斗力都是4
输入 两个int型数组，长度均为n（0 int[] count：里面的元素代表每一队士兵的士兵数量，大于0小于1000 int[] value：里面的元素代表每一队士兵的士兵战斗力，大于0小于1000 注意：count和value数组的队伍是一一对应的 例如，上面题目描述中的例子里： int[] count = {4, 2} //表示你一共有两队士兵，这两队士兵的士兵数量分别为4和2 int[] value = {1, 2} //表示你这两队士兵的战斗力分别为1和2（并且是跟count数组一一对应的。也就是说，士兵数量为4的队伍每个士兵的战斗力为1，士兵数量为2的队伍每个士兵的战斗力为2） | 样例输入 对于每个测试实例，要求输出一个long值，表示有多少种均分法（有多少种方法可以将你的所有队伍合并成战斗力相同的两队）。 |
输出 两个int型数组，长度均为n（0 int[] count：里面的元素代表每一队士兵的士兵数量，大于0小于1000 int[] value：里面的元素代表每一队士兵的士兵战斗力，大于0小于1000 注意：count和value数组的队伍是一一对应的 例如，上面题目描述中的例子里： int[] count = {4, 2} //表示你一共有两队士兵，这两队士兵的士兵数量分别为4和2 int[] value = {1, 2} //表示你这两队士兵的战斗力分别为1和2（并且是跟count数组一一对应的。也就是说，士兵数量为4的队伍每个士兵的战斗力为1，士兵数量为2的队伍每个士兵的战斗力为2） | 样例输出 {4, 2} {1, 2} |
时间限制 C/C++语言：2000MS 其它语言：4000MS | 内存限制 C/C++语言：65536KB 其它语言：589824KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> str2int(string str) {
vector<int> res;
int num = ;
for(int i = ; i < (int)str.length(); i++) {
if(str[i] == ' ') continue;
if(isdigit(str[i])) {
num *= ;
num += str[i] - '';
}
if(str[i] == ',' || i == (int)str.length() - ) {
res.push_back(num);
num = ;
}
}
return res;
}
int main()
{
// freopen("in.txt","r",stdin);
string str;
map<int,int> mp;
getline(cin,str);
str = str.substr(,str.length()-);
//cout <<str;
vector<int> cnt = str2int(str);
getline(cin,str);
str = str.substr(,str.length()-);
vector<int> val = str2int(str);
int sum = ;
for(int i = ; i < (int)cnt.size(); i++) {
sum+=val[i]*cnt[i];
if(mp.count(val[i])) {
mp[val[i]] +=cnt[i];
}
else mp[val[i]] = cnt[i];
}
if(sum%) {
puts("");
return ;
}
cnt.clear();
val.clear();
cnt.push_back();
val.push_back();
for(auto it = mp.begin(); it!=mp.end(); it++) {
val.push_back(it->first);
cnt.push_back(it->second);
}
int n = mp.size();
int m = sum/;
int dp[n+][m+];
memset(dp,,sizeof(dp));
dp[][] = ;
for(int i = ; i <= n; i++) {
for(int j = ; j <=cnt[i]; j++) {
for(int k = ; k <= m; k++) {
if(k>=j*val[i])
dp[i][k] +=dp[i-][k-j*val[i]];
}
}
}
cout<<dp[n][m]<<endl;
return ;
}