update acwc48

coderhare · coderhare · commit a47df169e1c1 · 2022-04-23T21:51:11.000+08:00
diff --git a/acwing/48.md b/acwing/48.md
@@ -0,0 +1,84 @@
+# acwing48场周赛
+
+
+
+### T1
+
+直接模拟
+
+```cpp
+
+void solve(){
+    int n, k;
+    cin >> n >> k;
+    for(int i = n; i <= 1000; i++){
+        double d = i/k;
+        if(n + d <= i) {
+            cout << i << endl;
+            return;
+        }
+    }
+
+}
+```
+
+### T2
+
+周期出现为6
+
+```cpp
+void solve(){
+    int n, x;
+    cin >> n >> x;
+    int r = n % 6;
+    int a[3] = {0, 0, 0};
+    a[x] = 1;
+    while(r--){
+        if(n & 1) swap(a[0], a[1]);
+        else swap(a[1], a[2]);
+        n--;
+    }
+    int ans = 0;
+    for(int i = 0; i < 3; i++) if(a[i] == 1) ans = i;
+    cout << ans << endl;
+}
+```
+
+
+
+### T3
+
+贪心，但是卡哈希了，搞得我还一直以为是我用了dfs
+
+先离散化了一下，用处不大..
+
+```cpp
+static constexpr int mod =  998244353;
+void solve(){
+    int n;
+    cin >> n;
+    vector <int> a(n);
+    for(int i = 0; i < n; i++) cin >> a[i];
+    set <int> st;
+    for(int i: a) st.insert(i);
+    map <int, int> m;
+    int cnt = 0;
+    for(int i: st) m[i] = cnt++;
+    for(int i = 0; i < n; i++) a[i] = m[a[i]];
+    vector <vector<int>> di(cnt);
+    for(int i = 0; i < n; i++) di[a[i]].push_back(i);
+    auto dfs = [&](auto & dfs, int u, int r, bool lead)->ll{
+        if(u >= n) return 1;
+        ll ans = 0; //对应两种选择，变成与之前的相同的或者+1
+        for(int i = u; i <= r; i++){
+            r = max(r, di[a[i]].back());
+        }
+        if(lead) ans = dfs(dfs, r + 1, r + 1, 0) % mod;
+        else ans = 2 * dfs(dfs, r + 1, r + 1, 0) % mod;
+        return ans % mod;
+    };
+    cout << dfs(dfs, 0, di[a[0]].back(), 1) % mod;
+}
+```
+
+
diff --git a/codeforces/README.md b/codeforces/README.md
@@ -1,3 +1,84 @@
+# tags🏷
+
+## Graph
+
+- **最短路算法**
+  
+  - 单源最短路
+    
+    1. Dijkstra：O(n^2) or O(mlogn)
+    
+    2. 0-1BFS：O(n)
+    
+    3. Bellmon-Ford
+    
+    4. SPFA
+  
+  - 多源最短路
+    
+    1. 多源BFS
+    
+    2. Floyd算法
+
+- **最小生成树算法**
+  
+  - Prim算法
+  
+  - Kruskal算法
+
+- **图的匹配**
+  
+  - 匈牙利算法
+  
+  - Km算法
+  
+  - 染色法判定二分图
+
+- **拓扑排序**
+  
+  - 队列实现的拓扑排序
+
+## Dynamic Programming
+
+- **线性DP**
+
+- **背包DP**
+
+- **区间DP**
+
+- **状态机DP**
+
+- **记忆化搜索**
+
+- **数位DP**
+
+- **计数DP**
+
+- **树形DP**
+
+## Binary Search
+
+- 二分 + 贪心
+
+- 二分 + 前缀和
+
+- 二分 + BFS
+
+## **Math**
+
+- 欧拉函数
+
+- gcd
+
+- 
+
+## Greedy
+
+### Simulation
+
+- 基本计算器（支持扩展运算）
+
+- 
 
 ## constructive algorithms
 
diff --git a/codeforces/constructive_algorithms/1630A.md b/codeforces/constructive_algorithms/1630A.md
@@ -7,5 +7,3 @@
 - 当且仅当n = 4, k = 3的时候，用枚举的方法容易发现这是无法构造出来的
 
 接着思考，在什么情况下可能会出现无解？
-
-
