題目鏈接：https://ac.nowcoder.com/acm/contest/9162#question
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;
}
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位極有可能會出現問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/226274.html
標籤：其他