1. 双核处理
一种双核CPU的两个核能够同时处理任务，现在有n个已知数据量的任务需要交给CPU处理，
假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照
任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，
求这个最小的时间
输入描述：
输入包括两行：
第一行为整数n(1 <= n <= 50)
第二行为n个整数length[i](1024 <= length[i] <= 4194304),表示每个任务的长度为length[i]kb,
每个数均为1024的倍数。
输出描述：
输出一个整数，表示最少需要处理的时间
输入例子：
5
3072 3072 7168 3072 1024
输出例子：
9216
//动态规划
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> arr(n);
int sum = 0;
for(int i=0; i<n; i++)
{
cin>>arr[i];
arr[i] >>= 10;
sum += arr[i];
}
// dp[j]表示在容量为j的情况下可存放的重量
// 如果不放arr[i]重量为dp[j],如果放arr[i]重量为dp[j-arr[i]] + arr[i];
vector<int> dp(sum/2 + 1);
for(int i=0; i<n; i++)
{
for(int j=sum/2; j>=arr[i]; j--)
dp[j] = max(dp[j], dp[j-arr[i]] + arr[i]);
}
cout<<(max(dp[sum/2], sum - dp[sum/2]) << 10)<<endl;
return 0;
}
2.赶去公司
终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要
立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，
小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去
办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打
车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime
时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费
多少时间去公司。
输入描述：
输入数据包括五行:
第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)
第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔
输出描述：
输出一个整数表示，小易最快能感到办公室的时间
输入例子：
2
-2 -2
0 -2
-4 -2
15 3
输出例子
42
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, tx[60], ty[60];
int gx, gy;
int walkTime, taxiTime;
cin>>n;
for(int i=0; i<n; i++)
cin>>tx[i];
for(int i=0; i<n; i++)
cin>>ty[i];
cin>>gx>>gy;
cin>>walkTime>>taxiTime;
int ans = (abs(gx - 0) + abs(gy - 0)) * walkTime;
int curCost = 0;
for(int i=0; i<n; i++)
{
curCost = (abs(tx[i] - 0) + abs(ty[i] - 0)) * walkTime
+ (abs(gx - tx[i]) + abs(gy - ty[i])) * taxiTime;
ans = min(ans, curCost);
}
cout<<ans<<endl;
return 0;
}3.调整队形
在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是
男生，有一些是女生，男生用'B'表示，女生用'G'表示。小朋友们都很顽皮，当一个男生挨着的
是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的
情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要
尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述：
输入数据包括一个长度为n且只包括G和B的字符串. n不超过50.
输出描述：
输出一个整数，表示最少需要的调整队伍的次数
输入例子：
GGBBG
输出例子：
2
// 目标状态只有两种可能，形如：BBBBGGG GGGGBBBB
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
int rb = 0, rg = 0;
int b = 0, g = 0;
cin>>s;
for(int i=0; i<s.length(); i++)
{
if(s[i] == 'B')
{
rb += i - b;
b++;
}
else
{
rg += i - g;
g++;
}
}
cout<<min(rb, rg)<<endl;
return 0;
}4.消除重复元素
小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后
出现的那个。小易遇到了困难,希望你来帮助他。
输入描述：
输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔
输出描述
输出消除重复元素之后的序列，以空格分隔，行末无空格
输入例子：
9
100 100 100 99 99 99 100 100 100
输出例子：
99 100
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[60];
map<int, int> m;
vector<int> ret;
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
for(int i=0; i<n; i++)
m[a[i]]++;
for(int i=0; i<n; i++)
{
m[a[i]]--;
if(m[a[i]] == 0)
ret.push_back(a[i]);
}
int len = ret.size();
for(int i=0; i<len; i++)
{
if(i == len - 1)
printf("%d\n", ret[i]);
else
printf("%d ", ret[i]);
}
return 0;
}
5.魔力手环
小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候
就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个
数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自
动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入描述：
输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.
输出描述：
输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。
输入例子：
3 2
1 2 3
输出例子：
8 9 7
分析： 把手环数字转为一个向量，然后乘
[1 1 0 0 0]
[0 1 1 0 0]
[0 0 1 1 0]
[0 0 0 1 1]
[1 0 0 0 1]
这个矩阵N次即可。用矩阵快速幂边算边求模
#include <bits/stdc++.h>
using namespace std;
void multiply(int A[50][50], int B[50][50], int C[50][50], int n)
{
int T[50][50];
memset(T, 0, sizeof(T));
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
T[i][j] = (T[i][j] + A[i][k] * B[k][j]) % 100;
}
memcpy(C, T, sizeof(T));
}
void myPower(int A[50][50], int R[50][50], int k, int n)
{
if(k == 0)
{
memset(R, 0, sizeof(R));
for(int i=0; i<n; i++)
R[i][i] = 1;
}
else if(k % 2 == 0)
{
myPower(A, R, k/2, n);
multiply(R, R, R, n);
}
else
{
myPower(A, R, k-1, n);
multiply(A, R, R, n);
}
}
vector<int> solve(vector<int>& seq, int k)
{
int A[50][50];
int R[50][50];
int n = seq.size();
memset(A, 0, sizeof(A));
for(int i=0; i<n; i++)
A[i][i] = A[i][(i+1)%n] = 1;
myPower(A, R, k, n);
vector<int> res;
int sum = 0;
for(int i=0; i<n; i++)
{
sum = 0;
for(int j=0; j<n; j++)
{
sum = (sum + R[i][j] * seq[j]) % 100;
}
res.push_back(sum);
}
return res;
}
int main()
{
int n, k;
cin>>n>>k;
vector<int> seq(n);
for(int i=0; i<n; i++)
cin>>seq[i];
vector<int> ans = solve(seq, k);
for(int i=0; i<n; i++)
i == 0 ? cout<<ans[i] : cout<<" "<<ans[i];
return 0;
}
6.工作安排
现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串
表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程
师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两
种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有
多少种不同工作安排计划。
输入描述：
输入数据有n+1行：
第一行为工程师人数n(1 ≤ n ≤ 6)
接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)
输出描述：
输出一个整数，表示有多少种不同的工作安排方案
输入例子：
6
012345
012345
012345
012345
012345
012345
输出例子：
720
#include <bits/stdc++.h>
using namespace std;
int ret = 0;
int n;
vector<string> a;
int b[6] = {1, 1, 1, 1, 1, 1};
void dfs(int i)
{
if(i == a.size())
ret++;
else
{
for(int j=0; j<a[i].length(); j++)
{
if(b[a[i][j] - '0'])
{
b[a[i][j] - '0'] = 0;
dfs(i+1);
b[a[i][j] - '0'] = 1;
}
}
}
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
string str;
cin>>str;
a.push_back(str);
}
dfs(0);
cout<<ret<<endl;
return 0;
}7.集合
小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述：
输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔
输出描述：
输出集合中元素的个数
输入例子：
1 10 1 1
输出例子：
10
#include <bits/stdc++.h>
using namespace std;
int main()
{
int w, x, y, z;
set<pair<int, int> > s;
cin>>w>>x>>y>>z;
for(int i=w; i<=x; i++)
{
for(int j=y; j<=z; j++)
{
int d = __gcd(i, j);
int ii = i / d;
int jj = j / d;
s.insert(make_pair(ii, jj));
}
}
cout<<s.size()<<endl;
return 0;
}8.奇怪的表达式求值
常规的表达式求值，我们都会根据计算的优先级来计算。比如* /的优先级就高于+ -。
但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易
所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 *)。现在给出一个表达式，
需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述：
输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。
输出描述：
输出一个数，即表达式的值
输入例子：
3+5*7
输出例子：
56
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int ans = s[0] - '0';
for(int i=1; i<s.length(); i+=2)
{
if(s[i] == '+')
ans += (s[i+1] - '0');
else if(s[i] == '-')
ans += (s[i+1] - '0');
else
ans *= (s[i+1] - '0');
}
cout<<ans<<endl;
}
9.涂棋盘
小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢
的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，
帮助小易算算他会涂画多少个棋格。
输入描述：
输入数据包括n+1行：
第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小
接下来的n行每行一个字符串表示第i行棋盘的颜色，'W'表示白色，'B'表示黑色
输出描述：
输出小易会涂画的区域大小
输入例子：
3
BWW
BBB
BWB
输出例子：
3
#include <bits/stdc++.h>
using namespace std;
int solve(vector<string>& grid, int n)
{
int b, bMax, w, wMax;
int ret = 0;
for(int j=0; j<n; j++)
{
b = 0;
bMax = 0;
w = 0;
wMax = 0;
for(int i=0; i<n; i++)
{
if(grid[i][j] == 'B')
{
b++;
w = 0;
if(b > bMax)
bMax = b;
}
else
{
w++;
b = 0;
if(w > wMax)
wMax = w;
}
}
if(bMax > ret)
ret = bMax;
if(wMax > ret)
ret = wMax;
}
return ret;
}
int main()
{
int n;
vector<string> mp;
cin>>n;
for(int i=0; i<n; i++)
{
string s;
cin>>s;
mp.push_back(s);
}
int ans = solve(mp, n);
cout<<ans<<endl;
return 0;
}10.小易记单词
小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆
一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，
如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意
小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
输入描述：
输入数据包括三行：
第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔
第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。
第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。
输出描述：
输出一个整数表示小易能获得的分数
输入例子：
3 4
apple orange strawberry
strawberry orange grapefruit watermelon
输出例子：
136
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
set<string> s1;
set<string> s2;
cin>>n>>m;
for(int i=0; i<n; i++)
{
string str;
cin>>str;
s1.insert(str);
}
for(int i=0; i<m; i++)
{
string str;
cin>>str;
s2.insert(str);
}
int ans = 0;
for(auto& x : s1)
{
if(s2.find(x) != s2.end())
ans += x.length() * x.length();
}
cout<<ans<<endl;
return 0;
}11.堆砖块
小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。
为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易
现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述：
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述：
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。
输入例子：
3
2 3 5
输出例子：
5
方法一：（暴力搜索+剪枝）
枚举两堆塔的高度，但是需要一些剪枝：
1. 当其中一堆高度大于500000，可以剪掉
2. 当较低的堆 + 剩下的砖块 < 较高的堆时，可以剪掉
3. 当当前可能达到的最大高度小于已经发现最大高度时，可以剪掉。
#include <bits/stdc++.h>
using namespace std;
#define MAX 500000
int n;
int height[52];
int sum[52];
int ans = 0;
void dfs(int n, int sum1, int sum2)
{
if(sum1 == sum2)
ans = max(ans, sum1);
if(n == 0)
return ;
if(sum2 > MAX)
return ;
if(sum1 + sum[n] < sum2)
return ;
if(sum1 + sum2 + sum[n] <= ans * 2)
return ;
dfs(n-1, min(sum1+height[n], sum2), max(sum1+height[n], sum2));
dfs(n-1, min(sum1, sum2+height[n]), max(sum1, sum2+height[n]));
dfs(n-1, sum1, sum2);
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
cin>>height[i];
sort(height, height+n+1);
for(int i=1; i<=n; i++)
sum[i] = sum[i-1] + height[i];
dfs(n, 0, 0);
cout<<(ans > 0 ? ans : -1)<<endl;
return 0;
}
方法二：（动态规划）
分析：从没有砖块开始分析。考虑每块砖块放入的决策，放入左边，放入右边和不使用
这块砖块三种情况.然后做个dp这里用滚动数组优化了下空间
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
int n;
vector<int> height;
int dp[2][MAXN];
int solve(vector<int>& height)
{
int res = 0;
memset(dp, 0, sizeof(dp));
int p = 0;
for(int i=0; i<n; i++)
{
dp[p][height[i]] = max(dp[1-p][height[i]], height[i]);
for(int j=0; j<MAXN; j++)
{
if(dp[1-p][j])
{
if(dp[p][j] < dp[1-p][j])
dp[p][j] = dp[1-p][j];
dp[p][j+height[i]] = max(dp[p][j+height[i]], max(dp[1-p][j+height[i]], dp[1-p][j] + height[i]));
dp[p][abs(j - height[i])] = max(dp[p][abs(j - height[i])], max(dp[1-p][abs(j - height[i])],
max(dp[1-p][j] - j + height[i], dp[1-p][j])));
}
}
p = 1 - p;
}
if(dp[1-p][0])
res = dp[1-p][0];
else
res = -1;
return res;
}
int main()
{
cin>>n;
int h;
for(int i=0; i<n; i++)
{
cin>>h;
height.push_back(h);
}
cout<<solve(height)<<endl;
return 0;
}
12.分饼干
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不
清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证
这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述：
输入包括两行：
第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)
第二行为小朋友的人数n
输出描述：
输出k肯能的数值种树，保证至少为1
输入例子：
9999999999999X
3
输出例子：
4
方法一：
#include <bits/stdc++.h>
using namespace std;
int main()
{
char ch[20];
int dp[20][20];
int n;
cin>>ch>>n;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i=1; i<=strlen(ch); i++) // 从前往后迭代
{
for(int j=0; j<n; j++) //所取值余数的可能性
{
for(int k=0; k<10; k++) //这一位所能取的数
{
if(ch[i-1] >= '0' && ch[i-1] <= '9' && ch[i-1] - '0' != k)//若是x计算所有可能的取值，若不是就计算当前这一种取值
continue;
dp[i][(j*10+k)%n] += dp[i-1][j]; // 迭代为下一位做准备
}
}
}
cout<<dp[strlen(ch)][0]<<endl; //最后一位余数为0的取值
return 0;
}方法二
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
void transform1(long long mod[], int n)
{
long long tmpMod[MAXN] = {0};
for(int i=0; i<n; i++)
{
for(int j=0; j<10; j++)
tmpMod[(i * 10 + j) % n] += mod[i];
}
memcpy(mod, tmpMod, sizeof(tmpMod));
}
void transform2(long long mod[], int k, int n)
{
long long tmpMod[MAXN] = {0};
for(int i=0; i<n; i++)
tmpMod[(i * 10 + k) % n] += mod[i];
memcpy(mod, tmpMod, sizeof(tmpMod));
}
int main()
{
string s;
int n;
cin>>s>>n;
long long mod[MAXN] = {0};
mod[0] = 1;
for(int i=0; i<s.length(); i++)
{
if(s[i] == 'X')
transform1(mod, n);
else
transform2(mod, s[i] - '0', n);
}
cout<<mod[0]<<endl;
return 0;
}