hw机试后感
hw机试后感
case1，简单，逗号隔开的数组，找出素数去重，排序
case2，动态规划，8个任务，分布式计算，给出每个任务的子任务数量和所需服务器数量，服务器数量必须全部满足才能运行一个大任务。
我将其抽象成图的最大路径查找，利用递归，最后因为判断条件未考虑全，时间只剩5min不想改了就直接教了，过了40%。
提交的代码
#include <iostream>
using namespace std;
struct task
{
int file_num, service_num;
};
int n, files = 0, service = 0, max_files = 0;
int sta[8], p = 0;
task tasks[8];
void find_maxfiles(int a)
{
service += tasks[a].service_num;
files += tasks[a].file_num;
if(service == n && files > max_files)
{
max_files = files;
service -= tasks[a].service_num;
files -= tasks[a].file_num;
}
else if(service < n)
{
sta[p++] = a;
int flag;
for(int i = 0; i < 8; i++)
{
flag = 0;
for(int j = 0; j < p; j++)
if(sta[j] == i)
{
flag = 1;
break;
}
if(flag == 1 || i == a)
continue;
find_maxfiles(i);
}
}
p--;
}
int main()
{
tasks[0].file_num = 300;
tasks[0].service_num = 20;
tasks[1].file_num = 500;
tasks[1].service_num = 30;
tasks[2].file_num = 620;
tasks[2].service_num = 50;
tasks[3].file_num = 370;
tasks[3].service_num = 30;
tasks[4].file_num = 400;
tasks[4].service_num = 50;
tasks[5].file_num = 450;
tasks[5].service_num = 30;
tasks[6].file_num = 380;
tasks[6].service_num = 40;
tasks[7].file_num = 150;
tasks[7].service_num = 10;
cin >> n;
if(n < 10)
return 0;
if(n >= 260)
{
cout << 3170;
return 0;
}
n = n - n % 10;
for(int i = 0; i < 8; i++)
{
files = 0;
service = 0;
p = 0;
find_maxfiles(i);
}
cout << max_files;
return 0;
} 改进算法：考虑到如下情况：总数为260，加入除了其中一个需要50个服务器的任务外，其他服务器都满足，此时 n应为210；若n在210到260区间，也只能是输出满足210的条件；（未经过hw机试的测试用例验证，仅自己模拟数据，感觉应该能过）
#include <iostream>
using namespace std;
struct task
{
int file_num, service_num;
};
int n, files = 0, service = 0, max_files = 0;
int sta[8], p = 0;
task tasks[8];
void find_maxfiles(int a)
{
service += tasks[a].service_num;
if(service > n)
{
service -= tasks[a].service_num;
return ;
}
files += tasks[a].file_num;
if(service <= n)
{
if(files > max_files)
{
max_files = files;
}
sta[p++] = a;
int flag;
for(int i = 0; i < 8; i++)
{
flag = 0;
for(int j = 0; j < p; j++)
if(sta[j] == i)
{
flag = 1;
break;
}
if(flag == 1 || i == a)
continue;
find_maxfiles(i);
}
service -= tasks[a].service_num;
files -= tasks[a].file_num;
}
p--;
}
int main()
{
tasks[0].file_num = 300;
tasks[0].service_num = 20;
tasks[1].file_num = 500;
tasks[1].service_num = 30;
tasks[2].file_num = 620;
tasks[2].service_num = 50;
tasks[3].file_num = 370;
tasks[3].service_num = 30;
tasks[4].file_num = 400;
tasks[4].service_num = 50;
tasks[5].file_num = 450;
tasks[5].service_num = 30;
tasks[6].file_num = 380;
tasks[6].service_num = 40;
tasks[7].file_num = 150;
tasks[7].service_num = 10;
cin >> n;
if(n < 10)
return 0;
if(n >= 260)
{
cout << 3170;
return 0;
}
n = n - n % 10;
for(int i = 0; i < 8; i++)
{
files = 0;
service = 0;
p = 0;
find_maxfiles(i);
}
cout << max_files;
return 0;
}
case3：给出一个数组，要求按输入的命令做出操作，U a b k 为更新从下标a到下标b（含）的值为其的k次方。可能是超过64bit的大数，因此要对1234567891取余数； C a b为求下标a 到 b（含）的数的和，并输出。
原谅我太菜，之前ccf就卡在大数上面了，当时思路也有，最简单的，用string进行操作多次的加减操作，但怕时间复杂度太大，而且因为第二题刚开始打算偷鸡，浪费了半个小时，导致时间也不太够了，放弃了。
#笔试题目#