T1

#include 
   
    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
    
     ());    cout << a[0] * a[1];    return 0;}

T2

#include 
   
    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 
   
    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 
   
    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 
   
    using namespace std;const int maxN = 105;bool notGo[maxN][maxN];vector
    
     
       > friCity[maxN][maxN];const int maxDays = 40005;vector
      
       
         > 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
        
          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
         
           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 
   
    using namespace std;const int maxN = 105;bool notGo[maxN][maxN];vector
    
     
       > friCity[maxN][maxN];const int maxDays = 40005;vector
      
       
         > 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
        
          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
         
           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 
   
    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
    
      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;}

==============================

长按识别二维码加好友获取卷子并邀请进信息学竞赛群

转载地址：http://vfvk.baihongyu.com/

你可能感兴趣的文章