蓝桥杯2020年第十一届省赛 CC++ 研究生组2.0
约数个数
#include<iostream>
#include<cmath>
using namespace std;
int main(){int n = 78120, ans = 0, sqr = sqrt(n);for(int i = 1; i <= sqr; i++){if(n % i == 0){ans++;//printf("%d,", i);if(i * i != n) {ans++;//printf("%d,", n / i);}}}//printf("\n");printf("%d", ans);//96return 0;
}
打卡题
寻找2020
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int maxn = 10, N = 6;
string s[maxn];
int main(){
// ll ans = 0;
// for(int i = 0; i < N; i++){
// cin >> s[i];
// }
// for(int i = 0; i < N; i++){
// for(int j = 0; j <= N; j++){
// if(s[i][j] == '2' && s[i][j + 1] == '0' && s[i][j + 2] == '2' && s[i][j + 3] == '0') ans++;
// if(s[i][j] == '2' && s[i + 1][j] == '0' && s[i + 2][j] == '2' && s[i + 3][j] == '0') ans++;
// if(s[i][j] == '2' && s[i + 1][j + 1] == '0' && s[i + 2][j + 2] == '2' && s[i + 3][j + 3] == '0') ans++;
// }
// }
// printf("%lld\n", ans);//16525printf("16525");return 0;
}
扣掉送的5分，可恶的菜狗属性啊
超出范围的位置直接不再判断
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int maxn = 310, N = 300;
string s[maxn];
int main(){
// ll ans = 0;
// for(int i = 0; i < N; i++){
// cin >> s[i];
// }
// for(int i = 0; i < N; i++){
// for(int j = 0; j <= N; j++){
// if(j + 3 <= N && s[i][j] == '2' && s[i][j + 1] == '0' && s[i][j + 2] == '2' && s[i][j + 3] == '0') ans++;
// if(i + 3 < N && s[i][j] == '2' && s[i + 1][j] == '0' && s[i + 2][j] == '2' && s[i + 3][j] == '0') ans++;
// if(i + 3 < N && j + 3 <= N && s[i][j] == '2' && s[i + 1][j + 1] == '0' && s[i + 2][j + 2] == '2' && s[i + 3][j + 3] == '0') ans++;
// }
// }
// printf("%lld\n", ans);//16520printf("16520");return 0;
}
平面分割
#include<iostream>
using namespace std;
int main(){int line = 20, q = 20;long long ans = 1 + line * (line + 1) / 2;//手推 while(q--){ans *= 2; }printf("%lld", ans);//221249536return 0;
}
圆的切割方式猜错了……每次加一个圆，至多可以把已有的圆和直线都分为两份。小结版戳这里
#include<iostream>
using namespace std;
int main(){int line = 20, q = 20;long long ans = 1 + line * (line + 1) / 2;//手推 for(int i = 1; i <= q; i++){ans += line * 2 + (i - 1) * 2;}printf("%lld", ans);//1391return 0;
}
蛇形填数
#include<iostream>
using namespace std;
const int N = 50;
int a[N][N];
int main(){int n = 20, d = 1, l = 1, c = 1;a[1][1] = d;
// while(l <= 2 * n && c <= 2 * n){
// a[l][++c] = ++d;//右移
// while(c >= 2){//左下
// a[++l][--c] = ++d;
// }
// a[++l][c] = ++d;//下移
// while(l >= 2){
// a[--l][++c] = ++d;
// }
// }
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++){
// printf("%d\t", a[i][j]);
// }
// printf("\n");
// }
// printf("%d\n", a[2][2]);
// printf("%d\n", a[20][20]);//761printf("761"); return 0;
}
模拟之图形打印
七段码
#include <iostream>
using namespace std;
int main()
{// 请在此输入您的代码cout << 74;return 0;
}
80
差太多，手算还是不行
#include<iostream>
using namespace std;
const int N = 10, M = 7;
int e[N][N] = {0}, f[N], open[N];//e[i][j]表示i和j之间是否连通；f[i]表示结点i的父节点；open[i] 1表示结点i打开，0表示关闭
long long ans = 0;int find(int x){if(f[x] == x) return x;return f[x] = find(f[x]); //压缩路径
}void dfs(int n){if(n == 8){for(int i = 1; i <= M; i++) {f[i] = i;//并查集初始化，每个结点各为一个集合 }for(int i = 1; i <= M; i++){for(int j = 1; j <= M; j++){if(e[i][j] && open[i] && open[j]){//连通则合并 f[find(i)] = find(j);}}} int cnt = 0;//当前方案中的连通块有几个 for(int i = 1; i <= M; i++){if(open[i] && f[i] == i) cnt++;} if(cnt == 1) ans++;//只有一个连通块，则为合法方案 return;}open[n] = 1;//打开二极管ndfs(n + 1);open[n] = 0;//关闭二极管n dfs(n + 1);
}int main(){e[1][2] = e[1][6] = 1;//把二极管视为顶点，是否连通视为之间是否有边 e[2][1] = e[2][3] = e[2][7] = 1;e[3][2] = e[3][7] = e[3][4] = 1;e[4][3] = e[4][5] = 1;e[5][4] = e[5][7] = e[5][6] = 1;e[6][1] = e[6][7] = e[6][5] = 1;e[7][2] = e[7][3] = e[7][6] = e[7][5] = 1;dfs(1); cout << ans;return 0;
}
成绩分析
#include<iostream>
using namespace std;
int main(){int n, max = -1, min = 101, x;double sum = 0;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &x);if(x > max) max = x;if(x < min) min = x;sum += x;}printf("%d\n%d\n%.2f", max, min, sum / n);return 0;
}
打卡题
回文日期
#include<iostream>
using namespace std;
bool isLeap(int y){if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) return true;//闰年29 return false;//平年28
}
bool judge(int n){int d = n % 100, m = n / 100 % 100, y = n / 10000;if(d < 1 || d > 31 || (d > 30 && (m == 4 || m == 6 || m == 9 || m == 11))) return false;if((m == 2 && d > 29 && isLeap(y)) || (m == 2 && d > 28 && !isLeap(y))) return false;if(m > 12 || m < 1) return false;return true;
}
bool sym(int n){int a[8] = {0}, t, num = 0;while(n){t = n % 10;a[num++] = t;n /= 10;}for(int i = 0; i < 4; i++){if(a[i] != a[7 - i]) return false;}return true;
}
bool special(int n){int a[8] = {0}, t, num = 0;while(n){t = n % 10;a[num++] = t;n /= 10;}if(a[0] == a[2] && a[2] == a[5] && a[5] == a[7] && a[1] == a[3] && a[3] == a[4] && a[4] == a[6]) return true;return false;
}
int main(){int t, t1, t2, flag = 1;scanf("%d", &t);t1 = t2 = t + 1;while(!judge(t1) || !sym(t1)) t1++;printf("%d\n", t1);while(!judge(t2) || !special(t2)) t2++;printf("%d", t2);return 0;
}
加了回文判断的日期处理类问题。
- 闰年
- 闰年：二月29天，y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)
- 平年：二月28天
- 大小月
- 1，3，5，7，8，10，12月都是31天
- 2月天数根据平闰判断
- 4，6，9，11月都是30天
- 得出周几 利用基姆拉尔森计算公式
W= (d+2m+3(m+1)/5+y+y/4-y/100+y/400+1)%7
其中，w为周几，0~6对应周日，周一，周二……周六
年y，月m， 日d
1月换为13月，2月换为14月
作物杂交
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2010, N = 1e5 + 10;
int need[maxn], have[maxn] = {0};
int n, m, k, t, x;struct f{int x, y, z;
} fs[N];bool cmp(f f1, f f2){return f1.z <= f2.z;
}ll time(int n){int xt = 0, yt = 0, l = 1, r = k, mid = (l + r) / 2;while(l <= r && fs[mid].z != n){mid = (l + r) / 2;if(fs[mid].z > n) r = mid - 1;else l = mid + 1; }if(have[fs[mid].x] == 0) xt = time(fs[mid].x);if(have[fs[mid].y] == 0) yt = time(fs[mid].y);return max(need[fs[mid].x], need[fs[mid].y]) + max(xt, yt);
}int main(){cin >> n >> m >> k >> t;for(int i = 1; i <= n; i++){cin >> need[i];}while(m--){cin >> x;have[x] = 1;}for(int i = 1; i <= k; i++){cin >> fs[i].x >> fs[i].y >> fs[i].z;}sort(fs + 1, fs + k + 1, cmp);printf("%lld", time(t));return 0;
}
1分都木得骗到
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
typedef pair<int, int> PII;
int w[N], f[N];
bool have[N];vector<PII> fa[N];int dfs(int t)
{for(int i = 0; i < fa[t].size(); i++){int a = fa[t][i].first, b = fa[t][i].second;if(!have[a]) dfs(a);if(!have[b]) dfs(b);if(have[a] && have[b]) {have[t] = true;f[t] = min(f[t], max(w[a], w[b]) + max(f[a], f[b]));}}return f[t];
}
int main()
{int n, m, k, t;cin >> n >> m >> k >> t;memset(f, 0x3f3f, sizeof f);for(int i = 1; i <= n; i++) cin >> w[i];for(int i = 1; i <= m; i++){int temp;cin >> temp;have[temp] = true;f[temp] = 0;}for(int i = 1; i <= k; i++){int a, b, c;cin >> a >> b >> c;fa[c].push_back({a, b}); }cout << dfs(t);return 0;
}
子串分值和
#include<iostream>
#include<string>
using namespace std;
int main(){string s;long long ans = 0;cin >> s;for(int i = 0; i < s.size(); i++){for(int j = i; j < s.size(); j++){int flag[26] = {0};for(int k = i; k <= j; k++){if(flag[s[k] - 'a'] == 0){flag[s[k] - 'a'] = 1;ans++;}}}}cout << ans;return 0;
}
过50%测试点
看出来了要用递推，但是找不出来规律欸
#include<iostream>
#include<string>
using namespace std;
int main(){string s;long long ans = 0, l, flag[25] = {0};//l也要设为long long否则两个测试点不过cin >> s;s = " " + s;l = s.size();for(int i = 1; i < l; i++){ans += (i - flag[s[i] - 'a']) * (l - i);flag[s[i] - 'a'] = i;//该元素最近出现的位置 } cout << ans; return 0;
}