题目链接：https://ac.nowcoder.com/acm/contest/9162#question
邀请码：acmwitedu2020
A. 最短逃生距离
当输入和输出的数据总数超过1000个时，建议不直接用C++的输入输出以免超时。
各种写法
# include <stdio.h>
# include <math.h>
int main() {
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", abs(x - y));
}
return 0;
}
第二种：如果不懂原理慎用
# include <iostream>
# include <cmath>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
while (m--) {
int x, y;
std::cin >> x >> y;
std::cout << abs(x - y) << "\n";
}
return 0;
}
第三种：手写输入输出
# include <iostream>
# include <cstdio>
# include <cmath>
template <typename T>
void read(T &val) {
T x = 0;
int bz = 1;
char c;
for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()) ;
if (c == '-') {
bz = -1;
c = getchar();
}
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - 48;
val = x * bz;
}
template <typename T>
void put(T x){
static char ss[20];
int bas;
if(x < 0) {
putchar('-');
x = -x;
}
if(x == (T)(0)) {
putchar('0');
return;
}
bas = 0;
for(;x;x/=10)
ss[bas++] = x % 10 + '0';
for(;bas--;)
putchar(ss[bas]);
}
int main() {
int n, m;
read(n);
read(m);
while (m--) {
int x, y;
read(x);
read(y);
put(abs(x - y));
puts("");
}
return 0;
}
第四种：直接读取数组（如果不懂原理慎用）
# include <iostream>
# include <cstdio>
# include <cmath>
const int BUFSIZE = 20 << 20; //40M
char Buf[BUFSIZE + 1], *buf = Buf;
template<class T>
void read(T &a) {
int sgn = 1;
for(a=0; *buf<'0'||*buf>'9'; buf++) if(*buf=='-') sgn = -1;
while(*buf>='0'&&*buf<='9') {
a=a*10+(*buf-'0');
buf++;
}
a *= sgn;
}
void put(int x) {
static char s[20];
int bas;
if(x < 0) {
putchar('-');
x = -x;
}
if(x == 0) {
putchar('0');
return;
}
bas = 0;
for(; x; x/=10)
s[bas++] = x%10+'0';
for(; bas--;)
putchar(s[bas]);
}
int main() {
fread(Buf, 1, BUFSIZE, stdin);
int n, m;
read(n);
read(m);
while (m--) {
int x, y;
read(x);
read(y);
put(abs(x - y));
printf("\n");
}
return 0;
}
Java写的时候要IO优化
import java.util.*;
import java.io.*;
public class Main {
public static void solve() {
int T = nextInt();
T = nextInt();
while (T-- > 0) {
long a = nextLong();
long b = nextLong();
out.println(Math.abs(a - b));
}
}
public static void main(String[] args) {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
out = new PrintWriter(System.out);
solve();
out.close();
}
static BufferedReader reader;
static StringTokenizer tokenizer;
static PrintWriter out;
static int nextInt(){
return Integer.parseInt(next());
}
static long nextLong(){
return Long.parseLong(next());
}
static double nextDouble(){
return Double.parseDouble(next());
}
static String next(){
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
}
Python没有IO优化的方式，因此输入数据多的时候基本不考虑Python。事实上，打ACM基本上都是用的C++，Java和Python写算法题很容易超时。个人观点，不一定正确
B. spj
这题没有啥好说的，举三个例子，还有其他的写法，随便选一种 （出题人写special judge时忘记验证换行，不换行也放过了。这题不是我出的，甩锅）
# include <cstdio>
int main() {
printf("1\n\kcxz");
return 0;
}
# include <cstdio>
int main() {
printf("2\n\小少爷\n宇少");
return 0;
}
# include <cstdio>
int main() {
printf("2\n宇少\n小少爷");
return 0;
}
C. 突然想到一个算法
看见水群里有人斗图时发了这张图片，所以就拿这张图片当热身题。
方法一： a b ∗ c = ( a b ) c a^{b*c}={(a^b)}^c ab∗c=(ab)c,每一步都快速幂即可。复杂度 O ( l o g ( n ! ) ) ≈ O ( n l o g ( n ) ) O(log(n!))≈O(nlog(n)) O(log(n!))≈O(nlog(n)) (斯特林公式)
# include <stdio.h>
const int mod = 1e9 + 7;
int pow(int x, int p) {
int ans = 1 % mod;
while (p) {
if (p & 1) {
ans = 1ll * ans * x % mod;
}
x = 1ll * x * x % mod;
p >>= 1;
}
return ans;
}
void solve() {
int n;
scanf("%d", &n);
int ans = n;
for (int i = 2; i <= n; i++) {
ans = pow(ans, i);
}
printf("%d\n", ans);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
方法二：欧拉函数
p p p为质数，所以 n n n和 p p p互质，让阶乘模质数的欧拉函数，再快速幂。复杂度 O ( n ) O(n) O(n)
# include <stdio.h>
const int mod = 1e9 + 7;
int phi;
int qpow(int x, int p) {
int ans = 1 % mod;
while (p) {
if (p & 1) {
ans = 1ll * ans * x % mod;
}
x = 1ll * x * x % mod;
p >>= 1;
}
return ans;
}
int fphi(int n) {
int ans = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
ans = ans / n * (n - 1);
}
return ans;
}
void solve() {
int n;
scanf("%d", &n);
int ans = 1;
for (int i = 2; i <= n; i++) {
ans = 1ll * ans * i % phi;
}
printf("%d\n", qpow(n, ans));
}
int main() {
int T;
scanf("%d", &T);
phi = fphi(mod);
while (T--) {
solve();
}
return 0;
}
D. 兀兀的请求
c o s ( π ) = − 1 cos(\pi)=-1 cos(π)=−1， a r c c c o s ( − 1 ) = π arcccos(-1)=\pi arcccos(−1)=π。C语言的库函数里面 a r c c o s ( ) arccos() arccos() 写作 a c o s ( ) acos() acos()。部分编译器 a c o s ( − 1 ) acos(-1) acos(−1)无法通过，需要写成 a c o s ( − 1.0 ) acos(-1.0) acos(−1.0)
# include <stdio.h>
# include <math.h>
typedef long long ll;
int main() {
double ans = acos(-1.0);
ans = ans * 100;
for (int i = 3; i <= 14; i++) {
ans = ans * 10;
ll t = ans;
printf("%lld", t % 10);
}
return 0;
}
用参考公式算到第14位极有可能会出现问题
京公网安备 11010502036488号