目录
1A：购物单（填空5分）
2B：等差素数列（填空7分）（枚举）
3C：承压计算（填空13分）
4D：方格分割（填空17分）（dp）
5E：取数位（代码填空9分）
6F：递增三元组（编程题11分）（前缀和）
解析代码
7G：螺旋折线（编程题19分）
解析代码
8H：日志统计（编程题21分）
解析代码（过78%数据）
9I：全球变暖（编程题23分
解析代码
10J：乘积最大（编程题25分）
解析代码
1A：购物单（填空5分）
.................答案：5200
2B：等差素数列（填空7分）（枚举）
答案：210
#include<iostream>
using namespace std;
long long int prime[100019];
bool isprime(long long int n)
{for (long long int i = 2; i * i <= n; i++){if (n % i == 0)return false;}return true;
}
int main()
{for (long long int i = 2; i <= 100009; i++) //素数打表{if (isprime(i))prime[i] = 1;}for (int i = 1; i <= 1000; i++) // 枚举公差{for (int j = 1; j <= 8000; j++) // 枚举首项 {int flag = 0;for (int k = 1; k <= 9; k++){if (prime[j + k * i] == 0){flag = 1;break;}}if (!flag){printf("%d\n", i);return 0;}}}return 0;
}
// 答案2103C：承压计算（填空13分）
75 87 8 89 2 7 28 1 4 9 18 1 8 8 4 17 9 6 1 4 5 45 6 5 5 6 9 5 65 5 4 7 9 3 5 5 17 5 7 9 7 4 7 3 3 14 6 4 5 5 8 8 3 2 4 31 1 3 3 1 6 6 5 5 4 4 29 9 9 2 1 9 1 9 2 9 5 7 94 3 3 7 7 9 3 6 1 3 8 8 3 73 6 8 1 5 3 9 5 8 3 8 1 8 3 38 3 2 3 3 5 5 8 5 4 2 8 6 7 6 98 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 42 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 97 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 69 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 35 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 96 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 42 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 47 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 61 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 32 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 87 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 97 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 65 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
为什么要求最小值？因为单位的不同，因此无法正确的数字，比如7无法正常从推出5 和 8，所以我们要求出单位
单位的求法就是：题目给出了最小值，所以我们也要计算出我们得出的最小值，这样就可以得到了单位，再用这个单位去乘以最大值，就得到了题目的正确所求最大值
#include <cstdio>
#include <iostream>
using namespace std;double g[40][40];int main()
{for (int i = 1; i <= 30; i++)for (int j = 1; j <= i; j++)cin >> g[i][j];for (int i = 1; i <= 29; i++){for (int j = 1; j <= i; j++){g[i + 1][j] += g[i][j] / 2;g[i + 1][j + 1] += g[i][j] / 2;}}double maxv = 0, minv = 0x3f3f3f3f;for (int i = 1; i <= 30; i++){maxv = max(maxv, g[30][i]);minv = min(minv, g[30][i]);}printf("%f", 2086458231 / minv * maxv);return 0;
}
// 答案72665192664答案72665192664
4D：方格分割（填空17分）（dp）
答案：19
#include <iostream>using namespace std;
#define endl '\n'
#define int long longint dp[1010][5];
// 状态表示：[[i][j]为i层j个手机的最多(最优)测试次数
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for (int i = 1;i <= 1000;i++) // 边界初始化{dp[i][1] = i; // 如果只有一个手机，则n层最多测试指数为n（本身层数）}for (int j = 2;j <= 3;j++) // 循环手机部数 ，从2开始，因为1已经知道了{for (int i = 1;i <= 1000;i++) // 循环楼层数{dp[i][j] = dp[i - 1][j] + 1; // 第j层楼还有i部手机时的测试次数=第j-1层楼还有i部手机时测试次数加1for (int k = 2;k <= i;k++) // 假设从第k层摔手机{dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);}}}cout << dp[1000][3] << endl;return 0;
}
// 答案195E：取数位（代码填空9分）
快速排序，就是每次选择一个数，然后做比较使得左边的数小于所选择的数，右边的数大于所选择的数。然后将左右两边在进行快速排序。
题目答案：
a, i+1, r, k-(i-l+1)
6F：递增三元组（编程题11分）（前缀和）
解析代码
排序 + 双指针
分析题目我们可以发现三元组中b[j] 可以同时制约 a[i] 和 c[k]，由此可以先排序 后枚举b 对于每个 b[i] 我们找到比它大的c[k] 的数量和比它小的a[i]的数量，因为我们排过序所有 a,b,c 只需遍历一遍即可。
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define int long longsigned main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 0;cin >> n;vector<int> A, B, C;for (int t = 0; t != 3; ++t){for (int i = 0; i != n; ++i){int a = 0;cin >> a;if (t == 0)A.push_back(a);else if (t == 1)B.push_back(a);elseC.push_back(a);}}sort(A.begin(), A.end());sort(B.begin(), B.end());sort(C.begin(), C.end());int i, j, k;i = j = k = n - 1;int res = 0;while (j >= 0){while (k >= 0 && B[j] < C[k])--k;while (i >= 0 && A[i] >= B[j])--i;res += (n - k - 1) * (i + 1);--j;}cout << res << endl;return 0;
}7G：螺旋折线（编程题19分）
解析代码
找规律+模拟
这道题的解法为 先找各个顶点坐标对应的长度，我们可以发现顶点 （-1，0） （-1，1） （1，1） （1 ，-1） （-2，-1） （-2，2）对应长度 1 1+1 1+1+2 1+1+2+2 1+1+2+2+3 1+1+2+2+3+3发现规律。细节的我们找到顶点的规律之后，给我们一个点我们先判断它在那个环上，然后求出对应顶点的长度，最后加或减即可
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define endl '\n'
#define int long longsigned main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int x, y, t, ans;cin >> x >> y;int abx = abs(x), aby = abs(y);if (x >= 0 && y >= 0) // 第一象限{t = max(abx, aby);ans = (t * 2 - 1) * (t * 2 - 1 + 1);if (abx == t)ans += t * 2 + t - aby;elseans += t + abx;}else if (x > 0 && y < 0) // 第四象限{t = max(abx, aby);ans = (t * 2 - 1) * (t * 2 - 1 + 1);if (abx == t)ans += 3 * t + aby;elseans += 4 * t + t - abx;}else if (x <= 0 && y <= 0) // 第三象限{t = max(abx - 1, aby);ans = (t * 2) * (t * 2 + 1);if (abx - 1 == t)ans += 2 * t + 1 + t - aby;elseans += t + abx;}else // 第二象限{t = max(abx, aby);ans = (t * 2 - 1) * (t * 2 - 1 + 1);if (abx == t)ans -= t - aby;elseans += t - abx;}cout << ans << endl;return 0;
}8H：日志统计（编程题21分）
解析代码（过78%数据）
哈希+排序
用哈希存储每个id的所有点赞的时间数据，然后遍历哈希，将时间排序再用双指针检查是否有区间D符合热帖要求。
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
#define endl '\n'
#define int long longsigned main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int N, D, K;cin >> N >> D >> K;unordered_map<int, vector<int>> map;for (int i = 0; i != N; i++){int ts, id;cin >> ts >> id;map[id].push_back(ts);}vector<int> ans;for (auto& m : map){int n = m.second.size();if (n < K)continue;sort(m.second.begin(), m.second.end());int i = 0, j = 0;int temp = 0;while (j < n && i < n){if (n - i < K)break;while (j < n && m.second[j] - m.second[i] < D){temp++;j++;if (temp >= K)break;}if (temp >= K){ans.push_back(m.first);break;}i++;temp--;}}sort(ans.begin(), ans.end());for (auto e : ans){cout << e << endl;}return 0;
}9I：全球变暖（编程题23分
解析代码
记录改变前和改变后的海域情况 然后计数
需要注意的是不能简单通过 计算原来的 和 后来的岛屿数差值来计算答案
原因是 例如：
........
.##.....
.####...
..#.#...
...###..
...###..
........
........
这种情况原来只有一个岛屿 改变后 却有2个
计数的方法为遍历原来的每个岛屿，只要这个岛屿改变后不存在任意一个元素，那么ans++；
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>using namespace std;typedef long long ll;int dis[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };bool sign;void dfs(vector<vector<int>>& a, int i, int j, vector<vector<int>>& b){if (i<1 || i>a.size() - 1 || j<1 || j>a.size() - 1||a[i][j]==0){return;}a[i][j] = 0;if (b[i][j] != 0)sign = false;for (int k = 0; k != 4; k++){dfs(a, i + dis[k][0], j + dis[k][1],b);}}int main()
{int N;cin >> N;vector<vector<int>> before;vector<vector<int>> later;for (int i = 0; i != N; i++){before.push_back(vector<int>());for (int j = 0; j != N; j++){char t;cin >> t;if (t == '.')before[i].push_back(0);else before[i].push_back(1);}}later = before;for (int i = 1; i != N - 1; i++){for (int j = 1; j != N - 1; j++){if (later[i][j] == 1){bool b = true;for (int k = 0; k != 4; k++){if (before[i + dis[k][0]][j + dis[k][1]] == 0){b = false;}}if (!b)later[i][j] = 0;}}}int ans = 0;for (int i = 1; i != N - 1; i++){for (int j = 1; j != N - 1; j++){if (before[i][j]){sign = true;dfs(before, i, j,later);if (sign)ans++;}}}cout << ans << endl;system("pause");return 0;}10J：乘积最大（编程题25分）
解析代码
思路
1、如果k== n的话，那么全部数字都要选
2、如果k%2== 0(即k为偶数)，那么选出来的一个是非负数
3、如果k%2== 1(即k为奇数)分两种：
（1）如果全部都为负数，那么全部都为负数，把最大最大负数取出来，然后变成了k为偶数的情况，要把符号改变过来
（2）否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来,然后变成了k为偶数的情况。
#include<bits/stdc++.h>
#define x first
#define y second
#define mem1(h) memset(h,-1,sizeof h)
#define mem0(h) memset(h,0,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{inline LL read(){LL o=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}return o*f;}
}using namespace IO;
//#############以上是自定义技巧（可忽略）##########
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+9,P=131;
int n,k;
int a[N];
int main(){cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);int res=1;int l=0,r=n-1;int sign=1;if(k&1){//k为奇数res=a[r--];//取最大的数k--;if(res<0)sign=-1;//如果是最大为负数，要改变符号}while(k){//k为偶数的情况LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];//取最小的两个与最大两个数乘积if(x*sign>y*sign){//看两个数与当前符号相乘哪个大取哪个res=x%mod*res%mod;l+=2;}else{res=y%mod*res%mod;r-=2;}k-=2;}cout<<res<<endl;return 0;
}本篇完。
