解析

题意：求2000/5/4是当年的第几天
- 明显的是判断闰年的题，判断闰年： $(n \% 100\quad!= 0\quad \&\&\quad n \%4 == 0 ) || (n \% 400 == 0)$
- 可知2000年为闰年，所答案为：31 + 29 + 31 + 30 + 4。即 $125$
```
#include<bits/stdc++.h>
using namespace std;
signed main() {
    cout << 31 + 29 + 31 + 30 + 4;
    return 0;
}
```

题意：给你待解密的共10个汉字，每个汉字由16个8位有符号整数组成，将其转换为点阵格式，输出题目要求

由题意可知，每个字节8位，一行2个字节，一个汉字由16 * 16 的点阵构成，将其每一位提取出来表示即可。
可能的坑点：8位有符号数字（即负数为1...开头）、提取时从低位到高位，输出记得从高位到低位
解密代码如下：

#include<bits/stdc++.h>
using namespace std;
signed main() {
    for(int i = 1; i <= 32; ++i) {
        int tmp;
        cin >> tmp;
        if(tmp < 0) {
            tmp = -tmp;
            tmp += (1 << 7);//1是第1位，左移七位即为第八位
        }//将其转换为无符号整型
        stack<char> s;
        for(int j = 1; j <= 8; ++j) {
            if(tmp & 1) s.push('*');
            else s.push('.');
            tmp >>= 1;
        }
        while(!s.empty()) {
            cout << s.top() << ' ';
            s.pop();
        }
        if(i % 2 == 0) cout << '\n';
    }return 0;
}

问题为九的九次方等于多少？，即 $387420489$

#include<bits/stdc++.h>
using namespace std;
signed main() {
    int ans = 1;
    for(int i = 1; i <= 9; ++i) ans *= 9;
    cout << ans;
    return 0;
}

题意：求出这一百个数的乘积尾部有多少0

~~这当然可以直接暴力算然后自己数一数~~
正经想法：尾部有多少0就等同于求这些数的乘积里面能分解出多少个10，又因为10由2、5这两个质因子组成。也就是求这100个数里边2，5质因子最少的那个有多少个就可以了

#include<bits/stdc++.h>
using namespace std;
int prime[10007];
signed main() {
    for(int i = 1; i <= 100; ++i) {
        int tmp;
        cin >> tmp;
        for(int j = 2; j * j <= tmp; ++j) {
            while(tmp % j == 0) {
                tmp /= j;
                ++prime[j];
            }
        }
        if(tmp > 1) ++prime[tmp];
    }cout << min(prime[2], prime[5]);
    return 0;
}

题意：给你3个测试手机测试抗摔1000层，求出在最坏情况下使用最佳策略下最少的测试次数
- 别上来就写10了，好好读题，只有3个测试手机。~~虽然说一开始就直接盲填10个了~~
- 既然只有三个手机，也就是说我们要最大化前面两个手机的利用价值，以达到使用最少的测试次数
- 明显的是个DP题目了，那就来考虑状态转移。**设 $dp[i][j]$ 为 $i$ 个手机测试 $j$ 层的最少测试次数**
  - 初始化：不论多少手机，测试 $j$ 层的最无脑的情况就是从低到高测试，测试 $j$ 层
    
    即： $dp[i][j] = j$
  - 当有 $i$ 个手机时：由于我们有 $i-1$ 个手机可以试错，所以要最大化利用它的价值。在小于 $j$ 层的层中选取一个测试用层 $k$
    
    则有两种情况：
    - 摔碎了：那就用 $i-1$ 个手机去测试剩下的 $k-1$ 层
    - 没摔碎：用 $i$ 个手机去测试还未测试的层数，即 $j-k$ 层
    但题意很明显说明了：在最坏的运气下，也就是说，我们需要在上面的两个状态里取一个较大值
- 所以状态转移方程为： $dp[i][j] = min(dp[i][j], max(dp[i-1][k-1],dp[i][j-k]))$ ，其中 $k<j$
```
#include<bits/stdc++.h>
using namespace std;
int dp[5][1007];
signed main() {
    for(int i = 1; i <= 1000; ++i) dp[1][i] = dp[2][i] = dp[3][i] = i;
    for(int i = 2; i <= 3; ++i) {
        for(int j = 2; j <= 1000; ++j) {
            for(int k = 1; k < j; ++k) {
                dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], dp[i][j - k]) + 1);
            }
        }
    }cout << dp[3][1000];//答案为19
    return 0;
}
```

程序填空题
- 一道程序填空题，瞄一眼程序可以看出来函数的接口意义， $quick\_select(a,l,r,k)$ 其中a为传数组地址， $l,r,k$ 分别为开始位置、终止位置，所求的第k大元素
- 然后看函数调用，是递归调用，先看递归调用部分
```
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);
```
- 很明显的：
  - 如果 $i - l + 1 == k$ 就返回 $a[i]$ ，可以大胆的猜想： $a[i]$ 就是第 $i$ 大的数
  - 然后看下面，根据上面的猜想，看已有的部分，即 $i - l + 1 > k$ 时，处理 $i$ 左边，调用 $[l,i-1]$ 符合猜想
- 所以填空就是：a, l + 1, r, k

题意：**在A,B,C中各选 $i,j,k$ 使得 $A[i], B[j], C[k]$ 单调递增**

$1 \le i,j,k\le1e5$ ，明显的不能完全暴力，所以考虑优化

第一，我们要去枚举一个数作为基数，然后再去寻找合法的组合。由于 $A[i] < B[j] < C[k]$ ，那么枚举A，C中元素都要去枚举第二遍，但枚举B中元素，只需要去查找A中比它小的和C中比它大的，所以枚举的复杂度由 $O(n^2)$ 降为了 $O(n)$
考虑排序然后二分查找，时间复杂度为 $O（nlog^2n）$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int A[N], B[N], C[N];
bool check(int pos, int value) {return (A[pos] < value);}
signed main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) scanf("%d", A + i);
    for(int i = 1; i <= n; ++i) scanf("%d", B + i);
    for(int i = 1; i <= n; ++i) scanf("%d", C + i); 
    sort(A + 1, A + 1 + n);
    sort(B + 1, B + 1 + n);
    sort(C + 1, C + 1 + n);
    long long ans = 0;
    for(int i = 1; i <= n; ++i) {
        int b = B[i];
        int pre = -1;
        int l = 1, r = n;
        while(l <= r) {
            int mid = l + r >> 1;
            if(check(mid, b)) pre = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(pre >= 1) {
            int net = C + n + 1 - upper_bound(C + 1, C + 1 + n, b);
            ans += pre * net;
        }
    }cout << ans << endl;
    return 0;
}

但是还有更好的解法，可以注意到，题目的真正意思是要让我们统计比一个数大的数在另一个集合中的个数

所以我们就要去考虑权值的大小，注意到 $0\le A[i],B[j],C[k] \le 1e5$ 比较小，所以可以桶装，然后借助前缀和快速查询

预期时间复杂度为 $O(n)$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
long long A[N], B[N], C[N];
signed main() {
    int n;
    cin >> n;
    int tmp;
    for(int i = 1; i <= n; ++i) scanf("%d", &tmp), ++A[tmp];
    for(int i = 1; i <= n; ++i) scanf("%lld", B + i);
    for(int i = 1; i <= n; ++i) scanf("%d", &tmp), ++C[tmp];
    for(int i = 1; i <= 1e5; ++i) {
        A[i] += A[i-1];
        C[i] += C[i-1];
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i) {
        long long value = B[i];
        ans += A[value-1] * (C[100000] - C[value]);
    }cout << ans << endl;
    return 0;
}

题意：求给出点在其定义下的距离

明显的找规律题目，在纸上多画两下就能看出规律，这里给出我自己的想法，仅供参考
将所有的点投影到轴上，然后再此基础上增减到点上的距离。
如下图，设 $a_i,b_i,c_i,d_i$ 分别为 $x$ 轴负方向、 $y$ 轴正方向、 $x$ 轴正方向、 $y$ 轴负方向，并且设 $a_i$ 下标从0开始
计算可得： $a_0 = 0,a_1 = 1,a_2 = 10, a_3 = 27, a_4 = 52$ ，并且容易看出： $b_i = a_i+2i,c_i=a_i+4i,d_i = a_i+6i$
现在只要推出 $a_i$ ，那么所有的式子就出来了。
对于 $a_i$ ，设： $d_{ij} = a_j-a_i$ ，那么 $d_{01} = 1,d_{12} = 9,d_{23} = 17,d_{34} = 25$
那么容易看出： $d_{34}-d_{23} = d_{23} - d_{12} = d_{12}-d_{01} = 8$
由累加可以得到： $a_n = 4n(n+1) - 7n$
然后进行计算即可，需要注意的是第三象限要特殊处理一下

图片说明

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;

signed main() {
    ll x, y;
    cin >> x >> y;
    ll n = max(abs(x), abs(y));
    if(x == 0 || y == 0) {//在轴上
        if(x == 0 && y == 0) cout << 0 << endl;
        else if(x == 0) {
            if(y > 0) {//y正轴上
                cout << 4 * y * (y + 1) - 5 * y << endl;
            }else {//y负轴上
                y = -y;
                cout << 4 * y * (y + 1) - y << endl;
            }
        }else {
            if(x > 0) {//x正轴上
                cout << 4 * x * (x + 1) - 3 * x << endl;
            }else {//x负轴上
                x = -x;
                cout << 4 * x * (x + 1) - 7 * x << endl;
            }
        }
    }else {//不在轴上
        ll dis = 4 * n * (n + 1);
        if(x > 0) {//一、二象限
            if(y > 0) {//第一, b
                dis += x;
                if(x == n) dis += n - y;
                cout << dis - 5 * n << endl;
            }else {//第二, c
                y = -y;
                dis += y;
                if(y == n) dis += n - x;
                cout << dis - 3 * n << endl;
            }
        }else {//三、四象限
            x = -x;
            if(y > 0) {//第四,a
                dis += y;
                if(y == n) dis += n - x;
                cout << dis - 7 * n << endl;
            }else {//第三,d。这里需要特殊处理
                y = -y;
                if(x <= y) n = y;
                else n = x - 1;
                dis = 4 * n * ( n + 1 );
                dis += x;
                if(x == n + 1) dis += n - y; 
                cout << dis - n << endl;
            }
        }
    }
    return 0;
}

题意：**给定日志，求是否存在长度为d的的区间，使得其点赞数 $\ge k$ **

分析一下： $1 \le n \le 1e5$ 明显不能暴力。看到任意一个区间的长度固定，使用尺取法，可以快速进行判断。
而且 $ti$ 比较大，对每一个 $id$ 开个 $1e5$ 大小的数组不可能，所以用 $vector$ 进行离散化
离散化 + 尺取法，注意坑点： $0\le id \le 1e5$ ，可以取0，而且题目输入中要自行判断 $id_{max}$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
ll n, d, k;
vector<int> T[N];
bitset<N> flag;
signed main() {
    int maxn = 0;
    scanf("%lld%lld%lld", &n, &d, &k);
    for(int i = 1; i <= n; ++i) {
        int ti, id;
        scanf("%d%d", &ti, &id);
        T[id].push_back(ti);
        maxn = max(maxn, id);
    }
    for(int i = 0; i <= maxn; ++i) sort(T[i].begin(), T[i].end());
    for(int i = 0; i <= maxn; ++i) {
        if(T[i].size() < k) continue;
        int s = T[i][0], e = T[i][0];
        int lindex = 0, rindex = 0;//[l, r]
        while(rindex < T[i].size()) {
            if(e - s < d) {
                if(rindex - lindex + 1 >= k) {
                    flag[i] = 1;
                    break;
                }
                ++rindex;
                if(rindex < T[i].size()) e = T[i][rindex];
            }else {
                ++lindex;
                s = T[i][lindex];
            }
        }
    }
    for(int i = 0; i <= maxn; ++i) {
        if(flag[i]) printf("%d\n", i);
    }
    return 0;
}

题意：给定一个图，若其中一点为岛屿，且上下左右方向存在水，则其会被淹没。求被完全淹没的岛屿个数

明显的搜索题，会 $bfs$ 或 $dfs$ 就可以
注意一下是求完全淹没的岛屿个数，一个联通块在淹没后可能变成两个联通块，注意维护
思路：先搜索一遍，找出所有联通块的个数，并将其一一编号。
然后依题义进行淹没操作，然后再搜索一遍，并且在搜索过程中标记已经搜索过的编号联通块，防止重复计算
然后二者求出的联通块数目相减即为答案

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
int n, tot = 0;
char G[1007][1007];
bitset<1007> flag[1007], m;
int vis[1007][1007];
queue<pair<int,int> > q;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool check(int x, int y) {
    bool flag = 0;
    if(x > 1) {
        if(G[x-1][y] == '.') flag = 1;
    }
    if(x < n) {
        if(G[x+1][y] == '.') flag = 1;
    }
    if(y > 1) {
        if(G[x][y-1] == '.') flag = 1;
    }
    if(y < n) {
        if(G[x][y+1] == '.') flag = 1;
    }return flag;
}

bool checkpos(int x, int y, int dx, int dy) {
    bool flag = 1;
    if(x + dx > n || x + dx < 1) flag = 0;
    if(y + dy > n || y + dy < 1) flag = 0;
    return flag;
}

void bfs(int a, int b) {
    while(!q.empty()) q.pop();
    ++tot;//给岛屿编号
    q.push(make_pair(a, b));
    vis[a][b] = tot;
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int mx = dx[i], my = dy[i];
            if(checkpos(x, y, mx, my) && G[x + mx][y + my] == '#' && !vis[x+mx][y+my]) {
                q.push(make_pair(x + mx, y + my));
                vis[x + mx][y + my] = tot;
            }
        }
    }
}

signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            scanf(" %c", &G[i][j]);
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(G[i][j] == '#' && !vis[i][j]) {
                bfs(i,j);
            }
        }
    }//搜索未淹没前个数

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(G[i][j] == '#' && check(i, j)) flag[i][j] = 1;
        }
    }//记录哪些被淹没

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(G[i][j] == '#' && flag[i][j]) G[i][j] = '.';
        }
    }//将相应的点淹没
    int nex = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(G[i][j] == '#' && !m[vis[i][j]]) {
                m[vis[i][j]] = 1;//标记已经淹没的岛屿序号
                ++nex;
            }
        }
    }
    printf("%d\n", tot - nex);
    return 0;
}

题意：在n个数里面任选k个，使得乘积最大

思维题，一步步分析就好
- $n =k$ 时，所有的数字都要选
- $n < k$ 时，那么可以不全选
- 如果 $k$ 为偶数的话，那么不论如何，最后得出的结果非负
- 反之，如果 $k$ 为奇数时，只有全部为负时，最后得出的结果为负，其余情况均为非负
- 所以，在 $k$ 为奇数的情况下，取出一个目前最大的数，然后将 $k$ 转换为偶数情况进行计算
此处利用双指针进行选择， $l,r$ 分别为负数，正数部分指针

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
ll arr[N];
int n, k;
signed main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%lld", arr + i);
    ll ans = 1;
    int l = 1, r = n, flag = 1;
    sort(arr + 1, arr + 1 + n);
    if(k & 1) {
        ans = arr[r--] % mod;
        --k;
        if(arr[n] < 0) flag = -1;
    }
    while(k > 0) {
        ll x = arr[l] * arr[l + 1], y = arr[r] * arr[r-1];
        if(x * flag > y * flag) {
            ans = x % mod * ans % mod;
            l += 2;
        }else {
            ans = y % mod * ans % mod;
            r -= 2;
        }
        k -= 2;
    }
    cout << ans << endl;
    return 0;
}

第九届蓝桥杯C/C++ B组 —— 2018

解析