A

題目

這個(gè)沒什么好說的，就先輸出一個(gè) 1，再輸出 $n$ 個(gè) 01就大功告成了。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;cout << 1;for (int i = 1; i <= n; i ++) cout << "01";return 0;
}

B

題目

要獲取更多 $x$ 國貨幣，只能用 $x?1$ 國貨幣換。
所以我們可以從 $1$ 國一直換到 $n$ 國，輸出，結(jié)束。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;
long long a[200100];
int s[200100], t[200100];int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i < n; i ++) cin >> s[i] >> t[i];for (int i = 1; i < n; i ++) {a[i + 1] += t[i] * (a[i] / s[i]);}cout << a[n];return 0;
}

C

題目

你會發(fā)現(xiàn)，$500^3<2?10^8$，所以可以暴力枚舉高橋所在的位置，如果他行進(jìn)的過程中沒有經(jīng)過海洋就將答案加一。如果經(jīng)過海洋了就直接枚舉下一個(gè)點(diǎn)。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int h, w, n;
char m[510][510];
string s;
map<char, int> dir;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
int ans;
bool check(int x, int y) {for (int i = 0; i < n; i ++) {int nx = x + dx[dir[s[i]]], ny = y + dy[dir[s[i]]];if (nx > 0 && nx <= h && ny > 0 && ny <= w && m[nx][ny] == '.') {x = nx;y = ny;}else return 0;}return 1;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> h >> w >> n;cin >> s;for (int i = 1; i <= h; i ++) {for (int j = 1; j <= w; j ++) cin >> m[i][j];}dir['L'] = 0, dir['R'] = 1, dir['U'] = 2, dir['D'] = 3;for (int i = 1; i <= h; i ++) {for (int j = 1; j <= w; j ++) {if (m[i][j] == '.') {ans += check(i, j);}}}cout << ans;return 0;
}

D

題目

這個(gè)題并不難，但是細(xì)節(jié)很多，仔細(xì)看！我因?yàn)橐恍┝闼榈募?xì)節(jié)卡了 40min！

首先，我們先討論那些“有規(guī)律”的部分。我們發(fā)現(xiàn)，對于兩個(gè)數(shù) $n$ 和 $m$，在 $nm$ 范圍內(nèi)有 $n+m?2\times \gcd (n,m)$ 個(gè)數(shù)滿足只被 $n$ 和 $m$ 中的一個(gè)數(shù)字整除。

這個(gè)結(jié)論怎么來的呢？

首先，對于可以被 $n$ 整除的一共有 $\frac{nm}{n}$ 共 $m$ 個(gè)，可以被 $m$ 整除的一共有 $\frac{nm}{m}$ 共 $n$ 個(gè)。

那么 $?2\times \gcd (n,m)$ 又是怎么來的呢？

首先，$nm$ 范圍內(nèi)有 $\frac{nm}{\frac{nm}{\gcd (n,m)}}$ 個(gè)數(shù)即 $\gcd (n,m)$ 個(gè)數(shù)可以被 $n$ 和 $m$ 整除。我們要在可以被 $n$ 整除的部分減去它，還要在可以被 $m$ 整除的部分減去它。所以是 $?2\times \gcd (n,m)$。

然后我們就可以將答案直接跳到 $nm(k/(n+m?2\gcd (n,m)))$，此時(shí) $k$ 變成 $k\mathrm{mod}(n+m?2\gcd (n,m))$。

我們繼續(xù)討論，可以枚舉，用 $k1$ 和 $k2$ 兩個(gè)變量依次跳到答案。如果 $k1$ 跳的遠(yuǎn)就跳 $k2$，否則跳 $k1$。如果兩個(gè)跳的一樣遠(yuǎn)就都跳依次，這兩次不算在跳的次數(shù)內(nèi)。一共跳 $k$ 次后，較大的就是滿足條件的，加到答案上即可。

你以為這就完了？

如果減掉前面“有規(guī)律”的部分后，發(fā)現(xiàn) $k$ 等于 $0$ 時(shí)，不加任何特判會輸出一個(gè) $nm$ 的倍數(shù)的數(shù)。但是我們要的是最大的比上述不合法答案小的答案。此時(shí)如果我們把 $k$ 設(shè)為 $n+m?2\gcd (n,m)$，答案減去 $nm$ 就可以解決這個(gè)問題。

還有一個(gè)很重要的東西：long long！

時(shí)間復(fù)雜度分析：

按最壞情況來說，$\gcd (n,m)=1$，此時(shí)時(shí)間復(fù)雜度就是 $n+m$，而且跑不到這么多，所以執(zhí)行次數(shù)不會超過 $2?10^8$，合格。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long n, m, k;
long long gcd(long long x, long long y) {return x % y == 0ll ? y : gcd(y, x % y);
}
long long ans;
long long cnt;
long long cnt1;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;long long g = gcd(n, m);ans = n * m * (k / (n + m - g * 2));k = k % (n + m - g * 2);if (k == 0) {ans -= n * m;k += n + m - g * 2;}long long k1 = 0ll, k2 = 0ll;cnt1 = 0ll;for (long long i = 1; i <= k; i ++) {if (k1 + n < k2 + m) {k1 += n;}else if (k1 + n > k2 + m) {k2 += m;}else {k1 += n;k2 += m;i--;}}ans += max(k1, k2);cout << ans;return 0;
}

E

什么，不是 A-D題解嗎？怎么還有 E？

我才不會給出詳細(xì)的解法的，我只給一個(gè)小小的提示：懶標(biāo)線段樹！