比赛链接：(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