2025春训第十九场
问题 A: 熊孩子打卡
题目描述
暑假期间，西海岸图书馆推出了一个“每天来图书馆打卡即可获奖”的活动。参与者只需要在电子屏前大声喊出自己的编号，系统就会记录下来。
但问题来了：有几个熊孩子特别调皮，打卡时故意连续喊自己编号好几次，比如“3！3！3！”，系统就会把这些编号全部记录下来。
管理员只想知道：每个编号在记录中一共出现了多少次“打卡段”。也就是说：
连续重复的编号只算作一次有效打卡；
同一个编号可能在不同时刻打卡多次，每次算作一个新的段。
你的任务是帮助管理员统计：每个编号一共打卡了多少段，并按编号升序输出结果。输入
第一行一个整数 N，表示系统记录的打卡总次数；
第二行 N 个正整数 a1 , a2 , ……, aN，表示每一次记录下的编号。输出
按编号升序输出每个出现过的编号及其有效打卡段数。
每一行两个整数，中间用一个空格分隔，表示“编号 打卡段数”。样例输入 Copy
【样例1】 11 0 0 1 2 2 2 1 3 3 1 1 【样例2】 7 3 3 -1 -1 0 0 -1样例输出 Copy
【样例1】 0 1 1 3 2 1 3 1 【样例2】 -1 2 0 1 3 1提示
对于 100% 的数据：1 ≤ N ≤ 106，编号范围 [-106 , 106]
1e6忘记加等号判错了KK
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[1000001],b[1000001],l;
void inn(int x){if(x>=0)a[x]++;else b[x*(-1)]++;
}
int main(){cin>>n>>l;inn(l);int x;for(int i=1;i<n;++i){cin>>x;if(x==l){continue;}else{inn(x);}l=x;}for(int i=1e6;i>0;--i){if(b[i]!=0)cout<<i*(-1)<<" "<<b[i]<<'\n';}for(int i=0;i<=1e6;++i){if(a[i]!=0)cout<<i<<" "<<a[i]<<'\n';}return 0;
}问题 B: 最省力整理法
题目描述
小唐最近在整理他堆满杂物的书架。书架上共有 n 本书，每本书的编号为 a1 ,a2 , ……, an，编号越小代表这本书越常用。
然而，书架上的书顺序是混乱的，小唐想把它们按从小到大的顺序摆好（即变成非递减序列）。
由于书架很窄，每次小唐只能交换相邻的两本书。而每次交换操作都会消耗他的体力，体力消耗量等于两本书中编号较大者的值。比如交换 4 和 2，会消耗 4 点体力。
小唐不想累趴，他想知道把整排书整理好，最少需要消耗多少体力。你能帮帮他吗？输入
第一行一个整数 n，表示书的数量。
第二行 n 个整数 a1 , a2 , ……, an，表示当前书的排列顺序。输出
输出一个整数，表示小唐最少需要消耗的体力值。
样例输入 Copy
4 4 3 2 1样例输出 Copy
20提示
【样例说明】
小唐可以按以下方式整理书：
1、交换4和3，代价4，得到[3,4,2,1]
2、交换4和2，代价4，得到[3,2,4,1]
3、交换4和1，代价4，得到[3,2,1,4]
4、交换3和2，代价3，得到[2,3,1,4]
5、交换3和1，代价3，得到[2,1,3,4]
6、交换2和1，代价2，得到[1,2,3,4]
总代价为：4+4+4+3+3+2=20。
【数据范围】
对于100%的数据：1≤n≤5000，1≤ai≤105
冒泡
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[5009],ans=0;
void test(){cout<<"test---\n";for(int i=0;i<n;++i){cout<<a[i]<<" ";}cout<<"\n-------\n";
}
int main(){cin>>n;for(int i=0;i<n;++i){cin>>a[i];}for(int i=n-1;i>=0;--i){int f=0;for(int j=n-1;j>=n-i;--j){if(a[j]<a[j-1]){f=1;ans+=a[j-1];swap(a[j],a[j-1]);}}//test();if(!f)break;}cout<<ans;return 0;
}问题 C: 穿心咒
题目描述
在人界，哪吒与敖丙因命运巧合，共用一具身体，各自拥有一圈神秘的灵魂之域，分别代表着他们各自的仙力。哪吒的灵魂之域以点(x1,y1)为中心，半径为r1；敖丙的灵魂之域以点(x2,y2)为中心，半径为r2。
传说，在封仙仪式上，无量仙翁暗中施下“穿心咒”，将其封印在两灵魂之域的交汇处。只有破解所有“穿心咒”，才能让哪吒与敖丙摆脱束缚，获得真正的自由。
现请你编写程序，根据输入的灵魂之域数据，计算出“穿心咒”的数量。如果“穿心咒”无限多，则输出-1。输入
第一行输入测试用例的个数T(1≤T≤10)。
接下来的每个测试用例占一行，包含六个由空格分隔的整数：x1 y1 r1 x2 y2 r2分别表示哪吒的灵魂之域中心坐标(x1,y1)、半径r1以及敖丙的灵魂之域中心坐标(x2,y2)、半径r2。输出
对于每个测试用例，输出一个整数，表示“穿心咒”可能存在的位置数量。如果存在无限多的位置，则输出 −1。
样例输入 Copy
3 0 0 13 40 0 37 0 0 3 0 7 4 1 1 1 1 1 5样例输出 Copy
2 1 0提示
-10000≤x1,y1,x2,y2≤10000
1≤r1,r2≤10000
10%的数据r1=r2
另有20%的数据x1=x2,y1=y2
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,x,y,z,a,b,c;
int main(){cin>>t;while(t--){cin>>x>>y>>z>>a>>b>>c;if(x==a&&y==b&&z==c){cout<<"-1\n";continue;}double d=sqrt(pow(x-a,2.0)+pow(y-b,2.0));//cout<<d<<" "<<z+c<<'\n';if(d<max(z,c)){if(d+min(z,c)==max(z,c))cout<<"1\n";else if(d+min(z,c)<max(z,c))cout<<"0\n";else cout<<"2\n";}else{if(d>z+c)cout<<"0\n";else if(d==z+c)cout<<"1\n";else cout<<"2\n";}}return 0;
}问题 D: 吃火锅
题目描述
在仙界传说中，太乙真人极为热爱美食，尤其钟情于传说中的“神仙火锅”。据说这火锅的食材并非随意摆放，而是以一种神秘的阵法排列在一张n×n的大桌上。每个区域内的火锅食材都有一个“香辣值”，用一个正整数表示，象征着食材的独特风味和辣度。
太乙真人决定开启他的火锅盛宴，但他有一个独特的品尝规矩：
每次换到下一个食材区域时，必须确保该区域的香辣值严格高于上一个区域，这样才能层层递进，激发出火锅的绝妙风味。也就是说，太乙真人只能沿着一条香辣值不断上升的路径前进，尽情品味每一处美味。
你的任务是：给定火锅桌上各区域的香辣值（构成一个n×n的矩阵），请你帮助太乙真人找出一条符合规则的路径，使他能品尝到尽可能多的不同食材区域，并计算出这条路径包含的区域数。输入
第一行输入一个整数n，表示火锅桌上区域的规模，即食材被排列成n×n的格子。
接下来的n行中，每行包含n个用空格分隔的正整数，分别代表各个区域中火锅食材的香辣值，数值不超过106。输出
输出一个整数，表示太乙真人依照规定能够连续品尝到的最大区域数（即火锅食材区域的最长连续路径长度）。
样例输入 Copy
4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8样例输出 Copy
4提示
对于 100% 的数据 1 ≤ n ≤ 500
DFS，开一个数组记录之前走过的路径，不然超时
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,pot[509][509],ans=0,jam[509][509];
int fx[]{0,1,0,-1},fy[]{1,0,-1,0};
int ok(int x,int y){return x>=0&&x<n&&y>=0&&y<n;
}
void dfs(int x,int y){int tx,ty;for(int i=0;i<4;++i){tx=x+fx[i],ty=y+fy[i];if(ok(tx,ty)&&pot[tx][ty]<pot[x][y]){if(jam[tx][ty]<jam[x][y]+1){jam[tx][ty]=jam[x][y]+1;dfs(tx,ty);}}}
}
int main(){cin>>n;for(int i=0;i<n;++i){for(int j=0;j<n;++j){cin>>pot[i][j];jam[i][j]=1;}}for(int i=0;i<n;++i){for(int j=0;j<n;++j){dfs(i,j);} }for(int i=0;i<n;++i){for(int j=0;j<n;++j){ans=max(ans,jam[i][j]);} }cout<<ans;return 0;
}