AI 助理
备案控制台
开发者社区 云计算 文章 正文

第十三届西南民族大学程序设计竞赛

2024-05-24 43
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 第十三届西南民族大学程序设计竞赛

先总结一下,这套题有 dfs,bfs,01背包,暴力,模拟,思维,签到

总体来说,是新生赛的水平,比较费体力,知识点不难,做不出来也是自己的代码有些小错误(看题解的时候发现思路一样,代码都几乎一样,就是几个小点eg:int -> long long)

《落花》&&《红衣集》

模拟题,注意边界就行

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
using namespace std;
const int N = 1e5+10;

int a[N],b[N];
//  美丽  价格
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n;
  cin>>n;
  rep(i,1,n-1) cin>>b[i]; 
  rep(i,1,n-1) cin>>a[i];
  
  int sp=a[1],val=b[1];
    
  for(int i=1;i<n;i++) {
    if(a[i]>sp) {
            sp = max(a[i],a[i+1]);
            if(a[i]==a[i+1]) val += min(b[i],b[i+1]);
            else if(a[i]>a[i+1]) val +=b[i];
            else val +=b[i+1];
      i++;
    }
  }
  cout<<val<<endl;
  
  return 0;
}

留春春不住，春归人寂寞。

最短路 spfa,dijkstra 啥的都行,反正我是学过一遍这几个最短路之后,只是会用,也不知道我写的叫啥…

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>

#define int long long 
#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 

using namespace std;
const int N = 1e6+10;
const int MOD = 1e9+7;


int e[N],h[N],ne[N],val[N],id;
void add(int a,int b,int c) {
  e[id]=b,val[id]=c,ne[id]=h[a],h[a]=id++;
}

int dist[N];
bool vis[N];

void sol() {
  memset(vis,false,sizeof vis);
  memset(h,-1,sizeof h);
  memset(dist,0x6f,sizeof dist);
  
  int n,m,u,v,t;
  cin>>n>>m;
  rep(i,1,m) {
    cin>>u>>v>>t;
    add(u,v,t);
    add(v,u,t);
  }
  
  queue<int>q;
    dist[1]=0;
  q.push(1);
  while(q.size()) {
    int u = q.front();
    q.pop();
    vis[u]=false;
    
    
    for(int i=h[u];i!=-1;i=ne[i]) {
      int v = e[i];
      if(dist[v]>dist[u]+val[i]) {
        dist[v]=dist[u]+val[i];
        if(!vis[v]) {
          q.push(v);
          vis[v]=true;
        }
      }
    }
  }
  
  cin>>m;
  while(m--) {
    cin>>t;
    cout<<dist[t]<<endl;
  }
  
//  rep(i,1,n) {
//    cout<<"dist["<<i<<"]:"<<dist[i]<<endl;
//  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T=1;
//  cin>>T;
  while(T--) sol();
  
  return 0;
}

厌风风不定，风起花萧索。

二位前缀和,字符串用数字标记(我这里用的map<string,int>)

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>

#define int long long 
#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 

using namespace std;
const int N = 1e3+10;

map<string,int>mp;
int id,a[N][N];
void sol() {
  int n,x;
  string s;
  cin>>n;
  rep(i,1,n) {
    cin>>s>>x;
    int t;
    if(!mp.count(s)) {
      mp[s]=++id;
    }
    t = mp[s];
    a[i][t]+=x;
  } 
    
  rep(i,1,n) {
    rep(j,1,id) {
      a[i][j]+=a[i-1][j];
    }
  }
    
    int q,l,r;
  cin>>q;
  while(q--) {
    cin>>l>>r>>s;
        if(!mp.count(s)) {
            cout<<0<<endl;
      continue;
        }
    int t = mp[s];
    cout<<a[r][t]-a[l-1][t]<<endl;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T=1;
//  cin>>T;
  while(T--) sol();
  
  return 0;
}

既兴风前叹，重命花下酌。

本人比较笨,只知道其中几个,剩下的打表一个个试

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
using namespace std;
const int N = 1e7+10;
const int MOD = 1e9+7;


signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  cout<<"FTFTTTF"<<endl;

  return 0;
}

劝君尝绿醅，教人拾红萼。

签到快乐

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
using namespace std;
const int N = 1e5+10;

vector<PII>ve;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  cout<<"\"xi\\nan\\min\\zu\\da\\xue,zhen\\mei!\""; 
  
  
  return 0;
}

桃飘火焰焰，梨堕雪漠漠。

把游戏分成两部分,必玩的直接累加时间,非必玩的排个序,从小往大加上剩下的k-m个游戏

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
#define pi acos(-1) 
using namespace std;
const int N = 1e5+10;
const int MOD = 1e9+7;

int a[N];
int b[N];

map<int,int>mp;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n,m,k,x,an=0;
  cin>>n>>m>>k;
  rep(i,1,n) cin>>a[i];
  rep(i,1,m) cin>>x,an+=a[x],mp[x]=1;
  
  int q=0;
  rep(i,1,n) if(!mp.count(i)) b[++q]=a[i];
  sort(b+1,b+1+q);
  for(int i=1;i<=k-m;i++) an+=b[i];
  
  cout<<an<<endl;
  return 0;
}

独有病眼花，春风吹不落。

并查集(看了眼题解的做法),但是我看了一眼数据,把棋牌扩大两倍,那么对每一步进行dfs搜索,好像也能过,不知道哪里写错了,最后过了一半数据

// 并查集
#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>

#define int long long 
#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 

using namespace std;
const int N = 1e7+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int fa[N];

int find(int x) {
  return fa[x]==x?x:(fa[x]=find(fa[x]));
}

void merge(int i,int j) {
  int x=find(i);
  int y=find(j);
  fa[x]=y;
}

bool sub(int a,int b) {
  int x = find(a);
  int y = find(b);
  return x==y;
}

void sol() {
    int n,m,x,y;
    char c;
    bool f=true;
    
    cin>>n>>m;
    n++;n++;
    rep(i,1,n*n) fa[i]=i;
  for(int i=1;i<=m;i++){
      cin>>x>>y>>c;
      int a=x*n+y,b;
      int xx,yy;
    if(c=='D') b=(x+1)*n+y,xx=x+1,yy=y;
    else b=x*n+y+1,xx=x,yy=y+1;
//    cout<<"x:"<<x<<" y:"<<y<<endl;
//    cout<<"xx:"<<xx<<" yy:"<<yy<<endl;
//    cout<<"fa[1]:"<<fa[a]<<" fa[2]:"<<fa[b]<<endl;
//    cout<<"===="<<endl;
    if(f&&sub(a,b)) {
      f = false;
      cout<<i<<endl;
    }
    merge(a,b);
  }
    if(f) cout<<"draw"<<endl;
    
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T=1;
  while(T--) sol();
  
  return 0;
} 

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>

#define int long long 
#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 

using namespace std;
const int N = 4e3+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
bool vis[N][N];
bool a[N][N];

int n,m;
bool f=false;

void dfs(int x,int y,int lx,int ly) {
//    cout<<"x:"<<x<<" y:"<<y<<endl;
  if(vis[x][y]) {
    f=true;
    return ;
  }
  vis[x][y]=true;
  
  for(int i=0;i<=3;i++) {
    int xx = x+dx[i];
    int yy = y+dy[i];
    
    if(xx<1||xx>n||yy<1||yy>n) continue;
    
    if(!a[xx][yy]) continue;
    
    if(xx==lx&&yy==ly) continue;
    dfs(xx,yy,x,y);
    
    if(f) return ;
  }
}

void sol() {
    int x,y;
    char c;
    memset(a,0,sizeof a);
    
  cin>>n>>m;  
  n+=3;
  n*=2;
  rep(i,1,m) {
    cin>>x>>y>>c;
    x<<=1;
    y<<=1;
    if(c=='D') {
      a[x][y]=true;
      a[x+1][y]=true;
      a[x+2][y]=true;
    }else {
      a[x][y]=true;
      a[x][y+1]=true;
      a[x][y+2]=true;
    }
    if(!f) {
            memset(vis,false,sizeof vis);
      dfs(x,y,0,0);
            if(f) cout<<i<<endl;
    }
//    cout<<"i:"<<i<<endl;
//    rep(j,1,n) {
//      rep(k,1,n) {
//        cout<<a[j][k]<<" ";
//      }
//      cout<<endl;
//    }
//    cout<<endl;
  }
    if(!f) cout<<"draw"<<endl;
  
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T=1;
  while(T--) sol();
  
  return 0;
}

荷池堪作镜，盈盈可鉴心。

做个预处理,从前往后推吧,开个1e7的数组不会爆

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
using namespace std;
const int N = 1e7+10;
const int MOD = 1e9+7;

int f[N];
void init() {
    f[1]=1;f[2]=2;f[3]=3;
    for(int i=4;i<=10000000;i++) {
        f[i]=(f[i-1]+f[i-3])%MOD;
    }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  init();
  int x;
  cin>>x;
  cout<<f[x]<<endl;
  return 0;
}

荷香堪筑梦，鸳鸯和月寻。

dfs 因为是只有有过的就行

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<cstring>

#define int long long 
#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 

using namespace std;
const int N = 1e3+10;
string s[N];
bool f=false;
int n,m,x;

void dfs(int po,int cel) {
  if(!cel) {
    f=true; 
    return ;
  }
  
  for(int j=1;j<=m;j++) {
    if(s[cel][j]=='.'&&abs(po-j)<=x) {
      dfs(j,cel-1);
      if(f) return ;
    }
  }
}

void sol() {
  
  cin>>n>>m>>x;
  rep(i,1,n) cin>>s[i],s[i]="_"+s[i];
  
    
  rep(j,1,m) {
    if(s[n][j]=='a') {
      dfs(j,n-1);
    }
  }
  cout<<(f?"yes":"no")<<endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T=1;
//  cin>>T;
  while(T--) sol();
  
  return 0;
}

荷香莫深湎，终付秋风落。

读入用 while(cin>>s) ,然后无脑判断 :w 就行

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
#define pi acos(-1) 
using namespace std;
const int N = 1e5+10;
const int MOD = 1e9+7;


signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  string s;
  int cn=0;
  while(cin>>s) {
    for(int i=0;i<=s.size()-1;i++) {
      if(s[i]==':'&&s[i+1]=='w') {
        cn++;
      }
    }
  }
  cout<<cn<<endl;
  
  return 0;
}

荷香竟深湎，永待盛夏陌。

dfs 维护路径(我这里是把路径维护成一个字符串了)

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>

#define PII pair<string,string>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
#define pi acos(-1) 
using namespace std;
const int N = 10;
const int MOD = 1e9+7;

bool f;
void dfs(int a,int b,int c,int d,string s) {
  if(f||s.size()>16) return ;
  a%=5;b%=5;c%=5;d%=5;
  if(a==b&&b==c&&c==d) {
    cout<<s.size()<<endl;
    for(int i=0;i<s.size();i++) cout<<s[i]<<" ";
    if(s.size()) cout<<endl;
    f=true;
    return ;
  }
  
  dfs(a+1,b+1,c,d+1,s+"1");
  dfs(a+1,b+1,c+1,d,s+"2");
  dfs(a,b+1,c+1,d+1,s+"3");
  dfs(a+1,b,c+1,d+1,s+"4");
  
}

int a[4];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int T;
  cin>>T;
  while(T--) {
        f=false;
    cin>>a[0]>>a[1]>>a[2]>>a[3];
    dfs(a[0],a[1],a[2],a[3],"");
  }
    
  return 0;
}

相思子肯来，约在莲花岸。

1e3 * 1e3 暴力扫就行

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
#define pi acos(-1) 
using namespace std;
const int N = 10;
const int MOD = 1e9+7;

//8行 7列 
int x[N],y[N],k[N];
int ex[N],ey[N],ek[N];

int dist(int i,int j) {
  return (x[i]-ex[j])*(x[i]-ex[j]) + (y[i]-ey[j])*(y[i]-ey[j]);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
    
  int n,m;
  cin>>n>>m;
  rep(i,1,n) cin>>x[i]>>y[i]>>k[i];
  rep(i,1,m) cin>>ex[i]>>ey[i]>>ek[i];
  
  rep(i,1,n) {
    int mx=0;
    int mi=0x3f3f3f3f;
        int po;
    rep(j,1,m) {
      int d = dist(i,j);
      if(k[i]==1) {
        if(d>mx) {
          mx=d;
          po=j;
        }
      }else {
        if(d<mi) {
          mi=d;
          po=j;
        }
      }
        
    }
    cout<<po<<" ";
  }
  cout<<endl;
  
  rep(i,1,m) {
    int mx=0;
    int mi=0x3f3f3f3f;
        int po;
    rep(j,1,n) {
      int d = dist(j,i);
      if(ek[i]==1) {
        if(d>mx) {
          mx=d;
          po=j;
        }
      }else {
        if(d<mi) {
          mi=d;
          po=j;
        }
      }
        
    }
    cout<<po<<" ";
  }
  cout<<endl;
  return 0;
}

潇潇日暮时，掠水鸳鸯散。

01 背包

#include<iostream>
#include<algorithm>
#include<map>
#include<algorithm>
#include<utility>
#include<vector>

#define PII pair<int,int>
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define int long long 
#define pi acos(-1) 
using namespace std;
const int N = 1e5+10;
const int MOD = 1e9+7;

int a[N],b[N],dp[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n,m;
  cin>>n>>m;
  rep(i,1,m) cin>>a[i]>>b[i];
  for(int i=1;i<=m;i++) {
    for(int j=n;j>=a[i];j--) {
      dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    }
  } 
  cout<<dp[n]<<endl;
  return 0;
}

Mr.anla
目录
相关文章
钊气蓬勃.
集美大学第九届程序设计竞赛
集美大学第九届程序设计竞赛
钊气蓬勃.
75 0
wait_
|
定位技术 Go
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（银川），签到题5题
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（银川），签到题5题
wait_
99 0
wait_
|
机器学习/深度学习 人工智能 BI
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南），签到题5题
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南），签到题5题
wait_
82 0
wait_
|
机器学习/深度学习 人工智能
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（澳门），签到题4题
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（澳门），签到题4题
wait_
155 1
wait_
|
8月前
|
人工智能 NoSQL 机器人
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题4题
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题4题
wait_
121 0
wait_
|
人工智能 BI
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南），签到题2题
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南），签到题2题
wait_
85 2
wait_
|
8月前
|
机器学习/深度学习 人工智能
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明），签到题4题
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明），签到题4题
wait_
84 0
wait_
|
人工智能 移动开发 分布式计算
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题5题
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题5题
wait_
244 0
wait_
|
机器学习/深度学习 物联网 BI
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明），签到题3题
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明），签到题3题
wait_
151 0
hu6spejpcbfwa
桂林电子科技大学第三届ACM程序设计竞赛 B题
桂林电子科技大学第三届ACM程序设计竞赛 B题
hu6spejpcbfwa
82 0

热门文章

最新文章

  • 1
    流批一体的近实时数仓的思考与设计
  • 2
    Nginx报错403 forbidden几个解决方法
  • 3
    丰富、连接、待集成—MaxCompute 生态再出发
  • 4
    【实战】锐捷AC+AP配置WLAN基本服务系列
  • 5
    为什么说流处理即未来？
  • 6
    securecrt克隆会话与sshd 的 MaxSessions
  • 7
    Elasticsearch 备忘
  • 8
    C++ Exercises（六）
  • 9
    勒索病毒出现新变种 传播方式与WannaCry类似
  • 10
    FCKEditor使用说明
  • 1
    基于EKF扩展卡尔曼滤波的一阶环形倒立摆控制系统simulink建模与仿真
    30
  • 2
    小模型也能有类o1的慢思考能力？使用CAMEL生成CoT数据、Unsloth微调Qwen2.5-1.5B模型并上传至Hugging Face
    55
  • 3
    《AI赋能共享经济：资源配置与服务质量的双重优化》
    31
  • 4
    《AI引领传统企业：数字化转型与商业创新的破局之路》
    38
  • 5
    《AI助力生物学：基因编辑与蛋白质结构解析的加速引擎》
    30
  • 6
    《AI赋能自由职业：开启竞争力提升新征程》
    26
  • 7
    《量子AI：突破量子比特稳定性与容错性的关键瓶颈》
    25
  • 8
    Workforce 应用示例：黑客松评审团
    26
  • 9
    使用 Qwen 生成数据模型和进行结构化输出
    104
  • 10
    实现时间序列的小波相干性分析，并画出图谱
    30

    • 相关课程

    更多
  • 高校精品课-杭州电子科技大学 -EDA技术
  • 重庆烟草2024年度全市系统网信素养能力提升轮训（第二期）暨数字创新培训班
  • 高校精品课-清华大学 - 计算机原理与设计
  • 高校精品课-北京大学 -推荐系统
  • 高校精品课-湖南大学 -市场营销
  • 高校精品课-清华大学 -人工神经网络

    • 相关电子书

    更多
  • 第九届深圳国际物联网博览会-夏季邀请函
  • 第九届深圳国际物联网博览会-夏季展
  • 第九届深圳国际物联网博览会（夏季展）

    • 相关实验场景

    更多
  • 基于阿里云DeepGPU实例，用AI画唯美国风少女
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月