2019 蓝桥杯10届省赛
1.组队
// 比对 #include <cstdio> #include <iostream> using namespace std; int main() { printf("%d\n", 98 99 98 97 98); return 0; } 2.年号字串 BYQ
#include <cstdio> #include <iostream> using namespace std; char a[10]; int main() { /* string s; int res = 0; cin >> s; for (int i = 0; i < s.size(); i ) { res = res * 26 s[i] - 'A' 1; } cout << res << endl; */ int n, i = 0; scanf("%d", &n); while (n > 0) { a[i ] = n % 26 'A' - 1; n /= 26; } for (int i = 0; i < 5; i ) { cout << a[i] << endl; } return 0; } 3.数列求值 前三项和
#include <cstdio> #include <iostream> using namespace std; int f(int n) { int a = 1, b = 1, c = 1, d; for (int i = 1; i < n; i ) { d = (a b c) % 10000; a = b; b = c; c = d; } return a; } int main() { cout << f(20190324) << endl; return 0; } 4.数的分解
#include <cstdio> #include <iostream> using namespace std; bool check(int n) { int t = n; while (t > 0) { if (t % 10 == 2 || t % 10 == 4) return false; t /= 10; } return true; } int sum; int main() { for (int i = 1; i <= 2019; i ) { if (check(i)) for (int j = i 1; j <= 2019; j ) { if (check(j)) if (2019 - i - j > j && check(2019 - i - j)) sum ; } } printf("%d\n", sum); return 0; } 5.迷宫
#include<bits/stdc .h> using namespace std; #define maxn 2000 string maze[maxn]= { "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"}; bool vis[maxn][maxn];//标记 int dir[4][2]={
{1，0}，{0，-1}，{0，1}，{1，0}D L R U bool in(int x,int y) { return x<30&&x>=0&&y>=0&&y<50; } struct node { int x,y,d; char pos;//存储D L R U }; node father[maxn][maxn];////当前节点的父节点 node now,nex;///指向当前和下一个位置 void dfs(int x,int y)///递归打印 { if(x==0&&y==///找到起点，开始正向打印路径 return; else dfs(father[x][y].x,father[x][y].y); cout<<father[x][y].pos; } void bfs(int x,int y) { queue<node> q; now.x=x; now.y=y; ow.d=0;
q.push(now);
vis[x][y]=true;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)//走下左右上按字典序的四个方向
{
int tx=now.x+dir[i][0];
int ty=now.y+dir[i][1];
if(in(tx,ty)&&!vis[tx][ty]&&maze[tx][ty]!='1')//判断是否超出范围，是否用过，是否为1
{
vis[tx][ty]=true;//标记为用过
nex.x=tx;
nex.y=ty;
nex.d=now.d+1;
q.push(nex);//压入队列
father[tx][ty].x=now.x;//存储父节点坐标
father[tx][ty].y=now.y;
if(i==0)//存储路径
father[tx][ty].pos='D';
else if(i==1)
father[tx][ty].pos='L';
else if(i==2)
father[tx][ty].pos='R';
else if(i==3)
father[tx][ty].pos='U';
}
}
}
}
int main()
{
bfs(0,0);
dfs(29,49);//打印路径
return 0;
}
6.特别数的和
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
int t = i;
bool flag = false;
while (t > 0) {
if (t % 10 == 2 || t % 10 == 0 || t % 10 == 1 || t % 10 == 9) {
flag = true;
break;
}
t /= 10;
}
if (flag) sum += i;
}
printf("%d\n", sum);
return 0;
}
7.完全二叉树的权值
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
LL maxs = -1e18;
int depth = 0;
for (int d = 1, i = 1; i <= n; i *= 2, d ++ ) {
LL s = 0;
for (int j = i; j < i + (1 << d - 1) && j <= n; j ++ )
s += a[j];
if (s > maxs) {
maxs = s;
depth = d;
}
}
printf("%d\n", depth);
return 0;
}
8.等差数列
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, d;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
scanf("%d", &n);
for (int i = 0; i <= n - 1; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
for (int i = 1; i <= n - 1; i ++ ) d = gcd(d, a[i] - a[0]);
if (d == 0) {
printf("%d\n", n);
} else {
printf("%d\n", (a[n - 1] - a[0]) / d + 1);
}
return 0;
}
9.后缀表达式
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int>a(n + m + 1);
for (int i = 0; i < n + m + 1; i++) cin >> a[i];
if (!m) cout << accumulate(a.begin(), a.end(), 0ll) << '\n';
else {
sort(a.begin(), a.end());
ll ans = -a.front() + a.back();
for (int i = 1; i < n + m; i++) ans += abs(a[i]);
cout << ans << '\n';
}
return 0;
}
10.灵能传输
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
signed main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<ll>s(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s[i + 1] = s[i] + x;
}
ll s0 = s[0], sn = s[n];
if (s0 > sn) swap(s0, sn);
sort(s.begin(), s.end());
for (int i = 0; i <= n; i++) if (s[i] == s0) {
s0 = i;
break;
}
for (int i = n; i >= 0; i--) if (s[i] == sn) {
sn = i;
break;
}
vector<ll>a(n + 1);
vector<bool>v(n + 1);
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2)
a[l++] = s[i], v[i] = true;
for (int i = sn; i <= n; i += 2)
a[r--] = s[i], v[i] = true;
for (int i = 0; i <= n; i++)
if (!v[i]) a[l++] = s[i];
ll ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, abs(a[i] - a[i - 1]));
cout << ans << '\n';
}
return 0;
}
2020 蓝桥杯11届省赛
1.门牌制作
#include <iostream>
#include <cstdio>
using namespace std;
int sum;
int main() {
for (int i = 1; i <= 2020; i ++ ) {
int t = i;
while (t > 0) {
if (t % 10 == 2) {
sum ++ ;
}
t /= 10;
}
}
printf("%d\n", sum);
return 0;
}
2.既约分数
#include <iostream>
#include <cstdio>
using namespace std;
int sum;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
// int gcd(int a, int b) {if (b == 0) return a; else return gcd(b, a % b);}
}
int main() {
for (int i = 1; i <= 2020; i ++ ) {
for (int j = 1; j <= 2020; j ++ ) {
if (gcd(i, j) == 1) sum ++ ;
}
}
printf("%d\n", sum);
return 0;
}
3.蛇形填数 找规律 (n - 1) * (n - 1) + n * n
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
cout << 19 * 19 + 20 * 20 << endl;
return 0;
}
4.跑步锻炼 模拟构造 日期
#include <iostream>
#include <cstdio>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool valid(int date) {
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (month == 0 || month > 12) return false;
if (day == 0 || month != 2 && day > days[month]) return false;
if (month == 2) {
int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0;
if (day > 28 + leap) return false;
}
return true;
}
int sum, ans; // 正确合法记录的总日子sum 求星期一 %7 == 3需要加 总答案ans
int main() {
for (int i = 20000101; i <= 20201001; i ++ ) {
if (valid(i)){
sum ++ ;
ans ++ ;
if (sum % 7 == 3 || i % 100 == 1) ans ++ ;
}
}
printf("%d\n", ans);
return 0;
}
5.七段码
/*
题目大意
小蓝要用七段码数码管来表示一种特殊的文字。
图片描述
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
解题思路
我们可以把每个二极管看成一条边，并把相邻的边相连，那么这样题目就可以转换为：
有多少种选边方案，使得选出来的边构成的图只有一个联通快。
于是现在只要枚举选边方案，再判断联通块的个数是否为 1 即可。
枚举选边方案可以采用状压（当然直接 dfs 搜索也行）：用二进制 1、0 分别表示二进制位所对应的边是选还是不选，复杂度为 2^7。
求联通块的个数可以采用 bfs（也可以采用并查集等方法）：从任意一个选中的边出发将所有能到达的选中的边全部打上标记；若标记覆盖了所有选中的边则联通快只有一个（满足条件），反之不止一个联通块（不满足条件）。
最后的答案为 80。
*/
#include<bits/stdc++.h>
using namespace std;
int ans , g[7][7] , vis[7] , flag[7];
void bfs(int x){
queue<int>que;
que.push(x);
vis[x] = true;
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = 0 ; i <= 6 ; i ++){
if(g[u][i] && flag[i] && !vis[i]){
vis[i] = true;
que.push(i);
}
}
}
}
bool check(int x){
for(int i = 0 ; i <= 6 ; i ++) flag[i] = vis[i] = false;
int cnt = 0;
for(int i = 6 ; ~i ; i --) if(x >> i & 1) flag[i] = true;
for(int i = 0 ; i <= 6 ; i ++){
if(flag[i] && !vis[i]){
bfs(i);
cnt ++ ;
}
}
return cnt == 1;
}
signed main()
{
g[0][1] = g[0][5] = 1;
g[1][0] = g[1][2] = g[1][6] = 1;
g[2][1] = g[2][3] = g[2][6] = 1;
g[3][2] = g[3][4] = 1;
g[4][3] = g[4][5] = g[4][6] = 1;
g[5][0] = g[5][4] = g[5][6] = 1;
g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
for(int i = 0 ; i < (1 << 7) ; i ++){
if(check(i)) {
ans ++ ;
}
}
cout << ans << '\n';
return 0;
}
6.成绩统计
#include <iostream>
#include <cstdio>
using namespace std;
int n, t, x, y, a, b;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &t);
if (t >= 60) {
x ++ ;
if (t >= 85) {
y ++ ;
}
}
}
int a = x * 100.0 / n + 0.5, b = y * 100.0 / n + 0.5;
printf("%d%%\n%d%%", a, b);
return 0;
}
7.回文日期 大模拟 构造
#include <iostream>
#include <cstdio>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool valid(int date) {
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (month == 0 || month > 12) return false;
if (day == 0 || month != 2 && day > days[month]) return false;
if (month == 2) {
int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0;
if (day > 28 + leap) return false;
}
return true;
}
bool check1(int date) {
int d1 = date / 10000, d2 = date % 10000, x = 0;
for (int i = 0; i < 4; i ++ ) {
x = x * 10 + d2 % 10, d2 /= 10; // 1234 -> 4321
}
return d1 == x;
}
bool check2(int date) {
int month = date % 10000 / 100, day = date % 100;
return month == day;
}
int n, ans1, ans2;
int main() {
scanf("%d", &n);
for (int i = n + 1; i <= 99999999; i ++ ) {
if (check1(i) && valid(i)) {
ans1 = i;
break;
}
}
for (int i = n + 1; i <= 99999999; i ++ ) {
if (check2(i) && check1(i) && valid(i)) {
ans2 = i;
break;
}
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
8.子串分值和
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
char s[N];
int suf[N] , last[30];
signed main()
{
cin >> s + 1;
int n = strlen(s + 1) , ans = 0;
for(int j = 0 ; j <= 25 ; j ++) last[j] = n + 1;
for(int i = n ; i >= 1 ; i --){
suf[i] = last[s[i] - 'a'];
last[s[i] - 'a'] = i;
}
for(int i = 1 ; i <= n ; i ++){
ans += i * (suf[i] - i);
}
cout << ans << '\n';
return 0;
}
9.平面切分
#include<bits/stdc++.h>
using namespace std;
int n , ans = 1;
set<pair<int , int>>line;
int calc(int a , int b){
set<pair<double , double>>node;
for(auto i : line){
int A = i.first , B = i.second;
if(A == a) continue ;
double x = 1.0 * (B - b) / (a - A);
double y = x * a + b;
node.insert(make_pair(x , y));
}
return node.size() + 1;
}
signed main()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++) {
int a , b;
cin >> a >> b;
if(line.find(make_pair(a , b)) != line.end()) continue;
ans += calc(a , b);
line.insert(make_pair(a , b));
}
cout << ans << '\n';
return 0;
}
10.字串排序
#include<bits/stdc++.h>
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){
memset(cnt , 0 , sizeof(cnt));
int add1 = 0 , add2 = 0;
for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];
sum[x] ++ ;
for(int L = 1 ; L <= n ; L ++){
int ma = -1 , pos = 0 , num = 0;
for(int j = 26 ; j >= 1 ; j --){
if(L - 1 - cnt[j] + num > ma){
ma = L - 1 - cnt[j] + num;
pos = j;
}
num += sum[j];
}
add2 += ma , cnt[pos] ++;
}
if(now + add1 + add2 >= V) {
now += add1;
return true;
}
else {
sum[x] -- ;
return false;
}
}
signed main()
{
string ans = "";
cin >> V;
for(int i = 1 ; ; i ++) {
if(get_max(i) >= V){
len = i;
break ;
}
}
for(int i = 1 ; i <= len ; i ++){
for(int j = 1 ; j <= 26 ; j ++){
if(check(j , len - i)){
ans += char(j + 'a' - 1);
break ;
}
}
}
cout << ans << '\n';
return 0;
}
2021 蓝桥杯12届省赛
1.空间
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
printf("%d\n", 256 * 1024 * 1024 / (32 / 8));
return 0;
}
2.卡片
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int a[10], temp;
for (int i = 0; i <= 9; i ++ ) {
a[i] = 2021;
}
for (int i = 1; ; i ++ ) {
int t = i;
bool flag = true;
while (t > 0) {
if (a[t % 10] > 0) {
a[t % 10] -- ;
}
else {
flag = false;
break;
}
t /= 10;
}
if (flag == false) {
temp = i;
break;
}
}
printf("%d\n", temp - 1);
return 0;
}
3.直线
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 500010;
struct node{
double k, b;
bool operator<(const node& t)const {
if (k != t.k) return k < t.k;
return b < t.b;
}
}line[N];
// k = (y2 - y1) / (x2 - x1)
// b = m
int cnt, sum;
int main() {
for (int x1 = 0; x1 < 20; x1 ++ ) {
for (int y1 = 0; y1 < 21; y1 ++ ) {
for (int x2 = 0; x2 < 20; x2 ++ ) {
for (int y2 = 0; y2 < 21; y2 ++ ) {
if (x1 != x2) {
double k = (double)(y2 - y1) / (x2 - x1);
double b = k * x1 - y1;
line[cnt ++ ] = {k, b};
}
}
}
}
}
sort(line, line + cnt);
for (int i = 0; i + 1 < cnt; i ++ ) {
if (fabs(line[i + 1].k - line[i].k) > 1e-8 || fabs(line[i + 1].b - line[i].b) > 1e-8)
sum ++ ;
}
printf("%d\n", sum + 1 + 20);
return 0;
}
4.货物摆放
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int ans;
int main() {
vector<long long> v;
long long n = 2021041820210418;
for (long long i = 1; i * i <= n; i ++ ) {
if (n % i == 0) {
v.push_back(i);
if (n / i != i) v.push_back(n / i); // 把自身，另一半约数，也放进去
}
}
for (long long i : v) {
for (long long j : v) {
for (long long k : v) {
if (i * j * k == n) ans ++ ;
}
}
}
printf("%d\n", ans);
return 0;
}
5.路径 最短路算法1-2021 21
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 2200, M = N * 50;
int n;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa() {
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q[tt ++ ] = 1;
st[1] = true;
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main() {
n = 2021;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
for (int j = max(1, i - 21); j <= min(n, i + 21); j ++ ) {
int d = gcd(i, j);
add(i, j, i * j / d);
}
spfa();
printf("%d\n", dist[n]);
return 0;
}
6.时间显示
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
long long t;
scanf("%lld", &t);
t /= 1000;
t %= (24 * 3600);
int h = t / 3600;
int m = t % 3600 / 60;
int s = t % 60;
printf("%02d:%02d:%02d", h, m, s);
return 0;
}
7.砝码称重 DP
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL dp[N], w[105];
int main() {
LL n;
scanf("%lld", &n);
for (LL i = 1; i <= n; i ++ ) {
scanf("%lld", &w[i]);
}
memset(dp, 0, sizeof dp);
dp[0] = 1;
for (LL i = 1; i <= n; i ++ ) {
for (LL j = 100000; j >= w[i]; j -- ) {
dp[j] = max(dp[j], dp[j - w[i]]);
}
}
for (LL i = 1; i <= n; i ++ ) {
LL siz = 100000 - w[i];
for (LL j = 1; j <= siz; j ++ ) {
dp[j] = max(dp[j], dp[j + w[i]]);
}
}
LL ans = 0;
for (LL i = 1; i <= 100000; i ++ ) {
ans += dp[i];
}
printf("%lld\n", ans);
return 0;
}
8.杨辉三角 int long long
#include <cstdio>
#include <iostream>
using namespace std;
long long n;
long long C(long a, long long b) {
long long res = 1;
for (long long i = a, j = 1; j <= b; i -- , j ++ ) {
res = res * i / j;
if (res > n) return res;
}
return res;
}
int main() {
scanf("%lld", &n);
for (long long k = 16; ~k; k -- ) {
long long l = 2 * k, r = max(n, l), res = -1;
while (l <= r) {
long long mid = (l + r) / 2;
if (C(mid, k) >= n) res = mid, r = mid - 1;
else l = mid + 1;
}
if (C(res, k) == n) {
printf("%lld\n", (res + 1) * res / 2 + k + 1);
return 0;
}
}
return 0;
}
9.双向排序
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main() {
scanf("%d %d", &n, &m);
int top = 0;
while (m -- ) {
int p, q;
scanf("%d %d", &p, &q);
if (!p) {
while (top && stk[top].x == 0)
q = max(q, stk[top--].y);
while (top >= 2 && stk[top - 1].y <= q)
top -= 2;
stk[++top] = {0, q};
} else if (top) {
while (top && stk[top].x == 1)
q = min(q, stk[top--].y);
while (top >= 2 && stk[top - 1].y >= q)
top -= 2;
stk[++top] = {1, q};
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ ) {
if (stk[i].x == 0)
while (r > stk[i].y && l <= r)
ans[r--] = k--;
else
while (l < stk[i].y && l <= r)
ans[l++] = k--;
if (l > r)
break;
}
if (top % 2) {
while (l <= r)
ans[l++] = k--;
}
else {
while (l <= r)
ans[r--] = k--;
}
for (int i = 1; i <= n; i ++ ) {
printf("%d ", ans[i]);
}
return 0;
}
10.括号序列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5010, MOD = 1e9 + 7;
int n;
char str[N];
LL f[N][N];
LL work() {
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n; i ++ ) {
if (str[i] == '(') {
for (int j = 1; j <= n; j ++ ) {
f[i][j] = f[i - 1][j - 1];
}
} else {
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
for (int j = 1; j <= n; j ++ )
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
}
}
for (int i = 0; i <= n; i ++ )
if (f[n][i])
return f[n][i];
return -1;
}
int main() {
scanf("%s", str + 1);
n = strlen(str + 1);
LL l = work();
reverse(str + 1, str + n + 1);
for (int i = 1; i <= n; i ++ ) {
if (str[i] == '(') str[i] = ')';
else str[i] = '(';
}
LL r = work();
printf("%lld\n", l * r % MOD);
return 0;
}
2021 蓝桥杯12届国赛 很难
1.带宽
200mbps = 25MB/s
2.纯质数 线性筛质数
#include <iostream>
using namespace std;
const int N = 20210605;
int prime[N];
bool st[N];
void get_Prime(){
int cnt=0;
for(int i=2;i<=N;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=N/i;j++){
st[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
int main()
{
int num=0;
get_Prime();
for(int i=2;i<=20210605;i++){
if(!st[i]){
int x=i,flag=1;
while(x){
if(x%10==2||x%10==3||x%10==5||x%10==7){
x/=10;
}else{
flag=0;
break;
}
}
if(flag==1) num++;
}
}
cout << num << endl;
return 0;
}
3.完全日期 模拟 构造 977
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool valid(int date) {
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if (month == 0 || month > 12) return false;
if (day == 0 || month != 2 && day > days[month]) return false;
if (month == 2) {
int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0;
if (day > 28 + leap) return false;
}
return true;
}
int add(int n) {
int sum = 0;
int t = n;
while (t > 0) {
sum += t % 10;
t /= 10;
}
return sum;
}
int ans;
int main() {
for (int i = 20010101; i <= 20211231; i ++ ) {
if (valid(i)) {
int x = i / 10000, y = i % 10000 / 100, z = i % 100;
int s = add(x) + add(y) + add(z);
if ((int)sqrt(s) * (int)sqrt(s) == s) ans ++ ;
}
}
printf("%d\n", ans);
return 0;
}
4.最小权值 二叉树
/**2597854139*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=2022;
#define ll long long
ll f[maxn],w[maxn];
void get(int c,int x,int l,int r){
if(x>2021)return ;
if(l<=2021){
f[c]++;
get(c,l,l*2,l*2+1);
}
if(r<=2021){
f[c]++;
get(c,r,r*2,r*2+1);
}
}
int main(){
for(int i=1;i<=2021;i++){
f[i]=0,w[i]=0;
}
for(int i=1;i<=2021;i++){
get(i,i,i*2,i*2+1);//当前结点 左结点 右结点
}
for(int i=2021;i>=1;i--){
if(2*i>2021 && 2*i+1>2021){
w[i]=0;
continue;
}
w[i]=1;
int mark=0;
if(i*2<=2021){
//左结点
w[i]+=2*w[i*2];
mark++;
}
if(i*2+1<=2021){
//右结点
w[i]+=3*w[i*2+1];
mark++;
}
if(mark==2){
w[i]+=(f[i*2]*f[i*2])*f[i*2+1];
}
}
cout<<w[1]<<endl;
return 0;
}
5.大写
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
string s;
getline(cin, s);
for (int i = 0; i < s.size(); i ++ ) {
if (s[i] >= 'a' && s[i] <= 'z') {
s[i] -= 32;
}
}
cout << s << endl;
return 0;
}
6.#F 123
c++语言 二分
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll cal(ll x){
return (x+1)*x/2;
}
//1.注意一定全部开ll
/* 一个数列 1 1 2 1 2 3 1 2 3 4 */
ll a[1500000];ll num[1500000];
//数组是不会改变的，打表预处理，结束条件是下标大于1e12
int main(int argc, char** argv) {
ll t,l,r;
cin>>t;
ll sum=0;int ed=0;
num[0]=0;
for(int i=1;;i++){
sum+=i;
if(sum>1e12){
ed=i-1;
break;
}
a[i]=sum;//a[i]是每个序列结尾的数字的位置，例如1234这个序列4的下标在序列下是10
//你可以写出来看一看，用这个结尾位置我们就好定位两个数字之间有多少个序列了
num[i]=num[i-1]+a[i];//类似前缀和的方法，方便计算，可以把下面那些注释掉的打开看看
}
// for(int i=1;i<ed;i++){
// cout<<a[i]<<' '<<num[i]<<endl;
// }
ll pos,pos1,tmp,tmp1;
while(t--){
cin>>l>>r;
pos=0,pos1=0;
pos=lower_bound(a,a+ed,l)-a;//lower_bound函数返回第一个大于等于该数字的下标
pos1=lower_bound(a,a+ed,r)-a;
//cout<<pos<<' '<<pos1<<endl;
ll ans=num[pos1-1]-num[pos-1];//虽然前缀和的是r - l-1，不过为了简便计算，我们最后一列可以不算，用求和的方式算出来，即下面的cal（tmp1）而前面多出来的部分是cal(tmp)
//cout<<ans<<endl;
tmp=l-a[pos-1]-1;//多减一个1，因为l这一位是要的
tmp1=r-a[pos1-1];
//cout<<tmp<<' '<<tmp1<<endl;
ans+=cal(tmp1);
ans-=cal(tmp);
printf("%lld\n",ans);//当输入输出很多的时候用scanf，printf。
}
return 0;
}
java 满分
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
new Main().run(); }
int N = (int)Math.sqrt(2E12) + 1;
long[] row = new long[N + 1], col = new long[N + 1];
void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
for (int i = 1; i <= N; i++) {
row[i] = i + row[i - 1];
col[i] = col[i - 1] + row[i];
}
int T = in.readInt();
long l, r;
while (T-- > 0) {
l = in.readLong();
r = in.readLong();
out.println(sum(r) - sum(l - 1));
}
out.flush();
}
long sum(long r) {
int k = lowerBound(r);
return r == row[k] ? col[k] : col[k - 1] + row[(int)(r - row[k - 1])];
}
int lowerBound(long k) {
int offset = 0, length = N + 1;
while (length > 0) {
int half = length >> 1;
if (k > row[offset + half]) {
offset += half + 1;
length -= half + 1;
} else length = half;
}
return offset;
}
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() {
return Integer.parseInt(read()); }
long readLong() {
return Long.parseLong(read()); }
}
}
7.异或变换
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=2,N=11000;
int c[N],n;
ll t;
char s[N];
int res[N];
int main()
{
cin>>n>>t;
for(int i=0;i<=n;i++){
c[i]=(t&i)==i;
}
cin>>s+1;
for(int i=1;i<=n;i++){
int v=s[i]-'0';
for(int j=0;j+i<=n;j++){
res[i+j]^=c[j]*v;
}
}
for(int i=1;i<=n;i++) {
cout<<res[i];
}
}
8.二进制问题
#include<iostream>
#include<cstring>
using namespace std;
int bits[70];
long long dp[70][70][2];
long long n, k;
long long dfs(int pos, long long count, int limit) {
if (pos == -1) return count == k;
if (!limit && dp[pos][count][limit] != -1) return dp[pos][count][limit];
int up = limit ? bits[pos] : 1;
long long ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos - 1, count + (i == 1), i == up && limit);
}
if (!limit) dp[pos][count][limit] = ans;
return ans;
}
int main() {
cin >> n >> k;
int len = 0;
memset(dp, -1, sizeof(dp));
while (n) {
bits[len++] = n & 1;
n >>= 1;
}
cout << dfs(len - 1, 0, 1) << endl;
return 0;
}
9.翻转括号序列
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls (t << 1)
#define rs (t << 1 | 1)
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
struct Node{int mx , mi , sw , add;}tr[maxn << 2];
int a[maxn];
char s[maxn];
int n , m;
template <typename T>
void read(T & x){ x = 0;T f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;
ch = getchar();}while (isdigit(ch)){x = x * 10 + (ch ^ 48);ch = getchar();}x *= f;}
template <typename T>
void write(T x){if(x < 0){putchar('-');x = -x;}if (x > 9)write(x / 10);putchar(x % 10 + '0');}
void pushup (int t){
tr[t].mx = max(tr[ls].mx , tr[rs].mx);
tr[t].mi = min(tr[ls].mi , tr[rs].mi);
}
void build (int t , int l , int r){
if (l == r){
tr[t].mx = tr[t].mi = a[l];
return ;
}
build(ls , l , mid);
build(rs , mid + 1 , r);
pushup(t);
}
void D_sw (int t){
int mx = tr[t].mx , mi = tr[t].mi;
tr[t].mx = -mi; tr[t].mi = -mx;
tr[t].sw ^= 1;
tr[t].add *= -1;
}
void D_add (int t , int c){
tr[t].mi += c;
tr[t].mx += c;
tr[t].add += c;
}
void pushdown (int t){
if (tr[t].sw){
D_sw(ls);
D_sw(rs);
tr[t].sw = 0;
}
if (tr[t].add){
D_add(ls,tr[t].add);
D_add(rs,tr[t].add);
tr[t].add = 0;
}
}
void Swap (int t , int l , int r , int L , int R){
if (L <= l && r <= R){
D_sw(t);
return ;
}
pushdown(t);
if (L <= mid) Swap(ls , l , mid , L , R);
if (R > mid) Swap(rs , mid + 1 , r , L , R);
pushup(t);
return ;
}
void add (int t , int l , int r , int L , int R , int c){
if (L <= l && r <= R){
D_add(t , c);
return ;
}
pushdown(t);
if (L <= mid) add(ls , l , mid , L , R , c);
if (R > mid) add(rs , mid + 1 , r , L , R , c);
pushup(t);
return ;
}
// 单点查值
int ask1 (int t , int l , int r , int p){
if (l == r) return tr[t].mx;
pushdown(t);
if (p <= mid) return ask1(ls , l , mid , p);
return ask1(rs , mid + 1 , r , p);
}
// 找[p,n]中离p最近的一个小于c的点
int ask2 (int t , int l , int r , int p , int c){
// -1 代表该区域没有 < c 的数
if (l == r) return l;
pushdown(t);
// 优先往左走,再考虑什么情况下可以往左走
// PS:这么走，答案只是"可能"存在
int res = -1;
if (tr[ls].mi < c && p <= mid)
res = ask2(ls , l , mid , p , c);
if (res != -1) return res;
// 程序能执行到这里代表左边不存在答案了.只能往右走了
if (tr[rs].mi < c)
res = ask2(rs , mid + 1 , r , p , c);
return res;
}
// 找[1,p]中离p最近的小于c的点
int ask3 (int t , int l , int r , int p , int c){
if (l == r) return l;
pushdown(t);
int res = -1;
if (tr[rs].mi < c && p > mid)
res = ask3(rs , mid + 1 , r , p , c);
if (res != -1) return res;
if (tr[ls].mi < c) res = ask3(ls , l , mid , p , c);
return res;
}
int pre[maxn];
void modify (int x){
if (x == 0) return ;
int v = ask1(1 , 1 , n , x);
Swap(1 , 1 , n , 1 , x);
if (x != n) add(1 , 1 , n , x + 1 , n , -2 * v);
}
int main()
{
read(n); read(m);
scanf("%s" , s + 1);
for (int i = 1 ; i <= n ; i++){
if (s[i] == '(') a[i] = a[i - 1] + 1;
else a[i] = a[i - 1] - 1;
}
build(1 , 1 , n);
for (int i = 1 ; i <= m ; i++){
int op , x , y; read(op);
if (op == 1){
read(x);read(y);
modify(x - 1);
modify(y);
}else {
read(x);
int v;
if (x == 1) v = 0;
else v = ask1(1 , 1 , n , x - 1);
int p = ask2(1 , 1 , n , x , v);
if (p == -1) p = n + 1;
int r = ask3(1 , 1 , n , p - 1 , v + 1);
if (r == -1) r = 0;
printf("%d\n" , (r <= x ? 0 : r));
}
}
return 0;
}
10.异或三角
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n;
int f[31][2][2][2][2][2][2];
int a[31],k;
int dfs(int pos,int op1,int op2,int op3,int c1,int c2,int big)
{
if(!pos) {
return big&&c1&&c2;
}
if(~f[pos][op1][op2][op3][c1][c2][big]) {
return f[pos][op1][op2][op3][c1][c2][big];
}
int up1=op1?a[pos]:1;
int up2=op2?a[pos]:1;
int up3=op3?a[pos]:1;
int res=0;
res+=dfs(pos-1,op1&&(!up1),op2&&(!up2),op3&&(!up3),c1,c2,big);
if(up1&&up3)res+=dfs(pos-1,op1,op2&&(up2==0),op3,c1,1,big);
if(up2&&up3)res+=dfs(pos-1,op1&&(up1==0),op2,op3,1,c2,big);
if(c1&&c2) res+=dfs(pos-1,op1,op2,op3&&(!up3),1,1,1);
return f[pos][op1][op2][op3][c1][c2][big]=res;
}
int solve(int x)
{
k=0;
memset(f,-1,sizeof f);
while(x)
{
a[++k]=x%2;x/=2;
}
return dfs(k,1,1,1,0,0,0);
}
signed main()
{
cin>>t;
while(t--){
int n;scanf("%lld",&n);
printf("%lld\n",solve(n)*3);
}
}
2022 蓝桥杯第13届模拟赛第1期
1.10000（含） 到 90000（含） 中，有多少个数是 128 的倍数。
#include <iostream>
#include <cstdio>
using namespace std;
int sum;
int main() {
for (int i = 10000; i <= 90000; i ++ ) {
if (i % 128 == 0) sum ++ ;
}
printf("%d\n", sum);
return 0;
}
2.2021 是一个特殊的年份，它的千位和十位相同，个位比百位多一。请问从 1000（含） 到 9999（含） 有多少个这样的年份？
#include <iostream>
#include <cstdio>
using namespace std;
int sum;
int main() {
for (int i = 1000; i <= 9999; i ++ ) {
int a = i / 1000, b = i % 1000 / 100, c = i % 100 / 10, d = i % 10;
if (a == c && b + 1 == d) sum ++ ;
}
printf("%d\n", sum);
return 0;
}
3.如果1到n 的一个排列中，所有奇数都在原来的位置上，称为一个奇不动排列,1到21的所有排列中，有多少个奇不动排列 11 奇数 10偶数
#include <iostream>
#include <cstdio>
using namespace std;
int sum = 1;
int main() {
for (int i = 1; i <= 10; i ++ ) {
sum *= i;
}
printf("%d\n", sum);
return 0;
}
4.上一个楼梯，共 15 级台阶。
小蓝每步可以上 1 级台阶，也可以上 2 级、3 级或 4 级，再多就没办法一步走到了。
台阶上的数值依次为：1, 2, 1, 1, 1, 1, 5, 5, 4, -1, -1, -2, -3, -1, -91,2,1,1,1,1,5,5,4,−1,−1,−2,−3,−1,−9。
小蓝希望不超过 6 步走到台阶顶端，请问他得分的最大值是多少？
#include <iostream>
#include <cstdio>
using namespace std;
int INF = 1e9;
int a[16] = {0,1,2,1,1,1,1,5,5,4,-1,-1,-2,-3,-1,-9};
int f(int stair, int step) {
if (stair == 15) return a[15];
if (step == 0) return -INF;
int maxscore = -INF;
for (int i = 1; i <= 4; i ++ ) {
if (stair + i <= 15) {
int score = f(stair + i, step - 1) + a[stair];
if (score > maxscore) maxscore = score;
}
}
return maxscore;
}
int main() {
printf("%d\n", f(0, 6));
return 0;
}
5.在数列a[1],a[2],⋯,a[n] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k],则称 a[i], a[j], a[k]为一组递增三元组。
请问对于下面的长度为 20 的数列，有多少个递增三元组？
2,9,17,4,14,10,25,26,11,14,16,17,14,21,16,27,32,20,26,36
#include <iostream>
#include <cstdio>
using namespace std;
int sum;
int a[21] = {0,2,9,17,4,14,10,25,26,11,14,16,17,14,21,16,27,32,20,26,36};
int main() {
int n = 20;
for (int i = 1; i < n + 1; i ++ ) {
for (int j = i + 1; j < n + 1; j ++ ) {
for (int k = j + 1; k < n + 1; k ++ ) {
if (a[i] < a[j] && a[j] < a[k]) sum ++ ;
}
}
}
printf("%d\n", sum);
return 0;
}
6.小蓝开车在高速上行驶了 t 小时，速度固定为每小时 v 千米，请问小蓝在高速上行驶了多长路程
#include <iostream>
#include <cstdio>
using namespace std;
long long t, v;
int main() {
scanf("%lld %lld", &t, &v);
printf("%lld\n", t * v);
return 0;
}
7.现在对这个棋盘进行黑白染色，左上角染成黑色。从左上角开始，每个黑 色格的相邻格染成白色，白色格的相邻格染成黑色。
#include <iostream>
#include <cstdio>
using namespace std;
long long n, m, cnt;
int main() {
scanf("%lld %lld", &n, &m);
cnt = n * m;
if (cnt % 2 == 0) {
printf("%lld\n", cnt / 2);
} else {
printf("%lld\n", cnt / 2 + 1);
}
return 0;
}
8.在路边划分停车位
编号1~L整数块，一个车位要连续k小块，不能停车n小块编号1-n
#include <iostream>
#include <cstdio>
using namespace std;
int l, k, n, a[100010], ans;
int main() {
scanf("%d%d%d", &l, &k, &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
a[0] = 0;
a[n + 1] = l + 1;
for (int i = 1; i <= n + 1; i ++ ) {
ans += (a[i] - a[i - 1] - 1) / k;
}
printf("%d\n", ans);
return 0;
}
9.人字排列 1~n全排列，多少个
一个 1 到 n 的排列被称为人字排列，是指排列中的第 1 到第 (n+1)/2个元素单调递增，第 (n+1)/2到第 n 个元素单调递减。
#include <iostream>
#include <cstdio>
using namespace std;
const int MOD = 1e9 + 7;
int n, c[1001][1001];
int main() {
scanf("%d", &n);
c[1][0] = c[1][1] = 1;
for (int i = 2; i <= n; i ++ ) {
c[i][0] = 1;
for (int j = 1; j <= i; j ++ ) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
printf("%d\n", c[n - 1][(n - 1) / 2]);
return 0;
}
10.输入一个整数，请在整数前面补 0 补足 8 位后输出
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main() {
scanf("%d", &n);
printf("%08d\n", n);
return 0;
}