一、试题A：第几天
二、试题B： 明码
三、试题C：乘积末零
四、试题D：测试次数
五、试题E：快速排序
六、试题F：递增三元组
七、试题G：螺旋折线
八、试题H：日志统计
九、试题I：全球变暖
十、试题J：乘积最大
一、试题A：第几天
题意：水题
代码如下：
#include<iostream>
using namespace std;
int year[] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int main(){
cout<< 1 + 31 + 29 + 31 + 30 + 3;
return 0;
}二、试题B： 明码
这段信息是（一共10个汉字）：
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4
4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64
16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128
0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0
2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0
1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0
0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0
注意：需要提交的是一个整数，不要填写任何多余内容。
题意：通过给出的字节来转换为汉字，每个汉字为一行字节，两个字节输出一行
这是一道考察进制的题，注意：负数的补码的求法
负数的补码：
1.先求出负数的绝对值的二进制
2.从右到左遍历，遇到第一个1时，将这个1左侧全部取反，右侧和它本身不变
3. eg：01100100 -> 10011100
代码如下：
#include<iostream>
using namespace std;
int a,b;
void show(int n){
bool flag = false;
if(n < 0) flag = true,n = -n;
int z[10];
for(int i = 7; i >= 0; i -- ){
z[i] = n % 2;
n /= 2;
}
if(flag){
for(int i = 7; i >= 0; i --){
if(z[i] == 1){
for(int j = 0; j < i; j ++)
z[j] = 1 - z[j];
break;
}
}
}
for(int i = 0; i <= 7; i ++ ){
if(z[i]) cout<<"*";
else cout<<" ";
}
}
int main(){
for(int i = 1; i <= 10; i ++ ){
for(int j = 1; j <= 16; j ++ ){
cin >> a;
show(a);
cin >> b;
show(b);
puts("");
}
puts("");
}
return 0;
}三、试题C：乘积尾零
题目描述：如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211
注意：需要提交的是一个整数，表示末尾零的个数。不要填写任何多余内容。
解题方法：
方法一：高精度乘法
这么多数相乘可定得用高精度了，但是题目就需要末尾零的个数，所以没必要这样求
代码如下:
#include<iostream>
#include<vector>
using namespace std;
vector<int > mul(vector<int > &a,int b){
vector<int > c;
int t = 0;
for(int i = 0; i < a.size() || t; i ++ ){
if(i < a.size()) t += a[i] * b;
c.push_back(t%10);
t /= 10;
}
while(c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
int main(){
vector<int > res;
res.push_back(1);
int b;
for(int i = 1; i <= 100; i ++ ){
cin >> b;
res = mul(res,b);
}
int cnt = 0;
for(int i = 0; i < res.size(); i ++ ){
if(res[i]) break;
cnt ++;
}
cout<<cnt;
return 0;
}方法二：0是怎么来的
0可定是2和5的乘积得来的，那么我们只需要求出这些数字里面2和5的个数就行了，取最小的那个
注意：不要用do while，原因：do会先做一次，导致答案不对 eg：31 ，也是+1
代码如下：
#include<iostream>
using namespace std;
int n;
int cnt,cnt1,cnt2;
void judge(int n){
int x = n, y = n;
while(x % 2 == 0){
x/=2;cnt1 ++;
};
while(y % 5 == 0){
y/=5;cnt2++;
};
}
int main(){
for(int i = 1; i <= 100; i ++ ){
cin >> n;
judge(n);
}
cnt = min(cnt1,cnt2);
cout<<cnt;
return 0;
}四、试题D：测试次数（待补）
五、试题E：快速排序（待补）
#include <stdio.h>
int quick_select(int a[], int l, int r, int k) {
int p = rand() % (r - l + 1) + l;
int x = a[p];
{int t = a[p]; a[p] = a[r]; a[r] = t;}
int i = l, j = r;
while(i < j) {
while(i < j && a[i] < x) i++;
if(i < j) {
a[j] = a[i];
j--;
}
while(i < j && a[j] > x) j--;
if(i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
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);
}
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;
}
注意：只填写划线部分缺少的代码，不要抄写已经存在的代码或符号。
六、试题F：递增三元组
【输出格式】
一个整数表示答案
【样例输入】
3 1 1 1 2 2 2 3 3 3
【样例输出】
27
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
解题方法:
方法一：暴力求解（TLE）
注意：a[i] < b[j] && b[j] < c[k] 不能写成 a[i] < b[j] < c[k]
这个坑点让你暴力也得不了多少分，样例过了很巧合（不多试试，就会掉坑）
代码如下：
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],c[N];
int n;
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i ++ ) scanf("%d",&a[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&b[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&c[i]);
int cnt = 0;
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 ++;
}
}
}
printf("%d",cnt);
return 0;
}方法二：二分法
1.二分法前提必须是单调函数
2. 在a数组中找出比b数组大于等于的那个数，在它之前就是小于b数组的
3. 在c数组中找出比b数组大于的那个数，在它往后都是比b数组大的了，个数就是n - 它的下标
4. 它俩相乘就为所有的方案
注意：用long long，累加防止爆int
写法一：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int a[N],b[N],c[N];
int n;
ll ans;
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i ++ ) scanf("%d",&a[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&b[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&c[i]);
sort(a,a + n);sort(b,b + n);sort(c,c + n);
for(int i = 0; i < n; i ++ ){
int x = lower_bound(a,a + n,b[i]) - a;
int y = n - (upper_bound(c,c + n,b[i]) - c);
ans += (ll)x * y;
}
printf("%lld",ans);
return 0;
}写法二：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int a[N],b[N],c[N];
int n;
ll ans;
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i ++ ) scanf("%d",&a[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&b[i]);
for(int i = 0; i < n; i ++ ) scanf("%d",&c[i]);
sort(a,a + n);sort(b,b + n);sort(c,c + n);
for(int i = 0,j = 0, k = 0; j < n; j ++ ){
while(i < n && a[i] < b[j]) i ++;
while(k < n && c[k] <= b[j]) k ++;
ans += (ll) i * (n - k);
}
printf("%lld",ans);
return 0;
}七、试题G：螺旋折线
【样例输入】
0 1
【样例输出】
3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
解题思路：
- 先把图中折现转换为几个正方形，正方形的大小为8，16，24，……
- 我们可以把求从原点到(X, Y)的螺旋折线段的长度转换为 它所在正方形的边到左下角顶点的长度+ 之前正方形的大小
- 求左下角顶点到（X，Y）的距离
- 分情况讨论：
- 如果y > x ，在上半部分就加上它俩的距离
- 如果y <= x ，在下半部分就加上这条正方形大小-它俩距离的长度
由于数据较大，全程都用long long 型
- 如果y <= x ，在下半部分就加上这条正方形大小-它俩距离的长度
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int x,y;
ll sum;
int main(){
scanf("%lld %lld",&x,&y);
ll n = max(abs(x),abs(y));
//之前的正方形的和
sum = n * (n - 1) * 4;
ll a = -n, b = -n;
ll d1 = x - a, d2 = y - b;
if(y > x){
sum += d1 + d2;
}else{
sum += 8 * n - d1 - d2;
}
printf("%lld",sum);
return 0;
}八、试题H：日志统计
【输入样例】
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
【输出样例】
1 3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
解题思路：
- 看到N的范围就要想到，时间复杂度不能是N^2
- 用set从大到小排序
- cnt[node[j].id] ++ ： 在这个时间段就+1，后面就不用加了，所以时间复杂度是O(n)
代码如下：
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
struct Node{
int ts,id;
}node[N];
int n,d,k,a,b;
set<int > s;
int cnt[N];
bool cmp(Node a,Node b){
return a.ts < b.ts;
}
int main(){
scanf("%d %d %d",&n,&d,&k);
for(int i = 0; i < n; i ++ ){
scanf("%d %d",&a,&b);
node[i].ts = a;
node[i].id = b;
}
sort(node,node + n,cmp);
for(int i = 0,j = 0; i < n; i ++ ){
while(j < n && node[j].ts - node[i].ts < d){
cnt[node[j].id] ++;
if(cnt[node[j].id] >= k) s.insert(node[j].id);
j ++;
}
cnt[node[i].id]--;
}
for(set<int>::iterator it = s.begin(); it != s.end(); it ++ ){
printf("%d\n",*it);
}
return 0;
}九、试题I：全球变暖
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
....... .##.... .##.... ....##. ..####. ...###. .......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
....... ....... ....... ....... ....#.. ....... .......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7 ....... .##.... .##.... ....##. ..####. ...###. .......
【输出样例】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
解题思路：
- 遍历每一个像素单位，如果遇到一个#就是一个岛屿
- 遇到一个岛屿，就把旁边的#标记一下，放入队列，观察是否有#周围有'.'，如果有的话，它就会被淹没
- 答案就是总共岛屿的个数减去淹没的个数
代码如下：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define PII pair<int,int>
const int N = 1e3 + 10;
int n;
char g[N][N];
bool st[N][N];
int ans;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int bfs(){
int cnt = 0;
queue<PII> q;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < n; j ++ ){
if(!st[i][j] && g[i][j] == '#'){
cnt ++;
bool judge = false;
st[i][j] = true;
q.push({i,j});
while(q.size()){
PII t = q.front();
q.pop();
for(int i = 0; i < 4; i ++ ){
int a = t.first + dx[i];
int b = t.second + dy[i];
if(a < 0 || a > n -1 || b < 0 || b > n-1 || g[a][b] != '#') continue;
if(st[a][b]) continue;
st[a][b] = true;
q.push({a,b});
bool flag = true;
for(int j = 0; j < 4; j ++ ){
int c = a + dx[j];
int d = b + dy[j];
if(g[c][d] == '.') flag = false;
}
if(flag && !judge){
ans ++;judge = true;
}
}
}
}
}
}
return cnt;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> g[i];
int t = bfs();
cout<< t - ans << endl;
return 0;
}十、试题J：乘积最大（待补）
【输入样例】
5 3 -100000 -10000 2 100000 10000
【输出样例】
999100009
再例如：
【输入样例】
5 3 -100000 -100000 -2 -100000 -100000
【输出样例】
-999999829
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。</xxx>
提交程序时，注意选择所期望的语言类型和编译器类型。
京公网安备 11010502036488号