90. 64位整数乘法

求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。
输出格式
输出一个整数，表示ab mod p的值。
*数据范围
1≤a,b,p≤10^18
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. typedef unsigned long long ULL;
  8. int main()
  9. {
  10.     ULL a,b,p,res=0;
  11.     cin >> a >> b >> p;
  12.     while(b){
  13.         if(b&1){
  14.             res = (res + a)%p;
  15.         }
  16.         b>>=1;
  17.         a = (a*2)%p;
  18.     }
  19.     cout << res;
  21. }

100. 增减序列

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数 n。
接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
image.png

  1. /*
  2. b1 = a1;
  3. b2 = a2-a1
  4. b3 = a3-a2
  5. ....
  6. bn = bn - bn-1
  7. 首先要所有数都相等，那么就等同于b2....bn都等于0,那么序列最终变成的数就是b1,求b1的方案数就可以了
  8. 如果要对a在[L,R]区间上进行+1
  9.     等价于b_L+1, b_(R+1)-1
  10. 因此分成以下：
  11.     - 在a数组的[2,n-1]区间上进行操作，对应的就是b数组在[2,n]上进行操作
  12.     - 在a数组的[1,n-1]区间上进行操作，对应的就是b数组在[1,n]上进行操作,此时会改变b1的值
  13.     - 在a数组的[2,n]区间上进行操作，对应的就是b数组在[2,n+1]上进行操作,此时会改变bn+1的值
  14.     - 在a数组的[1,n]区间上进行操作,a数组整体+1或-1,不可能实现最终每个数都相等的
  15. */
  16. #include <iostream>
  17. #include <cstring>
  18. #include <algorithm>
  19. typedef long long LL;
  20. using namespace std;
  21. const int N = 1e5+10;
  22. int a[N],b[N];
  23. int main()
  24. {
  25.     int n;
  26.     cin >> n;
  27.     for (int i = 1; i <= n; i ++ ){
  28.         cin >> a[i];
  29.     }
  30.     for (int i = n; i ; i -- ){
  31.         b[i] = a[i]-a[i-1];
  32.     }
  33.     LL p=0,q=0;
  34.     for (int i = 2; i <= n; i ++ ){
  35.         if(b[i]>0){
  36.             p+=b[i];
  37.         }else{
  38.             q-=b[i];
  39.         }
  40.     }
  41.     cout << max(p,q)<<endl;
  42.     cout << abs(p-q)+1<<endl;
  43. }

102. 最佳牛围栏

农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛，其数量不会少于 1 头，也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F，数据间用空格隔开。
接下来 N 行，每行输入一个整数，第 i+1 行输入的整数代表第 i 片区域内包含的牛的数目。
输出格式
输出一个整数，表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 1e5+10;
  6. int n,f;
  7. double a[N],s[N];
  8. bool check(double mid){
  9.     for (int i = 1; i <= n; i ++ ){
  10.         s[i] = s[i-1]+a[i]-mid;
  11.     }
  12.     double minv = 0;
  13.     for (int i = f; i <= n; i ++ ){
  14.         minv = min(minv,s[i-f]);
  15.         if(s[i]>=minv){
  16.             return true;
  17.         }
  18.     }
  19.     return false;
  20. }
  22. int main()
  23. {
  24.     cin >> n >> f;
  25.     double l = 0,r=0;
  26.     for (int i = 1; i <= n; i ++ ){
  27.         cin >> a[i];
  28.         r = max(a[i],r);
  29.     }
  30.     while(r-l>1e-6){
  31.         double mid = (l+r)/2;
  32.         if(check(mid)){
  33.             l = mid;
  34.         }else{
  35.             r = mid;
  36.         }
  37.     }
  38.     printf("%d",(int)(r*1000));
  39. }

113. 特殊排序

有 N 个元素，编号 1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是 N 个点与 N×(N−1)2 条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 10000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这 N 个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。
例如，编号为 a 和 b 的两个元素，如果元素 a 小于元素 b，则 compare(a,b) 返回 true，否则返回 false。
将 N 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。
输入样例
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]
输出样例
[3, 1, 2]

  1. /*
  2. 下面这种写法举例
  3. 在右边插入的情况
  4.  a1        a2        a3
  5.  l        mid        r
  6.  --以上情况要插入一个a4,
  7.  --开始比较
  8.      - if res[mid]<a4 l = mid+1, 此时l=r,并没有跳出循环，继续比较
  9.  -------------------------------------------
  10.  a1        a2        a3
  11.              l,r,mid
  12. -- if res[mid] < a4 l=mid+1, 此时l=r+1,跳出循环, 而r+1 这个位置正好是a4可以插入的位置
  13.     所以就将其插入到r+1的位置上去
  14. -- if res[mid] > a4 r=mid-1 
  16. 在左边插入的情况
  17.  a1        a2        a3
  18.  l        mid        r
  19.  --以上情况要插入一个a4,
  20.  --开始比较
  21.      - if res[mid]>a4 r = mid-1, 此时r=l,并没有跳出循环，继续比较
  22.  -------------------------------------------
  23.  a1        a2        a3
  24.  l,r,mid
  25. -- if res[mid] > a4 =mid-1, 此时r=l-1,跳出循环, 而r+1 这个位置正好是a4可以插入的位置
  26.     所以就将其插入到r+1的位置上去
  27. */
  29. /*
  30. 其实可以举一个最简单的例子
  31. 比如现在res种只有一个数
  32. a1
  33. l,r
  34. 1. 如果判断条件写成了l<r,那么新加入的数a2就不会参与比较，所以必须写成l<=r
  35. 2. 最后的退出判断条件一定是l>r,也就是l比r大1
  36. 3. 最终插入的位置一定是在a1之前，或者a1之后 ，也就是要么是0位置，要么是1位置
  37. 4. 如果a1 < a2 那么就应该插在1位置  如果a1 > a2就应该插在0位置
  38. */
  39. class Solution {
  40. public:
  41.     vector<int> specialSort(int N) {
  42.         vector<int> res;
  43.         res.push_back(1);
  44.         for(int i = 2;i <= N;i++){
  45.             int l = 0,r = res.size() - 1;
  46.             while(l <= r){
  47.                 int mid = l + r >> 1;
  48.                 if(compare(res[mid],i)) l = mid + 1;
  49.                 else    r = mid - 1;
  50.             }
  51.             res.push_back(i);
  52.             for(int j = res.size() - 2;j > r;j--)   swap(res[j],res[j + 1]);
  53.         }
  54.         return res;
  55.     }
  56. };

122. 糖果传递

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n，表示小朋友的个数。
接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数，表示最小代价。
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. typedef long long LL;
  5. using namespace std;
  6. const int N = 1e6+10;
  7. LL s[N],c[N];
  8. LL a[N];
  9. int main()
  10. {
  11.     int n;
  12.     cin >> n ;
  13.     for (int i = 1; i <= n; i ++ ){
  14.         cin >> s[i];
  15.         s[i]+=s[i-1];
  16.     }
  17.     LL b = s[n]/n;
  18.     for (int i = 1; i < n; i ++ ){
  19.         c[i] = i*b-s[i];
  20.     }
  21.     sort(c+1,c+n+1);
  22.     LL res=0;
  23.     for (int i = 1; i <= n; i ++ ){
  24.         res+=abs(c[i]-c[n/2+1]);
  25.     }
  26.     cout <<res; 
  27. }

105. 七夕祭

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是 TYVJ 今年举办了一次线下七夕祭。
Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。
TYVJ 七夕祭和 11 区的夏祭的形式很像。
矩形的祭典会场由 N 排 M 列共计 N×M 个摊点组成。
虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。
不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。
由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在 Vani 想知道他的两个要求最多能满足多少个。
在此前提下，至少需要交换多少次摊点。
输入格式
第一行包含三个整数 N 和 M 和 T，T 表示 cl 对多少个摊点感兴趣。
接下来 T 行，每行两个整数 x,y，表示 cl 对处在第 x 行第 y 列的摊点感兴趣。
输出格式
首先输出一个字符串。
如果能满足 Vani 的全部两个要求，输出 both；
如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；
如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；
如果均不能满足，输出 impossible。
如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
输入样例：
2 3 4
1 3
2 1
2 2
2 3
输出样例：
row 1

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. typedef long long LL;
  7. const int N = 1e5+10;
  8. int row[N],col[N];
  9. int d[N],s[N];
  10. LL work(int n,int a[]){
  11.     for (int i = 1; i <= n; i ++ ){
  12.         s[i] = s[i-1]+a[i];
  13.     }
  14.     if(s[n]%n){  // 注意 这里只能这么写或者大于等于1 不能写==1
  15.         return -1;
  16.     }
  17.     LL avg = s[n]/n;
  18.     d[n]=0;
  19.     for (int i = 1; i < n; i ++ ){
  20.         d[i] = i*avg - s[i];
  21.     }
  22.     sort(d+1,d+n+1);
  23.     LL res=0;
  24.     for (int i = 1; i <= n; i ++ ){
  25.         res+=abs(d[i]-d[(n+1)/2]);
  26.     }
  27.     return res;
  28. }
  30. int main()
  31. {
  32.     int n,m,T;
  33.     cin >> n >> m>> T;
  34.     while (T -- ){
  35.         int x,y;
  36.         cin >> x >> y;
  37.         row[x]++;
  38.         col[y]++;
  39.     }
  40.     LL r = work(n,row);
  41.     LL c = work(m,col);
  42.     if(r!=-1&&c!=-1){
  43.         cout << "both "<<r+c<<endl; 
  44.     }else if(r!=-1){
  45.         cout << "row "<<r<<endl;
  46.     }else if(c!=-1){
  47.         cout << "column "<<c<<endl;
  48.     }else{
  49.         cout << "impossible";
  50.     }
  52. }

106. 动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数 P，代表后面数据集的个数，接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数 M，代表数据集中包含数据的个数，M 一定为奇数，数据之间用空格隔开。
数据集的剩余行由数据集的数据构成，每行包含 10 个数据，最后一行数据量可能少于 10 个，数据之间用空格隔开。
输出格式
对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。
数据集的剩余行由输出的中位数构成，每行包含 10 个数据，最后一行数据量可能少于 10 个，数据之间用空格隔开。
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6. int main()
  7. {
  8.     int T;
  9.     cin >> T;
  10.     while(T--){
  11.         int n,m; // m编号，n是个数
  12.         cin >> m >> n;
  13.         cout << m <<" "<<(n+1)/2<<endl;
  14.         priority_queue<int>down;
  15.         priority_queue<int,vector<int>,greater<int>>up;
  16.         int cnt=0;
  17.         for (int i = 1; i <= n; i ++ ){
  18.             int x;
  19.             cin >> x;
  20.             if(down.empty()||x<=down.top()){
  21.                 down.push(x);
  22.             }else{
  23.                 up.push(x);
  24.             }
  25.             if(down.size()>up.size()+1){
  26.                 up.push(down.top());
  27.                 down.pop();
  28.             }
  29.             if(down.size()<up.size()){
  30.                 down.push(up.top());
  31.                 up.pop();
  32.             }
  33.             if(i%2){
  34.                 cout << down.top()<<" ";
  35.                 cnt++;
  36.                 if(cnt%10==0){
  37.                     cout << endl;
  38.                 }
  39.             }
  40.         }
  41.         if(cnt%10){
  42.             cout << endl;
  43.         }
  44.     }
  45. }

107. 超快速排序

在这个问题中，您必须分析特定的排序算法——超快速排序。
该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。
对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数 n，代表该用例中输入序列的长度。
接下来 n 行每行输入一个整数 ai,代表用例中输入序列的具体数据，第 i 行的数据代表序列中第 i 个数。
当输入用例中包含的输入序列长度为 0 时，输入终止，该序列无需处理。
输出格式
对于每个需要处理的输入序列，输出一个整数 op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。
输入样例：
5
9
1
0
5
4
3
1
2
3
0
输出样例：
6
0

  1. // 求逆序对数量
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. typedef long long LL;
  7. using namespace std;
  8. const int N = 5e5+10;
  9. int a[N],t[N];
  10. int n;
  11. LL res;
  12. void merge_sort(int l,int r){
  13.     if(l>=r){
  14.         return ;
  15.     }
  16.     int mid = (l+r)>>1;
  17.     merge_sort(l,mid);
  18.     merge_sort(mid+1,r);
  19.     // 求逆序对数量
  20.     int i=l,j=mid+1;
  21.     while(i<=mid&&j<=r){
  22.         if(a[i]>a[j]){
  23.             res+=mid-i+1;
  24.             j++;
  25.         }else{
  26.             i++;
  27.         }
  28.     }
  29.     // 合并
  30.     i = l,j=mid+1;
  31.     int k=0;
  32.     while(i<=mid&&j<=r){
  33.         if(a[i]<a[j]){
  34.             t[k++] = a[i++];
  35.         }else{
  36.             t[k++] = a[j++];
  37.         }
  38.     }
  39.     while(i<=mid){
  40.         t[k++] = a[i++];
  41.     }
  42.     while(j<=r){
  43.         t[k++] = a[j++];
  44.     }
  45.     for (int i = l,j=0; i <= r; i ++,j++ ){
  46.         a[i] = t[j];
  47.     }
  48. }
  50. int main(){
  51.     while(cin>>n&&n){
  52.         for (int i = 0; i < n; i ++ ){
  53.             cin>> a[i];
  54.         }
  55.         res=0;
  56.         merge_sort(0,n-1);
  57.         // for (int i = 0; i < n; i ++ ){
  58.         //     cout << a[i]<<" ";
  59.         // }
  60.         cout << res<<endl;
  61.     }
  62. }

1273. 天才的记忆

从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。
在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。
题是这样的：给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 M 个询问，每次询问就给你两个数字 A,B，要求你瞬间就说出属于 A 到 B 这段区间内的最大数。
一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。
但是，她每次都以失败告终，因为这数字的个数是在太多了！
于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！
输入格式
第一行一个整数 N 表示数字的个数。
接下来一行为 N 个数，表示数字序列。
第三行读入一个 M，表示你看完那串数后需要被提问的次数。
接下来 M 行，每行都有两个整数 A,B。
输出格式
输出共 M 行，每行输出一个数，表示对一个问题的回答。
输入样例：
6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3
输出样例：
34
123
123
8

RMQ算法

  1. 类似动态规划的思想
  2. f[i][j] 表示从i点开始到(i + 2^j -1)的最大值 即区间[i,i+2^j-1]的最大值
  3. 那么  f[i][j] = max(f[i][j-1],f[i+2^(j-1)][j-1]);
  4. 等价于f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
  5.     - f[i][j-1]表示的是区间[i,i+2^(j-1)-1]的最大值
  6.     - f[i+2^j] 表示的是区间[i+2^(j-1),i+2^(j-1) +2^(j-1)-1]的最大值
  7. 如果要求区间[l,r]的最大值怎么划分？
  8.     - （1）找到覆盖左端点l，但不超过右端点的区间最大值
  9.         - 找到小于区间长度的最大的2的幂，假设为k，求f[l][k]
  10.     - （2）和  覆盖右端点r, 但不超过左端点的区间的最大值
  11.         - 找到小于区间长度的最大的2的幂，假设为k，求f[r-a^k+1][k]
  12.     -- （3）两个最大值取最大值即可
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cmath>
  5. using namespace std;
  6. const int N = 2e5+10,M = 18;
  7. int f[N][M];
  8. int n,m;
  9. int a[N];
  10. void init(){
  11.     for (int j = 0; j < M; j ++ ){ // 枚举多少次方
  12.         for (int i = 1; i+(1<<j)-1<= n ; i ++ ){ // 枚举起点
  13.             if(j==0){
  14.                 f[i][j] = a[i];
  15.             }else{
  16.                 f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);   
  17.             }
  18.         }
  19.     }
  20. }
  22. int query(int l,int r){
  23.     int len = r-l+1;
  24.     int c = log(len)/log(2);
  25.     return max(f[l][c],f[r-(1<<c)+1][c]);
  26. }
  27. int main()
  28. {   
  29.     cin >> n ;
  30.     for (int i = 1; i <= n; i ++ ){
  31.         cin >> a[i];
  32.     }
  33.     init();
  34.     cin >> m;
  35.     while (m -- ){
  36.         int l,r;
  37.         cin >> l >> r;
  38.         cout << query(l,r)<<endl;
  39.     }
  40. }