题目结构

项目	题型	分值	题型
第一题	结果填空	5	第几天（日期处理）
第二题	结果填空	5	明码（位运算）
第三题	结果填空	10	乘积尾零（数学+取位数）
第四题	结果填空	10	测试次数（DP）
第五题	结果填空	15	递增三元组（双指针）
第六题	程序设计	15	快速排序
第七题	程序设计	20	螺旋曲线（找规律）
第八题	程序设计	20	日志统计（结构体）
第九题	程序设计	25	全球变暖（BFS）
第十题	程序设计	25	乘积最大

第一题第几天

excel解决
手算

答案：125

第二题明码

x>>j&1：判断x的二进制排列中，第j位是否为1

#include <iostream>
using namespace std;
int main(){
    for(int i=0;i<320;i++){
        int x;
        cin>>x;
        for(int j=7;j>=0;j--){
            if(x>>j&1) cout<<"1";
            else cout<<" ";
        }
        if(i%2==1) cout<<endl;
    }
    return 0;
}

10个汉字是：九的九次方等于多少？
答案： 387420489
注意：
思路：首先要明白，计算机存储的都是二进制，正数就是二进制表示即原码，负数是对其正数原码的各位取反末尾加一即补码，计算机中存储的本身就是二进制，不用特意去求所以直接用 n&1 就可以直接得到其二进制数字。

x >>= 1 等同于 x = x/2;
这是位运算， >>左移运算，<< 右移运算
x >> n 等同于 x / (2^n)
x << n 等同于 x * (2^n)
当然了，要注意类型所占内存的大小，以防溢出

第三题乘积尾零

#include <iostream>
using namespace std;
int main()
{
    int num2=0,num5=0;
    for(int i=0;i<100;i++){
        int x;
        cin>>x;
        while(x%2==0){
            num2++;
            x/=2;
        }
        while(x%5==0){
            num5++;
            x/=5;
        }
    }
    cout<<(num2>num5?num5:num2)<<endl;
} // namespace std;

第四题测试次数

第五题递增三元组

题解一：三重循环（超时）

#include <iostream>
#define MAX 1000005
using namespace std;
typedef long long ll;
ll A[MAX],B[MAX],C[MAX];
ll N,cnt;
int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }for(int i=0;i<N;i++){
        cin>>B[i];
    }for(int i=0;i<N;i++){
        cin>>C[i];
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                if(A[i]<B[j]&&B[j]<C[k]){
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

题解二：双指针法

时间复杂度：N logN

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N],b[N],c[N];
int n,p,q;
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    long long ans=0;
    for(int i=0;i<n;i++){
        while(p<n&&a[p]<b[i]) p++;
        while(q<n&&c[q]<=b[i])q++;
        ans+=(long long)p*(n-q);
    }
    cout<<ans<<endl;
    return 0;
}

在这里插入图片描述

若出现比较大小问题，最好先进行排序，因为三重循环会超时所以使用双指针方法。
遍历B数组，在A数组中找到p个比b1小的数，在C数组中找到q个小于等于b1的数，那么比b1大的数的个数为n-q
最后结果即为p*(n-q)然后随着遍历B数组累加。

第六题快速排序

#include <stdio.h>
#include<cstdlib>

int quick_select(int a[], int l, int r, int k) {
	int p = rand() % (r - l + 1) + l; //l~r之间的一个随机数 
	int x = a[p];//x的值随机数a[p]的值 
	{int t = a[p]; a[p] = a[r]; a[r] = t;} //交换随机数a[p]和高位右边第一个数 
	int i = l, j = r; //i左指针 j右指针
	while(i < j) {
		while(i < j && a[i] < x) i++;// 最后i==j 或者 a[i]>=x
		if(i < j) {//如果a[i]>=随机数x 
			a[j] = a[i]; //选一个比x大的数 放到高位 
			j--;
		}
		while(i < j && a[j] > x) j--;// 最后j==i 或者 a[i]<=x
		if(i < j) {//如果a[i]<=随机数x
			a[i] = a[j]; //选一个比x小的数 放到低位
			i++;
		}
	}
	a[i] = x;
	p = i;//这里改了p的值 说明会用到p 
	if(i - l + 1 == k) return a[i];
	if(i - l + 1 < k) return quick_select(_________); //填空
	else return quick_select(a, l, i - 1, k);//a数组不变 k不变 
}
	
int main()
{
	int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
	printf("%d\n", quick_select(a, 0, 14, 5));
	return 0;
}

答案：a, p+1, r, k-(i-l+1) 或者 a, p, r, k-i+l

首先看参数要求：
第一个参数a：数组
第二个参数l：左指针
第三个参数r：优指针
第四个参数k：寻找第k个元素
l~i区间里为比枢纽小的数，共l-i+1个元素
i+1~r区间都是比枢纽大的元素
如果l-i+1大于k，还是在l~i-1区间找第k个元素
如果l-i+1小于k，在i+1~r区间找元素，那么是找第几个元素呢？应为k-(i-l+1)个元素

第七题螺旋曲线

参照链接
https://blog.csdn.net/qq799028706/article/details/84312062

#include <iostream>
#include <algorithm>
using namespace std;
long long  x,y,sn,n,sum;
long long  px,py,d1,d2;
int main()
{
    cin>>x>>y;
    n=max(abs(x),abs(y));
    sn=4*(n-1)*n;
    sum=sum+sn;
    px=-n,py=-n;
    d1=x-px,d2=y-py;
    if(y>x){
        sum+=(d1+d2);
    }else{
        sum+=(8*n-d1-d2);
    }
    cout<<sum<<endl;
} // namespace std;

第八题日志统计

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first                 // 简化操作，用 x 代替 first
#define y second                // 简化操作，同上

using namespace std;

// 不懂的话可以先去查明pair的用法
typedef pair<int, int > PII;    // 简化操作

const int N = 100010;

PII a[N];   // 另数组的每个元素都拥有两个属性

int cnt[N]; // 记录某一合法时间段，id出现的数量
bool st[N]; // 记录某一合法时间段，id是否曾是热帖

int main()
{
    int n, d, k;
    cin >> n >> d >> k;
    
                                             //  ts时刻   日志id
    for (int i = 0; i < n; i ++) scanf("%d%d", &a[i].x, &a[i].y);
    
    sort(a, a + n); // 按照时间排序
    
    for (int i = 0, j = 0; i < n; i ++)
    {
        // 在合法时间段内，id的记录加一
        cnt[a[i].y] ++;
        // 超出合法时间
       while(a[i].x - a[j].x >= d)
       {
            // 起始时间的id的记录减一
            cnt[a[j].y] --;
            // 指针后移一位
            j ++;
            
       }
        //记录某个id曾是热帖
       if(cnt[a[i].y] >= k) st[a[i].y] = true;
    }
    
    for (int i = 0; i < N; i ++)
        if(st[i]) printf("%d\n", i);
}