2023年国高校计算机大赛-团队程序设计天梯赛GPLT上海理工大学校内选拔赛 题解

总结：本场比赛总共A了两题，主要是因为是在课上做的，老师一直比比个不停，还让关上手机电脑，静不下心去做，做题感觉很差

A A Xor B Problem

两个数异或和为零则两个数相等！！！

思路：使用数组记录每个数的个数，可以先输入，然后再对数组进行逐个遍历，可通过计算得出数对个数等于每个数的平方和。也可以边输入边处理，每输入一个数便更新数对的结果数

赛场AC代码：

1.  
   #include<cstdio>
2.  
   #include<iostream>
3.  
   #define int long long
4.  
   using namespace std;
5.  
    
6.  
   int a[100005];
7.  
   int b[114520];
8.  
   signed main(){
9.  
   int n,ans=0;
10.  
    cin>>n;
11.  
    for(int i=1;i<=n;i ){
12.  
    cin>>a[i];
13.  
    ans-=(b[a[i]]*b[a[i]]);
14.  
    b[a[i]] ;
15.  
    ans =(b[a[i]]*b[a[i]]);
16.  
    }
17.  
    cout<<ans;
18.  
    return 0;
19.  
    }

另一种思路：

1.  
   #include<iostream>
2.  
   #define int long long
3.  
   using namespace std;
4.  
    
5.  
   const int N=1000005;
6.  
   int a[N];
7.  
   signed main(){
8.  
   int x,n,ans;
9.  
   cin>>n;
10.  
    for(int i=0;i<n;i ){
11.  
    cin>>x;
12.  
    a[x] ;
13.  
    }
14.  
    for(int i=0;i<=N;i ){
15.  
    ans =a[i]*a[i];
16.  
    }
17.  
    cout<<ans;
18.  
    }

B 吃苹果 

思路：贪心算法，计算早上和晚上愉悦值的差并进行排序，差值越小（可能为负值）则代表晚上的愉悦值相对早上的更多，先选晚上的，剩下的则为早上的

注意对结构体的定义和结构体的排序!!!

赛场AC代码：

1.  
   #include<cstdio>
2.  
   #include<iostream>
3.  
   #include<algorithm>
4.  
   #define int long long
5.  
   using namespace std;
6.  
    
7.  
   const int N=100005;
8.  
    
9.  
   struct Node{
10.  
    int a;
11.  
    int b;
12.  
    int c;
13.  
    }ap[N];
14.  
     
15.  
    bool cmp(Node x,Node y){
16.  
    return x.c<y.c;
17.  
    }
18.  
     
19.  
    signed main(){
20.  
    int n,k,ans=0;
21.  
    cin>>n>>k;
22.  
    for(int i=0;i<n;i ){
23.  
    cin>>ap[i].a>>ap[i].b;
24.  
    ap[i].c=ap[i].a-ap[i].b;
25.  
    }
26.  
    sort(ap,ap n,cmp);
27.  
    for(int i=0;i<k;i ){
28.  
    ans =ap[i].b;
29.  
    }
30.  
    for(int i=k;i<n;i ){
31.  
    ans =ap[i].a;
32.  
    }
33.  
    cout<<ans;
34.  
    return 0;
35.  
    }

另一种思路：(也可以反过来)

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   using namespace std;
4.  
   const int N=100005;
5.  
   int a[N];
6.  
    
7.  
   int main(){
8.  
   int n,k,x,y;
9.  
   cin>>n>>k;
10.  
    int ans=0;
11.  
    for(int i=1;i<=n;i ){
12.  
    cin>>x>>y;
13.  
    ans =x;
14.  
    a[i]=y-x;
15.  
    }
16.  
    sort(a 1,a n 1,greater<int>());
17.  
    for(int i=1;i<=k;i ){
18.  
    ans =a[i];
19.  
    }
20.  
    cout<<ans;
21.  
    }

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   using namespace std;
4.  
   const int N=100005;
5.  
   int a[N];
6.  
    
7.  
   int main(){
8.  
   int n,k,x,y;
9.  
   cin>>n>>k;
10.  
    int ans=0;
11.  
    for(int i=0;i<n;i ){
12.  
    cin>>x>>y;
13.  
    ans =x;
14.  
    a[i]=x-y;;
15.  
    }
16.  
    sort(a,a n);
17.  
    for(int i=0;i<k;i ){
18.  
    ans-=a[i];
19.  
    }
20.  
    cout<<ans;
21.  
    return 0;
22.  
    }

 C n皇后问题

 思路：用四个数组分别表示横竖左斜右斜

注意超时问题！！！

cin/cout会超时，需要用：   

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

或者使用scanf！！！

1.  
   #include<iostream>
2.  
   #include<cstdio>
3.  
   using namespace std;
4.  
    
5.  
   const int N=3000005;
6.  
   bool h[N],l[N],a[N],b[N];
7.  
    
8.  
   int main(){
9.  
   ios::sync_with_stdio(false);
10.  
    cin.tie(0);
11.  
    cout.tie(0);
12.  
    int n,T;
13.  
    cin>>n>>T;
14.  
    while(T--){
15.  
    int x,y;
16.  
    cin>>x>>y;
17.  
    if(h[x]||l[y]||a[x-y 1000000]||b[x y]){
18.  
    cout<<"No"<<endl;
19.  
    }else{
20.  
    cout<<"Yes"<<endl;
21.  
    h[x]=1;
22.  
    l[y]=1;
23.  
    a[x-y 1000000]=1;
24.  
    b[x y]=1;
25.  
    }
26.  
    }
27.  
     
28.  
    return 0;
29.  
    }

D 分苹果 

思路：数学知识，将坐标分别带入直线方程，结果大于零和小于零位于直线两侧

1.  
   #include<iostream>
2.  
   #include<algorithm>
3.  
   #define int long long
4.  
   using namespace std;
5.  
    
6.  
   int ans[5];
7.  
   signed main(){
8.  
   int n,ae,be,ce,ar,br,cr;
9.  
   cin>>n;
10.  
    cin>>ae>>be>>ce;
11.  
    cin>>ar>>br>>cr;
12.  
    int x,y,a,b;
13.  
    while(n--){
14.  
    cin>>x>>y;
15.  
    a=ae*x be*y ce;
16.  
    b=ar*x br*y cr;
17.  
    if(a>0&&b>0){
18.  
    ans[0] ;
19.  
    }else if(a>0&&b<0){
20.  
    ans[1] ;
21.  
    }else if(a<0&&b>0){
22.  
    ans[2] ;
23.  
    }else{
24.  
    ans[3] ;
25.  
    }
26.  
    }
27.  
    sort(ans,ans 4);
28.  
    for(int i=0;i<4;i ){
29.  
    cout<<ans[i]<<' ';
30.  
    }
31.  
    return 0;
32.  
    }

E 完型填空

思路：动态规划，用数组dp[i][j][k][p]分别表示有ijkp道题选ABCD

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
    
4.  
   const int N=30;
5.  
   int dp[N][N][N][N];
6.  
   int a[105][5];
7.  
   int main(){
8.  
   int n,h;
9.  
   cin>>n;
10.  
    for(int i=1;i<=n;i ){
11.  
    for(int j=1;j<=4;j ){
12.  
    cin>>a[i][j];
13.  
    }
14.  
    }
15.  
    for(int i=0;i<=n/4;i ){
16.  
    for(int j=0;j<=n/4;j ){
17.  
    for(int k=0;k<=n/4;k ){
18.  
    for(int p=0;p<=n/4;p ){
19.  
    h=i j k p;
20.  
    if(i){
21.  
    dp[i][j][k][p]=max(dp[i][j][k][p],dp[i-1][j][k][p] a[h][1]);
22.  
    }
23.  
    if(j){
24.  
    dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j-1][k][p] a[h][2]);
25.  
    }
26.  
    if(k){
27.  
    dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j][k-1][p] a[h][3]);
28.  
    }
29.  
    if(p){
30.  
    dp[i][j][k][p]=max(dp[i][j][k][p],dp[i][j][k][p-1] a[h][4]);
31.  
    }
32.  
    }
33.  
    }
34.  
    }
35.  
    }
36.  
    cout<<dp[n/4][n/4][n/4][n/4];
37.  
    return 0;
38.  
    }

F 坐火车 （最短路改编）不是很懂，老是卡在9分！！！

最好从头开始学一遍最短路！！！

推荐Dijkstra链式前向星优化：算法小讲堂之最短路算法(Floyd bellman SPFA Dijkstra)

关键是考虑如何求经过城市的数量的最小值!

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   #include<queue>
4.  
   #define int long long
5.  
   using namespace std;
6.  
    
7.  
   typedef pair<int,int> PII;
8.  
   const int N=1e5 10;
9.  
   const int M=4*N;
10.  
    const int inf=0x3f3f3f3f;
11.  
    int n,m;
12.  
    int h[N],e[M],ne[M],w[M],idx;
13.  
    int dist[N];
14.  
    int cnt[N];
15.  
    bool vis[N];
16.  
     
17.  
    void init(){
18.  
    memset(dist,inf,sizeof(dist));
19.  
    memset(cnt,inf,sizeof(cnt));
20.  
    memset(h,-1,sizeof(h));
21.  
    cnt[1]=1;
22.  
    dist[1]=0;
23.  
    }
24.  
     
25.  
    void add(int a,int b,int c){
26.  
    e[idx]=b;
27.  
    w[idx]=c;
28.  
    ne[idx]=h[a];
29.  
    h[a]=idx ;
30.  
    }
31.  
     
32.  
    void dij(){
33.  
    priority_queue<PII,vector<PII>,greater<PII> > q;
34.  
    q.push({0,1});
35.  
    while(q.size()){
36.  
    PII t=q.top();
37.  
    q.pop();
38.  
    int ver=t.second;
39.  
    if(vis[ver]){
40.  
    continue;
41.  
    }
42.  
    vis[ver]=1;
43.  
    for(int i=h[ver];i!=-1;i=ne[i]){
44.  
    int j=e[i];
45.  
    if(cnt[j]>cnt[ver] 1){
46.  
    cnt[j]=cnt[ver] 1;
47.  
    dist[j]=dist[ver] w[i];
48.  
    q.push({cnt[j],j});
49.  
    }else if(cnt[j]==cnt[ver] 1){
50.  
    if(dist[j]>dist[ver] w[i]){
51.  
    dist[j]=dist[ver] w[i];
52.  
    q.push({cnt[j],j});
53.  
    }
54.  
    }
55.  
    }
56.  
    }
57.  
    }
58.  
     
59.  
    signed main(){
60.  
    cin>>n>>m;
61.  
    init();
62.  
    while(m--){
63.  
    int a,b,c;
64.  
    cin>>a>>b>>c;
65.  
    add(a,b,c);
66.  
    add(b,a,c);
67.  
    }
68.  
    dij();
69.  
    cout<<cnt[n]<<' '<<dist[n];
70.  
    return 0;
71.  
    }

9分代码： 啊啊啊啊——

1.  
   #include<iostream>
2.  
   #include<cstring>
3.  
   #include<queue>
4.  
   #define int long long
5.  
   using namespace std;
6.  
    
7.  
   const int inf=0x3f3f3f3f;
8.  
   const int N=100005;
9.  
   const int M=4*N;
10.  
    int n,m,cnt;
11.  
    int head[N],dis[N],sum[N];
12.  
    bool vis[N];
13.  
    typedef pair<int,int>Pll;
14.  
     
15.  
    struct Edge{
16.  
    int next;
17.  
    int to;
18.  
    int w;
19.  
    }edge[M];
20.  
     
21.  
    void init(){
22.  
    memset(vis,0,sizeof(vis));
23.  
    memset(dis,inf,sizeof(dis));
24.  
    memset(head,-1,sizeof(head));
25.  
    memset(sum,inf,sizeof(sum));
26.  
    cnt=0;
27.  
    dis[1]=0;
28.  
    sum[1]=1;
29.  
    }
30.  
     
31.  
    void add(int u,int v,int w){
32.  
    edge[cnt].to=v;
33.  
    edge[cnt].w=w;
34.  
    edge[cnt].next=head[u];
35.  
    head[u]=cnt ;
36.  
    }
37.  
     
38.  
    void dij(){
39.  
    priority_queue<Pll,vector<Pll>,greater<Pll> > q;
40.  
    q.push(Pll(0,1));
41.  
    Pll temp;
42.  
    while(!q.empty()){
43.  
    temp=q.top();
44.  
    q.pop();
45.  
    int u=temp.second;
46.  
    if(vis[u]){
47.  
    continue;
48.  
    }
49.  
    vis[u]=1;
50.  
    int t,len;
51.  
    for(int i=head[u];i!=-1;i=edge[i].next){
52.  
    t=edge[i].to;
53.  
    len=edge[i].w;
54.  
    if(sum[t]>sum[u] 1){
55.  
    sum[t]=sum[u] 1;
56.  
    dis[t]=dis[u] len;
57.  
    q.push(Pll(dis[t],t));
58.  
    }else if(sum[t]==sum[u] 1){
59.  
    if(dis[t]>dis[u] len){
60.  
    dis[t]=dis[u] len;
61.  
    }
62.  
    }
63.  
    }
64.  
    }
65.  
    }
66.  
     
67.  
    signed main(){
68.  
    init();
69.  
    cin>>n>>m;
70.  
    int u,v,w;
71.  
    for(int i=1;i<=m;i ){
72.  
    cin>>u>>v>>w;
73.  
    add(u,v,w);
74.  
    add(v,u,w);
75.  
    }
76.  
    dij();
77.  
    cout<<sum[n]<<' '<<dis[n];
78.  
    return 0;
79.  
    }

G A Xor B Problem again   位运算问题，不懂！！！

学习位运算~~~

1.  
   #include<iostream>
2.  
   #define int long long
3.  
   using namespace std;
4.  
    
5.  
   const int N=300005;
6.  
   int n,pre[N],a[N];
7.  
   signed main(){
8.  
   cin>>n;
9.  
   for(int i=1;i<=n;i ){
10.  
    cin>>a[i];
11.  
    pre[a[i]] ;//记录每一个数出现的次数
12.  
    }
13.  
    //枚举每一个位数（变成二进制之后）
14.  
    for(int i=0;i<18;i ){
15.  
    //二进制枚举每（1-1e5）
16.  
    for(int j=0;j<262144;j ){
17.  
    // 如果这个数与这个二进制数一样那么
18.  
    if(j&(1<<i)){
19.  
    pre[j] =pre[j^(1<<i)];
20.  
    }
21.  
    }
22.  
    }
23.  
    int ans=0;
24.  
    for(int i=1;i<=n;i ){
25.  
    int x=a[i]^((1<<18)-1);
26.  
    ans =pre[x];
27.  
    }
28.  
    cout<<ans;
29.  
    return 0;
30.  
    }

H  摘苹果

思路：正常思路，模拟，玄学问题，g 编译器超时，clang 编译器能过

可以考虑其他做法进行时间优化！！！

1.  
   #include<iostream>
2.  
   #include<cmath>
3.  
   #define int long long
4.  
   using namespace std;
5.  
    
6.  
   const int N=100005;
7.  
   int a[N];
8.  
   signed main(){
9.  
   int n,m;
10.  
    cin>>n>>m;
11.  
    for(int i=1;i<=n;i ){
12.  
    scanf("%lld",&a[i]);
13.  
    }
14.  
    while(m--){
15.  
    int op,l,r,ans;
16.  
    scanf("%lld%lld%lld",&op,&l,&r);
17.  
    if(op==1){
18.  
    for(int i=l;i<=r;i ){
19.  
    if(a[i]>=10){
20.  
    a[i]-=((a[i]-1)/3 1);
21.  
    }
22.  
    }
23.  
    }
24.  
    if(op==2){
25.  
    ans=0;
26.  
    for(int i=l;i<=r;i ){
27.  
    if(a[i]<100){
28.  
    ans ;
29.  
    }
30.  
    }
31.  
    printf("%lld\n",ans);
32.  
    }
33.  
    if(op==3){
34.  
    ans=0;
35.  
    for(int i=l;i<=r;i ){
36.  
    ans =a[i];
37.  
    }
38.  
    printf("%lld\n",ans);
39.  
    }
40.  
    }
41.  
     
42.  
    return 0;
43.  
    }

这篇好文章是转载于：学新通技术网