ABC203 A~E
- [A - Chinchirorin](https://atcoder.jp/contests/abc203/tasks/abc203_a)
-
- 題目大意
- 輸入格式
- 輸出格式
- 樣例
- 分析
- 代碼
- [B - AtCoder Condominium](https://atcoder.jp/contests/abc203/tasks/abc203_b)
-
- 題目大意
- 輸入格式
- 輸出格式
- 樣例
- 分析
- 代碼
- [C - Friends and Travel costs](https://atcoder.jp/contests/abc203/tasks/abc203_c)
-
- 題目大意
- 輸入格式
- 輸出
- 樣例
-
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 樣例輸入3
- 樣例輸出3
- 分析
- 代碼
- [D - Pond](https://atcoder.jp/contests/abc203/tasks/abc203_d)
-
- 題目大意
- 輸入格式
- 輸出格式
- 樣例
-
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 分析
- 代碼
- [E - White Pawn](https://atcoder.jp/contests/abc203/tasks/abc203_e)
-
- 題目大意
- 輸入格式
- 輸出格式
- 樣例
-
- 樣例輸入1
- 樣例輸出1
- 樣例輸入2
- 樣例輸出2
- 分析
- 代碼
A - Chinchirorin
題目大意
給定三個整數 a , b , c a,b,c a,b,c，如果它們中有兩個相等，輸出另一個；否則，輸出 0 0 0。
1 ≤ a , b , c ≤ 6 1\le a,b,c\le 6 1≤a,b,c≤6
輸入格式
a b c a~b~c a b c
輸出格式
如果 a , b , c a,b,c a,b,c中有兩個相等，輸出另一個；否則，輸出 0 0 0。
樣例
| a a a | b b b | c c c | 輸出 |
|---|---|---|---|
| 2 2 2 | 5 5 5 | 2 2 2 | 5 5 5 |
| 4 4 4 | 5 5 5 | 6 6 6 | 0 0 0 |
| 1 1 1 | 1 1 1 | 1 1 1 | 1 1 1 |
分析
A A A題還是一如既往的水……直接暴力判斷三種相等的情況即可。
代碼
#include <cstdio>
using namespace std;
int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a == b) printf("%d\n", c);
else if(b == c) printf("%d\n", a);
else if(a == c) printf("%d\n", b);
else puts("0");
return 0;
}
B - AtCoder Condominium
題目大意
給定 N N N和 K K K，求 ∑ i = 1 N ∑ j = 1 K i 0 j ‾ \sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j} i=1∑Nj=1∑Ki0j。
1 ≤ N , K ≤ 9 1\le N,K\le 9 1≤N,K≤9
輸入格式
N K N~K N K
輸出格式
輸出 ∑ i = 1 N ∑ j = 1 K i 0 j ‾ \sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j} i=1∑Nj=1∑Ki0j。
樣例
| N N N | K K K | 輸出 |
|---|---|---|
| 1 1 1 | 2 2 2 | 203 203 203 |
| 3 3 3 | 3 3 3 | 1818 1818 1818 |
分析
本題可以直接暴力，但我使用的是如下 O ( 1 ) \mathcal O(1) O(1)算法：
根據 i 0 j ‾ = 100 i + j \overline{i0j}=100i+j i0j=100i+j且 1 + 2 + ⋯ + N = N ( N + 1 ) 2 1+2+\dots+N=\frac{N(N+1)}2 1+2+⋯+N=2N(N+1)，則有如下推導：
- ∑ i = 1 N ∑ j = 1 K i 0 j ‾ = ∑ i = 1 N ∑ j = 1 K 100 i + ∑ i = 1 N ∑ j = 1 K j \sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}=\sum\limits_{i=1}^N\sum\limits_{j=1}^K 100i+\sum\limits_{i=1}^N\sum\limits_{j=1}^K j i=1∑Nj=1∑Ki0j=i=1∑Nj=1∑K100i+i=1∑Nj=1∑Kj
- ∑ i = 1 N ∑ j = 1 K 100 i = ∑ i = 1 N 100 i K = 100 K ∑ i = 1 N i = 100 N ( N + 1 ) K 2 \sum\limits_{i=1}^N\sum\limits_{j=1}^K 100i=\sum\limits_{i=1}^N 100iK=100K\sum\limits_{i=1}^N i=\frac{100N(N+1)K}2 i=1∑Nj=1∑K100i=i=1∑N100iK=100Ki=1∑Ni=2100N(N+1)K
- ∑ i = 1 N ∑ j = 1 K j = ∑ i = 1 N K ( K + 1 ) 2 = K ( K + 1 ) N 2 \sum\limits_{i=1}^N\sum\limits_{j=1}^K j=\sum\limits_{i=1}^N\frac{K(K+1)}2=\frac{K(K+1)N}2 i=1∑Nj=1∑Kj=i=1∑N2K(K+1)=2K(K+1)N
- ∑ i = 1 N ∑ j = 1 K i 0 j ‾ = 100 N ( N + 1 ) K 2 + K ( K + 1 ) N 2 = 100 N ( N + 1 ) K + K ( K + 1 ) N 2 \sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}=\frac{100N(N+1)K}2+\frac{K(K+1)N}2=\frac{100N(N+1)K+K(K+1)N}2 i=1∑Nj=1∑Ki0j=2100N(N+1)K+2K(K+1)N=2100N(N+1)K+K(K+1)N
這樣，我們就可以直接通過公式 100 N ( N + 1 ) K + K ( K + 1 ) N 2 \frac{100N(N+1)K+K(K+1)N}2 2100N(N+1)K+K(K+1)N計算出結果了。
代碼
#include <cstdio>
using namespace std;
inline int sum(int x) { return x * (x + 1) >> 1; }
int main()
{
int n, k;
scanf("%d%d", &n, &k);
printf("%d\n", sum(n) * k * 100 + sum(k) * n);
return 0;
}
C - Friends and Travel costs
題目大意
有 1 0 100 + 1 10^{100}+1 10100+1個村莊，分别為村莊 0 , 1 , … , 1 0 100 0,1,\dots,10^{100} 0,1,…,10100，相鄰兩個村莊之間的過路費是 1 1 1元。
Taro一開始有 K K K元且在村莊 0 0 0。他想要到達編号盡可能大的村莊。
他有 N N N個朋友。第 i i i個朋友會在Taro到達村莊 A i A_i Ai時給他 B i B_i Bi元。
求Taro最後到達的村莊的編号。
1 ≤ N ≤ 2 × 1 0 5 1\le N\le 2\times10^5 1≤N≤2×105
1 ≤ K ≤ 1 0 9 1\le K\le 10^9 1≤K≤109
1 ≤ A i ≤ 1 0 18 1\le A_i\le 10^{18} 1≤Ai≤1018
1 ≤ B i ≤ 1 0 9 1\le B_i\le 10^9 1≤Bi≤109
輸入格式
N K N~K N K
A 1 B 1 A_1~B_1 A1 B1
A 2 B 2 A_2~B_2 A2 B2
… \dots …
A N B N A_N~B_N AN BN
輸出
輸出Taro最後到達的村莊的編号。
樣例
樣例輸入1
2 3
2 1
5 10
樣例輸出1
樣例輸入2
5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
樣例輸出2
請不要使用 32 32 32位整數。
樣例輸入3
3 2
5 5
2 1
2 2
樣例輸出3
Taro在一個村莊可能有多個朋友。
分析
根據題目中的資料範圍，我們可以證明答案嚴格小于 2 64 2^{64} 264，是以我們使用
unsigned long long
作為存儲資料類型。
可是，由于村莊數量還是太多，我們仍然無法依次模拟到達每個村莊。
我們發現 N N N較小，是以我們可以從朋友的角度考慮。
我們可以按 A i A_i Ai排序所有朋友（ B i B_i Bi的順序不重要），這樣就能把整個行程形成分成若幹個區間，并依次判斷每個區間是否能走完即可。
代碼
注意：我這裡排序使用的是優先隊列（
priority_queue
）。
#include <cstdio>
#include <queue>
#define maxn 200005
#define INF 18446744073709551615ULL
using namespace std;
using ULL = unsigned long long;
using pll = pair<ULL, ULL>;
int main()
{
int n;
ULL k;
scanf("%d%llu", &n, &k);
priority_queue<pll, vector<pll>, greater<pll> > q;
for(int i=0; i<n; i++)
{
ULL a, b;
scanf("%llu%llu", &a, &b);
q.emplace(a, b);
}
ULL lastv = 0ULL;
q.emplace(INF, 0ULL);
while(!q.empty())
{
auto [a, b] = q.top(); q.pop();
ULL cost = a - lastv;
if(k < cost)
{
printf("%llu\n", lastv + k);
return 0;
}
k -= cost;
lastv = a, k += b;
}
return 0;
}
D - Pond
題目大意
給定一個 N × N N\times N N×N的正方形矩陣 A A A，第 i i i行第 j j j列的元素是 A i , j A_{i,j} Ai,j。
求 A A A中所有的 K × K K\times K K×K的子矩陣的中間值的最小值。
一個 K × K K\times K K×K的正方形的中間值為其中第 ( ⌊ K 2 2 ⌋ + 1 ) (\left\lfloor\frac{K^2}2\right\rfloor+1) (⌊2K2⌋+1)大的值。
1 ≤ K ≤ N ≤ 800 1\le K\le N\le 800 1≤K≤N≤800
1 ≤ A i , j ≤ 1 0 9 1\le A_{i,j}\le 10^9 1≤Ai,j≤109
如果不能了解題意，請看下圖：
對應的輸入輸出：
3 2
5 9 8
2 1 3
7 4 6
/
輸入格式
N K N~K N K
A 1 , 1 A 1 , 2 … A 1 , N A_{1,1}~A_{1,2}~\dots~A_{1,N} A1,1 A1,2 … A1,N
A 2 , 1 A 2 , 2 … A 2 , N A_{2,1}~A_{2,2}~\dots~A_{2,N} A2,1 A2,2 … A2,N
A N , 1 A N , 2 … A N , N A_{N,1}~A_{N,2}~\dots~A_{N,N} AN,1 AN,2 … AN,N
輸出格式
輸出答案。
樣例
樣例輸入1
3 2
1 7 0
5 8 11
10 4 2
樣例輸出1
N = 3 K = 2 A = [ 1 7 0 5 8 11 10 4 2 ] N=3~~~~~K=2\\ A=\begin{bmatrix} 1 & 7 & 0\\ 5 & 8 & 11\\ 10 & 4 & 2 \end{bmatrix} N=3 K=2A=⎣ ⎡15107840112⎦ ⎤
我們有四個 2 × 2 2\times2 2×2的正方形： { 8 , 7 , 5 , 1 } , { 11 , 8 , 7 , 0 } , { 10 , 8 , 5 , 4 } , { 11 , 8 , 4 , 2 } \{8, 7, 5, 1\}, ~\{11,8,7,0\},~ \{10,8,5,4\}, ~\{11,8,4,2\} {8,7,5,1}, {11,8,7,0}, {10,8,5,4}, {11,8,4,2}。
我們依次從每個的元素中取第 ⌊ K 2 2 ⌋ + 1 = 3 \left\lfloor\frac{K^2}2\right\rfloor+1=3 ⌊2K2⌋+1=3大的： { 5 , 7 , 5 , 4 } \{5,7,5,4\} {5,7,5,4}
最後，我們從 { 5 , 7 , 5 , 4 } \{5,7,5,4\} {5,7,5,4}中選出最小的： 4 4 4。
樣例輸入2
3 3
1 2 3
4 5 6
7 8 9
樣例輸出2
分析
本題可以二分答案。我們判定一個數是否為一個 K × K K\times K K×K的正方形的中間值時，隻需要計算這個正方形内嚴格大于這個數的數的個數是否為 ⌊ K 2 2 ⌋ \left\lfloor\frac{K^2}2\right\rfloor ⌊2K2⌋即可。
是以，我們可以使用矩陣字首和快速計算一個正方形内嚴格大于一個數的數的數的個數。
總時間複雜度 O ( n 2 log max { A } ) \mathcal O(n^2\log\max\{A\}) O(n2logmax{A})。
代碼
#include <cstdio>
#define maxn 805
#define INF 2147483647
using namespace std;
int a[maxn][maxn], dp[maxn][maxn], n, k, target;
inline int count(int x1, int y1, int x2, int y2)
{
return dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
inline bool check(int x)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (a[i][j] > x);
for(int x2=k; x2<=n; x2++)
for(int y2=k; y2<=n; y2++)
{
int x1 = x2 - k + 1, y1 = y2 - k + 1;
if(count(x1, y1, x2, y2) < target)
return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &k);
target = (k * k >> 1) + 1;
int l = INF, r = 0, ans = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
scanf("%d", a[i] + j);
if(a[i][j] > r) r = a[i][j];
if(a[i][j] < l) l = a[i][j];
}
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
E - White Pawn
題目大意
有一個 ( 2 N + 1 ) × ( 2 N + 1 ) (2N+1)\times(2N+1) (2N+1)×(2N+1)的正方形棋盤，行數、列數下标都依次從 0 0 0到 2 N 2N 2N。我們用 ( i , j ) (i,j) (i,j)表示棋盤上 i i i行 j j j列的位置。
我們有一顆棋子，初始位置在 ( 0 , N ) (0,N) (0,N)。棋盤上有 M M M個黑方格，第 i i i個的位置在 ( X i , Y i ) (X_i,Y_i) (Xi,Yi)，其餘都是白方格。
當棋子在 ( i , j ) (i,j) (i,j)時，你可以執行任意下列操作，但不能移出棋盤：
- ( i + 1 , j ) (i+1,j) (i+1,j)是白色時，移到 ( i + 1 , j ) (i+1,j) (i+1,j)；
- ( i + 1 , j − 1 ) (i+1,j-1) (i+1,j−1)是黑色時，移到 ( i + 1 , j − 1 ) (i+1,j-1) (i+1,j−1)。
- ( i + 1 , j + 1 ) (i+1,j+1) (i+1,j+1)是黑色是，移到 ( i + 1 , j + 1 ) (i+1,j+1) (i+1,j+1)。
棋盤上的方格不能移動。求棋盤的最後一行的能到達的列的個數。
1 ≤ N ≤ 1 0 9 1\le N\le 10^9 1≤N≤109
0 ≤ M ≤ 2 × 1 0 5 0\le M\le 2\times 10^5 0≤M≤2×105
1 ≤ X i ≤ 2 N 1\le X_i\le 2N 1≤Xi≤2N
0 ≤ Y i ≤ 2 N 0\le Y_i\le 2N 0≤Yi≤2N
( X i , Y i ) (X_i,Y_i) (Xi,Yi)互不相等。
輸入格式
N M N~M N M
X 1 Y 1 X_1~Y_1 X1 Y1
X 2 Y 2 X_2~Y_2 X2 Y2
⋮ \vdots ⋮
X M Y M X_M~Y_M XM YM
輸出格式
輸出棋盤的最後一行的能到達的列的個數。
樣例
樣例輸入1
2 4
1 1
1 2
2 0
4 2
樣例輸出1
我們可以将棋子移動到 ( 4 , 0 ) (4,0) (4,0)、 ( 4 , 1 ) (4,1) (4,1)和 ( 4 , 2 ) (4,2) (4,2)，如下：
- ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 4 , 2 ) (0,2)\to(1,1)\to(2,1)\to(3,1)\to(4,2) (0,2)→(1,1)→(2,1)→(3,1)→(4,2)
- ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 4 , 1 ) (0,2)\to(1,1)\to(2,1)\to(3,1)\to(4,1) (0,2)→(1,1)→(2,1)→(3,1)→(4,1)
- ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 0 ) → ( 3 , 0 ) → ( 4 , 0 ) (0,2)\to(1,1)\to(2,0)\to(3,0)\to(4,0) (0,2)→(1,1)→(2,0)→(3,0)→(4,0)
我們不能移動到 ( 4 , 3 ) (4,3) (4,3)或 ( 4 , 4 ) (4,4) (4,4)，是以輸出 3 3 3。
樣例輸入2
1 1
1 1
樣例輸出2
我們無法移動棋子。
分析
我們發現，當 N N N較大時，大多數行多是空着的，是以我們從每個 X i X_i Xi開始考慮。對于白色的位置 ( i , j ) (i,j) (i,j)，如果不能到達 ( i − 1 , j ) (i-1,j) (i−1,j)，則不能到達 ( i , j ) (i,j) (i,j)。相反，對于黑色的 ( i , j ) (i,j) (i,j)，如果能到達 ( i − 1 , j − 1 ) (i-1,j-1) (i−1,j−1)或 ( i − 1 , j + 1 ) (i-1,j+1) (i−1,j+1)，則能到達 ( i , j ) (i,j) (i,j)。
是以，我們先排序每個 ( X i , Y i ) (X_i,Y_i) (Xi,Yi)，再對于每個有黑色的行，用
set
維護能到達的列數，再按上述方法判斷即可。
代碼
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#pragma GCC optimize("Ofast")
using namespace std;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
vector<pair<int, int> > black;
black.reserve(m);
while(m--)
{
int x, y;
scanf("%d%d", &x, &y);
black.emplace_back(x, y);
}
m = black.size();
sort(black.begin(), black.end());
set<int> cols;
cols.insert(n);
for(int l=0, r=0; l<m; l=r)
{
while(r < m && black[r].first == black[l].first) r ++;
vector<int> rem, add;
for(int i=l; i<r; i++)
{
int y = black[i].second;
bool ok = cols.count(y - 1) || cols.count(y + 1);
if(cols.count(y))
{
if(!ok)
rem.push_back(y);
}
else if(ok)
add.push_back(y);
}
for(int y: rem) cols.erase(y);
for(int y: add) cols.insert(y);
}
printf("%llu\n", cols.size());
return 0;
}
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)