update P2602.md

coderhare · coderhare · commit da1f09b4aade · 2022-04-14T18:45:07.000+08:00
diff --git a/acwing/46.md b/acwing/46.md
@@ -0,0 +1,109 @@
+### T1
+> 贪心
+```c++
+void solve(){
+    int a, b, c, d;
+    cin >> a >> b >> c >> d;
+    if(b < a) cout << "First\n";
+    else cout << "Second\n";
+}
+
+```
+
+### T2
+> 贪心，排序
+思考切换后得到效益最高，必定出现在背面值减去正面值最大的情况下
+```c++
+void solve(){
+    int n, m; cin >> n >> m;
+    vector <pii> a(n);
+    for(int i = 0; i < n; i++) cin >> a[i].fi;
+    for(int i = 0; i < n; i++) cin >> a[i].se;
+    sort(begin(a), end(a), [&](const auto & a, const auto & b){
+       return a.fi - a.se > b.fi - b.se;
+    });
+    m = n - m;
+    int ans = 0;
+    for(int i = 0; i < n; i++){
+        if(m > 0 && a[i].fi - a[i].se > 0) ans += a[i].se, m--;
+        else ans += a[i].fi;
+    }
+    cout << ans << endl;
+    
+}
+```
+
+### T3
+> 预处理
+
+```c++
+#include <bits/stdc++.h>
+using namespace std;
+
+using pii = pair<int,int>;
+using ll = long long;
+using ull = unsigned long long;
+using piii = pair<int, pii>;
+
+void dbg(){puts("");}
+template<typename T, typename... R>void dbg(const T &f, const R &... r) {
+    cout << f << " ";
+    dbg(r...);
+}
+#define pb push_back
+#define ep emplace_back
+#define all(x) (x).begin(),(x).end()
+#define fi first
+#define se second
+#define mp make_pair
+#define all(x) x.begin(), x.end()
+#define endl "\n"
+
+template <typename T> void chkmax(T &x, T y) { if (y > x) x = y; }
+template <typename T> void chkmin(T &x, T y) { if (y < x) x = y; }
+
+
+void solve(){
+    int n, q;
+    cin >> n;
+    string s;
+    unordered_map <string, int> cnt;
+    unordered_map <string, string> pstr;
+    unordered_set <string> S;
+    for(int i = 0; i < n; i++){ 
+        cin >> s;
+        S.clear();
+        for(int i = 1; i <= s.size(); i++){
+            for(int j = 0; j + i <= s.size(); j++){
+                S.insert(s.substr(j, i));
+            }
+        }
+        for(auto & str: S) {
+            cnt[str]++;
+            if(!pstr.count(str)) pstr[str] = s;
+        }
+    }
+    cin >> q;
+    while(q--){
+        cin >> s;
+        cout << cnt[s] << ' ';
+        if(cnt[s]) cout << pstr[s] << endl;
+        else cout << '-' << endl;
+    }
+}
+
+
+int main(){
+    ios_base::sync_with_stdio(0);
+    cin.tie(0);
+    int t = 1;
+    while(t--){
+        solve();
+    }
+    return 0;
+}
+
+
+
+
+```
diff --git a/codeforces/779/codeforces779 div2.md b/codeforces/779/codeforces779 div2.md
@@ -118,5 +118,3 @@ void solve(){
     cout << ans << endl;
 }
 ```
-
-
diff --git a/codeforces/constructive_algorithms/1630A.md b/codeforces/constructive_algorithms/1630A.md
@@ -0,0 +1,11 @@
+# codeforces 1630A
+
+> 这是一道分类细节稍多的构造，我参考了scott的一种比较优秀的作法，按照他的构造，能把分类情况减少很多
+
+首先是无解的情况：
+
+- 当且仅当n = 4, k = 3的时候，用枚举的方法容易发现这是无法构造出来的
+
+接着思考，在什么情况下可能会出现无解？
+
+
diff --git a/codeforces/constructive_algorithms/1646C.md b/codeforces/constructive_algorithms/1646C.md
@@ -47,3 +47,11 @@ int main(){
     return 0;
 }
 ```
+
+
+
+
+
+
+
+### 
diff --git a/codeforces/constructive_algorithms/contest748C.md b/codeforces/constructive_algorithms/contest748C.md
@@ -0,0 +1,37 @@
+# codeforces contest748 C
+
+> 按tag是constructive problems，但是实际上感觉是greedy的
+
+首先需要明确一点，最少的点依赖于这些走的距离一定是最长的线段，就是说，我不是到处设点，如何判断是否当前点一定是需要设点的呢？需要厘清一下过程：
+
+**当出现往回走的情况的时候，如果说我们走着走着往回走了，这就说明，之前方向的最远处一定是需要走的点，我们走完了往回走寻找下一个点**
+
+```cpp
+int main(){
+    ios_base::sync_with_stdio(0);
+    cin.tie(0);
+    //greedy: makes points as least as possible
+    //line as long as possible
+    string s;
+    int n;
+    cin >> n >> s;
+    unordered_set <int> S;
+    int ans = 0;
+    for(char & c: s){
+        if(c == 'L') c = -1;
+        if(c == 'R') c = 1;
+        if(c == 'U') c = -2;
+        if(c == 'D') c = 2;
+    }
+    for(int i = 0; i < n; i++){
+        if(S.count(s[i])) continue;
+        if(S.count(-s[i])) { //当出现了往回走的情况，这说明我们当前深入的点是需要走的，否则不需要如此“大费周章”
+            S.clear();
+            ans++;
+        }
+        S.insert(s[i]);
+    }
+    cout << ans + 1 << endl;
+    return 0;
+}
+```

Original file line number	Diff line number	Diff line change
`@@ -118,5 +118,3 @@ void solve(){`
`118`	`118`	`cout << ans << endl;`
`119`	`119`	`}`
`120`	`120`	```
`121`		`-`
`122`		`-`
-Original file line number
+Diff line change
     return 0;
+}
 ```
++
++
++
++
++
++
++
 +###