C/C++编程七级 题库
红色警报
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。
时间限制:5000
内存限制:65536
输入
输入在第一行给出两个整数 N(0 < N <=500)和 M(<=5000),分别为城市个数(于是默认城市从 0 到 N-1 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以 1 个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数 K 和随后的 K 个被攻占的城市的编号。 注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。
输出
对每个被攻占的城市,如果它会改变整个国家的连通性,则输出“Red Alert: City k is lost!”,其中k是该城市的编号;否则只输出“City k is lost.”即可。如果该国失去了最后一个城市,则增加一行输出“Game Over.”。
样例输入
5 4 0 1 1 3 3 0 0 4 5 1 2 0 4 3
样例输出
City 1 is lost. City 2 is lost. Red Alert: City 0 is lost! City 4 is lost. City 3 is lost.
//参考代码1
#include<cstdio>
#include<cstring>
using namespace std;
int pre[505];
bool del[505];
struct node{
int x,y;
}p[5005];
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void merge(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx!=fy)
pre[fx] = fy;
}
int main(){
int n,m,k,x;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
pre[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&p[i].x,&p[i].y);
merge(p[i].x,p[i].y);
}
int ans=0;
for(int i=0;i<n;i++){
if(i==pre[i]) ans++;
}
scanf("%d",&k);
while(k--){
scanf("%d",&x);
del[x]=true;
for(int i=0;i<n;i++)
pre[i]=i;
for(int i=1;i<=m;i++){
if(!del[p[i].x]&&!del[p[i].y])
merge(p[i].x,p[i].y);
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(pre[i]==i&&!del[i])
cnt++;
}
if(cnt>ans)
printf("Red Alert: City %d is lost!\n",x);
else
printf("City %d is lost.\n",x);
ans=cnt;
if(ans==0)
printf("Game Over.\n");
}
return 0;
}//参考代码2
#include<bits/stdc++.h>
using namespace std;
#define N 510
#define M 5010
int n ,m ,k ,vis[N] ,p[N];
struct node {
int x;
int y;
}g[M];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
p[i] = i;
for (int i = 0; i < m; i++) {
cin >> g[i].x >> g[i].y;
if (find(g[i].x) != find(g[i].y))
p[find(g[i].x)] = find(g[i].y);
}
int cnt1 = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i)
cnt1 ++;
}
cin >> k;
for (int j = 0; j < k; j++) {
int x ,cnt2 = 0;
cin >> x;
vis[x] = 1;
for (int i =0 ; i < n; i++)
p[i] = i;
for (int i = 0; i < m; i++) {
if (vis[g[i].x] == 1 ||vis[g[i].y] == 1)
continue;
if (find(g[i].x) != find(g[i].y))
p[find(g[i].x)] = find(g[i].y);
}
for (int i = 0; i < n; i++) {
if (p[i] == i)
cnt2++;
}
if (cnt2 - cnt1 > 1)
printf ("Red Alert: City %d is lost!\n" ,x);
else
printf ("City %d is lost.\n" ,x);
cnt1 = cnt2;
}
if (k >= n) cout << "Game Over.\n";
return 0;
}到底爱不爱我
古代少女有了心上人时,会悄悄折一条树枝,揪那枝上的叶子,揪一片叶子念一句“爱我”,再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候,看看是停在“爱”还是“不爱”。
但聪明的慧娘一眼洞穿,只要数一下叶子有多少片,根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始,就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫,理科生杀死浪漫。
于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”:
- “专情枝”:是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候,这根枝条的根部才传出“爱”;否则树枝根部传出的是“不爱”。
- “博爱枝”:也是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候,这根枝条的根部才传出“不爱”;否则树枝根部传出的都是“爱”。
- “情变枝”:是没有分岔的一根直枝,如果一端接到“爱”,另一端必须传出“不爱”;反之如果一端接到“不爱”,另一端则会传出“爱”。
慧娘将这些树枝摆放在院子里,布了一个“情阵”,从某一枝的根部开始,扩散开去,令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来,在初始一枝的根部,她能得到“爱”还是“不爱”?
时间限制:10000
内存限制:65536
输入
输入在第一行中给出正整数 N(≤ 30),是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行,第 i 行给出第 i 枝的描述,格式为 类型 左分枝连接的编号 右分枝连接的编号 其中 `类型` 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝,则后面跟的是其唯一末端连接的情枝编号,并没有两个分枝的信息。如果一个分枝是末梢,并没有连接其它枝条,则对应编号为 0。 接下来一行中给出正整数 K(≤ 30),是慧娘询问的次数。以下 K 行,每行给出一个由 0 和 1 组成的字符串,其中 0 表示“不爱”,1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。
输出
对慧娘的每个询问,如果她在初始一枝的根部能得到“爱”,就输出 `Ai`;否则输出 `BuAi`。
样例输入
6 2 6 4 1 0 0 3 1 2 0 0 3 0 1 5 2 5 11111 00000 11100 10011 01100
样例输出
BuAi Ai Ai BuAi BuAi
提示
样例说明: 样例对应的情阵以及慧娘第 3 问的情势如图所示,其中完整的心对应 1,裂开的心对应 0。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int t,root,i,tree[44][3],p[44],f[44],n;
string s;
bool dfs(int u){
int x,y;
if(p[u]!=3){
if(tree[u][1])x=dfs(tree[u][1]);
else x=s[i++]-'0';
if(tree[u][2])y=dfs(tree[u][2]);
else y=s[i++]-'0';
if(p[u]==1)return x&&y;
return x||y;
}
else {
if(tree[u][1])return !dfs(tree[u][1]);
else return !(s[i++]-'0');
}
}
signed main(){
ios;
cin>>n;
for(int i=1,x,y;i<=n;i++){
cin>>p[i];
if(p[i]==1||p[i]==2){
cin>>x>>y;
tree[i][1]=x;
tree[i][2]=y;
f[x]=f[y]=1;
}
else {
cin>>x;
tree[i][1]=x;
f[x]=1;
}
}
for(int i=1;i<=n;i++){
if(f[i]==0){
root=i;
break;
}
}
cin>>t;
while(t--){
cin>>s;
i=0;
if(dfs(root))cout<<"Ai\n";
else cout<<"BuAi\n";
}
return 0;
}兰州拉面派餐系统
兰州拉面是著名美食,其煮面很有讲究,不同种类的面需要煮不同的时长。拉面馆的煮面师傅的规则很简单,只要手头有煮面篮子是空闲的,就把下一份客单指定的面放到空闲篮子里煮;如果空闲的篮子不止一个,那么先放到其中编号最小的篮子里煮;如果没有篮子是空闲的,就等待。一个篮子里的面煮够了时间,师傅要准时捞出来放到该客单对应的碗里,招呼服务员端给客人;如果有多个篮子里的面同时到了捞取时间,师傅会同时捞起,但要本着先到先得的原则,按下单顺序招呼送餐。
在生意火爆的拉面馆里,煮面师傅需要很强的记忆力和计时能力,才能面对源源不断的客单,同时照顾一大堆煮面篮子而不出错。如果面的品种不太多,篮子也不太多,那一位拉面师傅的大脑还是能应对的。但如果我们有上千种面、上万只煮面篮、数十万客单呢…… 这就需要请你帮忙,写个派餐系统来完成这个任务了。
时间限制:7000
内存限制:65536
输入
输入在第一行中给出 3 个正整数:N(≤ 103)为面的种类数;M(≤ 104)为煮面篮子的个数;L(≤ 105)为客单总数。于是我们假设面的种类从 1 到 N 编号、篮子从 1 到 M 编号、客单从 1 到 L 编号。 第二行给出 N 个不超过 10 的正整数,第 i 个数字对应第 i 种面需要煮的时间长度(分钟)。 第三行给出 L 个正整数,第 i 个数字对应第 i 份客单所点的面种 —— 这里我们将情况简化为一份客单只要一种面,并且只要一碗,所以只要给出面的种类即可。 一行中数字间以空格分隔。 因为面馆的生意太火爆,我们可以认为所有的客单都是在开门前就预约好的,并且是按预约的顺序递增编号的。此外,与煮面的时长相比,下面、捞面和送餐的时长是可以忽略不计的。
输出
首先按照送单顺序在一行中输出所有客单的编号和送餐时间,格式为 `编号:时间`。 随后在下一行按照编号递增序输出每只篮子煮了多少碗面。 一行的输出之间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
3 5 10 3 5 8 2 1 3 3 1 1 2 1 3 2
样例输出
2:3 5:3 1:5 6:6 3:8 4:8 7:8 8:8 10:13 9:14 3 3 1 1 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
int n,m,l;
// t代表每种面需要的时间,c代表每个顾客需要的面的种类,cnt代表每个篮子被用的次数
int t[N], c[N], cnt[N];
// 小跟堆升序,维护篮子所用的时间和篮子编号
priority_queue<PII,vector<PII>,greater<PII>> heap;
// 维护时间,顾客编号,可以实现时间由小到大排序
vector<PII> ans;
//对时间相同的按编号从小到大排序
bool cmp(PII a,PII b)
{
if(a.first!=b.first) return a.first<b.first;
return a.second<b.second;
}
int main()
{
cin>>n>>m>>l;
for(int i=1;i<=n;i++) cin>>t[i]; // 每种面需要的时间
for(int i=1;i<=l;i++) cin>>c[i]; // 每个顾客需要的面的种类
for(int i=1;i<=m;i++) heap.push({0,i}); // 开始时间都是0,然后对篮子编号
for(int i=1;i<=l;i++)
{
auto u=heap.top(); // 取当前时间被用最短的篮子
heap.pop();
int id=u.second, time=u.first;
cnt[id]++;
ans.push_back({time+t[c[i]], i});
heap.push({time+t[c[i]],id});
}
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<l;i++)
{
if(i!=l-1) cout<<ans[i].second<<":"<<ans[i].first<<" ";
else cout<<ans[i].second<<":"<<ans[i].first<<endl;
}
for(int i=1;i<=m;i++)
{
if(i!=m) cout<<cnt[i]<<" ";
else cout<<cnt[i]<<endl;
}
return 0;
}有多少种二叉树(2024-3-7级)
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <iostream>
using namespace std;
long long cat(int n) {
if (n == 0)
return 1;
long long sum(0);
for (int i = 0; i < n; i++)
sum += cat(i) * cat(n - 1 - i);
return sum;
}
int main() {
int n;
cin >> n;
cout << cat(n);
return 0;
}快速堆猪(2024-3-7级)
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u){
while(u/2&&h[u/2]>h[u]){
swap(h[u/2],h[u]);
u/=2;
}
}
void down(int u){
int t=u;
if(u*2<=size_&&h[u*2]<h[u]) t=u*2;
if(u*2+1<=size_&&h[u*2+1]<h[u]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);down(t);
}
}
int main()
{
char t[10];
string s;
int n;
while(scanf("%s",t)!=EOF){
s=string(t);
if(s=="pop"){
if(size_==0) continue;
h[1]=h[size_];
size_--;
down(1);
}
else if(s=="min"){
if(size_==0) continue;
cout<<h[1]<<endl;
}
else if(s=="push"){
cin>>n;
size_++;
h[size_]=n;
up(size_);
}
}
return 0;
}二叉树遍历
题目描述
有一棵二叉树,结点数量不超过 26 个,树上的每个结点都有一个大写字母。
给定这棵二叉树的中序遍历及后序遍历,请输出它的前序遍历。
输入格式
第一行:一个字符串,表示二叉树的中序遍历;
第二行:一个字符串,表示二叉树的后序遍历。
输出格式
单独一行:一个字符串,表示二叉树的前序遍历。
输入样例
DBEAC
DEBCA
输出样例
ABDEC
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <string>
using namespace std;
// 中序in, 后序post, 输出前序
void build(string in, string post) {
if (in.empty()) return;
// 后序最后一个是根
char root = post.back();
cout << root;
int pos = in.find(root);
// 递归左右
build(in.substr(0, pos), post.substr(0, pos));
build(in.substr(pos+1), post.substr(pos, in.size()-pos-1));
}
int main() {
string in, post;
cin >> in >> post;
build(in, post);
return 0;
}平衡运输
题目描述
远古遗迹中发掘出了 n 件魔力核心,第 i 件核心蕴含的能量为 ki。
为了安全运输,需要将这些核心分配到两个不同的能量舱(记为舱 A 和舱 B)中。
每件核心必须整个放入一个舱,不可拆分。
分配完成后,设舱 A 的总能量为 sa,舱 B 的总能量为 sb。
为了平衡运输风险,希望两个舱中总能量较大的一方尽可能小,即最小化 max(sa,sb)。
请你计算这个最小的最大值。
输入格式
第一行,一个整数 n。
第二行,n 个整数 k1,k2,…,kn。
输出格式
输出一个整数,表示 max(sa,sb) 的最小可能值。
输入样例#1
5 2 3 5 10 12
输出样例#1
17
输入样例#2
6 22 25 26 45 22 31
输出样例#2
89
说明提示
2≤n≤20
1≤ki≤108
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
int N;
int A[20];
int S = 0;
int solve(int i, int sum)
{
if (i == N)
{
return std::max(sum, S - sum);
}
else
{
auto pick = solve(i + 1, sum + A[i]);
auto drop = solve(i + 1, sum);
return std::min(pick, drop);
}
}
int main()
{
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
S += A[i];
}
std::cout << solve(0, 0) << "\n";
}专属教室
题目描述
在一所学校中,有 N 个班级,每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si,但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同,所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室,且一次只能安排一个班级进行更换。在更换时,目标教室必须是空闲的。
学校希望找到一个合理的更换顺序,使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行,每行两个字符串 Si 和 Ti,表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换,输出 Yes,否则输出 No。
输入样例#1
2 b m m d
输出样例#1
Yes
输入样例#2
3 a b b c c a
输出样例#2
No
说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串,长度在 1 到 8 之间。
Si≠Ti
所有 Si 互不相同。
所有 Ti 互不相同。
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<string, vector<string>> adj;
map<string, int> state;
bool has_cycle(string v) {
state[v] = 1;
for (string next_v : adj[v]) {
if (state[next_v] == 1) return true;
if (state[next_v] == 0) {
if (has_cycle(next_v)) return true;
}
}
state[v] = 2;
return false;
}
int main() {
int N;
cin >> N;
vector<string> S(N), T(N);
for (int i = 0; i < N; i++) {
cin >> S[i] >> T[i];
adj[S[i]].push_back(T[i]);
}
for (auto const& [name, _] : adj) {
if (state[name] == 0) {
if (has_cycle(name)) {
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}数字之和
题目描述
给定一个数字字符串 n,定义一次操作为:移除字符串中一个非空子串,并将剩余部分拼接形成新数字。
求所有可能操作方案生成的新数字之和,结果对 109+7取模。
输入格式
一行字符串 n
输出格式
一个整数,表示所有方案生成数字之和取模后的结果。
输入样例#1
1003
输出样例#1
339
输入样例#2
123
输出样例#2
52
说明提示
【数据范围】
1≤∣n∣≤105,| n |表示字符串长度。
限制
时间限制:1000ms
内存限制:256MiB
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_LEN = 1e5 + 10;
long long pow10[MAX_LEN];
long long inv9, inv81;
long long mod_pow(long long base, long long exp, int mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
void precompute(int L) {
pow10[0] = 1;
for (int i = 1; i <= L; ++i) {
pow10[i] = (pow10[i - 1] * 10) % MOD;
}
inv9 = mod_pow(9, MOD - 2, MOD);
inv81 = mod_pow(81, MOD - 2, MOD);
}
int main() {
string n;
cin >> n;
int L = n.size();
precompute(L);
long long ans = 0;
for (int k = 0; k < L; ++k) {
int d = n[k] - '0';
if (d == 0) {
continue; // 贡献为0,可直接跳过
}
// 计算左侧贡献
long long left = 0;
if (k > 0) {
long long count = (1LL * k * (k + 1)) / 2 % MOD;
int exponent = L - k - 1;
long long pow_val = pow10[exponent];
left = (count * pow_val) % MOD;
}
// 计算右侧贡献
long long right = 0;
int exponent = L - k - 1;
if (exponent > 0) {
long long part1 = (1LL * (L - k - 1) * pow10[exponent]) % MOD;
long long term1 = (part1 * inv9) % MOD;
long long part2 = (pow10[exponent] - 1 + MOD) % MOD;
long long term2 = (part2 * inv81) % MOD;
right = (term1 - term2 + MOD) % MOD;
}
long long total = (left + right) % MOD;
ans = (ans + 1LL * d * total) % MOD;
}
cout << ans << endl;
return 0;
}花车巡游
题目描述
嘉年华的花车巡游正在展示精心编排的队列变换!
最初,所有 N辆花车排成一行,花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中:
· 第 1 分钟:位置 a1 与 b1 的花车交换位置
· 第 2 分钟:位置 a2 与 b2 的花车交换位置
· ……
· 第 K 分钟:位置 aK 与 bK 的花车交换位置
· 第 K+1 分钟:重新从 (a1,b1) 开始交换(即位置 a1 与 b1 交换)
· 第 K+2 分钟:位置 a2 与 b2 交换
· 如此无限循环……
请计算每辆花车在整个表演过程中能到达的不同位置数量。
输入格式
第一行输入 N,K。
接下来 K 行每行包含 ai,bi(1≤ai<bi≤N)。
输出格式
输出 N行,第 i行为花车 i能到达的不同位置数量。
输入样例
5 4 1 3 1 2 2 3 2 4
输出样例
4 4 3 4 1
说明提示
样例解释
· 花车 1 可到达位置 {1,2,3,4}
· 花车 2 可到达位置 {1,2,3,4}
· 花车 3 可到达位置 {1,2,3}
· 花车 4 可到达位置 {1,2,3,4}
· 花车 5 始终在位置 5(未移动)
【数据范围】
1≤K≤2×105
2≤N≤105
限制
时间限制:1000ms
内存限制:256MiB
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<pair<int, int>> swaps(K);
unordered_set<int> S;
for (int i = 0; i < K; ++i) {
int a, b;
cin >> a >> b;
swaps[i] = {a, b};
S.insert(a);
S.insert(b);
}
// 计算P = Q_K,即经过K步后的置换
vector<int> Q(N + 1), R(N + 1); // 1-based
for (int i = 1; i <= N; ++i) {
Q[i] = i;
R[i] = i;
}
for (auto [a, b] : swaps) {
int x1 = R[a];
int x2 = R[b];
swap(R[a], R[b]);
swap(Q[x1], Q[x2]);
}
vector<int> P = Q; // P是Q_K
// 对P进行循环分解
vector<bool> visited(N + 1, false);
vector<vector<int>> cycles;
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
vector<int> cycle;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
cycle.push_back(cur);
cur = P[cur];
}
cycles.push_back(cycle);
}
}
// 为每个循环计算答案
vector<int> ans(N + 1);
for (auto& cycle : cycles) {
// 检查循环是否与S有交集
bool has_intersection = false;
for (int x : cycle) {
if (S.count(x)) {
has_intersection = true;
break;
}
}
if (!has_intersection) {
// 答案是循环大小
int sz = cycle.size();
for (int x : cycle) {
ans[x] = sz;
}
continue;
}
// 模拟current_set的变化,计算Y的大小
unordered_set<int> current_set(cycle.begin(), cycle.end());
unordered_set<int> Y(current_set.begin(), current_set.end());
for (int t = 0; t < K - 1; ++t) { // t处理0到K-2,对应步骤1到K-1
auto [a, b] = swaps[t];
bool has_a = current_set.count(a);
bool has_b = current_set.count(b);
if (has_a && has_b) {
// 交换后集合不变
continue;
} else if (has_a) {
current_set.erase(a);
current_set.insert(b);
Y.insert(b);
} else if (has_b) {
current_set.erase(b);
current_set.insert(a);
Y.insert(a);
}
// 否则集合不变
}
int res = Y.size();
for (int x : cycle) {
ans[x] = res;
}
}
for (int i = 1; i <= N; ++i) {
cout << ans[i] << '\n';
}
return 0;
}公平
题目描述
有多干所精英学院和 N 名天才学员(编号 1 到 N)。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。
联盟定期进行学员调院操作(共 Q 次):第 j次操作将学员 Cj 调到学院 Dj。
联盟公平指数定义为:
对每所至少有一名学员的学院,取该学院最高能力值;再取这些最高能力值中的最小值。
请计算每次调院操作后的联盟公平指数。
输入格式
· 第一行:N Q
· 接下来 N 行:每行 Ai Bi,表示学员 ii 的能力值和初始学院
· 接下来 Q 行:每行 Cj Dj,表示将学员 Cj 调到学院 Dj
输出格式
· Q 行:每行一个整数,表示每次操作后的公平指数
输入样例#1
6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2
输出样例#1
6
2
6
输入样例#2
2 2
4208 1234
3056 5678
1 2020
2 2020
输出样例#2
3056
4208
说明提示
1≤N,Q≤2×105,1≤N,Q≤2×105
1≤Ai≤109,1≤Ai≤109
1≤Cj≤N,1≤Cj≤N
1≤Bi,Dj≤2×105,1≤Bi,Dj≤2×105
输入均为整数
每次转园操作会改变所属学院
限制
时间限制:1000ms
内存限制:256MiB
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<int> ability(N + 1);
vector<int> current_college(N + 1);
unordered_map<int, multiset<int>> college_students;
for (int i = 1; i <= N; ++i) {
int A, B;
cin >> A >> B;
ability[i] = A;
current_college[i] = B;
college_students[B].insert(A);
}
multiset<int> global_max;
for (const auto& pair : college_students) {
const auto& s = pair.second;
if (!s.empty()) {
global_max.insert(*s.rbegin());
}
}
while (Q--) {
int Cj, Dj;
cin >> Cj >> Dj;
int c = Cj;
int a = ability[c];
int old_college = current_college[c];
int new_college = Dj;
// 处理旧学院
auto& old_set = college_students[old_college];
int x = *old_set.rbegin();
auto it_old = old_set.find(a);
old_set.erase(it_old);
if (old_set.empty()) {
auto it_global = global_max.find(x);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
college_students.erase(old_college);
} else {
int x_new = *old_set.rbegin();
if (x_new != x) {
auto it_global = global_max.find(x);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
global_max.insert(x_new);
}
}
// 处理新学院
auto& new_set = college_students[new_college];
bool was_empty = new_set.empty();
int y = 0;
if (!was_empty) {
y = *new_set.rbegin();
}
new_set.insert(a);
int y_new = *new_set.rbegin();
if (was_empty) {
global_max.insert(y_new);
} else {
if (y_new != y) {
auto it_global = global_max.find(y);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
global_max.insert(y_new);
}
}
current_college[c] = new_college;
cout << *global_max.begin() << '\n';
}
return 0;
}子序列
题目描述
给定两个整数序列,第一个序列长度为 n,第二个序列长度为 m。请问,这两个序列有多少种公共的子序列?输出数量模 998244353 的余数。
所谓子序列,是指从原序列中选择部分或全部元素组成新序列,这些元素在原序列中不必连续,但要保持在原序列中的顺序。只要下标不同,哪怕数字相同,也要算成不同的子序列。
输入格式
第一行:两个整数表示 n 与 m;
第二行: n 个数字 a1,a2,... ,an;
第三行:m 个数字 b1,b2,... ,bm;
输出格式
单个整数表示答案。
输入样例
4 3 3 4 6 2 3 3 2
输出样例
6
说明提示
1≤n,m≤2000
1≤ai,bj≤100,000
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 空子序列
for (int i = 0; i <= n; ++i) dp[i][0] = 1;
for (int j = 0; j <= m; ++j) dp[0][j] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i-1] == b[j-1]) {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
} else {
dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
}
if (dp[i][j] < 0) dp[i][j] += MOD;
}
}
cout << dp[n][m] << endl;
return 0;
}逻辑表达式
题目描述
给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^:
& 表示逻辑与运算
| 表示逻辑或运算
^ 表示逻辑异或运算
表达式还包含三种基本逻辑值:0、1、?。
每个 ? 必须赋值成为 0 或 1 中的一种,请问有多少种不同的赋值方式,可以让整个逻辑表达式的值为 0?
由于答案可能很大,请输出方案数模1,000,000,007 的余数。
前缀表达式的定义如下:
0、1、? 都是前缀表达式;
如果 x,y 都是前缀表达式,则 &xy、|xy、^xy 都是前缀表达式;
不满足以上两条规则的表达式都不是前缀表达式。
输入格式
单个字符串表示输入的前缀表达式
输出格式
单个整数:表示答案模 1,000,000,007 的余数。
输入样例#1
&??
输出样例#1
3
输入样例#2
||??|||?^?|0|1&???|??
输出样例#2
4
输入样例#3
|?^?|0|&??||?^?|1??
输出样例#3
64
说明提示
设 ∣s∣表示输入字符串的长度
50%的数据,1≤∣s∣<1,000
100%的数据,1≤∣s∣<200,000
限制
时间限制:1000ms
内存限制:512MiB
//C语言参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef struct {
long long zero;
long long one;
} Node;
Node stack[200000];
int top = -1;
void push(Node node) {
stack[++top] = node;
}
Node pop() {
return stack[top--];
}
int main() {
char s[200001];
scanf("%s", s);
int len = strlen(s);
for (int i = len - 1; i >= 0; i--) {
char c = s[i];
if (c == '0') {
push((Node){1, 0});
} else if (c == '1') {
push((Node){0, 1});
} else if (c == '?') {
push((Node){1, 1});
} else {
Node right = pop();
Node left = pop();
Node res = {0, 0};
if (c == '&') {
res.zero = (left.zero * right.zero % MOD + left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
res.one = left.one * right.one % MOD;
} else if (c == '|') {
res.zero = left.zero * right.zero % MOD;
res.one = (left.one * right.zero % MOD + left.zero * right.one % MOD + left.one * right.one % MOD) % MOD;
} else if (c == '^') {
res.zero = (left.zero * right.zero % MOD + left.one * right.one % MOD) % MOD;
res.one = (left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
}
push(res);
}
}
Node result = pop();
printf("%lld\n", result.zero);
return 0;
}//C++参考代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
struct Node {
long long zero, one;
Node(long long z=0, long long o=0) : zero(z), one(o) {}
};
int main() {
string s;
cin >> s;
stack<Node> st;
for (int i = s.size()-1; i >= 0; --i) {
char c = s[i];
if (c == '0') {
st.push(Node(1, 0));
} else if (c == '1') {
st.push(Node(0, 1));
} else if (c == '?') {
st.push(Node(1, 1));
} else {
Node right = st.top(); st.pop();
Node left = st.top(); st.pop();
Node res;
if (c == '&') {
res.zero = (right.zero * left.zero % MOD +
right.zero * left.one % MOD +
right.one * left.zero % MOD) % MOD;
res.one = right.one * left.one % MOD;
} else if (c == '|') {
res.zero = right.zero * left.zero % MOD;
res.one = (right.one * left.one % MOD +
right.one * left.zero % MOD +
right.zero * left.one % MOD) % MOD;
} else if (c == '^') {
res.zero = (right.zero * left.zero % MOD +
right.one * left.one % MOD) % MOD;
res.one = (right.zero * left.one % MOD +
right.one * left.zero % MOD) % MOD;
}
st.push(res);
}
}
cout << st.top().zero % MOD << endl;
return 0;
}联盟
题目描述
在国际会议上,共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况,请计算存在多少种合法的联盟分配方案。
输入格式
第一行:单个整数 n 表示国家数量
第二行到第 n 行:在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n,其中
ci,j=0-表示 i 号国家与 j 号国家不接壤
ci,j=1 表示 i 号国家与 j 号国家接壤
输出格式
单个整数:表示合法的联盟分配方案总数。
输入样例#1
3 1 1 1
输出样例#1
6
输入样例#2
4 1 1 1 1 1 1
输出样例#2
0
说明提示
数据范围
对于 50% 的数据,1≤n≤12
对于 100% 的数据,1≤n≤20
样例1说明
三国两两接壤,形成三角形。三个联盟的排列方案为 3!=6种。
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> adj;
vector<int> color;
int count = 0;
bool isValid(int country, int c) {
for (int i = 0; i < country; ++i) {
if (adj[i][country] && color[i] == c) {
return false;
}
}
return true;
}
void dfs(int country) {
if (country == n) {
count++;
return;
}
for (int c = 1; c <= 3; ++c) {
if (isValid(country, c)) {
color[country] = c;
dfs(country + 1);
color[country] = 0;
}
}
}
int main() {
cin >> n;
adj.resize(n, vector<int>(n, 0));
color.resize(n, 0);
for (int i = 0; i < n-1; ++i) {
for (int j = i+1; j < n; ++j) {
cin >> adj[i][j];
adj[j][i] = adj[i][j];
}
}
dfs(0);
cout << count << endl;
return 0;
}树的同构
给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

图一

图二
现给定两棵树,请你判断它们是否是同构的。
时间限制:1000
内存限制:65536
输入
输入给出2棵二叉树的信息。对于每棵树,首先在一行中给出一个非负整数 n(≤ 10),即该树的结点数(此时假设结点从 0 到 n -1 编号);随后 n 行,第 i 行对应编号第 i 个结点,给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。
输出
如果两棵树是同构的,输出“Yes”,否则输出“No”。
样例输入
样例#1(对应图1):
8 A 1 2 B 3 4 C 5 - D - - E 6 - G 7 - F - - H - - 8 G - 4 B 7 6 F - - A 5 1 H - - C 0 - D - - E 2 -
样例#2(对应图2):
8 B 5 7 F - - A 0 3 C 6 - H - - D - - G 4 - E 1 - 8 D 6 - B 5 - E - - H - - C 0 2 G - 3 F - - A 1 4
样例输出
样例#1:
Yes
样例#2:
No
答案整理中……
网红点打卡攻略
一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
时间限制:1000
内存限制:65536
输入
首先第一行给出两个正整数:网红点的个数 N(1 < N ≤ 200)和网红点之间通路的条数 M。随后 M 行,每行给出有通路的两个网红点、以及这条路上的旅行花费(为正整数),格式为“网红点1 网红点2 费用”,其中网红点从 1 到 N 编号;同时也给出你家到某些网红点的花费,格式相同,其中你家的编号固定为 0。 再下一行给出一个正整数 K,是待检验的攻略的数量。随后 K 行,每行给出一条待检攻略,格式为: n V1 V2 … Vn 其中 n (≤ 200) 是攻略中的网红点数,Vi 是路径上的网红点编号。这里假设你从家里出发,从 V1 开始打卡,最后从 Vn 回家。
输出
在第一行输出满足要求的攻略的个数。 在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。 题目保证至少存在一个有效攻略,并且总路费不超过 109。
样例输入
6 13 0 5 2 6 2 2 6 0 1 3 4 2 1 5 2 2 5 1 3 1 1 4 1 2 1 6 1 6 3 2 1 2 1 4 5 3 2 0 2 7 6 5 1 4 3 6 2 6 5 2 1 6 3 4 8 6 2 1 6 3 4 5 2 3 2 1 5 6 6 1 3 4 5 2 7 6 2 1 3 4 5 2 6 5 2 1 4 3 6
样例输出
3 5 11
提示
样例说明: 第 2、3、4、6 条都不满足攻略的基本要求,即不能做到从家里出发,在每个网红点打卡仅一次,且能回到家里。所以满足条件的攻略有 3 条。 第 1 条攻略的总路费是:(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14; 第 5 条攻略的总路费同理可算得:1 + 1 + 1 + 2 + 3 + 1 + 2 = 11,是一条更省钱的攻略; 第 7 条攻略的总路费同理可算得:2 + 1 + 1 + 2 + 2 + 2 + 1 = 11,与第 5 条花费相同,但序号较大,所以不输出。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> matrix(201, vector<int>(201, -1));
for (int i = 0; i < M; ++i) {
int u, v, c;
cin >> u >> v >> c;
matrix[u][v] = c;
matrix[v][u] = c;
}
int K;
cin >> K;
vector<pair<int, int>> valid_plans;
for (int plan_idx = 1; plan_idx <= K; ++plan_idx) {
int n;
cin >> n;
vector<int> Vi(n);
for (int i = 0; i < n; ++i) {
cin >> Vi[i];
}
if (n != N) {
continue;
}
vector<bool> visited(N + 1, false);
bool valid_vi = true;
for (int v : Vi) {
if (v < 1 || v > N || visited[v]) {
valid_vi = false;
break;
}
visited[v] = true;
}
for (int i = 1; i <= N && valid_vi; ++i) {
if (!visited[i]) {
valid_vi = false;
break;
}
}
if (!valid_vi) {
continue;
}
int cost = 0;
int current = 0;
bool path_valid = true;
if (matrix[current][Vi[0]] == -1) {
path_valid = false;
} else {
cost += matrix[current][Vi[0]];
current = Vi[0];
}
for (int i = 1; i < n && path_valid; ++i) {
int next = Vi[i];
if (matrix[current][next] == -1) {
path_valid = false;
} else {
cost += matrix[current][next];
current = next;
}
}
if (path_valid) {
if (matrix[current][0] == -1) {
path_valid = false;
} else {
cost += matrix[current][0];
}
}
if (path_valid) {
valid_plans.emplace_back(plan_idx, cost);
}
}
cout << valid_plans.size() << endl;
if (!valid_plans.empty()) {
auto min_plan = valid_plans[0];
for (const auto &p : valid_plans) {
if (p.second < min_plan.second || (p.second == min_plan.second && p.first < min_plan.first)) {
min_plan = p;
}
}
cout << min_plan.first << " " << min_plan.second << endl;
}
return 0;
}树的偏斜度
对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。
时间限制:1000
内存限制:65536
输入
输入在第一行给出正整数 n (≤ 103),为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列,键值为 1 到 n 的整数。同行数字间以空格分隔。
输出
在一行中按以下格式输出树的偏斜度: Ds = nL - nR
样例输入
7 1 2 7 5 4 3 6 1 2 3 4 7 5 6
样例输出
2 = 3 - 1
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> calcSkew(vector<int>& post, vector<int>& in, int ps, int pe, int is, int ie) {
if (ps > pe) return {0, 0};
int root = post[pe], idx = is;
while (in[idx] != root) idx++;
pair<int, int> left = calcSkew(post, in, ps, ps + idx - is - 1, is, idx - 1);
pair<int, int> right = calcSkew(post, in, ps + idx - is, pe - 1, idx + 1, ie);
return {left.first + right.first + (idx > is && idx == ie), left.second + right.second + (idx < ie && idx == is)};
}
int main() {
int n;
cin >> n;
vector<int> post(n), in(n);
for (int &x : post) cin >> x;
for (int &x : in) cin >> x;
pair<int, int> res = calcSkew(post, in, 0, n - 1, 0, n - 1);
cout << res.first - res.second << " = " << res.first << " - " << res.second << endl;
}//参考代码2
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {
if (inStart > inEnd || postStart > postEnd) return nullptr;
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = inMap[rootVal];
int leftSize = rootIndex - inStart;
root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1, inMap);
root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1, inMap);
return root;
}
void countSkew(TreeNode* node, int& nL, int& nR) {
if (!node) return;
bool hasLeft = node->left != nullptr;
bool hasRight = node->right != nullptr;
if (hasLeft && !hasRight) nL++;
else if (!hasLeft && hasRight) nR++;
countSkew(node->left, nL, nR);
countSkew(node->right, nL, nR);
}
int main() {
int n;
cin >> n;
vector<int> post(n), in(n);
for (int i = 0; i < n; i++) cin >> post[i];
for (int i = 0; i < n; i++) cin >> in[i];
unordered_map<int, int> inMap;
for (int i = 0; i < n; i++) inMap[in[i]] = i;
TreeNode* root = buildTree(in, post, 0, n-1, 0, n-1, inMap);
int nL = 0, nR = 0;
countSkew(root, nL, nR);
cout << nL - nR << " = " << nL << " - " << nR << endl;
return 0;
}是不是堆
二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。
时间限制:1000
内存限制:65536
输入
输入在一行中给出两个正整数:m(≤ 100)是将要测试的完全二叉树的数量;n(1 < n ≤ 1000)是完全二叉树中的结点数。 随后 m 行,每行给出 n 个互不相同的键值(均在整型范围内),为完全二叉树的层序遍历序列。
输出
对输入的每棵完全二叉树,如果它是最大堆(大顶堆),就在一行中输出 `Max Heap`;如果是最小堆(小顶堆),则输出 `Min Heap`;如果根本不是堆,则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
3 8 98 72 86 60 65 12 23 50 8 38 25 58 52 82 70 60 10 28 15 12 34 9 8 56
样例输出
Max Heap 50 60 65 72 12 23 86 98 Min Heap 60 58 52 38 82 70 25 8 Not Heap 56 12 34 28 9 8 15 10
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
string checkHeap(const vector<int>& tree) {
int n = tree.size();
for (int i = 0; i < n; ++i) {
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && tree[i] > tree[l]) return "Min Heap";
if (r < n && tree[i] > tree[r]) return "Min Heap";
if (l < n && tree[i] < tree[l]) return "Max Heap";
if (r < n && tree[i] < tree[r]) return "Max Heap";
}
return "Not Heap";
}
void printPostOrder(const vector<int>& tree, int i, vector<int>& res) {
if (i >= tree.size()) return;
printPostOrder(tree, 2 * i + 1, res);
printPostOrder(tree, 2 * i + 2, res);
res.push_back(tree[i]);
}
int main() {
int m, n;
cin >> m >> n;
while (m--) {
vector<int> tree(n);
for (int &x : tree) cin >> x;
cout << checkHeap(tree) << endl;
vector<int> res;
printPostOrder(tree, 0, res);
for (int i = 0; i < res.size(); ++i) cout << res[i] << (i == res.size() - 1 ? '\n' : ' ');
}
}//参考代码2
#include <iostream>
#include <vector>
using namespace std;
void postOrder(int index, const vector<int>& arr, vector<int>& res) {
if (index >= arr.size()) return;
postOrder(2 * index + 1, arr, res);
postOrder(2 * index + 2, arr, res);
res.push_back(arr[index]);
}
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> testCases(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> testCases[i][j];
}
}
for (const auto& arr : testCases) {
bool is_max = true, is_min = true;
int size = arr.size();
for (int i = 0; i < size; ++i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size) {
if (arr[i] < arr[left]) is_max = false;
if (arr[i] > arr[left]) is_min = false;
}
if (right < size) {
if (arr[i] < arr[right]) is_max = false;
if (arr[i] > arr[right]) is_min = false;
}
if (!is_max && !is_min) break;
}
if (is_max) cout << "Max Heap\n";
else if (is_min) cout << "Min Heap\n";
else cout << "Not Heap\n";
vector<int> post;
postOrder(0, arr, post);
for (int i = 0; i < post.size(); ++i) {
if (i) cout << ' ';
cout << post[i];
}
cout << endl;
}
return 0;
}