<>我以为省赛考了这种内存的题目国赛就不会考了,所以省赛时不会,现在还是不会,好多人答案都是25。

<>先用欧拉筛晒出质数,然后暴力一个数一个数地判断就好了,注意0和1不是质数(开始我就忘了,不过还好后面检查出来了),答案应该是 1903 1903 190
3。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N
= 20210605 + 5, mod = 1e9 + 7; int n = 20210605, p[N], cnt, res; bool vis[N];
void get() { vis[0] = vis[1] = 1; //vis[i] = 1表示被筛掉了 for(int i = 2; i <= n; i++)
{ if(!vis[i]) p[cnt++] = i; for(int j = 0; p[j] <= n / i; j++) { vis[p[j] * i] =
1; if(i % p[j] == 0) break; } } } bool check(int x) { while(x) { int y = x % 10;
x/= 10; if(vis[y]) return false; } return true; } int main() { get(); for(int i
= 0; i < cnt; i++) { int x = p[i]; if(check(x)) res++; } cout << res; return 0;
}

<>先用一个 d a y day day数组打表出来每个月的天数,然后特判一下闰年的2月份,再写一个时间自增的函数就行了,答案应该是 977 977 977

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N
= 1e5 + 5, mod = 1e9 + 7; struct Time { int y, m, d; }; int res, day[] = {0, 31,
28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; void add(Time &a) { a.d++; int x =
day[a.m]; if(((a.y % 4 == 0 && a.y % 100 != 0) || a.y % 400 == 0) && a.m == 2) x
++; //特判闰年的2月份 if(a.d > x) a.m++, a.d = 1; if(a.m > 12) a.y++, a.m = 1; } bool
check(Time a) { int s[] = {a.y, a.m, a.d}, y = 0; for(int i = 0; i < 3; i++) {
int x = s[i]; while(x) { y += x % 10; x /= 10; } } int z = sqrt(y); return z * z
== y; } int main() { Time a = {2001, 1, 1}, b = {2021, 12, 31}; while(a.y != b.y
|| a.m != b.m || a.d != b.d) { if(check(a)) res++; add(a); } cout << res; return
0; }

<>这题我也不会,据说要用 d p dp dp来做,大概估计了一下可能会是一颗完全二叉树,最后答案我也忘了,挺大的一个数。

<>~~ 签到题就不多说了~~
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N
= 1e5 + 5, mod = 1e9 + 7; int main() { string s; cin >> s; for(auto &x : s) if(x
>= 'a' && x <= 'z') x = x - 'a' + 'A'; cout << s; return 0; }

<>先设第 i i i个块为从 1 1 1到 i i i这一串数,以便下面描述,我们先预处理出来每个块的左端点和右端点是排列后的第几个数,再用一个 s u
m sumsum数组记录前 i i i个块的总和,然后对于每组询问用 l o w e r b o u n d lowerbound lowerbound函数求出
l ll和 r r r所在的块(分别记作 i d 1 id1 id1和 i d 2 id2 id2),然后求出 l l l和 r r r在块中的位置(分别记作
i d l idlidl和 i d r idr idr),如果在同一个块先就直接可以得到 ( i d r − i d l + 1 ) ∗ ( i d l +
i d r ) / 2 (idr-idl+1)*(idl+idr)/2(idr−idl+1)∗(idl+idr)/2
,不在的话就先求出l到它所在块的右端点的总和以及r到它所在块左端点的总和,最后两个块之间的总和就是 s u m [ i d 2 − 1 ] − s u m [
i d 1 ] sum[id2-1]-sum[id1]sum[id2−1]−sum[id1],答案就是这三部分相加。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int
maxn= 1414214, N = maxn + 5, mod = 1e9 + 7; ll l[N], r[N], sum[N], T; int main()
{ cin >> T; for(ll i = 1; i <= maxn; i++) { l[i] = r[i - 1] + 1; r[i] = l[i] + i
- 1; sum[i] = sum[i - 1] + (1 + i) * i / 2; } while(T--) { ll L, R, res; cin >>
L>> R; ll id1 = lower_bound(r, r + maxn, L) - r; ll id2 = lower_bound(r, r +
maxn, R) - r; if(id1 == id2) res = (R - L + 1) * (R - l[id1] + L - l[id1] + 2) /
2; else { ll sum1 = sum[id2 - 1] - sum[id1]; ll idl = L - l[id1] + 1, idr = R -
l[id2] + 1; //求出L和R在块中的位置 ll suml = (id1 - idl + 1) * (id1 + idl) / 2; ll sumr =
(1 + idr) * idr / 2; //cout << sum1 << ' ' << suml << ' ' << sumr << endl; res =
sum1+ suml + sumr; } cout << res << endl; } return 0; }

<>
我根据异或的运算法则大概找了一下规律,第1位的循环节是1,第2位是2,第3,4位是4,第5,6,7,8位是8(我只推到了第5位,大胆猜测了一下,每一位的循环节应该是大于等于它位数的最小的2的次幂),所以我先预处理每一位的循环节,用
b bb数组来存,然后我开了一个二维 b o o l bool bool数(开成 b o o l bool bool类型是为了节省空间)记录第 i i i
位的循环 j j j次的结果, n n n最大为10000,所以开成 a n s [ 10005 ] [ 16400 ] ans[10005][16400] a
ns[10005][16400]这么大就行了,最后通过递推推出 a n s [ i ] [ j ] = a n s [ i − 1 ] [ ( j − 1 )
% b [ i − 1 ] ] ans[i][j]=ans[i-1][(j-1)\%b[i-1]]ans[i][j]=ans[i−1][(j−1)%b[i−1]
] ⨁ \bigoplus ⨁ a n s [ i ] [ j − 1 ] ans[i][j-1] ans[i][j−1]。时间复杂度大概是 O ( n 2
) O(n^2)O(n2)。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N
= 1e4 + 5, M = 16400, mod = 1e9 + 7; char s[N]; int n, b[N]; ll t; bool a[N],
ans[N][M]; int f(int x) { int l = 0, r = 14; while(l < r) { int mid = l + r >> 1
, y = 1 << mid; if(y >= x) r = mid; else l = mid + 1; } return 1 << l; } int
main() { cin >> n >> t >> (s + 1); for(int i = 1; i <= n; i++) { a[i] = s[i] -
'0'; b[i] = f(i); ans[i][0] = a[i]; } for(int i = 2; i <= n; i++) for(int j = 1;
j< b[i]; j++) ans[i][j] = ans[i - 1][(j - 1) % b[i - 1]] ^ ans[i][j - 1]; for(
int i = 1; i <= n; i++) cout << ans[i][t % b[i]]; return 0; }

<>数位 d p dp dp板子题,先预处理出组合数,然后求出 N N N的二进制数,如果从左往右第 i i i位为 1 1 1,我们先把它置为 0 0 0
,然后记录一下它前面有多少个 1 1 1(用 l a s t last last表示),对于其后面的 n − i − 1 n-i-1 n−i−1
位可以直接用组合数得到 C [ n − i − 1 ] [ K − l a s t ] C[n-i-1][K-last] C[n−i−1][K−last]
,如果它 l a s t last last已经大于 K K K了就直接 b r e a k break break,最后特判一下 N N N自己是否满足有
K KK个 1 1 1就行了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N
= 60 + 5; ll c[N][N], k; string f(ll x) //把x转化为二进制 { string s; while(x) { char y
= x % 2 + '0'; x /= 2; s = y + s; } return s; } ll get(ll x) { string s = f(x);
int n = s.size(), last = 0, flag = 1; ll res = 0; for(int i = 0; i < n; i++) {
if(s[i] == '1') { res += c[n - i - 1][k - last]; last++; if(last > k) { flag = 0
; break; } } } return res + flag; } int main() { for(int i = 0; i < N; i++) for(
int j = 0; j <= i; j++) { if(j) c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; else c[
i][j] = 1; } ll n; cin >> n >> k; cout << get(n); return 0; }
<>最后两题都不会,都是打的暴力来骗分

技术
©2019-2020 Toolsou All rights reserved,
程序员的520,送给女友的几行漂亮的代码(python版)基于stm32控制四轮小车电机驱动(一)linux查看磁盘空间命令实验四 自动化测试工具-软件测试axios拦截器封装与使用C语言——qsort函数opencv-python傅里叶变换以及逆变换在算法研究过程中如何进行算法创新nc的安装和简单操作C语言做一个简易的登陆验证(功能)界面