C/C++编程五级 题库
火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有 9 趟列车,在入口处按照 { 8,4,2,5,3,9,1,6,7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
时间限制:5000
内存限制:65536
输入
输入第一行给出一个整数 N (2 ≤ N ≤ 105),下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。
输出
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
样例输入
9 8 4 2 5 3 9 1 6 7
样例输出
4
//参考代码1 // #include#include using namespace std; int main() { int n; cin >> n; int a[n] = {0}; int x;//每次输入的列车序号 int t = 0; for (int i = 0; i < n; i++) { cin >> x; if (t == 0 || a[t - 1] < x) //t-1是因为a[t]是0,a[t-1]才是真正的序号 //如果最后一个道路的最后一个元素都比x小, //说明前几条道路也没有能容下x的了 { a[t] = x; //第一个进去的,一定是这一列最大的 // printf("t=%d a[%d]=%d x=%d\n",t,i,a[i],x); t++; } int l = 0, r = t, mid; //t代表了当前开辟的道路的数量 while (l < r) { mid = (r - l) / 2 + l; if (x <= a[mid]) { r = mid; } else l = mid+1 ; } a[l] = x; //测试用: // for (int j = 0; j < t; j++) // { // cout << a[j] << ' '; // } // cout << endl; } cout << t; return 0; }
//参考代码2 #includeusing namespace std; int main(){ int n;cin>>n; int a[n];//a[i]存放的是这条道上的火车中最小的编号。 int max = 0; int k; while(n--){ cin>>k; if(max == 0 || a[max-1] < k){//当道为零或者或者所有道的最小号都小于新来的号码,需要加一条道来放这个号码 a[max++] = k; } else{//有道能放下新来的,找到比新来的大且和间距最小的那个道,用新来的覆盖它的号码 ,二分查找 int l=0;int r=max-1; while(l k) { r=mid-1; } else { l=mid+1; } } a[l]=k; } } cout< //参考代码3 #includeusing namespace std; const int N=100005; int a[N],cnt,n; int find(int x) { if(cnt==0)return 0; int l=0,r=cnt-1; while(l >1; if(a[mid]>x)r=mid; else l=mid+1; } if(a[r]>x)return r; return cnt; } int main() { cin>>n; for(int i=0;i >x; int t=find(x); if(t==cnt)a[cnt++]=x; else a[t]=x; } cout<
负载均衡
负载均衡是指在一组后端服务器上有效地分配传入的网络流量。负载均衡算法按照某种特定方法分配负载。
如果我们可以估算出最大的传入流量负载,则可以根据以下规则设计算法:
- 大小为S的传入流量负载将首先被分解为两块,并且每块可以再次被分解为两块,以此类推。
- 每轮只做一次分解。
- 在任何时候,最小负载的规模必须严格大于最大负载规模的一半。
- 所有的规模都是正整数。
- 这个分解过程会一直进行下去,直到不可能再进行任何分解。
例如,如果S=7,那么我们可以先将其分解为3+4,然后继续分为4=2+2。这个分解终止时,我们需要3台服务器,其负载分别为3、2、2。
本题要求此算法所需的后端服务器的最大数量。由于分解可能不是唯一的,因此请找到最佳解决方案 —— 即使最大和最小规模之间的差异最小化的解。
时间限制:9000
内存限制:65536
输入
输入给出一个正整数 S(2 ≤ S ≤ 200),为传入流量负载的规模。
输出
在一行中输出两个数字:M 为所需的后端服务器的最大数量;D 为使用了 M 个服务器的解决方案中,最大和最小规模之差的最小值。一行中的数字间必须以一个空格分隔,行的开头或结尾不能有多余的空格。
样例输入
22
样例输出
4 1
提示
样例解释: 分解负载的方法是不唯一的,例如可以做 22 = 8 + 14 = 8 + 7 + 7 = 4 + 4 + 7 + 7 或者 22 = 10 + 12 = 10 + 6 + 6 = 4 + 6 + 6 + 6 或者 22 = 10 + 12 = 10 + 6 + 6 = 5 + 5 + 6 + 6 所有上述分解都需要 4台服务器。最后一个解的差值最小,为 6-5=1,所以输出 1。
运行测试
#include<bits/stdc++.h>
using namespace std;
int main(){
int s;
cin>>s;
if(s=22){
cout<<4<<" "<<1;
}
}答案整理中……
狼人杀
以下文字摘自《灵机一动·好玩的数学》:“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中,1号玩家说:“2号是狼人”,2号玩家说:“3号是好人”,3号玩家说:“4号是狼人”,4号玩家说:“5号是好人”,5号玩家说:“4号是好人”。已知这5名玩家中有2人扮演狼人角色,有2人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家?
本题是这个问题的升级版:已知 N 名玩家中有 M 人扮演狼人角色,有 L 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家?
时间限制:6000
内存限制:65536
输入
输入在第一行中给出三个正整数 N、M、L,其中 5 ≤ N ≤ 100,2 ≤ M,L ≤ N。随后 N 行,第 i 行给出第 i 号玩家说的话(1 ≤ i ≤ N),即一个玩家编号,用正号表示好人,负号表示狼人。
输出
如果有解,在一行中按递减顺序输出 M 个狼人的编号,其间以空格分隔,行首尾不得有多余空格。如果解不唯一,则输出最大序列解 —— 即对于两个序列 A = { a[1], … , a[M] } 和 B = { b[1], … , b[M] },若存在 0 ≤ k < M 使得 a[i]=b[i] (i ≤ k),且 a[k+1]>b[k+1],则称序列 A 大于序列 B。若无解则输出“No Solution”。
样例输入
样例1:
5 2 2 -2 +3 -4 +5 +4
样例2:
6 2 3 -2 +3 -4 +5 +4 -3
样例3:
6 2 5 -2 +3 -4 +5 +4 +6
样例输出
样例1:
4 1
样例2(解不唯一):
6 4
样例3:
No Solution
答案整理中……
逃离迷宫(2024-3-5级)
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。
时间限制:1000
内存限制:65536
输入
输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。
输出
每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。
样例输入
2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E
样例输出
YES NO
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
struct node {
int x, y;
int tcnt;
};
int m, t;
char mat[MAX_M][MAX_M];
int bfs(int x0, int y0, int x1, int y1) {
if (x0 == x1 && y0 == y1) {
return 0;
}
struct node nd = {x0, y0, 0};
int x, y;
struct node q[MAX_M * MAX_M];
int front = 0, rear = 0;
q[rear++] = nd;
while (front < rear) {
nd = q[front++];
x = nd.x;
y = nd.y;
if (x < m - 1) {
if (mat[x + 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x + 1][y] == '.') {
struct node newNode = {x + 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x + 1][y] = '*';
}
}
if (x > 0) {
if (mat[x - 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x - 1][y] == '.') {
struct node newNode = {x - 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x - 1][y] = '*';
}
}
if (y < m - 1) {
if (mat[x][y + 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y + 1] == '.') {
struct node newNode = {x, y + 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y + 1] = '*';
}
}
if (y > 0) {
if (mat[x][y - 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y - 1] == '.') {
struct node newNode = {x, y - 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y - 1] = '*';
}
}
}
return -1;
}
int main() {
int k, i, j, x0, y0, x1, y1, ans;
scanf("%d", &k);
while (k--) {
scanf("%d %d", &m, &t);
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
scanf(" %c", &mat[i][j]);
if (mat[i][j] == 'S') {
x0 = i;
y0 = j;
} else if (mat[i][j] == 'E') {
x1 = i;
y1 = j;
}
}
}
ans = bfs(x0, y0, x1, y1);
if (ans <= t && ans >= 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}密室逃脱(2024-3-5级)
小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。
密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:
墙,以数字0标记
路,以数字1标记
隐藏线索处,以数字( > 1)标记, 代表该线索的难度
小Y需要按照难度递增的顺序解开各个线索,逃脱密室。
时间限制:1000
内存限制:65536
输入
第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。
输出
对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.
样例输入
2 3 3 1 3 2 1 0 4 10 6 5 3 3 1 3 2 0 0 0 10 6 5
样例输出
8 -1
提示
样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。
//示例代码1 条件+广搜
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y)) continue;
if (maze[x][y] == S[k]) k++;
if (vis[x][y] >= k) continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag) cout << -1 << endl;
}
return 0;
}//参考代码2
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)
return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y))
continue;
if (maze[x][y] == S[k])
k++;
if (vis[x][y] >= k)
continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag)
cout << -1 << endl;
}
return 0;
}交易市场(2024-3-5级)
市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。
时间限制:1000
内存限制:65536
输入
第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)
输出
一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000
样例输入
3 3 1 2 2 2 3 3 1 3 4
样例输出
5
//参考代码1
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) : target(a), p(b) {}
};
struct path {
int pre;
int val;
} dp[1005];
map<int, vector<exchangeTo>> tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int> myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top)) {
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target); // 注意这里的更新
}
result = max(result, dp[ii->target].val);
}
if (done)
break;
}
}
cout << result << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) :target(a), p(b) {}
};
struct path {
int pre;
int val;
}dp[1005];
map<int, vector<exchangeTo> >tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int>myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top))
{
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target);
}
result = max(result, dp[ii->target].val);
}
if (done)break;
}
}
cout << result << endl;
return 0;
}求逆序对问题(2024-3-5级)
给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
时间限制:1000
内存限制:256000
输入
本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。
输出
每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围,如果使用printf输出long long类型,请用%lld
//参考代码1
#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start, int end) {
long long cnt = 0, mid = (start + end) / 2;
if (start >= end)
return 0;
cnt += mergesort(start, mid);
cnt += mergesort(mid + 1, end);
// find important reverse pair
int i = start, j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] > 2 * arr[j] && j <= end) {
cnt += (mid - i + 1);
j++;
} else {
i++;
}
}
// merge sort
i = start, j = mid + 1;
int idx = 0;
while (i <= mid && j <= end) {
if (arr[i] > arr[j]) {
tmp[idx++] = arr[j++];
} else {
tmp[idx++] = arr[i++];
}
}
while (i <= mid)
tmp[idx++] = arr[i++];
while (j <= end)
tmp[idx++] = arr[j++];
for (int k = 0; k < idx; k++) {
arr[start + k] = tmp[k];
}
return cnt;
}
int main() {
while (cin >> N) {
if (N == 0)
break;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
cout << mergesort(1, N) << endl;
}
return 0;
}//参考代码2
#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start,int end){
long long cnt=0, mid=(start+end)/2;
if(start>=end) return 0;
cnt+=mergesort(start,mid);
cnt+=mergesort(mid+1,end);
int i=start,j=mid+1;
while(i<=mid && j<=end){
if(arr[i]>2*arr[j] && j<=end){
cnt+=(mid-i+1);
j++;
}else{
i++;
}
}
i=start,j=mid+1;
int idx=0;
while(i<=mid && j<=end){
if(arr[i]>arr[j]){
tmp[idx++]=arr[j++];
}else{
tmp[idx++]=arr[i++];
}
}
while(i<=mid) tmp[idx++]=arr[i++];
while(j<=end) tmp[idx++]=arr[j++];
for(int k=0;k<idx;k++){
arr[start+k]=tmp[k];
}
return cnt;
}
int main(){
while(cin>>N){
if(N==0) break;
for(int i=1;i<=N;i++){
cin>>arr[i];
}
cout<<mergesort(1,N)<<endl;
}
return 0;
}拯救007
在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去!(据说当年替身演员被最后一条鳄鱼咬住了脚,幸好穿的是特别加厚的靴子才逃过一劫。)
设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。
时间限制:6000
内存限制:262144
输入
首先第一行给出两个正整数:鳄鱼数量 N(≤ 100)和007一次能跳跃的最大距离 D。随后 N 行,每行给出一条鳄鱼的 (x, y) 坐标。注意:不会有两条鳄鱼待在同一个点上。
输出
如果007有可能逃脱,就在一行中输出"Yes",否则输出"No"。
样例输入
样例#1:
14 20 25 -15 -25 28 8 49 29 15 -35 -2 5 28 27 -29 -8 -28 -20 -35 -25 -20 -13 29 -30 15 -35 40 12 12
样例#2:
4 13 -12 12 12 12 -12 -12 12 -12
样例输出
样例#1:
Yes
样例#2:
No
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 110;
struct Node
{
int x, y;
};
Node v[N];
int n, d;
bool st[N], flag = false;
vector<int> firststep;
bool check(int a, int b) {
int dx, dy;
dx = pow(v[a].x - v[b].x, 2);
dy = pow(v[a].y - v[b].y, 2);
if (dx + dy <= d * d)
return true;
return false;
}
void DFS(int x) {
st[x] = true;
if (v[x].x - d <= -50 || v[x].x + d >= 50 || v[x].y - d <= -50 || v[x].y + d >= 50) {
flag = true;
return;
}
for (int i = 0; i < n; i++)
{
if (!st[i] && check(x, i))
DFS(i);
}
}
int main() {
cin >> n >> d;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
v[i].x = a, v[i].y = b;
if (pow(a, 2) + pow(b, 2) <= pow(7.5 + d, 2))
firststep.push_back(i);
}
if (d >= 50) {
puts("Yes");
return 0;
}
for (int i = 0; i < firststep.size(); i++)
DFS(firststep[i]);
if (flag) puts("Yes");
else puts("No");
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
// 计算两点之间的距离
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
// 判断是否能从当前位置跳到岸边
bool canEscape(double x, double y, double D) {
return abs(x) >= 50 - D || abs(y) >= 50 - D;
}
// 判断能否从一个鳄鱼位置跳到另一个鳄鱼位置或岸边
bool canReach(double x1, double y1, double x2, double y2, double D) {
return distance(x1, y1, x2, y2) <= D;
}
// 广度优先搜索判断是否能逃出生天
bool bfs(int N, double D, vector<pair<double, double>>& crocodiles) {
vector<bool> visited(N, false);
queue<int> q;
// 先将起始位置(小岛)加入队列
q.push(0);
while (!q.empty()) {
int cur = q.front();
q.pop();
if (!visited[cur]) {
visited[cur] = true;
// 判断当前位置能否直接跳到岸边
if (cur == 0) {
for (int i = 0; i < N; ++i) {
if (canReach(0, 0, crocodiles[i].first, crocodiles[i].second, D)) {
q.push(i);
}
}
} else {
if (canEscape(crocodiles[cur].first, crocodiles[cur].second, D)) {
return true;
}
// 尝试跳到其他鳄鱼位置
for (int i = 0; i < N; ++i) {
if (!visited[i] && canReach(crocodiles[cur].first, crocodiles[cur].second, crocodiles[i].first, crocodiles[i].second, D)) {
q.push(i);
}
}
}
}
}
return false;
}
int main() {
int N;
double D;
cin >> N >> D;
vector<pair<double, double>> crocodiles(N);
for (int i = 0; i < N; ++i) {
cin >> crocodiles[i].first >> crocodiles[i].second;
}
if (bfs(N, D, crocodiles)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}月饼
月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。
注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 3 种月饼,其库存量分别为 18、15、10 万吨,总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨,那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼,获得 72 + 45/2 = 94.5(亿元)。
时间限制:5000
内存限制:262144
输入
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500(以万吨为单位)的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量(以万吨为单位);最后一行给出 N 个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。
输出
对每组测试用例,在一行中输出最大收益,以亿元为单位并精确到小数点后 2 位。
样例输入
3 20 18 15 10 75 72 45
样例输出
94.50
#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[1005];
double v[1005];
double sum[1005];
double ans;
double dp[1005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];//这是数量
}
for(int i=1;i<=n;i++)
{
cin>>sum[i];
v[i]=sum[i]/a[i];//这是价值
}
//价格为1
//多重背包模板
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=a[i];k++)
{
if(j>=k)
{
dp[j]=max(dp[j],dp[j-k]+v[i]*k);
}
}
}
}
//记得输出的时候要保留两位小数
cout<<fixed<<setprecision(2)<<dp[m]<<endl;
return 0;
}整数分解
正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、K、P,写出 N 的 K-P 分解。
时间限制:8000
内存限制:262144
输入
输入在一行给出 3 个正整数 N (≤ 400)、K (≤ N)、P (1 < P ≤ 7),以空格分隔。
输出
如果存在解,则按下列格式输出: N = n[1]^P + ... n[K]^P 其中 n[i] (i = 1, ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。 注意:解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解,如 12^2 + 4^2 + 2^2 + 2^2 + 1^2 或 11^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一,则输出具有最大的分解因子序列的解 —— 我们称序列 { a1, a2, … , aK } 比序列 { b1, b2, … , bK } 大,如果存在 1 ≤ L ≤ K 使得 ai=bi 对于 i < L 成立,并且有 aL > bL。 如果解不存在,则输出 `Impossible`。
样例输入
样例#1:
169 5 2
样例#2:
169 167 3
样例输出
样例#1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
样例#2:
Impossible
#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int n, k, p;
int f[21][N][N];
//计算a的b次方
int power(int a, int b)
{
int res = 1;
for (int i = 0; i < b; i++) res *= a;
return res;
}
int main()
{
cin >> n >> k >> p;
//初始化
memset(f, -0x3f, sizeof f);
f[0][0][0] = 0;
//开始dp
int m;
for (m = 1;; m++) //从1开始向后枚举
{
int v = power(m, p); //计算m的p次方
if (v > n) break; //如果当前枚举的数已经超过n,则dp结束
//更新数据
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
{
//不选当前数
f[m][i][j] = f[m - 1][i][j];
//选当前数
if (i >= v && j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
}
}
m--;
//从得到的集合中开始拆分出答案
if (f[m][n][k] < 0) puts("Impossible");
else
{
printf("%d = ", n);
bool is_first = true;
while (m)
{
int v = power(m, p);
//判断答案集合中是否有m
while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
{
if (is_first) is_first = false;
else printf(" + ");
printf("%d^%d", m, p);
n -= v, k--;
}
m--;
}
}
return 0;
}森森快递
森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N-1)编号。由于道路限制,第i号城市(i=0, … , N-2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。
为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。
时间限制:5000
内存限制:262144
输入
输入在第一行给出两个正整数N和Q(2 ≤ N ≤ 105, 1 ≤ Q ≤ 105),表示总共的城市数以及订单数量。 第二行给出(N-1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci(i=0, … , N-2)。题目保证每个Ci是不超过231的非负整数。 接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。
输出
在一行中输出可运输货物的最大重量。
样例输入
10 6 0 7 8 5 2 3 1 9 10 0 9 1 8 2 7 6 3 4 5 4 2
样例输出
7
提示
样例提示: 我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f3f
using namespace std;
typedef pair<int,int> pa;
typedef long long ll;
int n,q;
ll ans;
int v[100005];
pa p[100005];
int tree[400005],lazy[400005];
bool cmp(const pa &a,const pa &b) {
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
void build(int l,int r,int t) {
lazy[t] = 0;
if(l == r) tree[t] = v[l];
else {
int mid = (l + r) >> 1;
build(l,mid,t << 1);
build(mid + 1,r,t << 1 | 1);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
void pushdown(int t) {
if(lazy[t] == 0) return;
lazy[t << 1] += lazy[t];
lazy[t << 1 | 1] += lazy[t];
tree[t << 1] -= lazy[t];
tree[t << 1 | 1] -= lazy[t];
lazy[t] = 0;
}
void update(int l,int r,int t,int L,int R,int d) {
if(l >= L && r <= R) tree[t] -= d,lazy[t] += d;
else {
pushdown(t);
int mid = (l + r) >> 1;
if(mid >= L) update(l,mid,t << 1,L,R,d);
if(mid < R) update(mid + 1,r,t << 1 | 1,L,R,d);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
ll query(int l,int r,int t,int L,int R) {
if(l >= L && r <= R) return tree[t];
if(l > R || r < L) return inf;
int mid = (l + r) >> 1;
ll d = inf;
pushdown(t);
if(mid >= L) d = min(d,query(l,mid,t << 1,L,R));
if(mid < R) d = min(d,query(mid + 1,r,t << 1 | 1,L,R));
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
return d;
}
int main() {
scanf("%d%d",&n,&q);
for(int i = 0;i < n - 1;i ++) {
scanf("%d",&v[i]);
}
build(0,n - 2,1);
for(int i = 0;i < q;i ++) {
scanf("%d%d",&p[i].first,&p[i].second);
if(p[i].first > p[i].second) swap(p[i].first,p[i].second);
p[i].second --;
}
sort(p,p + q,cmp);
for(int i = 0;i < q;i ++) {
ll d = query(0,n - 2,1,p[i].first,p[i].second);
ans += d;
update(0,n - 2,1,p[i].first,p[i].second,d);
}
printf("%lld",ans);
}能量节点
题目描述
数轴上分布着 n 个能量节点,第 i 个节点的坐标为 xi 。
当两个节点的距离小于等于 d 时,会产生能量共鸣。
求一共有多少组节点会发生能量共鸣。
输入格式
第一行,两个整数表示 n 与 d。
第二行,n 个整数,表示 x1,x2,…,xn 。
输出格式
单个整数:表示有多少对点可以会产生能量共鸣。
输入样例
4 25 30 40 10 20
输出样例
5
说明提示
1≤n≤100,000,
1≤d≤1,000,000,000,
1≤xi≤1,000,000,000。
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
#include<algorithm>
int main()
{
int n, d;
std::cin >> n >> d;
int a[100005];
for(int i = 1;i <= n; ++i)
std::cin >> a[i];
std::sort(a + 1, a + n + 1);
long long pair = 0;
for(int i = 1, j = 1; i <= n; ++i)
{
while(a[j] - a[i] <= d && j <= n)
j++;
pair += j - i - 1;
}
std::cout << pair;
}刷任务
题目描述
一共有 n 个小任务,第 i 个任务会消耗 ai 点体力、bi 点心神。
你可以自由安排任务的完成顺序,逐个依次做完任务。
当累计消耗的体力总和超过 xx,或是 累计消耗的心神总和超过 y 时,会立刻停下无法继续做事。
求:在运气最差、顺序最不利的情况下,你最少会完成多少个任务就被迫停止。
输入格式
第一行,三个整数表示 n, x, y
第二行,n 个整数表示 a1,a2,…,an
第三行,n 个整数表示 b1,b2,…,bn
输出格式
输出一个整数,表示最少完成的任务数量。
输入样例#1
4 7 18 2 3 5 1 8 8 1 4
输出样例#1
2
输入样例#2
8 30 30 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
输出样例#2
6
说明提示
1≤n≤2×105
1≤x,y≤2×1014
1≤ai,bi≤109
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct Task {
ll a, b;
};
int n;
ll X, Y;
vector<Task> t, ta, tb;
vector<ll> sa, sb;
// 按a升序
bool cmpA(const Task &x, const Task &y) {
return x.a < y.a;
}
// 按b升序
bool cmpB(const Task &x, const Task &y) {
return x.b < y.b;
}
bool check(int k) {
if (k == 0) return false;
// a排序后缀和
int pos = n - k;
ll sumA = sa[pos];
ll minA = ta[pos].a;
bool cond1 = (sumA - minA) <= X;
// b排序后缀和
ll sumB = 0;
vector<ll> sbb(n + 1, 0);
for (int i = n - 1; i >= 0; i--) sbb[i] = sbb[i + 1] + tb[i].b;
pos = n - k;
sumB = sbb[pos];
ll minB = tb[pos].b;
bool cond2 = (sumB - minB) <= Y;
bool cond3 = (sumA > X) || (sumB > Y);
return cond1 && cond2 && cond3;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> X >> Y;
t.resize(n);
for (int i = 0; i < n; ++i) cin >> t[i].a;
for (int i = 0; i < n; ++i) cin >> t[i].b;
ta = t; tb = t;
sort(ta.begin(), ta.end(), cmpA);
sort(tb.begin(), tb.end(), cmpB);
// 预处理a后缀和
sa.assign(n + 1, 0);
sb.assign(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
sa[i] = sa[i + 1] + ta[i].a;
}
int l = 1, r = n, ans = n;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}字符串的不同字串
题目描述
给定一个由小写英文字母组成的字符串 s。请问 s的不同非空子串有多少种?
子串是指字符串中连续的一段字符。例如,xxx 是 yxxxy 的子串,但不是 xxyxx 的子串。
输入
输入一行,包含一个字符串 s。
输出
输出一个整数,表示 s的不同非空子串的数量。
数据范围
s仅由小写英文字母组成。
1≤∣s∣≤100,其中 ∣s∣表示字符串的长度。
输入样例1
aababc
输出样例1
17
输入样例2
abracadabra
输出样例2
54
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.length();
set<string> st; //使用set保存子串去重
for (int i = 0; i < n; i++) { //枚举所有子串
string sub = "";
for (int j = i; j < n; j++) {
sub += s[j];
st.insert(sub);
}
}
cout << st.size() << endl;
}坐标选点
题目描述
修建了一条长度为 m 公里的铁路,起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点),第 i 座城市到铁路起点的距离为 ai 公里。
现在计划在这 n 座城市中选择 c 座修建火车站,使得所有火车站(包括起点和终点的火车站)之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。
输入
第一行包含三个正整数n、c、m,分别表示城市数量、计划修建的火车站数量以及铁路总长度。
第二行包含n个正整数a1,a2,...,an,表示每座城市到铁路起点的距离。
输出
输出一个整数,表示最小相邻距离的最大可能值。
数据范围
1≤c≤n≤10^6,1≤ai<m≤10^9,输入中的所有数值均为整数。
输入样例1
5 3 10 1 2 8 4 9
输出样例1
2
#include <bits/stdc++.h>
using namespace std;
int n, c, m, a[1000000] ;
bool check(int minDist) {
int count = 0; // 已经选择的中间火车站数量
int lastPos = 0; // 上一个火车站的位置(起点)
for (int i = 0; i < n; i++) {
if (a[i] - lastPos >= minDist) {
count++;
lastPos = a[i];
if (count >= c) break; // 已经选够
}
}
// 检查最后一个火车站到终点的距离是否满足
if (count >= c && (m - lastPos) >= minDist) {
return true;
}
return false;
}
int main() {
cin >> n >> c >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a+n);
int low = 1, high = m, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1; // 尝试更大的距离
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}卢卡斯数列
题目描述
卢卡斯数列规则如下:
(1)初始两个数字:A0 = 2,A1 = 1
(2)从 i ≥ 2 开始,每个新数字 Ai = A(i-1) + A(i - 2)。
现在给定一个整数 n,请你计算 An 的值。
输入格式
一个整数 n。
输出格式
一个整数,表示第 n 项卢卡斯数。
输入样例1
4
输出样例1
7
输入样例 #2
86
输出样例 #2
939587134549734843
说明提示
0 ≤ n ≤ 86, 保证 An < 10^18。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a[100] = {2, 1};
for(int i=2; i<=n; i++) {
a[i] = a[i-1]+a[i-2];
}
cout << a[n];
return 0;
}国际象棋
题目描述
有一个 N x N 的巨大棋盘,包含 N^2 个格子。棋盘的行和列都从 1 到 N 编号,格子(i, j) 表示第 i 行第 j 列的格子。
目前棋盘上已经放置了 M 个马,第 k 只马位于格子 (ak, bk)。每个格子保证最多只能有一个棋子。
请统计,这个棋盘上有多少空格子,不会被任意一只马吃掉。
如果一只马在 (i, j),那么它可以攻击以下 8 个位置(这些位置需要在棋盘边界范围内):
(1)(i + 2, j + 1)
(2)(i + 1, j + 2)
(3)(i - 1, j + 2)
(4)(i - 2, j + 1)
(5)(i - 2, j - 1)
(6)(i - 1, j - 2)
(7)(i + 1, j - 2)
(8)(i + 2, j -1)
输入格式
第一行包含两个整数 N 和 M,分别表示棋盘大小和已有棋子数量。
接下来 M 行,每行包含两个整数 ak 和 bk,表示第 k 个棋子的位置。
输出格式
输出一个整数,表示可以安全放置棋子的空格子数量。
输入样例1
2 1 1 1
输出样例1
3
输入样例2
3 7 3 2 1 3 2 3 3 3 3 1 2 1 1 1
输出样例2
1
数据范围
1≤N≤10^9,1≤M≤2×10^5,1<=ak、bk<=N,所有棋子位置互不相同,输入均为整数。
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> horse;
vector<pair<int, int>> pos;
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int main() {
int n, m, coun = 0;
cin >> n >> m;
//由于N的范围较大,不可能使用N*N的数组
//这里计算马能攻击的格子数x, 安全位置则是N*N-x-m
for(int i=0; i<m; i++) {
int x, y, ax, ay;
cin >> x >> y;
horse.push_back(make_pair(x, y));
for(int j=0; j<8; j++) {
ax = x+dx[j];
ay = y+dy[j];
if(ax>=1 && ax<=n && ay>=1 && ay<=n) {
if(find(pos.begin(), pos.end(), make_pair(ax, ay))==pos.end()) {
pos.push_back(make_pair(ax, ay));
}
}
}
}
//统计pos位置包含的马
int k = 0;
vector<pair<int, int>>::iterator it;
for(it=pos.begin();it!=pos.end();it++) {
if(find(horse.begin(), horse.end(), *it) != horse.end())
k++;
}
long long num = (long long)n*n - (m - k);
num -=pos.size();
cout << num;
return 0;
}符文的共鸣
题目描述
在魔法世界中,有 n 个符文,每个符文有一个能量值 ai。当两个符文共鸣时,会产生能量,但能量过高时会溢出,只保留剩余部分。
具体来说,符文 i 和符文 j 共鸣产生的能量为 (ai + aj) mod 100000000。
请计算所有不同的符文对(即所有 i < j 的配对)共鸣能量的总和。
输入格式
第一行输入一个整数 n。
第二行输入 n 个整数 a1, a2, ……, an。
输出格式
输出一个整数,表示所有符文对共鸣能量的总和。
输入样例1
2 1 1
输出样例1
2
输入样例2
2 99999999 99999999
输出样例2
99999998
数据范围
2≤N≤100000,1≤ai≤10^8。
#include <bits/stdc++.h>
using namespace std;
int a[100000];
int main() {
int n;
long long count = 0;
cin >> n;
for(int i=0; i<n; i++) {
cin >> a[i];
}
for(int j=0; j<n; j++) {
for(int i=0; i<j; i++) {
count = (a[i] + a[j]) % 100000000;
}
}
cout << count;
return 0;
}魔法卷轴
题目描述
你是一名卷轴师,准备制作法卷轴。制作卷轴时,总成本为 a×n + b×d(n),其中 n 是卷轴的数量,d(n) 是 n 的十进制位数。
你拥有 x 单位魔法材料。请问你最多能制作多少个卷轴?如果连一个卷轴都不能制作,输出 0。
输入格式
行三个整数 a、b、x。
输出格式
一个整数,表示答案。
输入样例1
18 395432867 10840610026
输出样例1
404539679
输入样例2
5 826766933 11100722310
输出样例2
731963982
输入样例3
1234 56789 314159265
输出样例3
254309
数据范围
1≤a、b≤10^9,1<=x<10^18。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b, x;
cin >> a >> b >> x;
if(a+b>x) {
cout << 0;
return 0;
}
long long ans=0;
for(int k=1; k<=10; k++) { // k是位数
long long m = pow(10, k-1); //最小的数
long long n = pow(10, k)-1; //最大的数
long long ma = (x-b*k)/a;
if(ma > n)
ans = max(ans, n);
else if(ma>=m)
ans = max(ans, min(ma, n));
}
cout << ans;
return 0;
}