比赛链接:(8条未读通知) 牛客小白月赛51_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
快要期末考试了,就不搞头脑风暴了,来写几道简单题保持一下手感哈,暑假还要集训。
A.选择题
一个奇数加一个偶数,一定是一个奇数,所以如果N是奇数,那么答案就是N-2,如果N是偶数,答案就是N-1。
总之就是,答案是小于N的最大奇数。
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int N;scanf("%lld", &N); printf("%lld\n", (N & 1) ? N - 2 : N - 1); return 0; }
B.填空题
其实是个简单构造+贪心,要使得和最小且数组严格单增,那么每个空a[i] = a[i - 1] + 1,最后如果出现了单调不增的部分,说明不存在解。
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9; int a[maxn]; signed main() { int N;scanf("%lld", &N); for(int i = 1;i <= N; ++ i)scanf("%lld", a + i); int ans = 0; for(int i = 1;i <= N; ++ i) { if(a[i] == 0)a[i] = a[i - 1] + 1; if(a[i] > a[i - 1])ans += a[i]; else { ans = -1; break; } } printf("%lld\n", ans); return 0; }
C.零一题
将最终串分两种情况讨论,一种是01依次排列,一种是10依次排列。
只有当按照10 / 01 排列后剩下的0和1都是非负偶数才可能构造出答案。
答案的构造就很简单了,连续的0,连续的1和01 / 10的排列即可。
注意要判断a-c0>=0&&b-c1>=0,因为负数也可能是偶数。当然你一开始就特判x > a + b也可以。
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; void solve(int a,int b,int x) { //方法1: 01依次排列作为最终结果 { int c0 = x / 2, c1 = x / 2; if(x & 1)c0 ++; if(a - c0 >= 0 && b - c1 >= 0 && (a - c0) % 2 == 0 && (b - c1) % 2 == 0) { for(int i = 1;i <= a - c0; ++ i)printf("0"); for(int i = 1;i <= b - c1; ++ i)printf("1"); for(int i = 1;i <= x; ++ i)printf("%lld", (i & 1) ? 0 : 1); return; } } //方法2: 10依次排列作为最终结果 { int c0 = x / 2, c1 = x / 2; if(x & 1)c1 ++; if(a - c0 >= 0 && b - c1 >= 0 && (a - c0) % 2 == 0 && (b - c1) % 2 == 0) { for(int i = 1;i <= a - c0; ++ i)printf("0"); for(int i = 1;i <= b - c1; ++ i)printf("1"); for(int i = 1;i <= x; ++ i)printf("%lld", (i & 1) ? 1 : 0); return; } } return printf("-1\n"), void(); } signed main() { int a, b, x;cin >> a >> b >> x; solve(a, b, x); return 0; }
D.操作题
本来直观想这题可能是dfs,看一眼数据范围,太大了。
有个小技巧,做题往往从数据小的变量入手,这里的x比较小,然后看见0和1,乘x,不难想到将n用x进制表示,那么就可以用接近logN的步数从0变化到n。
方法就是将n用x进制表示存入一个数组,然后从后往前遍历数组,因为我们的数组中存放是从低位到高位的,而构造数字n要从高位往低位构造。
比如10的3进制是1010,在数组a中存放的是0101,那么我们构造时应该先遍历到1,发现要加1,就给a加上b,然后再乘x,遍历到0,不动,乘x,再到1,加上1次b 乘x......
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 30; int a[100]; void solve() { int n, x;scanf("%lld %lld", &n, &x); int k = 0, ans = 0; while(n)a[++ k] = n % x, n /= x, ans += a[k] + 1; printf("%lld\n",ans); for(int i = k;i >= 1; -- i) { printf("2 a\n"); for(int j = 1;j <= a[i]; ++ j)printf("1 a\n"); } } signed main() { int _;scanf("%lld", &_); while(_ --)solve(); return 0; }
E.语法题
这题说实话有点小骚。
这么多条件语句中,至多执行一句,有可能一个条件都不符合就不执行。不执行也就是说n还是原来的n没变,那么方案数就是1,这个需要特判(n > max_num)。
我们将最初的n记作k。
假如程序可以执行到第i条判断语句,那么也就是说k要大于等于语句1 ~ i - 1的 a 的最大值。同时为了执行第i条,k应该要小于a[i]。
所以有了对于第i条语句有了第一个限制条件max_num <= k < a[i]。
接下来看n = k / b[i]向下取整,也就是说k >= n * b[i],与此同时k < (n + 1) * b[i],这样才能保证k / b[i]向下取整是n。
所以将两个限制条件取交集,得到的就是max(max_num, n * b[i]) <= k <= min(a[i] - 1, (n + 1) * b[i] - 1)。
稍加考虑就可以知道,这么多的线段是不会相交的。因为max_num >= a[i - 1] > a[i - 1] - 1。
(线段i-1)的终点一定比(线段i)的起点小。
将线段长度加起来就是答案。
代码 / Code
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int inf = 8e18, maxn = 1e5 + 9; int a[maxn], b[maxn]; signed main() { int x, n;scanf("%lld", &x); int max_num = 1, ans = 0; for(int i = 1;i <= x; ++ i)scanf("%lld %lld", a + i, b + i); scanf("%lld", &n); for(int i = 1;i <= x; ++ i) { int k = n * b[i]; int l = max(k, max_num); int r = min(k + b[i], a[i]); if(r > l)ans += r - l; max_num = max(max_num, a[i]); } printf("%lld\n", n >= max_num ? 1 : ans); return 0; }
Comments NOTHING