第一题
朴素的枚举思想：暴力遍历所有可能的差值（1 - maxp/(n-1))，在某一差值下，从后往前遍历所有的点作为等差数列的末位数，这样 d + an 就可以确定该数列，此时只需要判断余下的数字即可
第一题
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int isprime[maxn]; // false是 true不是
void primechoice(int maxp) {
isprime[0] = 1;
isprime[1] = 1;
for (int i = 2; i <= maxp; i++) {
if (isprime[i] == false) {
for (int j = i + i; j <= maxp; j += i) {
isprime[j] = true;
}
}
}
}
int main() {
int n, maxp;
cin>>n>>maxp;
primechoice(maxp);
int flag = 0;
if (n != 1) {
for (int d = maxp / (n - 1); d > 0; d--) {
for (int i = maxp; i >= 0; i--) {
if (isprime[i]) continue;
int k = 0;
for (k = 0; k < n; k++) {
if (i <= k * d) break;
if (isprime[i - k * d] != 0) break;
}
if (k == n) {
flag = 1;
for (int j = n - 1; j >= 0; j--) {
cout<<i - j * d;
if (j != 0) cout<<" ";
else cout<<endl;
}
break;
}
}
if (flag == 1) break;
}
}
if (flag == 0) {
while(isprime[maxp]) maxp--;
cout<<maxp<<endl;
}
}
第二题
贪心：每次选择最早离开的人
第二题
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2 * 1e3 + 5;
int n;
struct person{
int enter, exit;
}per[maxn];
bool cmp (person a, person b) {
if (a.exit != b.enter) return a.exit < b.exit;
return a.enter < b.enter;
}
int main() {
cin>>n;
for (int i = 0; i < n; i++) {
int h1, h2, m1, m2, s1, s2;
scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
per[i].enter = h1 * 3600 + m1 * 60 + s1;
per[i].exit = h2 * 3600 + m2 * 60 + s2;
}
sort(per, per + n, cmp);
int count = 1;
int nex = per[0].exit;
for (int i = 1; i < n; i++) {
if (per[i].enter >= nex) {
count++;
nex = per[i].exit;
}
}
cout<<count<<endl;
}
第三题
最大堆的建立，每插入一个数就需要调整一次，而不是全部放入后再调整
字符串的分类，考虑数字没有在大顶堆中出现的情况
第三题
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 4;
int ori[maxn];
int n, m;
void maxHeap(int l, int r) {
int father = l;
int son = 2 * l + 1;
while (son <= r) {
if (son + 1 <= r && ori[son] < ori[son + 1]) son++;
if (ori[son] > ori[father]) {
swap(ori[son], ori[father]);
father = son;
son = 2 * son + 1;
} else {
return;
}
}
}
int main() {
cin>>n>>m;
for (int i = 0; i < n; i++) {
cin>>ori[i];
int len = i + 1;
for (int j = len / 2 - 1; j >= 0; j--) maxHeap(j, len - 1);
}
getchar();
string s;
while (m--) {
getline(cin, s);
if (s[s.size() - 1] == 't') {
string word = "is";
int pos = s.find(word);
int num = stoi(s.substr(0, pos - 1));
if (ori[0] == num) cout<<"1";
else cout<<"0";
} else if (s[s.size() - 1] == 's') {
string word = "and", word2 = "are";
int pos1 = s.find(word);
int num1 = stoi(s.substr(0, pos1 - 1));
int pos2 = s.find(word2);
int num2 = stoi(s.substr(pos1 + 3, pos2 - 1));
int flag1 = -1, flag2 = -1;
for (int i = 0; i < n; i++) {
if (num1 == ori[i]) flag1 = i;
if (num2 == ori[i]) flag2 = i;
}
if (flag1 != -1 && flag2 != -1 && (flag1 - 1) / 2 == (flag2 - 1) / 2) cout<<"1";
else cout<<"0";
} else if (s.find("parent") != -1) {
string word = "is", word2 = "of";
int pos1 = s.find(word);
int num1 = stoi(s.substr(0, pos1 - 1));
int pos2 = s.find(word2);
int num2 = stoi(s.substr(pos2 + 2));
int flag1 = -1, flag2 = -1;
for (int i = 0; i < n; i++) {
if (num1 == ori[i]) flag1 = i;
if (num2 == ori[i]) flag2 = i;
}
if (flag1 != -1 && flag2 != -1 && (flag1 * 2 + 1 == flag2 || flag1 * 2 + 2 == flag2)) cout<<"1";
else cout<<"0";
} else if (s.find("left") != -1) {
string word = "is", word2 = "of";
int pos1 = s.find(word);
int num1 = stoi(s.substr(0, pos1 - 1));
int pos2 = s.find(word2);
int num2 = stoi(s.substr(pos2 + 2));
int flag1 = -1, flag2 = -1;
for (int i = 0; i < n; i++) {
if (num1 == ori[i]) flag1 = i;
if (num2 == ori[i]) flag2 = i;
}
if (flag1 != -1 && flag2 != -1 && flag2 * 2 + 1 == flag1) cout<<"1";
else cout<<"0";
} else if (s.find("right") != -1) {
string word = "is", word2 = "of";
int pos1 = s.find(word);
int num1 = stoi(s.substr(0, pos1 - 1));
int pos2 = s.find(word2);
int num2 = stoi(s.substr(pos2 + 2));
int flag1 = -1, flag2 = -1;
for (int i = 0; i < n; i++) {
if (num1 == ori[i]) flag1 = i;
if (num2 == ori[i]) flag2 = i;
}
if (flag1 != -1 && flag2 != -1 && flag2 * 2 + 2 == flag1) cout<<"1";
else cout<<"0";
}
}
}
第四题
血泪教训：一定把题目读懂后，样例手推明白后再做
卡车的选择：每次都选择距离最近的编号最小的点出发。距离最近的点不一定与当前所在的点直接相连，间接相连也可以
n遍迪杰斯特拉算法 或者floyd算法 + dfs
第四题
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int inf = 1e7;
int d[maxn][maxn];
int visit[maxn];
int n, m, dis = 0;
vector<int> path;
map<int, int> mp;
void dfs(int root) {
visit[root] = 1;
path.push_back(root);
int mindis = inf, minid = 0;
for (int i = 0; i <= n; i++) {
// cout<<i<<" "<<n<<" "<<visit[i]<<endl;
if (visit[i] == 0) {
// cout<<i<<",,,,"<<endl;
if (d[root][i] < mindis) {
mindis = d[root][i];
minid = i;
}
if (d[root][i] == mindis) {
if (minid > i) minid = i;
}
}
}
if (minid != 0) {
dis += mindis;
dfs(minid);
}
}
void Floyd() {
for (int k = 0; k <= n; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (d[i][k] != inf && d[k][j] != inf && d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
int main() {
cin>>n>>m;
int s1, s2, d12;
fill(d[0], d[0] + maxn * maxn, inf);
for (int i = 0; i < m; i++) {
cin>>s1>>s2>>d12;
d[s1][s2] = d[s2][s1] = d12;
}
Floyd();
fill(visit, visit + maxn, 0);
dfs(0);
for (int i = 0; i < path.size(); i++) {
if (i != 0) cout<<" ";
cout<<path[i];
}
cout<<endl;
if (path.size() == n + 1) {
cout<<dis<<endl;
} else {
vector<int> lac;
for (int i = 1; i <= n; i++) {
if (visit[i] == 0) lac.push_back(i);
}
for (int i = 0; i < lac.size(); i++) {
if (i != 0) cout<<" ";
cout<<lac[i];
}
}
}
网友评论