第一题 (https://ac.nowcoder.com/acm/contest/67238/A)
直接输出即可
#include <iostream>
using namespace std;
int main() {
cout << "All in!";
return 0;
}
print('All in!')
复杂度分析：
时间复杂度：O(1)
空间复杂度：O(1)
第三题 (https://ac.nowcoder.com/acm/contest/67238/C)
考察乘法，输出乘积
注意：
1. c++要留心数据范围，这题要long long
2. 题目输出值为整数
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n * 3156 * 10000;
return 0;
}
print(int(input()) * 3156 * 10 ** 4)
时间复杂度：O(1)
空间复杂度：O(1) 只用了一个变量
第五题 (https://ac.nowcoder.com/acm/contest/67238/E)
题目只要求写核心代码，下文亦如此
先看数据范围 1 <= n <= 1000 ,先想想模拟。初始化答案 ans = 0
对于从 1 到 n 的每一个数 i 求它的因子之和 s，当 s / i < 2 时，加入答案
小优化：
1.肯定是 i 的 因子，初始化 s = 1
2.s / i 可能为小数，不妨写成 s < 2 * i
int doQuestion(int n) {
int ans = 0;
for(int i = 1; i <= n; i += 1)
{
int s = 1;
for(int j = 2; j <= i; j += 1)
{
if(i % j == 0) s += j;
}
if(s < 2 * i) ans += i;
}
return ans;
}
def doQuestion(self , n ):
ans = 0
for i in range(1, n + 1):
s = 1
for j in range(2, i + 1):
if i % j == 0:
s += j
if s < 2 * i:
ans += i
return ans
时间复杂度：O(n ^ 2) n 个数，第 i 个数遍历 i 次
空间复杂度：O(1) 只用了几个变量而已
第七题
举个栗子，n = 12345 可拆分为：
1 * 2345 = n / 10000 * (n - n / 10000 * 10000)
12 * 345 = n / 1000 * (n - n / 1000 * 1000)
123 * 45 = n / 100 * (n - n / 100 * 100)
1234 * 5 = n / 10 * (n - n / 10 * 10)
每个5位数都可以拆分为上面四个数之和，对于上面四个等式右边要乘或除的数字都是相同的，不妨先设一个数组nums ={10,100,1000,10000}
对于python 可以切片
#include <iostream>
using namespace std;
int main() {
int nums[] = {10,100,1000,10000};
for(int i = 10000; i < 100000; i += 1)
{
int s = 0;
for(int j = 3; j >= 0; j -= 1)
{
s += i / nums[j] * (i - i / nums[j] * nums[j]);
}
if(s == i) cout << i << " ";
}
return 0;
}
for i in range(10000, 100000):
ss = str(i)
s = 0
for j in range(1, 5):
s += int(ss[0:j]) * int(ss[j:])
if s == i:
print(i, end = " ")
时间复杂度：O(T * n) n = 100000 - 10000 + 1, T = 4：每个数要求四个和式
空间复杂度：O(1) 只用了几个变量而已
第九题 (https://ac.nowcoder.com/acm/contest/67238/I)
阅读理解题
1 <= n <= 10, 1 <= m <= 10 数据范围很小
当 k = 1 时，求离的最远的敌方棋子编号，当 k = 0 时，求离的最近的敌方棋子编号，距离相等时取编号小的
对每个棋子求答案时,为了编码量小，在求棋子于敌方棋子距离是记录最远和最近敌方棋子编号
小技巧：求最小，将变量初始化尽可能大，反之尽可能小
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int m, n;
cin >> n >> m;
// n 是 我方 m 是敌方
vector<vector<int>>a(n, vector<int>(3));
vector<vector<int>>b(m, vector<int>(3));
for(int i = 0; i < n; i += 1)
{
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
for(int i = 0; i < m; i += 1)
{
cin >> b[i][0] >> b[i][1] >> b[i][2];
}
// a 是我方 b 是 敌方
vector<int>ansa(n);
vector<int>ansb(m);
// n 个我方答案
for(int i = 0; i < n; i += 1)
{
int x = a[i][0], y = a[i][1], k = a[i][2];
// m 个敌方距离
int mn = 1000, mx = -1;
int idmn = 0, idmx = 0;
for(int j = 0; j < m; j += 1)
{
int xx = b[j][0], yy = b[j][1];
int dis = (xx - x) * (xx - x) + (yy - y) * (yy - y);
if(dis > mx)
{
mx = dis;
idmx = j + 1;
}
if(dis < mn)
{
mn = dis;
idmn = j + 1;
}
}
if(k) ansa[i] = idmx;
else ansa[i] = idmn;
}
// m 个敌方答案
for(int i = 0; i < m; i += 1)
{
int x = b[i][0], y = b[i][1], k = b[i][2];
//n 个敌方距离
int mn = 1000, mx = -1;
int idmn = 0, idmx = 0;
for(int j = 0; j < n; j += 1)
{
int xx = a[j][0], yy = a[j][1];
int dis = (xx - x) * (xx - x) + (yy - y) * (yy - y);
if(dis > mx)
{
mx = dis;
idmx = j + 1;
}
if(dis < mn)
{
mn = dis;
idmn = j + 1;
}
}
if(k) ansb[i] = idmx;
else ansb[i] = idmn;
}
//不会溢出
for(int i = 0; i < n; i += 1)
{
cout << ansa[i] << " ";
}
cout << endl;
for(int i = 0; i < m; i += 1)
{
cout << ansb[i] << " ";
}
return 0;
}
n, m = map(int, input().split(" "))
a = [[0] * 3 for _ in range(n)]
b = [[0] * 3 for _ in range(m)]
for i in range(n):
a[i][0], a[i][1], a[i][2] = map(int, input().split(" "))
for i in range(m):
b[i][0], b[i][1], b[i][2] = map(int, input().split(" "))
ansa = [0] * n
ansb = [0] * m
for j in range(n):
x, y, k = a[j][0], a[j][1], a[j][2]
dis = [[0] * 2 for _ in range(m)]
for i in range(m):
xx = b[i][0]
yy = b[i][1]
dis[i][0] = (x - xx) ** 2 + (y - yy) ** 2
dis[i][1] = i + 1
if k:
dis.sort(key = lambda x: (-x[0],x[1]))
ansa[j] = dis[0][1]
else:
dis.sort(key = lambda x: (x[0],x[1]))
ansa[j] = dis[0][1]
for j in range(m):
x, y, k = b[j][0], b[j][1], b[j][2]
dis = [[0] * 2 for _ in range(n)]
for i in range(n):
xx = a[i][0]
yy = a[i][1]
dis[i][0] = (x - xx) ** 2 + (y - yy) ** 2
dis[i][1] = i + 1
if k:
dis.sort(key = lambda x: (-x[0],x[1]))
ansb[j] = dis[0][1]
else:
dis.sort(key = lambda x: (x[0],x[1]))
ansb[j] = dis[0][1]
for x in ansa:
print(x, end = " ")
print(" ")
for x in ansb:
print(x, end = " ")
京公网安备 11010502036488号