蓝桥杯

试题 历届真题 杨辉三角形【第十二届】【省赛】【B组】

2022/03/20

得分：80

#include <iostream>
using namespace std;
long long m;     //行-1
long long n;     //列-1
long long v;     // C(m,n)的值
long long temp;  //临时变量用来提速

void down() {  //下一层
  v = v * (m + 1) / (m - n + 1);
  ++m;
}
void left() {  //左一个
  v = v * n / (m - n + 1);
  --n;
}
void center() {                  //尝试往中间靠
  temp = v * (m - n) / (n + 1);  //如果右边更大就向右，否则不用动
  if (v < temp) {
    v = temp;
    ++n;
  }
}
int main() {
  long long N, ans = 0;
  cin >> N;
  v = 1;
  m = 1;
  n = 0;
  while (1) {  //查找
    if (v < N) {
      down();
      center();
    } else if (v > N) {
      left();
    } else {
      break;
    }
  }
  //检查位置正确性
  // cout << m+1 << " " << n+1 << endl;
  ans = m * (m + 1) / 2 + n + 1;  //前面的等差数列求和然后加当前行
  if (ans == 2) ans = 1;
  cout << ans << endl;
  return 0;
}

试题 历届真题 时间显示【第十二届】【省赛】【B组】

2022/03/21

得分：100

#include <iomanip>
#include <iostream>
using namespace std;
// 46800999
// 1618708103123
int main() {
  unsigned long long time;
  cin >> time;
  int now = (time / 1000) % (24 * 60 * 60);
  int hour = now / (60 * 60);
  int minute = (now - hour * 60 * 60) / 60;
  int second = now - hour * 60 * 60 - minute * 60;
  cout << setw(2) << setfill('0') << hour << ":" << setw(2) << setfill('0')
       << minute << ":" << setw(2) << setfill('0') << second;
}

试题 历届真题 双向排序【第十二届】【省赛】【B组】

2022/03/21

得分：60 (后面超时)

#include <algorithm>
#include <iostream>
#include <vector>
bool cmp(int a, int b) { return a > b; }

using namespace std;
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int length, times;
  cin >> length >> times;
  vector<int> array;
  for (int i = 0; i < length; i++) {
    array.push_back(i + 1);
  }
  while (times--) {
    bool operation;
    int index;
    cin >> operation >> index;
    if (operation) {
      sort(array.begin() + index - 1, array.end());
    } else {
      sort(array.begin(), array.begin() + index, cmp);
    }
  }
  for (int i = 0; i < length; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

试题 历届真题 砝码称重【第十二届】【省赛】【B组】

2022/03/22

得分：100

#include <bits/stdc++.h>
#define int long long
using namespace std;

int W = 100001;
int N;

signed main() {
  cin >> N;
  int nums[N];
  for (int i = 0; i < N; i++) {
    cin >> nums[i];
  }

  vector<vector<bool> > dp(N, vector<bool>(W));
  dp[0][nums[0]] = true;
  for (int i = 1; i < N; i++) {
    dp[i][nums[i]] = true;
    for (int j = 0; j < W; j++) {
      if (dp[i - 1][j]) {
        dp[i][j] = true;
        dp[i][j + nums[i]] = true;
        dp[i][abs(nums[i] - j)] = true;
      }
    }
  }
  int count = 0;
  for (int i = 1; i < W; i++) {
    count += dp.back()[i];
  }
  cout << count << endl;
  return 0;
}

试题 历届真题 回文日期【第十一届】【省赛】【B组】

2022/03/28

得分：100

一共366个回文，直接暴力求解

#include <bits/stdc++.h>
#define int long long
using namespace std;

int days[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int reverse(int num) {
    int ans = 0;
    while (num) {
        ans *= 10;
        ans += num % 10;
        num /= 10;
    }
    return ans;
}

signed main() {
    int date;
    cin >> date;
    vector<int> dates;
    for (int month = 1; month <= 12; month++) {
        for (int day = 1; day <= days[month - 1]; day++) {
            int month_day = month * 100 + day;
            int year = reverse(month_day);
            dates.push_back(month_day + year * (year / 1000 == 0 ? 100000 : 10000));
        }
    }
    sort(dates.begin(), dates.end());
    bool flag = 0;
    for (int i = 0; i < dates.size(); i++) {
        if (!flag) {
            if (dates[i] > date) {
                cout << setfill('0') << setw(8) << dates[i] << endl;
                flag = 1;
                if (dates[i] % 100 == (dates[i] / 100) % 100) {
                    cout << setfill('0') << setw(8) << dates[i] << endl;
                    break;
                }
            }
        } else if (flag) {
            if (dates[i] % 100 == (dates[i] / 100) % 100) {
                cout << setfill('0') << setw(8) << dates[i] << endl;
                break;
            }
        }
    }
    return 0;
}

试题 历届真题 成绩分析【第十一届】【省赛】【B组】

2022/03/29

得分：100

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
int Max = 0;
int Min = INT_MAX;
float average = 0;

signed main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        Max = max(Max, tmp);
        Min = min(Min, tmp);
        average += tmp;
    }
    average /= n;
    cout << Max << endl
         << Min << endl;
    cout << fixed << setprecision(2) << average << endl;
}

2019-1

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> haihaihai = {
    {97, 90, 0, 0, 0},
    {92, 85, 96, 0, 0},
    {0, 0, 0, 0, 93},
    {0, 0, 0, 80, 86},
    {89, 83, 97, 0, 0},
    {82, 86, 0, 0, 0},
    {0, 0, 0, 87, 90},
    {0, 97, 96, 0, 0},
    {0, 0, 89, 0, 0},
    {95, 99, 0, 0, 0},
    {0, 0, 96, 97, 0},
    {0, 0, 0, 93, 98},
    {94, 91, 0, 0, 0},
    {0, 83, 87, 0, 0},
    {0, 0, 98, 97, 98},
    {0, 0, 0, 93, 86},
    {98, 83, 99, 98, 81},
    {93, 87, 92, 96, 98},
    {0, 0, 0, 89, 92},
    {0, 99, 96, 95, 81},
};
int m;

void fun(int pos, int sum, int num, vector<bool> visited) {
    if (num == 5) {
        m = max(m, sum);
    } else {
        for (int i = 0; i < 20; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            fun(pos + 1, sum + haihaihai[i][pos], num + 1, visited);
            visited[i] = false;
        }
    }
}

signed main() {
    vector<bool> visited(20, 0);
    fun(0, 0, 0, visited);
    cout << m << endl;
    return 0;
}

2019-2

#include <bits/stdc++.h>
#define int long long
using namespace std;

// 答案是反着的
signed main() {
    int k = 2019;
    while (k) {
        cout << char(k % 26 + 'A' - 1);
        k /= 26;
    }
}

2019-3

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> haihaihai(20190324);

signed main() {
    haihaihai[0] = 1;
    haihaihai[1] = 1;
    haihaihai[2] = 1;
    for (int i = 3; i < 20190324; i++) {
        haihaihai[i] = haihaihai[i - 1] + haihaihai[i - 2] + haihaihai[i - 3];
        haihaihai[i] %= 10000;
    }
    cout << haihaihai.back();
}

2019-4

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool judge(int x) {
    while (x) {
        if (x % 10 == 2 || x % 10 == 4) return false;
        x /= 10;
    }
    return true;
}

signed main() {
    int sum = 0;
    for (int i = 1; i < 2019 / 3; i++) {
        if (!judge(i)) continue;
        for (int j = i + 1; j < 2019; j++) {
            if (!judge(j)) continue;
            if (2019 - i - j > j) {
                int k = 2019 - i - j;
                if (!judge(k)) continue;
                sum++;
            }
        }
    }
    cout << sum << endl;
}

2019-5

#include <bits/stdc++.h>
#define int long long
using namespace std;

queue<pair<pair<int, int>, string>> bfs;
int nextX[] = {1, 0, 0, -1};
int nextY[] = {0, -1, 1, 0};
char nextC[] = {'D', 'L', 'R', 'U'};

vector<string> maps = {
    "01010101001011001001010110010110100100001000101010",
    "00001000100000101010010000100000001001100110100101",
    "01111011010010001000001101001011100011000000010000",
    "01000000001010100011010000101000001010101011001011",
    "00011111000000101000010010100010100000101100000000",
    "11001000110101000010101100011010011010101011110111",
    "00011011010101001001001010000001000101001110000000",
    "10100000101000100110101010111110011000010000111010",
    "00111000001010100001100010000001000101001100001001",
    "11000110100001110010001001010101010101010001101000",
    "00010000100100000101001010101110100010101010000101",
    "11100100101001001000010000010101010100100100010100",
    "00000010000000101011001111010001100000101010100011",
    "10101010011100001000011000010110011110110100001000",
    "10101010100001101010100101000010100000111011101001",
    "10000000101100010000101100101101001011100000000100",
    "10101001000000010100100001000100000100011110101001",
    "00101001010101101001010100011010101101110000110101",
    "11001010000100001100000010100101000001000111000010",
    "00001000110000110101101000000100101001001000011101",
    "10100101000101000000001110110010110101101010100001",
    "00101000010000110101010000100010001001000100010101",
    "10100001000110010001000010101001010101011111010010",
    "00000100101000000110010100101001000001000000000010",
    "11010000001001110111001001000011101001011011101000",
    "00000110100010001000100000001000011101000000110011",
    "10101000101000100010001111100010101001010000001000",
    "10000010100101001010110000000100101010001011101000",
    "00111100001000010000000110111000000001000000001011",
    "10000001100111010111010001000110111010101101111000",
};

signed main() {
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), 0));
    bfs.push({{0, 0}, ""});
    visited[0][0] = 1;
    string ans;
    while (true) {
        for (int i = 0; i < bfs.size(); i++) {
            pair<int, int> tmp = bfs.front().first;
            if (tmp.first == maps.size() - 1 && tmp.second == maps[0].size() - 1) {
                ans = bfs.front().second;
                break;
            }
            for (int j = 0; j < 4; j++) {
                pair<int, int> newTmp(tmp.first + nextX[j], tmp.second + nextY[j]);
                if (newTmp.first < 0 || newTmp.first >= maps.size() || newTmp.second < 0 || newTmp.second >= maps[0].size() || maps[newTmp.first][newTmp.second] == '1' || visited[newTmp.first][newTmp.second]) {
                    continue;
                } else {
                    bfs.push({newTmp, bfs.front().second + nextC[j]});
                    visited[newTmp.first][newTmp.second] = 1;
                }
            }
            bfs.pop();
        }
        if (!ans.empty()) break;
    }
    cout << ans << endl;
}

/*
答案：
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
*/