2020年第四届海淀区智慧杯C++组参考代码

ゝ一世哀愁。 2022-12-10 03:49 140阅读 0赞

# T1 #

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 100000 + 5;
    int a[maxN];
    
    int main()
    { 
        freopen("carpet.in", "r", stdin);
        freopen("carpet.out", "w", stdout);
    
        int n;
        cin >> n;
    
        for(int i = 0; i < n; i++)
        { 
            cin >> a[i];
        }
    
    
        sort(a, a + n, greater<int>());
    
        cout << a[0] * a[1];
    
        return 0;
    }

# T2 #

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    { 
        freopen("volleyball.in", "r", stdin);
        freopen("volleyball.out", "w", stdout);
    
        char ch;
        int scoreA = 0, scoreB = 0; //a和b的得分
        int round = 1;              //第几轮比赛
        int cntA = 0, cntB = 0;     //a和b赢的次数
        while(cin >> ch)
        { 
            if('E' == ch)
            { 
                break;
            }
            else if('A' == ch)
            { 
                scoreA++;
            }
            else if('B' == ch)
            { 
                scoreB++;
            }
    
            if(round == 5)
            { 
                if(scoreA >= 15 && scoreA - scoreB >= 2)
                { 
                    cntA++;
                    break;
                }
                else if(scoreB >= 15 && scoreB - scoreA >= 2)
                { 
                    cntB++;
                    break;
                }
            }
            else
            { 
                if(scoreA >= 25 && scoreA - scoreB >= 2)
                { 
                    cntA++;
                    scoreA = 0;
                    scoreB = 0;
                    round++;
                }
                else if(scoreB >= 25 && scoreB - scoreA >= 2)
                { 
                    cntB++;
                    scoreA = 0;
                    scoreB = 0;
                    round++;
                }
            }
        }
    
        cout << cntA << ':' << cntB;
    
        return 0;
    }

# T3 #

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 105;
    int a[maxN];
    int f[maxN];
    
    int main()
    { 
        freopen("stonehenge.in", "r", stdin);
        freopen("stonehenge.out", "w", stdout);
    
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        { 
            cin >> a[i];
        }
    
        f[1] = a[1];
        for(int i = 2; i <= n; i++)
        { 
            if(f[i - 2] + a[i] > f[i - 1])
            { 
                f[i] = f[i - 2] + a[i];
            }
            else
            { 
                f[i] = f[i - 1];
            }
        }
    
        cout << f[n];
    
        return 0;
    }

# T4 #

## 解法一：深度优先搜索，30分 ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 105;
    char a[maxN][maxN];
    bool vis[maxN][maxN];
    int ans = INT_MAX;
    int dir[4][2] = { { -1, 0}, { 0, 1}, { 1, 0}, { 0, -1}};
    int n;
    
    void dfs(int curRow, int curCol, int step)
    { 
        if(n == curRow && n == curCol)
        { 
            ans = min(ans, step);
            return;
        }
    
        for(int i = 0; i < 4; i++)
        { 
            int nextRow = curRow + dir[i][0];
            int nextCol = curCol + dir[i][1];
            if(nextRow >= 1 && nextRow <= n && nextCol >= 1 && nextCol <= n && !vis[nextRow][nextCol] && a[nextRow][nextCol] != '#')
            { 
                vis[nextRow][nextCol] = true;
                dfs(nextRow, nextCol, step + 1);
                vis[nextRow][nextCol] = false;
            }
        }
    
    }
    
    int main()
    { 
        freopen("record.in", "r", stdin);
        freopen("record.out", "w", stdout);
    
        int p, q;
        cin >> n >> p >> q;
    
        for(int row = 1; row <= n; row++)
        { 
            for(int col = 1; col <= n; col++)
            { 
                a[row][col] = '.';
            }
        }
    
        for(int i = 1; i <= p; i++)
        { 
            int x, y;
            cin >> x >> y;
            a[x][y] = '#';
        }
    
        vis[1][1] = true;
        dfs(1, 1, 1);
    
        cout << (ans == INT_MAX ? -1 : ans);
    
        return 0;
    }

## 解法二：广度优先搜索，不考虑友好城市，60分 ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 105;
    bool notGo[maxN][maxN];
    vector<pair<int, int> > friCity[maxN][maxN];
    const int maxDays = 40005;
    vector<pair<int, int> > step[maxDays];
    int dis[maxN][maxN];
    int mv[4][2] = { { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1}};
    int n, p, q;
    
    bool checkMin(int &x, int y)
    { 
        return x > y ? x = y, true : false;
    }
    
    bool check(pair<int, int> u)
    { 
        return u.first >= 1 && u.first <= n &&
               u.second >= 1 && u.second <= n &&
               !notGo[u.first][u.second];
    }
    
    int main()
    { 
        cin >> n >> p >> q;
    
        for(int i = 1; i <= p; i++)
        { 
            int x, y;
            cin >> x >> y; //野蛮城市
            notGo[x][y] = true;
        }
    
        for(int i = 1; i <= q; i++)
        { 
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            friCity[a][b].push_back(make_pair(c, d));
        }
    
        step[1].push_back(make_pair(1, 1));
    
        for(int i = 1; i <= n; i++)
        { 
            for(int j = 1; j <= n; j++)
            { 
                dis[i][j] = maxDays;
            }
        }
        dis[1][1] = 1;
    
        int ans = -1;
        for(int i = 1; i < maxDays; i++)
        { 
            for(auto v : step[i])
            { 
                if(dis[v.first][v.second] != i)
                { 
                    continue;
                }
    
                if(v.first == n && v.second == n)
                { 
                    ans = i;
                }
    
                //往四个方向挪动一格
                for(int t = 0; t < 4; t++)
                { 
                    pair<int, int> grid = make_pair(v.first + mv[t][0], v.second + mv[t][1]);
                    if(!check(grid))
                    { 
                        continue;
                    }
    
                    int day = dis[v.first][v.second] + 1;
                    if(checkMin(dis[grid.first][grid.second], day))
                    { 
                        step[day].push_back(grid);
                    }
                }
            }
        }
    
        cout << ans << endl;
    
        return 0;
    }

## 解法三：广度优先搜索，100分 ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 105;
    bool notGo[maxN][maxN];
    vector<pair<int, int> > friCity[maxN][maxN];
    const int maxDays = 40005;
    vector<pair<int, int> > step[maxDays];
    int dis[maxN][maxN];
    int mv[4][2] = { { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1}};
    int n, p, q;
    
    bool checkMin(int &x, int y)
    { 
        return x > y ? x = y, true : false;
    }
    
    bool check(pair<int, int> u)
    { 
        return u.first >= 1 && u.first <= n &&
               u.second >= 1 && u.second <= n &&
               !notGo[u.first][u.second];
    }
    
    int main()
    { 
        freopen("record.in", "r", stdin);
        freopen("record.out", "w", stdout);
    
        cin >> n >> p >> q;
    
        for(int i = 1; i <= p; i++)
        { 
            int x, y;
            cin >> x >> y; //野蛮城市
            notGo[x][y] = true;
        }
    
        for(int i = 1; i <= q; i++)
        { 
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            friCity[a][b].push_back(make_pair(c, d));
        }
    
        step[1].push_back(make_pair(1, 1));
    
        for(int i = 1; i <= n; i++)
        { 
            for(int j = 1; j <= n; j++)
            { 
                dis[i][j] = maxDays;
            }
        }
        dis[1][1] = 1;
    
        int ans = -1;
        for(int i = 1; i < maxDays; i++)
        { 
            for(auto v : step[i])
            { 
                if(dis[v.first][v.second] != i)
                { 
                    continue;
                }
    
                if(v.first == n && v.second == n)
                { 
                    ans = i;
                }
    
                //往四个方向挪动一格
                for(int t = 0; t < 4; t++)
                { 
                    pair<int, int> grid = make_pair(v.first + mv[t][0], v.second + mv[t][1]);
                    if(!check(grid))
                    { 
                        continue;
                    }
    
                    int day = dis[v.first][v.second] + 1;
                    if(checkMin(dis[grid.first][grid.second], day))
                    { 
                        step[day].push_back(grid);
                    }
                }
    
                //从友好城市坐飞机到另一城市
                for(auto h : friCity[v.first][v.second])
                { 
                    int day = dis[v.first][v.second] + 4;
                    if(!check(h))
                    { 
                        continue;
                    }
    
                    if(checkMin(dis[h.first][h.second], day))
                    { 
                        step[day].push_back(h);
                    }
                }
            }
        }
    
        cout << ans << endl;
    
        return 0;
    }

## 解法四：迪杰特斯拉算法，100分 ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 105;
    int dis[maxN][maxN];
    bool vis[maxN][maxN];
    bool notGo[maxN][maxN];
    int friCity[maxN][maxN];
    int N;
    int dir[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}}; //右下左上
    int flyTo[maxN][2];
    
    struct node
    { 
        int x;
        int y;
        int dist;
        node(int _x = 0, int _y = 0, int _dist = 0) : x(_x), y(_y), dist(_dist)
        { 
        }
    };
    
    bool operator < (node a, node b)
    { 
        return a.dist > b.dist;
    }
    
    void dijkstra()
    { 
        for(int i = 1; i <= N; i++)
        { 
            for(int j = 1; j <= N; j++)
            { 
                dis[i][j] = INT_MAX;
                vis[i][j] = false;
            }
        }
    
        priority_queue<node> q;
        dis[1][1] = 1;
        q.push(node(1, 1, 1));
    
        while(!q.empty())
        { 
            node p = q.top();
            q.pop();
            int ux = p.x;
            int uy = p.y;
            if(vis[ux][uy])
            { 
                continue;
            }
            vis[ux][uy] = true;
    
            for(int i = 0; i < 4; i++)
            { 
                int vx = ux + dir[i][0];
                int vy = uy + dir[i][1];
    
                int w = 1;
                if(vx < 1 || vx > N || vy < 1 || vy > N || notGo[vx][vy])
                { 
                    continue;
                }
    
                if(dis[ux][uy] + w < dis[vx][vy])
                { 
                    dis[vx][vy] = dis[ux][uy] + w;
                    q.push(node(vx, vy, dis[vx][vy]));
                }
            }
    
            if(friCity[ux][uy] > 0)
            { 
                int vx = flyTo[friCity[ux][uy]][0];
                int vy = flyTo[friCity[ux][uy]][1];
                int w = 4;
                if(dis[ux][uy] + w < dis[vx][vy])
                { 
                    dis[vx][vy] = dis[ux][uy] + w;
                    q.push(node(vx, vy, dis[vx][vy]));
                }
            }
        }
    }
    
    int main()
    { 
        freopen("record.in", "r", stdin);
        freopen("record.out", "w", stdout);
    
        int P, Q;
        cin >> N >> P >> Q;
        int i;
        for(i = 1; i <= P; i++)
        { 
            int x, y;
            cin >> x >> y;
            notGo[x][y] = true; //不去这个城市
        }
    
        for(i = 1; i <= Q; i++)
        { 
            int x, y, xx, yy;
            cin >> x >> y >> xx >> yy;
            friCity[x][y] = i; //(x,y)是第i个友好城市
            flyTo[i][0] = xx;
            flyTo[i][1] = yy;
        }
    
        dijkstra();
    
        if(dis[N][N] == INT_MAX)
        { 
            cout << -1 << endl;
        }
        else
        { 
            cout << dis[N][N] << endl;
        }
    
        return 0;
    }

==============================  
长按识别二维码加好友获取卷子并邀请进信息学竞赛群  
![在这里插入图片描述][20200923182612351.png_pic_center]

[20200923182612351.png_pic_center]: /images/20221123/a7306ec6d52f4bc68f1c36db449cb507.png