#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("age.in", "r", stdin);
freopen("age.out", "w", stdout);
int x;
cin >> x;
if (x < 15)
cout << 0;
else if (x < 23)
cout << 1;
else
cout << (x - 24) / 4 + 2;
return 0;
}
有很多同学错在了 以及 。我也比较残忍，没注意到这个直接 10 分哈哈哈。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
signed main()
{
freopen("add.in", "r", stdin);
freopen("add.out", "w", stdout);
cin >> a >> b;
// 调整为 a>=b
if (b > a)
swap(a, b);
// 输出每一位
bool zero = true;
for (int i = 1'000'000'000'000'000'000; i; i /= 10)
{
int x = a / i % 10;
int y = b / i % 10;
int z = (x + y) % 10;
if (z != 0)
zero = false;
if (z || !zero) // z>0 || (z==0 && zero==false)
cout << z;
}
if (zero)
cout << 0;
return 0;
}
这题其实是作为教学题出的。首先简单的暴力枚举就不说了。
所有的枚举优化第一个要找的突破口就是限制条件，比较好想到根据回文数这个限制，可以通过枚举左半边，构造右半边的形式，来把枚举规模降低到 。很轻松能写出 60 分的代码.
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool p(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
int gen(int x)
{
int xx = x;
x /= 10;
while (x > 0)
{
xx = xx * 10 + x % 10;
x /= 10;
}
return xx;
}
bool test7(int x)
{
while (x > 0)
{
if (x % 10 == 7)
return true;
x /= 10;
}
return false;
}
int n, cnt;
signed main()
{
cin >> n;
cnt = 0;
for (int i = 1;; i++)
{
int x = gen(i);
if (x > n)
break;
if (!test7(x))
continue;
if (!p(x))
continue;
cnt++;
}
cout << cnt;
return 0;
}
本地跑完会发现极限数据有 多个解，达标的话只记半边 也写不下呀。那满分怎么看都超，怎么办呢？
实际上可以考虑分段达标， 个 的枚举，每 个记一下当前的 就好。
...
int n, cnt;
vector<int> a;
signed main()
{
freopen("a.txt", "w", stdout);
n = 1'000'000'000'000;
cnt = 0;
for (int i = 1;; i++)
{
int x = gen(i);
if (i % 1000 == 1)
cout << cnt << ",";
if (x > n)
break;
if (!test7(x))
continue;
if (!p(x))
continue;
cnt++;
}
return 0;
}
最后满分代码就好写了：
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool p(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
int gen(int x)
{
int xx = x;
x /= 10;
while (x > 0)
{
xx = xx * 10 + x % 10;
x /= 10;
}
return xx;
}
bool test7(int x)
{
while (x > 0)
{
if (x % 10 == 7)
return true;
x /= 10;
}
return false;
}
int n, cnt;
int half1000[] = {0, 45, 89, 89, 138, 138, 138, 138, 293, 293, 344, 390, 427, 466, 508, 542, 580, 614, 755, 790, 829, 829, 829, 829, 829, 829, 829, 829, 829, 829, 829, 859, 902, 938, 981, 1018, 1051, 1087, 1209, 1235, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1265, 1392, 1523, 1663, 1781, 1915, 2045, 2154, 2264, 2379, 2508, 2508, 2508, 2508, 2508, 2508, 2508, 2508, 2508, 2508, 2508, 2549, 2589, 2618, 2650, 2684, 2719, 2756, 2883, 2920, 2955, 2995, 3036, 3063, 3095, 3130, 3163, 3194, 3306, 3343, 3375, 3411, 3439, 3469, 3501, 3540, 3570, 3597, 3701, 3738, 3771, 3802, 3825, 3848, 3883, 3923, 3958, 3985, 4095, 4119, 4155, 4194, 4219, 4250, 4282, 4308, 4336, 4363, 4470, 4499, 4528, 4559, 4594, 4626, 4663, 4694, 4728, 4751, 4845, 4879, 4905, 4925, 4956, 4983, 5005, 5039, 5069, 5094, 5203, 5228, 5258, 5292, 5327, 5356, 5388, 5415, 5447, 5474, 5591, 5615, 5639, 5750, 5861, 5972, 6099, 6218, 6316, 6420, 6528, 6630, 6746, 6777, 6808, 6835, 6858, 6879, 6917, 6951, 7061, 7089, 7121, 7149, 7174, 7202, 7233, 7265, 7287, 7312, 7428, 7458, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7481, 7516, 7535, 7569, 7605, 7628, 7665, 7695, 7803, 7833, 7866, 7897, 7930, 7952, 7981, 8004, 8037, 8060, 8161, 8193, 8229, 8258, 8286, 8319, 8349, 8375, 8408, 8435, 8531, 8562, 8585, 8611, 8636, 8666, 8694, 8718, 8751, 8784, 8890, 8922, 8942, 8978, 9013, 9044, 9070, 9095, 9127, 9153, 9257, 9283, 9314, 9348, 9381, 9410, 9440, 9465, 9500, 9527, 9621, 9651, 9679, 9704, 9739, 9766, 9790, 9828, 9860, 9893, 9987, 10014, 10047, 10160, 10291, 10405, 10509, 10613, 10710, 10807, 10906, 11011, 11115, 11147, 11180, 11207, 11232, 11263, 11286, 11306, 11409, 11438, 11466, 11499, 11530, 11555, 11590, 11622, 11646, 11674, 11773, 11803, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11826, 11922, 12018, 12129, 12228, 12344, 12449, 12548, 12656, 12753, 12862, 12951, 13059, 13165, 13280, 13387, 13511, 13607, 13705, 13812, 13925, 14030, 14148, 14271, 14376, 14487, 14591, 14701, 14795, 14894, 14992, 15088, 15207, 15315, 15400, 15504, 15604, 15691, 15798, 15911, 16017, 16103, 16205, 16305, 16395, 16506, 16622, 16719, 16819, 16915, 17010, 17124, 17230, 17335, 17442, 17545, 17640, 17745, 17844, 17948, 18030, 18142, 18250, 18360, 18466, 18574, 18675, 18775, 18892, 18987, 19095, 19203, 19318, 19417, 19533, 19624, 19731, 19831, 19925, 20023, 20120, 20225, 20336, 20446, 20553, 20656, 20764, 20870, 20964, 21057, 21156, 21259, 21389, 21510, 21613, 21728, 21820, 21908, 22025, 22116, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22225, 22255, 22292, 22313, 22339, 22375, 22402, 22436, 22535, 22561, 22594, 22624, 22654, 22682, 22711, 22734, 22767, 22797, 22893, 22930, 22957, 22983, 23009, 23037, 23071, 23099, 23124, 23154, 23272, 23298, 23324, 23338, 23368, 23392, 23421, 23444, 23478, 23498, 23604, 23632, 23660, 23681, 23704, 23734, 23768, 23800, 23826, 23858, 23945, 23978, 24006, 24030, 24058, 24094, 24124, 24150, 24185, 24213, 24322, 24355, 24379, 24408, 24438, 24467, 24487, 24516, 24545, 24570, 24665, 24688, 24709, 24819, 24935, 25032, 25144, 25254, 25353, 25458, 25559, 25650, 25727, 25751, 25785, 25813, 25837, 25862, 25895, 25916, 26024, 26048, 26075, 26106, 26142, 26169, 26196, 26222, 26254, 26285, 26383, 26409};
signed main()
{
freopen("seven.in", "r", stdin);
freopen("seven.out", "w", stdout);
cin >> n;
int l = 0;
int r = 999;
int st = 0;
while (l <= r)
{
int mid = (l + r) / 2;
int x = gen(mid * 1000);
if (x <= n)
{
st = mid * 1000;
cnt = half1000[mid];
l = mid + 1;
}
else
r = mid - 1;
}
for (int i = st;; i++)
{
int x = gen(i);
if (x > n)
break;
if (!test7(x))
continue;
if (!p(x))
continue;
cnt++;
}
cout << cnt;
return 0;
}
前两个子任务就不说了，有些同学没注意到第二个子任务有四种情况。
满分做法首先要能看出来先二分答案，把构造转换成检验。然后怎么检查 秒能不能踏遍呢？
显然最左边的人需要负责把左边的踏满，那有两种方案，先左再右还是先右再左。显然哪种能覆盖更多就选哪种即可。后面每个人依次看看怎么在上一次的基础上能多覆盖就好。
（这题最高 10 分数据可能会有问题，但是 OI 赛制题面没问题就还好，回头如果发现了数据问题重测一下就好了。）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000000 + 5];
bool check(int x)
{
// 从前往后
int last = -1;
for (int i = 1; i <= m; i++)
{
int now = a[i];
// 要回头
if (now >= last + 2)
{
// 能不能接上，last 和 now 中间有 now - last - 1 个数
if (now - last - 1 > x)
return false;
// 可以先左再右，也可以先右再左
int max1 = now + max(0LL, x - (now - last - 1) * 2);
int max2 = now + max(0LL, (x - (now - last - 1)) / 2);
last = max(max1, max2);
}
// 继续往前
else if (now <= last + 2)
last = max(last, now + x);
}
return last >= n;
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> a[i];
sort(a + 1, a + m + 1);
int l = 0;
int r = n * 2;
int ans;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans;
return 0;
}