CXXP#1 非官方题解
2026-02-18 15:27:49
发布于：云南
50阅读
0回复
0点赞
计算出购买的千克数 ，判断购买的是哪种皮皮虾，乘上对应的单价，最后保留两位小数输出即可。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
char s;
int x;
double ans;
int main(){
cin>>s>>x;
if (s=='A'){
ans=x/1000.0*60;
}
else if (s=='B'){
ans=x/1000.0*45;
}
else {
ans=x/1000.0*30;
}
printf("%.2lf",ans);
return 0;
}
简单的模拟。
遍历 ，
- 若当前 为 ，则将 加上 ；
- 若当前 为 ，则将 加上 。
最后计算出 即可。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int c[105],d[105],t[105],s[105],u[105];
double ans;
signed main(){
cin>>n>>m;
for (int i=1;i<=n;i++){
cin>>c[i]>>d[i];
}
for (int i=1;i<=m;i++){
cin>>t[i]>>s[i]>>u[i];
}
for (int i=1;i<=m;i++){
if (t[i]==1){
d[u[i]]+=s[i];//当前强化点用于第 u[i] 个技能
}
else {
d[u[i]]+=d[u[i]]*s[i]/100;
}
}
for (int i=1;i<=n;i++){
ans+=d[i]*1.0/c[i];
}
cout<<(int)ans;
return 0;
}
三维广搜板子题。
广搜算法详见 OI-Wiki。
先找到起点和终点，将起点加入队列并标记。
对于每一个在队首的位置，枚举其右、左、后、前、上、下六个方向。若新的位置在网格范围内、没有被标记、并且不为墙壁，就加入队尾，并标记。
直到队首为终点时，输出步数。
#include <bits/stdc++.h>
using namespace std;
int n;
char a[25][25][25];
bool vis[25][25][25];
int dx[]={0,0,0,0,1,-1};//偏移量
int dy[]={-1,0,1,0,0,0};
int dz[]={0,1,0,-1,0,0};
struct node{
int x,y,z,s;//s 代表步数
}st,en;
int main(){
cin>>n;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
for (int k=1;k<=n;k++){
cin>>a[i][j][k];
if (a[i][j][k]=='S'){//起点
st.x=i,st.y=j,st.z=k,st.s=0;
}
if (a[i][j][k]=='E'){//终点
en.x=i,en.y=j,en.z=k,en.s=0;
}
}
}
}
queue<node> q;
q.push(st);
vis[st.x][st.y][st.z]=1;
while (q.size()){
int cx=q.front().x,cy=q.front().y,cz=q.front().z,cs=q.front().s;
q.pop();
if (cx==en.x&&cy==en.y&&cz==en.z){//到达终点
cout<<cs;
return 0;
}
for (int i=0;i<6;i++){
int nx=cx+dx[i],ny=cy+dy[i],nz=cz+dz[i];//新的位置
if (nx>=1&&nx<=n&&ny>=1&&ny<=n&&nz>=1&&nz<=n&&!vis[nx][ny][nz]&&a[nx][ny][nz]!='#'){//可以走
q.push({nx,ny,nz,cs+1});
vis[nx][ny][nz]=1;
}
}
}
cout<<-1;//无法到达终点
return 0;
}
相邻交换、从小到大排序，考虑逆序对。
我是蒟蒻，只会用归并排序。
令 。
可以证明，当 为奇数时，是否可能实现的结果与 的结果相等；
当 为偶数时，是否可能实现的结果与 的结果相等。
令 为 中逆序对的个数。
显然，需满足 。
可以证明，对于所有 两两不同的情况，还需满足 才可能恰好进行 次操作。
同理，令 为 中逆序对的个数。
显然，需满足 。
可以证明，对于所有 两两不同的情况，还需满足 才可能恰好进行 次操作。
时间复杂度：。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m,w,c1,c2,f1=2,f2=2;
int a[100005],b[100005];
void mergesort1(int l,int r){//求数组 a 的逆序对数量 c1
if (l>=r){
return ;
}
int mid=(l+r)/2;
mergesort1(l,mid);
mergesort1(mid+1,r);
int i=l,j=mid+1;
vector<int> v;
while (i<=mid&&j<=r){
if (a[i]<=a[j]){
v.push_back(a[i++]);
}
else {
v.push_back(a[j++]);
c1+=mid-i+1;
}
}
while (i<=mid){
v.push_back(a[i++]);
}
while (j<=r){
v.push_back(a[j++]);
}
for (int i=l;i<=r;i++){
a[i]=v[i-l];
}
}
void mergesort2(int l,int r){//求数组 b 的逆序对数量 c2
if (l>=r){
return ;
}
int mid=(l+r)/2;
mergesort2(l,mid);
mergesort2(mid+1,r);
int i=l,j=mid+1;
vector<int> v;
while (i<=mid&&j<=r){
if (b[i]<=b[j]){
v.push_back(b[i++]);
}
else {
v.push_back(b[j++]);
c2+=mid-i+1;
}
}
while (i<=mid){
v.push_back(b[i++]);
}
while (j<=r){
v.push_back(b[j++]);
}
for (int i=l;i<=r;i++){
b[i]=v[i-l];
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k>>m;
for (int i=1;i<=n;i++){
cin>>a[i];
b[i]=abs(a[i]);
}
mergesort1(1,n);
mergesort2(1,n);
for (int i=1;i<n;i++){
if (a[i]==a[i+1]){
f1=1;//mod 1 一定成立
}
if (b[i]==b[i+1]){
f2=1;
}
}
if (k>=c1&&(k-c1)%f1==0){
cout<<"Yes\n";
}
else {
cout<<"No\n";
}
for (int i=1;i<=m;i++){
cin>>w;
if (w%2){
if (k>=c1&&(k-c1)%f1==0){
cout<<"Yes\n";
}
else {
cout<<"No\n";
}
}
else {
if (k>=c2&&(k-c2)%f2==0){
cout<<"Yes\n";
}
else {
cout<<"No\n";
}
}
}
return 0;
}
有帮助，赞一个