1208. 翻硬币(1月18日)
分析
長度100, 如果用dfs, 每個狀态有2種, 2^100, 必定逾時
需要想額外的方法去做
觀察下一些性質
長度是n的話, 一共可以進行的操作n - 1種, 第1次操作前兩個, 以此類推
能夠改變第1個位置, 其實隻有1種, 而且發現n - 1種操作有以下性質
- 操作順序沒影響
- 每個操作最多1次, 操作2次等于沒有操作
可以列下清單
| 操作清單 | 1 | 2 | … | n - 1 |
|---|---|---|---|---|
| 能否操作 | 第1硬币與目标狀态是否相同: 相同1, 不同0 |
是以第1個狀态是唯一确定的
樣例模拟:
o * o o * o *
* o o o * * o
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 |
- 第一個位置不一樣(翻轉)
翻轉前:
o * o o * o *
* o o o * * o
翻轉後:
* o o o * o *
* o o o * * o
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ |
- 第2個硬币(因為第一個硬币已經操作過, 此時能影響第2個硬币的狀态隻有2), 因為狀态相同, 必然不能做翻轉
翻轉前後:
* o o o * o *
* o o o * * o
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ | ❌ |
- 看下第3個硬币, 此時能夠影響第3個硬币的操作隻有3
翻轉前:
* o o o * o *
* o o o * * o
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ | ❌ | ❌ |
相同不能做
- 相同不能做
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ | ❌ | ❌ | ❌ |
- 相同不能做
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ | ❌ | ❌ | ❌ | ❌ |
- 不同, 必須做
| 操作清單 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 能否操作 | ☑️ | ❌ | ❌ | ❌ | ❌ | ☑️ |
答案保證一定有解, 是以做完前6個操作以後, 最後一個硬币狀态必然相同, 如果不同的話, 一定無解
因為如果最後兩個硬币狀态不同, 此時前面的操作被唯一确定, 能夠影響最後一個硬币的操作已經沒有了, 是以如果最後一個硬币狀态不同, 就一定無解
是以最後一個狀态不用枚舉, 答案保證一定有解, 是以最後一個硬币狀态一定相同
發現每個操作序列被唯一确定的, 然後從前往後遞推下, 看下每個操作沒有被做, 統計下操作次數
關聯題
八數位
code
#include <iostream>
using namespace std;
const int N = 110;
string a, b;
void turn(int x){
if (a[x] == 'o') a[x] = '*';
else a[x] = 'o';
}
int main(){
cin >> a >> b;
int res = 0;
for (int i = 0; i + 1 < a.size(); i ++ ){ // 隻需要枚舉到倒數第2個字元, 最後一個字元答案保證有解, 不需要判斷, 必然相同
if (a[i] != b[i]){
turn(i), turn(i + 1);
res ++;
}
}
cout << res << endl;
return 0;
}
1532. 找硬币 (1月19日)
分析(hash表)
code(hash表, 不開數組) O(n)
#include <iostream>
#include <unordered_set>
using namespace std;
const int INF = 100010;
int n, m;
int main(){
scanf("%d%d", &n, &m);
unordered_set<int> S;
int v1 = INF, v2;
for (int i = 0; i < n; i ++ ){
int a, b;
scanf("%d", &a);
b = m - a;
if (S.count(b)){
S.insert(a);
if (a > b) swap(a, b);
if (a < v1) v1 = a, v2 = b;
}
else S.insert(a);
}
if (v1 == INF) puts("No Solution");
else printf("%d %d\n", v1, v2);
return 0;
}
n 0;
}
分析(雙指針)
是以先将數組排序
對于每個
i
都要找到和它配對的
j
, 使得a[i] + a[j] <= m, 且j最大
定義完後, 如果存在a[i] + a[j] = m的話, 因為上述定義是j最大, 并且數組是拍完序的, 越往後越大, 是以通過上面的方式一定能夠找到 a[i] + a[j] = m
當 i —> 往後走的時候, <—j隻會往前走, 那麼就可以用雙指針算法, 否則不可以
證明(單調性)
i—> i’得時候, 假如j —>j’ 往後走了
那麼a[i] + a[j] <= m(藍色線) , a[i’] + a[j’] <= m(藍色線),
那麼a[i] + a[j’] <= a[i’] + a[j’] <= m (紅色線)
那麼說明與i比對得應該是j’與, 假設沖突
code(雙指針, 需要單調性)(O(nlogn))
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
sort(w, w + n);
for (int i = 0, j = n - 1; i < j; i ++ ){
while (i < j && w[i] + w[j] > m) j --;
if (i < j && w[i] + w[j] == m) {
printf("%d %d", w[i], w[j]);
return 0;
}
}
puts("No Solution");
return 0;
}
1341. 十三号星期五(1月20日)
分析
通用的做法, 就是一般的星期的做法, 就是枚舉天
400年 * 360天 ~= 1.2 ∗ 1 0 5 1.2*10^5 1.2∗105
另外的話可以枚舉月
400年 * 12月 = 4800次
枚舉每個月份第1天 距離1900-1-1過了多少天
1900-1-1 距離1900-1-1 過了0天
1900-2-1 距離1900-1-1 過了31天( 1月31 - 1月1 = 30, 再+1 = 31)
1900-3-1 距離1900-1-1 過了31 + 28 = 59天
目前年的某個月距離 1900-1-1 過了days天的話,
那麼目前月的 13号 距離1900-1-1過了 days + 12天 (13 - 1 = 12天)
起點的話是星期一, 那麼days + 12是周幾呢(7天一循環)
(days + 12) % 7 == 0 (周一) 以此類推
剩下的關鍵: 就是求每個月的1-1 到1900-1-1過了多少天
直接枚舉, 從1900開始 一年一年枚舉
對于某一年的話, 枚舉每個月的1月1号過了多少天
判斷下閏年和平年
閏年:
- 100 不能整除年份的話, 4| 年份 (2020☑️)
- 100 | year, 400 | year (1900❌, 2000☑️)
for 年 (用一個變量表示目前距離起點過了多少天days)
for 每個月
(内層循環, 将days+内層循環的天數)
為了寫代碼友善判斷出來, 每個月有多少天, 可以開個數組記錄下每個月多少天
month[] = {0, 31, 27, 31, 30}; // 前面補個0, 因為數組從0開始
month[5] 直接求出5月多少天
int weekend[7]
表示每個星期幾有多少天, 下标0-周一, 1-周二
code
#include <iostream>
using namespace std;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekend[7];
int n;
int main(){
scanf("%d", &n);
int days = 0; // 記錄目前年目前月距離1900-1-1過了多少天
for (int year = 1900; year < 1900 + n; year ++ ){
for (int i = 1; i <= 12; i ++ ){
weekend[(days + 12) % 7] ++;
days += month[i];
if (i == 2){
if (year % 100 && year % 4 == 0 || year % 400 == 0) days ++;
}
}
}
for (int i = 5, j = 0; j < 7; j ++) // 從5開始 j枚舉7次
cout << weekend[(i + j) % 7] << ' ';
cout << endl;
return 0;
}
754. 平方矩陣 II(1月21日)
分析(對角線)
從對角線開始, 分别往右邊/下邊 延伸
code
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], n;
int main(){
while (cin >> n, n){
for (int i = 1; i <= n; i ++ )
for (int j = i, k = 1; j <= n; j ++, k ++ ){ // j從對角線開始
a[i][j] = k; // 向右延伸
a[j][i] = k;// 行變動, 列不變, 向下延伸
}
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ )
cout << a[i][j] << ' ';
cout << endl;
}
cout << endl;
}
return 0;
}
分析(找規律)
每一行, 對角線之前的部分是從大到小, 對角線之後的部分從小到大
這樣做的話, 直接按行枚舉
比如
1 2 3 4
2 1 2 3 第2行, 第1個數就是2, 然後一直遞減到1
3 2 1 2 第3行, 第1個數就是3, 然後一直遞減到1, 1後面的2, j - i + 1
4 3 2 1
code
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], n;
int main(){
while (cin >> n, n){
for (int i = 1; i <= n; i ++ ){
for (int j = i; j >= 1; j -- ) cout << j << ' ';
for (int j = i + 1; j <= n; j ++ ) cout << j - i + 1 << ' ';
cout << endl;
}
cout << endl;
}
return 0;
}
1432. 棋盤挑戰(1月22日)
分析
類似八皇後
題目的意思是cnt > 3就不用輸出方案了
是以用
cnt
記錄下個數, 然後判斷下
cnt
code
#include <iostream>
using namespace std;
const int N = 50;
int col[N], row[N], udg[N], dg[N];
int cnt;
int n;
int path[N];
void dfs(int u){// u表示目前掃描到第u行。
if (u == n + 1) {
cnt ++;
if (cnt > 3) return ;
for (int i = 1; i <= n; i ++ ) cout << path[i] << ' ';
cout << endl;
}
for (int i = 1; i <= n; i ++ )
if (!col[i] && !udg[i - u + n] && !dg[i + u]){
path[u] = i;
col[i] = udg[i - u + n] = dg[i + u] = 1;
dfs(u + 1);
col[i] = udg[i - u + n] = dg[i + u] = 0;
path[u] = 0;
}
}
int main(){
cin >> n;
dfs(1);
cout << cnt << endl;
return 0;
}
1371. 貨币系統(1月23日)
分析
完全背包問題(與基礎班整數劃分問題相同)
code
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
LL a[N], f[N];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
f[0] = 1;
for (int i = 0; i < n; i ++ )
for (int j = a[i]; j <= m; j ++ )
f[j] = (f[j] + f[j - a[i]]);
cout << f[m] << endl;
return 0;
}
1381. 階乘
分析
先要考慮下怎麼去求末尾數字
要求非零數字的話, 那就是意味着我們要先将末尾的0都去掉
假設 n ! n! n!末尾有k個零
要求 n ! n! n!末尾的非零數字, n 1 0 k % 10 \frac{n}{10^k} \% 10 10kn%10
将 n ! n! n!分解質因數 2 α 5 β p 1 α 2 p 1 α 2 . . . . p m α m 2^{\alpha} 5^{\beta}p_1^{\alpha_2}p_1^{\alpha_2}....p_m^{\alpha_m} 2α5βp1α2p1α2....pmαm
k = m i n ( α , β ) k = min(\alpha, \beta) k=min(α,β)
n ! 1 0 k = 2 α − k 2 β − k p 1 α 2 . . . . p m α m \frac{n!}{10^k} = 2^{\alpha - k}2^{\beta - k}p_1^{\alpha_2}....p_m^{\alpha_m} 10kn!=2α−k2β−kp1α2....pmαm
我們可以将1, 2, 3, … n的所有質因數分成2,5和其他質因數, 其他質因數直接%10, 對于2, 5統計次數再-k % 10
時間複雜度
首先我們會枚舉所有數, 每個數有 l o g ( n ) log(n) log(n)級别的2和5, 是以每個數logn時間複雜度, 總共nlogn
code
#include <iostream>
using namespace std;
int n;
int main(){
scanf("%d", &n);
int d2 = 0, d5 = 0;
int res = 1;
for (int i = 1; i <= n; i ++ ){
int x = i;
while (x % 2 == 0) d2 ++, x /= 2;
while (x % 5 == 0) d5 ++, x /= 5;
res = res * x % 10; // 計算其餘數乘積%10
}
int k = min(d2, d5);
for (int i = 0; i < d2 - k; i ++ ) res = res * 2 % 10;
for (int i = 0; i < d5 - k; i ++ ) res = res * 5 % 10;
cout << res << endl;
return 0;
}