企业官网建设流程全解析

A题：

唐克老师最近学习了一种有趣的题型——《构造题》，这种题目是根据题意去构造一组符合规则的输出，有的是序列，有的是数据结构，有的是图和树

今天唐克老师做了一道基础的题目，这道题的要求如下：
（以下提到的 i,j 满足均 i < j）
1. 构造一个尽可能长的数组 ai，在数组中不能有数字重复出现，并且要保证数组元素是升序的，即 ai < aj
2. 当数组的元素个数 ≥ 2 时，对于任意一组 i,j 满足 aj % ai = 0
3. 对于任意元素 ai 满足 L ≤ ai ≤ R

现在唐克老师已经完成了这道题，但是他不知道他的结果是否正确，所以他希望你帮他计算一下两个问题：1. 最长数组的长度应该是多少，2. 有多少种符合长度最长的数组构造方案？

观察题目：长度最优考虑a,2*a,4*a,8*a，据此可算出最长长度，对于所有方案的枚举，假设当前是第i个数，如果这个数字b满足b<<(cnt-i)<=r,cnt是最大长度，即满足，于是对于每种情况做最小枚举即可，代码如下：

#include <bits/stdc++.h> using namespace std; int ans = 0; void search(int x, int l, int r, int cnt) { if (cnt == 0) { ans++; return; } for (int i = 2 * x; (i << (cnt - 1)) <= r; i += x) { search(i, l, r, cnt - 1); } }//递推 int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int l, r; cin >> l >> r; int o = r, cnt = 0; for (; o >= l; o >>= 1) cnt++; for (int i = l; (i << (cnt - 1)) <= r; i++) { search(i, l, r, cnt - 1); } cout << cnt << " " << ans << "\n"; ans = 0; } }

！！A有更妙的解法，对于因子大于2的，只能是3，所有大于4的都>=2*2，本来可以拆成两个，如果有4，只能说明长度算错了，而且只能一个3，3*3>=2*2*2，可以拆成多个，下面给出O1做法：

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--) { long long l,r; cin>>l>>r; long long cnt=0; long long x=l; while(x<=r)cnt++,x<<=1; long long A=r/(1<<(cnt-1))-l+1;//都是2 if(A<0)A=0;//cnt-1代表起始的可以很小，长度是cnt迭代了cnt-1次 long long B=0; if(cnt>=2) { long long dm=3*(1<<(cnt-2));//一个3 B=r/dm-l+1; } if(B<0)B=0; long long ans=A+B*(cnt-1); cout<<cnt<<" "<<ans<<"\n"; } }

B

众所周知，唐克老师热衷于给班级的同学们排座位，希望以此来促进同学们的学习
这天唐克老师又有了一个新的座位思路——让成绩好的同学和成绩差的同学交叉着坐
是不是就可以让成绩差的同学更好的向成绩好的同学学习，让成绩好的同学更好的帮助成绩差的同学呢？
现在唐克老师已经把前 n 位同学的座位排好了，但是他发现好像座位排的有点问题
于是唐克老师决定重新设定要求，他认为只要对于第 i 位同学来说，要么他左右两侧的同学成绩都比他好，要么左右两侧的同学成绩都比他差，那么就满足唐克老师的要求
当然，这里头尾两位同学不需要满足上述条件
现在唐克老师想知道，如果他有足够多任意成绩的同学，最少需要替换这 n 个同学中的几个人，可以使得这个座位满足唐克老师的要求？

显然，分两种情况，第一个为好学生和差学生即可，注意我们计算答案要考虑数值更替，也就是如果i是差生cnt[i],代表i之前处理好的次数，如果i+1比i差，可以把i+1变成1e9,对于i+1更有利(因为差生优生一定交替)，这是思考过程，体现在代码上可以直接跳到i+2,但是题目数据给的1-1e9，对于多个1和多个1e9需要特判，代码如下：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); int _0 = 0, _1 = 0; for (int i = 0; i < n; i++) cin >> a[i]; vector<int> num_0(a), num_1(a); for (int i = 0; i < n; i++) { if (i % 2 == 0) { // 弱 if (i + 1 < n && num_0[i + 1] <= num_0[i]) { if (num_0[i + 1] != 1e9&&num_0[i]!=1e9) num_0[i + 1] = 1e9; _0++; } } else { // 强 if (i + 1 < n && num_0[i + 1] >= num_0[i]) { if (num_0[i + 1] != 1&&num_0[i+1]!=1) num_0[i + 1] = 1; _0++; } } } for (int i = 0; i < n; i++) { if (i % 2 == 0) // qiang { if (i + 1 < n && num_1[i + 1] >= num_1[i]) { if (num_1[i + 1] != 1&&num_1[i+1]!=1) num_1[i + 1] = 1; _1++; } } else { if (i + 1 < n && num_1[i + 1] <= num_1[i]) { if (num_1[i + 1] != 1e9&&num_1[i+1]!=1e9) num_1[i + 1] = 1e9; _1++; } } } cout << min(_0, _1) << "\n"; }

C

最近又开始流行串姓名手串了，店家会把刻有单个字或者字母的小珠子摆在篮子里，然后大家可以找自己的名字或者自己想要的珠子，最后把珠子串起来组成一条手串
而唐克老师今天心血来潮，决定也来玩一玩，但是由于中文珠子不好找，于是他决定使用 xls 三个字母
现在唐克老师一共从篮子里找出 n 颗刻有 x,l,s 三个字母之一的珠子，并且摆成了一排
现在唐克老师准备从中拿出一些珠子组成他的名字—— xls，但是由于珠子比较多，所以唐克老师懒得将它们重新排序了，他只会用从排列顺序依次为 x,l,s 的三颗珠子来组成一个手串
形式化的，我们可以理解为，能够组成手串的三颗珠子编号为 i,j,k，那么必须要满足 i < j < k，并且 ai ='x', aj = 'l', ak='s'
例如 xxllssslx，唐克老师可以取出 1,3,5 这三颗珠子组成一串手串，用 2,4,6 这三颗珠子组成另一串手串，而剩下 7,8,9 三个珠子为 slx 没办法组成一个手串

计数即可，不过多赘述

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin>>s; int x=0,l=0,s_=0; int xl=0; int ans=0; for(int i=0;i<s.size();i++) { if(s[i]=='x')x++; else if(s[i]=='l') { if(x>0) { l--,x--; xl++; } } else { if(xl>0) { xl--; ans++; } } } cout<<ans<<"\n"; }

D

唐克老师认为每个数字都拥有或多或少的力量，而一个数字拥有的力量多少取决于它每一位的数字和
例如 123 拥有的力量就是 1+2+3=6
现在唐克老师想知道，如果给定一个区间 [l,r]， 在这个区间内，力量值最大的数是多少，它的力量值是几？

l与r的差值小于等于1e5，枚举即可，复杂度<=1e6

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long l,r; cin>>l>>r; long long max_=0,max_num; for(long long i=r;i>=l;i--) { long long now=0,cur=i; while(cur)now+=cur%10,cur/=10; if(now>max_)max_=now,max_num=i; } cout<<max_num<<"\n"<<max_<<"\n"; }

问题 I：Diff-prime Pairs

题目描述
Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem. diff-prime pairs problem is that given N, you need to find the number of pairs (i, j), where and are both prime and i ,j ≤ N. gcd(i, j) is the greatest common divisor of i and j. Prime is an integer greater than 1 and has only 2 positive divisors.
Eddy tried to solve it with inclusion-exclusion method but failed. Please help Eddy to solve this problem.
Note that pair (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.

总的来说题干是要求除以最大公因数后为两个质数的数对，及求符合要求的合数成对排列数

那么我们可以转化为先求质数，然后找某个因子下质数的数量，计算方案=cnt*(cnt-1)/2相加即可，对于n=1e7埃氏筛即可，在有序的质数数组中进行二分查找(双指针也可以，并且肯定不会TIE)

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); vector<int> a(1e7 + 1); a[0] = a[1] = 1; for (int i = 2; i * i <= 1e7; i++) { for (int j = i * i; j <= 1e7; j += i) { a[j] = 1; } } vector<long long> prime; int n; cin >> n; for (int i = 2; i <= n; i++) if (!a[i]) prime.push_back(i); long long ans = 0; for (long long i = 1; i <= n / 3; i++) { long long cnt = 0; long long left = 0, right = prime.size() - 1; if (i == 1) { cnt = right + 1; ans += (cnt - 1) * cnt; continue; } while (left < right) { long long mid = left + (right - left + 1) / 2; if (prime[mid] * i <= n) left = mid; else right = mid - 1; } cnt = left + 1; ans += (cnt - 1) * cnt; } cout << ans << "\n"; }