C/C++编程六级 题库
区块反转
给定一个单链表 L,我们将每 K 个结点看成一个区块(链表最后若不足 K 个结点,也看成一个区块),请编写程序将 L 中所有的区块链反转。例如:给定 L 为 1→2→3→4→5→6→7→8,K 为 3,则输出应该为 7→8→4→5→6→1→2→3。
时间限制:6000
内存限制:65535
输入
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤ 105)、以及正整数 K (≤ N),即区块的大小。结点的地址是 5 位非负整数,NULL 地址用 -1 表示。 接下来有 N 行,每行格式为: Address Data Next 其中 Address 是结点地址,Data 是该结点保存的整数数据,Next 是下一结点的地址。
输出
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
样例输入
00100 8 3 71120 7 88666 00000 4 99999 00100 1 12309 68237 6 71120 33218 3 00000 99999 5 68237 88666 8 -1 12309 2 33218
样例输出
71120 7 88666 88666 8 00000 00000 4 99999 99999 5 68237 68237 6 00100 00100 1 12309 12309 2 33218 33218 3 -1
#include <iostream>
#include <vector>
using namespace std;
struct node {
int data, next;
}A[100001];
vector<int> L, ans, E[100001];
int s, n , a, t, k, mark, cnt, c;
int main() {
cin >> s >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a;
cin >> A[a].data >> A[a].next;
}
t = s;
while (t != -1) {
L.push_back(t);
t = A[t].next;
}
n = L.size();
for (int i = 0; i < n; i++) {
E[c].push_back(L[i]);
cnt++;
if (cnt == k && i != n - 1) {
cnt = 0;
c++;
}
}
for (int i = c; i >= 0; i--)
for (auto it : E[i])
ans.push_back(it);
for (int i = 1; i < n; i++)
printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);
printf("%05d %d -1", ans.back(), A[ans.back()].data);
return 0;
}彩虹瓶
彩虹瓶的制作过程(并不)是这样的:先把一大批空瓶铺放在装填场地上,然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。
假设彩虹瓶里要按顺序装 N 种颜色的小球(不妨将顺序就编号为 1 到 N)。现在工厂里有每种颜色的小球各一箱,工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色,就直接拆箱装填;如果不是,就把箱子先码放在一个临时货架上,码放的方法就是一箱一箱堆上去。当一种颜色装填完以后,先看看货架顶端的一箱是不是下一个要装填的颜色,如果是就取下来装填,否则去工厂里再搬一箱过来。
如果工厂里发货的顺序比较好,工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色,工厂按照 7、6、1、3、2、5、4 这个顺序发货,则工人先拿到 7、6 两种不能装填的颜色,将其按照 7 在下、6 在上的顺序堆在货架上;拿到 1 时可以直接装填;拿到 3 时又得临时码放在 6 号颜色箱上;拿到 2 时可以直接装填;随后从货架顶取下 3 进行装填;然后拿到 5,临时码放到 6 上面;最后取了 4 号颜色直接装填;剩下的工作就是顺序从货架上取下 5、6、7 依次装填。
但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货,工人就必须要愤怒地折腾货架了,因为装填完 2 号颜色以后,不把货架上的多个箱子搬下来就拿不到 3 号箱,就不可能顺利完成任务。
另外,货架的容量有限,如果要堆积的货物超过容量,工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货,如果货架够高,能码放 6 只箱子,那还是可以顺利完工的;但如果货架只能码放 5 只箱子,工人就又要愤怒了……
本题就请你判断一下,工厂的发货顺序能否让工人顺利完成任务。
时间限制:6000
内存限制:65536
输入
输入首先在第一行给出 3 个正整数,分别是彩虹瓶的颜色数量 N(1 < N ≤ 103)、临时货架的容量 M(< N)、以及需要判断的发货顺序的数量 K。 随后 K 行,每行给出 N 个数字,是 1 到N 的一个排列,对应工厂的发货顺序。 一行中的数字都以空格分隔。
输出
对每个发货顺序,如果工人可以愉快完工,就在一行中输出 YES;否则输出 NO。
样例输入
7 5 3 7 6 1 3 2 5 4 3 1 5 4 2 6 7 7 6 5 4 3 2 1
样例输出
YES NO NO
#include <bits/stdc++.h>
using namespace std;
int N, M, K, temp, need, num, Stack[1002];
int main() {
cin >> N >> M >> K;
for (int i = 0; i < K; i++) {
need = 1, num = 1;
for (int j = 0; j < N; j++) {
cin >> temp;
if (temp == need) {
need++;
while (Stack[num - 1] == need) need++, num--;
} else if (num <= M) Stack[num++] = temp;
}
printf("%s\n", num == 1 ? "YES" : "NO");
}
return 0;
}智能陪护
智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。
本题就请你实现这样一个自动分配功能。
时间限制:6000
内存限制:65536
输入
输入在第一行中给出 2 个正整数:N(≤ 104)是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号,且一开始按照编号升序在系统队列中排队;K(≤ 105)是系统订单信息的条数。随后 K 行,每行给出一条订单信息,格式为: 老人ID 指令 日期 其中 老人ID是一个长度不超过 5 的字符串,由英文小写字母和数字组成;指令 为 1 表示下单,为 0 表示结算;日期是按照 年年年年月月日日 格式给出的,保证是一个 2022 年 1 月 1 日到 3022 年 12 月 31 日 之间的合法日期。 题目保证所有数据合理,即对每位老人,结算一定发生在下单之后,结算了一单才允许下另一单,且不存在只有下单没有结算、或只有结算没有下单的数据。
输出
按照下单的时间顺序,输出机器人护工的分配信息,每行输出一条,格式为: 老人ID - 机器人护工编号 如果同一天有多位老人下单或结算,保证先处理结算的,使得机器人能及时回到队列。对于同时下达相同指令的,则按照老人ID的升序排队处理。如果一位老人下单时,系统中没有机器人护工了,则需要等待。如果到老人结算时,都没有等到一位护工,则对应输出 老人ID - NONE 最后在一行中顺序输出队列中的机器人护工的编号。要求数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
3 10 a01 0 20220202 a04 1 20220103 a02 1 20220101 a05 0 20220202 a03 1 20220101 a03 0 20220202 a04 0 20220201 a02 0 20220102 a05 1 20220101 a01 1 20220101
样例输出
a01 - 1 a02 - 2 a03 - 3 a05 - 2 a04 - NONE 1 3 2
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int K = 1e5 + 10;
int n, k;
queue<int> que;
struct Order {
string name;
int type, dt;
bool operator<(const Order& o) const {
if (dt != o.dt) return dt < o.dt;
if (type != o.type) return type < o.type;
return name < o.name;
}
friend ostream& operator<<(ostream& out, const Order& o) {
out << o.name << " " << o.type << " " << o.dt;
return out;
}
} orders[K];
unordered_map<string, int> mp;
queue<Order> wt_que;
unordered_map<string, bool> waiting;
int _ = []() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
return 0;
}();
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) que.push(i);
for (int i = 0; i < k; ++i) {
cin >> orders[i].name >> orders[i].type >> orders[i].dt;
}
sort(orders, orders + k);
for (int i = 0; i < k; ++i) {
const Order& u = orders[i];
// cout << u << "\n";
if (u.type) {
if (!que.empty()) {
mp[u.name] = que.front();
cout << u.name << " - " << que.front() << '\n';
que.pop();
} else {
wt_que.push(u);
waiting[u.name] = true;
}
} else {
if (mp.find(u.name) != mp.end()) {
while (!wt_que.empty() && !waiting[wt_que.front().name]) wt_que.pop();
if (!wt_que.empty()) {
const Order& v = wt_que.front(); wt_que.pop();
mp[v.name] = mp[u.name];
cout << v.name << " - " << mp[u.name] << '\n';
} else que.push(mp[u.name]);
mp.erase(u.name);
} else {
cout << u.name << " - NONE\n";
waiting[u.name] = false;
}
}
}
while (!que.empty()) {
cout << que.front(); que.pop();
cout << (que.empty() ? "\n" : " ");
}
return 0;
}词频统计
请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前10%的单词。
所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。
时间限制:8000
内存限制:65536
输入
输入给出一段非空文本,最后以符号#结尾。输入保证存在至少10个不同的单词。
输出
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写,例如“PAT”和“pat”被认为是同一个单词。 随后按照词频递减的顺序,按照词频:单词的格式输出词频最大的前10%的单词。若有并列,则按递增字典序输出。
样例输入
This is a test. The word “this” is the word with the highest frequency. Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this…# this line should be ignored.
样例输出
23 5:this 4:is
提示
(注意:虽然样例里单词the也出现了4次,但因为我们只要输出前10%(即23个单词中的前2个)单词,而按照字母序,the排第3位,所以不输出。)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef pair<string, int> PII;
map<string,int> mp;
map<string,int>::iterator it;
vector<PII> q;
bool cmp(PII a,PII b) // 自定义排序方式
{
if(a.second!=b.second) return a.second>b.second; // 出现的次数
else
return a.first<b.first; // 字母序
}
int main()
{
string s;
char x;
while(~scanf("%c",&x)&&x!='#') // 一个字符一个字符的读 遇到 # 结束
{
if( (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x>='0'&&x<='9') || x=='_')
{
if(x>='A'&&x<='Z') x=x-'A'+'a'; // 都转化成小写
if(s.size()<15) s+=x; // 如果大于 长度15 只要前十五个
}
else // 遇到非合法字符
{
if(s.size()>0) mp[s]++,s.clear(); // 存到map<string,int> 中去
}
}
for(it=mp.begin();it!=mp.end();it++) // 把map 中的信息转入到 vector中去 也可转到结构体中 用结构体解决
q.push_back({it->first,it->second});
sort(q.begin(),q.end(),cmp); // 按定义的方式排序
cout<<q.size()<<endl; // 输出一共单词个数
int l=q.size()/10;
for(int i=0;i<l;i++) // 遍历前10%
cout<<q[i].second<<':'<<q[i].first<<endl;
return 0;
}小白鼠再排队2(2024-3-6级)
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
//参考代码1
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct sb {
int z;
char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].z >> a[i].s;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < strlen(a[i].s); j++) {
cout << a[i].s[j];
}
cout << endl;
}
return 0;
}//参考代码2
#include <bits/stdc++.h>
using namespace std;
struct shu
{
int n;
string s;
}a[100010];
bool cmp(shu a,shu b)
{
return a.n<b.n;
}
int main()
{
int N;
cin>>N;
for(int i=0;i<N;i++)
{
cin>>a[i].n>>a[i].s;
}
sort(a,a+N,cmp);
for(int i=0;i<N;i++)
{
cout<<a[i].s<<endl;
}
}扩号匹配问题(2024-3-6级)
在某个字符串(长度不超过 100)中有左括号、 右括号和大小写字母;规定(与常见的算数式子一样) 任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。 写一个程序, 找到无法匹配的左括号和右括号, 输出原来字符串, 并在下一行标出不能匹配的括号。 不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
时间限制: 3000
内存限制: 65536
输入
输入包括多组数据, 每组数据一行, 包含一个字符串, 只包含左右括号和大小写字母, 字符串长度不超过 100
输出
对每组输出数据, 输出两行, 第一行包含原始输入字符, 第二行由"$","?"和空格组成, "$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x) )(rttyy())sss)(
样例输出
((ABCD(x) $$ )(rttyy())sss)( ? ?$
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
while (getline(cin, s)) { // 输入不结束
memset(ans, 0, sizeof(ans));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
cnt = 1;
cnn = 1; // 数据初始化
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
st.push(i); // 左括号统一入栈
}
if (s[i] == ')') {
if (!st.empty()) {
st.pop(); // 若栈非空,则可以匹配
} else {
a[cnt++] = i; // 否则无法匹配,记录
}
}
}
if (!st.empty())
while (!st.empty()) {
b[cnn++] = st.top();
st.pop();
} // 栈内数据(下标)的出栈
for (int i = 1; i < cnn; i++) {
ans[b[i]] = '$'; // 在ans内标记
}
for (int i = 1; i < cnt; i++) {
ans[a[i]] = '?'; // 在ans内标记
}
cout << s << endl;
for (int i = 0; i < s.size(); i++) {
if (ans[i] == 0)
cout << " ";
if (ans[i] == '$')
cout << "$";
if (ans[i] == '?')
cout << "?"; // 格式转化
}
cout << endl;
}
return 0;
}//解法2:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记
{
int lp = si;//当前左括号的下标
si++;
while(si < len)
{
if(s[si] == ')')
return;
else if(s[si] == '(')
find();
si++;
}
sign[lp] = '$';//没有找到右括号,左括号的位置标记为$
}
int main()
{
while(cin >> s)
{
len = strlen(s);
for(int i = 0; i < len; ++i)//初始化sign字符串为空格
sign[i] = ' ';
sign[len] = '\0';
si = 0;
while(si < len)
{
if(s[si] == ')')//右括号的位置标记为?
sign[si] = '?';
else if(s[si] == '(')
find();
si++;
}
cout << s << endl << sign << endl;
}
return 0;
}stack or queue(2024-3-6级)
栈和队列都是常用的线性结构,它们都提供两个操作:
Push:加入一个元素。
Pop:弹出一个元素。
不同的是,栈是”先进后出”,而队列则是”先进先出”。
给出一个线性结构的进出顺序,判定这个结构是栈还是队列。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表有t组测试数据 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 随后输入n行,每行包含两个整数 type val。 当type = 1时,表示该次操作为push操作,val表示进入的数字。当type=2时,表示该次操作为pop操作,val代表出来的数字。 3<=n<=2000
输出
每组测试数据输出一行。 输出该组数据对应的线性结构,”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。
样例输入
2 6 1 1 1 2 1 3 2 3 2 2 2 1 4 1 1 1 2 2 1 2 2
样例输出
Stack Queue
//参考代码1
#include <deque>
#include <iostream>
using namespace std;
int main() {
int t;
scanf("%d", &t);
deque<int> ds; // imitating stack
for (int i = 0; i < t; i++) {
int n;
bool tag = false;
scanf("%d", &n);
for (int j = 0; j < n; j++) {
int type, val;
scanf("%d%d", &type, &val);
if (tag)
continue;
if (type == 1) {
ds.push_back(val);
} else {
int s = ds.back();
ds.pop_back();
if (s != val) {
printf("Queue\n");
tag = true;
}
}
}
if (!tag)
printf("Stack\n");
ds.clear();
}
}//参考代码2
#include <bits/stdc++.h>
using namespace std;
string Struct;
bool H;
int push[2005];
int pop[2005];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,type,val,Innum=0,Outnum=0;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>type>>val;
if(type==1)
{
push[Innum++]=val;
}
else
{
pop[Outnum++]=val;
}
}
int num=min(Innum,Outnum);
H=false;
for(int i=0;i<num;++i)
{
if(push[i]!=pop[i])
{
Struct="Stack";
H=true;
break;
}
}
if(!H) Struct="Queue";
cout<<Struct<<endl;
}
return 0;
}利用队列进行数字排序(2024-3-6级)
对于 N 个数字, 有人提出了如下的排序策略:
例如, 对于数字 53、 47、 85、 38、 64、 23
先建立 10 个队列(0 到 9) , 用于存放数字的大小, 将这 N 个数字依个位存放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队。
例如, 对于上面的数字, 依次进队后, 结果如下:
队列 3: 53、 23 队列 4: 64 队列 5: 85 队列 7: 47 队列 8: 38
将其依次出队后, 结果为 53,23,64,85,47,38
然后, 再将方才出队后的队对, 依照十位放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队
例如, 对于上面刚刚出队的序列 53,23,64,85,47,38, 将其依次进队,结果如下:
队列 2: 23 队列 3: 38 队列 4: 47 队列 5: 53 队列 6: 64 队列 8: 85
将其依次出队后, 结果为 23,38,47,53,64,85.因为这组数字最大只是两位数, 所以排序结束。
如果还有更大的数字, 那么, 接下来就是其百位、 千位……(如果位数不够, 就补 0.比如最大的数字是四位数, 那么数字 23 就当成 0023处理)
请根据上述算法, 对这些数字进行排序
时间限制: 1000
内存限制: 65535
输入
分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999
输出
输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行:Step1. 之后用Queue0:...表示, 共 10 行, 结果用空格分隔, 下同 之后为第二次进队出队的结果(如果需要第二次进队出队的话) , 先显示一行: Step2. 之后仍然用 Queue0:...表示, 共 10 行 之后如果需要的话, 则分别显示第三次、 第四次的进队出队结果 第二部分为一行,即将数字排序后的结果(升序排序)
样例输入
20 41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
样例输出
Step1. Queue0:0 Queue1:41 81 61 91 Queue2:62 42 Queue3: Queue4:34 24 64 Queue5:5 45 95 Queue6:36 Queue7:67 27 27 Queue8:78 58 Queue9:69 Step2. Queue0:0 5 Queue1: Queue2:24 27 27 Queue3:34 36 Queue4:41 42 45 Queue5:58 Queue6:61 62 64 67 69 Queue7:78 Queue8:81 Queue9:91 95 0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MaxSize 2000
typedef struct ss {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q) {
q = (SqQueue *)malloc(sizeof(SqQueue));
q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, ElemType e) {
if (q->rear == MaxSize - 1)
return false;
q->rear++;
q->data[q->rear] = e;
return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
if (q->rear == q->front)
return false;
q->front++;
e = q->data[q->front];
return true;
}
int Num(int h) // 返回h的位数
{
int i = 0;
if (h == 0)
return 1;
while (h > 0) {
i++;
h /= 10;
}
return i;
}
int data(int g, int num) // 返回num的第g位数字
{
int result, i = 1;
int k = Num(num); // 获取位数
if (num == 0 || g > k)
return 0;
else if (num <= 9 && g == 1)
return num;
while (num >= 10 && i < g) {
num /= 10;
i++;
}
result = num % 10;
return result;
}
int main() {
int n, i = 0, j, a[100], max = 0, k = 0, e, t = 0;
scanf("%d\n", &n);
SqQueue *q[10];
for (i = 0; i < 10; i++) {
InitQueue(q[i]);
}
for (i = 0; i < n; i++) {
if (i != n - 1)
scanf("%d ", &a[i]);
else
scanf("%d", &a[i]);
} // a[i]='\0';
for (i = 0; i < n; i++) // 找出最大值
{
k = Num(a[i]);
if (k > max)
max = k;
}
// printf("%d\n",max);
for (i = 1; i <= max; i++) //
{
printf("Step%d.\n", i);
for (j = 0; j < 10; j++) { // 建立0-9的队对应的数字并输出
for (k = 0; k < n; k++) {
if (data(i, a[k]) == j)
enQueue(q[j], a[k]);
}
}
t = 0;
for (j = 0; j < 10; j++) {
printf("Queue%d:", j);
while (!QueueEmpty(q[j])) {
deQueue(q[j], e);
a[t++] = e;
printf("%d ", e);
}
printf("\n");
}
// printf("\n");
}
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
system("pause");
return 0;
}重链重排
给定一个单链表 L1→L2→…→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→…。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。
时间限制:1000
内存限制:65536
输入
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (≤ 105)。结点的地址是5位非负整数,NULL地址用-1表示。 接下来有N行,每行格式为: Address Data Next 其中`Address`是结点地址;`Data`是该结点保存的数据,为不超过105的正整数;`Next`是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出
对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。
样例输入
00100 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
样例输出
68237 6 00100 00100 1 99999 99999 5 12309 12309 2 00000 00000 4 33218 33218 3 -1
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
struct LinkNode
{
int address; //当前结点的地址
int data; //当前结点的数据
int next; //下一结点的地址
}node[MAX];
int main()
{
int Head,N; //头结点Head、结点总个数N
cin >> Head >> N;
for(int i = 0; i < N; i++)
{
int temp;
cin >> temp;
node[temp].address = temp;
cin >> node[temp].data >> node[temp].next;
}
vector<LinkNode> v,ans;
for(int i = Head; i != -1; i = node[i].next) //先根据地址来将链表排序
{
v.push_back(node[i]);
}
int l = 0, r = v.size()-1;
while(true) //链表重排
{
ans.push_back(v[r]);
r--;
if(r < l) break; //当r出现在l左侧时说明链表重排完成
ans.push_back(v[l]);
l++;
if(r < l) break; //当r出现在l左侧时说明链表重排完成
}
for(int i = 0; i < ans.size(); i++)
{
if(i != ans.size()-1)
{
printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i+1].address);
}
else
{
printf("%05d %d -1\n",ans[i].address,ans[i].data);
}
}
return 0;
}堆宝塔
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:
- 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。
- 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱放好。
- 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下,如果比最上面的小,就直接放上去;否则把 C 跟 B 柱最上面的彩虹圈比一下:
-- 如果 B 柱是空的、或者 C 大,就在 B 柱上放好;
-- 否则把 A 柱上串好的宝塔取下来作为一件成品;然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上,最后把 C 也放到 A 柱上。
重复此步骤,直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品,B 柱上剩下的彩虹圈被逐一取下,堆成另一座宝塔。问:宝宝一共堆出了几个宝塔?最高的宝塔有多少层?
时间限制:1000
内存限制:262144
输入
输入第一行给出一个正整数 N(≤ 103),为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数,对应每个彩虹圈的直径。
输出
在一行中输出宝宝堆出的宝塔个数,和最高的宝塔的层数。数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
11 10 8 9 5 12 11 4 3 1 9 15
样例输出
4 5
提示
样例解释:
宝宝堆成的宝塔顺次为: - 10、8、5 - 12、11、4、3、1 - 9 - 15、9
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n;
cin>>n;
stack<int>A,B;
int count=0;
int max1=0;
while(n--)
{
int C;
cin>>C;
if(A.empty()||C<A.top())
A.push(C);
else
{
if(B.empty()||C>B.top())
B.push(C);
else
{
max1=max(max1,A.size());
while(A.size())
A.pop();
count++;
while(!B.empty()&&B.top()>C)
{
A.push(B.top());
B.pop();
}
A.push(C);
}
}
}
if(!A.empty())
{
max1=max(max1,A.size());
count++;
while(!A.empty())
{
A.pop();
}
}
if(!B.empty())
{
max1=max(max1,B.size());
count++;
while(!B.empty())
{
B.pop();
}
}
cout<<count<<" "<<max1;
}一头进两头出
某队列允许在其两端进行出队操作,但仅允许在一端进行入队操作。现给定入队的序列,请你判断一系列出队序列是否可能。例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。
时间限制:1000
内存限制:262144
输入
输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。
输出
对每个需要查验的出队序列,如果是可能的,则在一行中输出 `yes`,否则输出 `no`。
样例输入
5 4 10 2 3 4 5 10 3 2 5 4 5 10 3 2 4 2 3 10 4 5 3 5 10 4 2
样例输出
yes no yes yes
整理中……
学生课表
某大学有 40000 名学生,开了 2500 门课。给定所有课程的选课名单,你的任务是为每一位前来查询的学生打印其选课的课表。
时间限制:2000
内存限制:262144
输入
输入第一行给出 2 个正整数:N(≤ 40000)为查询课表的学生人数;K(≤ 2500)为课程总数。 下面给出每门课的选课名单(课程从 1 到 K 编号),格式为: 课程编号 选课人数 学生姓名1 学生姓名2 ... 其中 选课人数 不超过 200 人。学生姓名由 3 个英文大写字母和 1 位数字组成。 最后一行给出 N 个前来查询的学生姓名。 一行中的数字和姓名都以空格分隔。
输出
对每个前来查询的学生,在一行中输出学生的姓名、选课门数、升序输出的课程编号,其间以 1 个空格分隔。行首尾不得有多余空格。
样例输入
11 5 4 7 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 1 4 ANN0 BOB5 JAY9 LOR6 2 7 ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6 3 1 BOB5 5 9 AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9
样例输出
ZOE1 2 4 5 ANN0 3 1 2 5 BOB5 5 1 2 3 4 5 JOE4 1 2 JAY9 4 1 2 4 5 FRA8 3 2 4 5 DON2 2 4 5 AMY7 1 5 KAT3 3 2 4 5 LOR6 4 1 2 4 5 NON9 0
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
// 比较函数,用于对课程编号进行升序排序
bool compareCourse(const int& a, const int& b) {
return a < b;
}
int main() {
int N, K;
cin >> N >> K;
// 使用哈希表存储每门课程的选课学生姓名
unordered_map<int, vector<string>> courseToStudents;
// 读取每门课程的选课名单
for (int i = 0; i < K; ++i) {
int courseId, numStudents;
cin >> courseId >> numStudents;
vector<string> students;
for (int j = 0; j < numStudents; ++j) {
string studentName;
cin >> studentName;
students.push_back(studentName);
courseToStudents[courseId].push_back(studentName);
}
}
// 读取前来查询的学生姓名
vector<string> queryStudents;
for (int i = 0; i < N; ++(i)) {
string studentName;
cin >> studentName;
queryStudents.push_back(studentName);
}
// 为每个查询的学生打印课表
for (const string& studentName : queryStudents) {
vector<int> selectedCourses;
// 遍历所有课程,查找该学生所选的课程
for (const auto& coursePair : courseToStudents) {
const vector<string>& students = coursePair.second;
if (find(students.begin(), students.end(), studentName)!= students.end()) {
selectedCourses.push_back(coursePair.first);
}
}
// 对所选课程进行升序排序
sort(selectedCourses.begin(), selectedCourses.end(), compareCourse);
// 输出学生课表信息
cout << studentName << " " << selectedCourses.size() << " ";
for (int courseId : selectedCourses) {
cout << courseId << " ";
}
cout << endl;
}
return 0;
}删除字符串


#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, stk;
cin >> s;
for (char c : s) {
stk.push_back(c);
// 长度够3个字符才可以校验XYZ
if (stk.size() >= 3) {
int len = stk.size();
if (stk[len - 3] == 'X' && stk[len - 2] == 'Y' && stk[len - 1] == 'Z') {
// 弹出末尾三位
stk.pop_back();
stk.pop_back();
stk.pop_back();
}
}
}
cout << stk << '\n';
return 0;
}空间折叠




#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int H, W;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
// 普通四方向步行偏移
int dir4[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> H >> W;
int ch, cw, dh, dw;
cin >> ch >> cw >> dh >> dw;
// 输入下标1转0
int sx = ch - 1, sy = cw - 1;
int tx = dh - 1, ty = dw - 1;
for (int i = 0; i < H; i++) cin >> grid[i];
memset(dist, 0x3f, sizeof dist);
dist[sx][sy] = 0;
deque<pii> dq;
dq.emplace_back(sx, sy);
while (!dq.empty())
{
auto [x, y] = dq.front();
dq.pop_front();
int curCost = dist[x][y];
// 到达终点直接提前输出答案
if (x == tx && y == ty) break;
// 行动1:步行,代价0
for (auto &d : dir4)
{
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (grid[nx][ny] == '#') continue;
if (dist[nx][ny] > curCost)
{
dist[nx][ny] = curCost;
dq.emplace_front(nx, ny);
}
}
// 行动2:空间折叠,5*5范围,代价+1
for (int dr = -2; dr <= 2; dr++)
{
for (int dc = -2; dc <= 2; dc++)
{
int nx = x + dr, ny = y + dc;
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (grid[nx][ny] == '#') continue;
if (dist[nx][ny] > curCost + 1)
{
dist[nx][ny] = curCost + 1;
dq.emplace_back(nx, ny);
}
}
}
}
int ans = dist[tx][ty];
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}宝可梦


#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
ll dp0 = 0, dp1 = -INF;
for (int i = 0; i < n; ++i)
{
ll x;
cin >> x;
ll nd0 = dp0, nd1 = dp1; // 不放走:原样继承
// 选择击败进行状态更新
nd0 = max(nd0, dp1 + 2 * x);
nd1 = max(nd1, dp0 + x);
dp0 = nd0; dp1 = nd1;
}
cout << max(dp0, dp1) << '\n';
return 0;
}L形硬币


#include <iostream>
#include <string>
using namespace std;
const int MAXN = 2005;
int row[MAXN], col[MAXN];
string grid[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; ++i)
{
cin >> grid[i];
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 'o')
{
row[i]++;
col[j]++;
}
}
}
long long ans = 0; // 防止int溢出,2000*2000量级乘积会超int范围
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 'o')
ans += 1LL * (row[i] - 1) * (col[j] - 1);
}
}
cout << ans << '\n';
return 0;
}能量槽
题目描述
在实验室中,有一个“能量槽”和 n 个待处理的能量块。第i个能量块的能级为ai,其蕴含的能量为2ai。
实验需按顺序执行n次操作,第i次操作流程如下:
(1)将第i个能量块放入堆槽的顶部。
(2)随后启动“自动融合程序”,重复执行以下检查,直到无法继续:
若槽中能量块数量≤1,停止融合。
若顶部第 1 个与第 2 个能量块的能级不同,停止融合。
若顶部两个能量块能级相同,则将它们从槽中移除,并向顶部放入一个能级为原能级 + 1的新能量块,其能量为两者之和。
再次回到检查步骤,继续尝试融合。
求 n 次操作全部完成后,槽中剩余的能量块总数。
输入格式
第一行,一个整数n。
接下来 n 行,每行一个整数 ai。
输出格式
输出 n 次操作结束后槽中剩余能量块的数量。
输入样例#1
7 2 1 1 3 5 3 3
输出样例#1
3
输入样例#2
5 0 0 0 1 2
输出样例#2
4
说明提示:
1≤n≤2×10^5,0≤ai≤10^9,输入均为整数。
限制:
时间限制:1000ms,内存限制:256MiB
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
stack<long long> st; // 存储能级,用 long long 防止溢出
while (n--) {
long long x;
cin >> x;
st.push(x);
// 循环合并栈顶两个相同的元素
while (st.size() >= 2) {
// 取出栈顶两个
long long a = st.top(); st.pop();
long long b = st.top(); st.pop();
if (a == b) {
// 相同则合并成 +1 级,重新压入
st.push(a + 1);
} else {
// 不同则放回,停止合并
st.push(b);
st.push(a);
break;
}
}
}
// 最终栈大小就是答案
cout << st.size() << endl;
return 0;
}星际探险
题目描述
星际探险队计划从 n 名候选者中挑选队员组成小队,每名候选者只能入选一次。
飞船上有 m 个关键系统,第 i 名候选者的加入会对第 j 个系统的状态值产生 (ai, j) 的影响,影响可正可负。
探险安全条例要求,最终小队组成后,每个系统的状态值总和都必须不低于 0,否则飞船无法维持安全航行。
在满足该要求的前提下,希望小队的人数尽可能多,请输出这个最大人数。若不存在任何满足条件的选人方案,输出0。
输入格式
第一行:两个整数表示 n 与 m;
第二行到第 n+1 行:第 i+1 行有 m 个整数,表示 (ai,1)、(ai,2)、……、(ai,m)。
输出格式
单个整数:表示答案。
输入样例
4 3 1 1 -2 1 -2 1 -2 1 1 2 2 2
输出样例
4
说明提示:
1≤n、m≤16,1,000,000≤ (ai, j) ≤1,000,000。
限制:
时间限制:1000ms,内存限制:256MiB
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
// 存储每个人对m个系统的贡献
vector<vector<long long>> a(n, vector<long long>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int max_people = 0;
// 枚举所有子集:mask 二进制第i位=1表示选第i个人
for (int mask = 1; mask < (1 << n); ++mask) {
int cnt = __builtin_popcount(mask); // 选中的人数
if (cnt <= max_people) continue; // 剪枝:人数更少直接跳过
vector<long long> sum(m, 0);
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) { // 选了第i个人
for (int j = 0; j < m; ++j) {
sum[j] += a[i][j];
}
}
}
// 检查所有系统是否都 ≥ 0
bool ok = true;
for (long long s : sum) {
if (s < 0) {
ok = false;
break;
}
}
if (ok) {
max_people = cnt;
}
}
cout << max_people << endl;
return 0;
}博弈游戏
题目描述
两位玩家进行回合制博弈游戏,游戏总计进行 n 轮。每一轮,双方都要从1、2、3三个数字中选择一个出招,胜负规则如下:
(1)若双方选择的数字相同,本轮为平局;
(2)若数字不同,胜负遵循固定克制关系:1克制2,2克制3,3克制1,被克制的一方本轮落败,克制的一方本轮获胜。
其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si,所有 si 组成一个长度为 n 的序列。
该玩家需要规划自己每一轮的出招,满足以下全部条件:
(1)任何一轮都不能落败(即每一轮只能获胜或平局);
(2)不能连续两轮选择相同的数字出招;
(3)在满足前两个条件的前提下,尽可能多地获得轮次的胜利。
请计算该玩家最多能赢得的轮次数量。
输入格式
第一行:一个整数表示n。
第二行:n 个整数,表示s1、s2、……、sn,每个数为1、2或3。
输出格式
输出一个整数,表示玩家最多能赢得的游戏轮数。
输入样例#1
6 3 1 2 2 1 2
输出样例#1
5
输入样例#2
24 2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2
输出样例#2
18
说明提示:
1≤n≤200,000,si∈{1,2,3}
限制:
时间限制:1000ms,内存限制:256MiB
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int ans = 0;
int last = 0; // 上一轮出的数
for (int x : s) {
int win; // 能赢的数
int draw = x; // 能平的数
// 计算克制关系:1克2,2克3,3克1
if (x == 1) win = 3;
else if (x == 2) win = 1;
else win = 2;
// 优先选赢的,只要不和上一轮重复
if (win != last) {
ans++;
last = win;
}
// 不能赢 → 只能平
else {
last = draw;
}
}
cout << ans << endl;
return 0;
}作品选拔
题目描述
创新大赛组委会收到了 n 件学生参赛作品,每件作品都有对应的综合评审得分,其中第 i 件作品的得分为 ai。
根据赛事章程,组委会需从所有备选作品中选出 m 件作品晋级市级终评。为保障终评作品的整体质量,要求选出的 m 件作品中,至少有 k 件作品的综合得分不低于赛事划定的基准线 x。
请你帮助组委会计算,一共有多少种符合要求的作品遴选方案?由于答案数值可能过大,请输出方案数对998244353取模后的结果。
输入格式
第一行,两个正整数n、m;
第二行,n 个正整数,分别表示 a1、a2、……、an;
第三行,两个正整数 k、x。
输出格式
输出满足条件的方案数对 998244353 取模后的结果。
输入样例#1
3 2
10 20 30
1 20
输出样例#1
3
输入样例#2
4 2
5 10 15 20
1 12
输出样例#2
5
说明提示:
对于50%的数据,1≤n≤20;
对于100%的数据,1≤n≤1000,1≤k≤m≤n,1≤ai、x≤10^9。
限制:
时间限制:1000ms,内存限制:256MiB
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
const int MAX = 1005;
long long C[MAX][MAX];
// 预处理组合数 C(n, k)
void init() {
C[0][0] = 1;
for (int i = 1; i < MAX; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
int main() {
init();
// 第一步:读 n, m
int n, m;
cin >> n >> m;
// 第二步:读 n 个分数
int a[MAX];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 第三步:读 k, x
int k, x;
cin >> k >> x;
// 统计高分、低分数量
int high = 0, low = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) high++;
else low++;
}
// 计算答案
long long ans = 0;
int max_t = min(high, m);
for (int t = k; t <= max_t; t++) {
int need = m - t;
if (need < 0 || need > low) continue;
ans = (ans + C[high][t] * C[low][need]) % MOD;
}
cout << ans << endl;
return 0;
}