update lc & astar

lzyrapx · Aug 9, 2020 · 3ea0140 · 3ea0140
1 parent 4468177
commit 3ea0140
Show file tree

Hide file tree

Showing 4 changed files with 188 additions and 0 deletions.
diff --git a/LeetCode/Medium/1276.cpp b/LeetCode/Medium/1276.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+    // 问是否可以让x,y 满足以下条件
+    // 1. 4 * x + 2 * y = tomatoSlices
+    // 2. x + y = cheeseSlices
+    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
+        vector<int>ans;
+        if(tomatoSlices == 0 || cheeseSlices == 0) {
+            return {0, 0};
+        }
+        if(tomatoSlices % 2 != 0) {
+            return {};
+        }
+        if(tomatoSlices < cheeseSlices * 2) {
+            return {};
+        }
+        if(cheeseSlices * 4 < tomatoSlices) {
+            return {};
+        }
+        return {tomatoSlices / 2 - cheeseSlices, cheeseSlices * 2 - tomatoSlices / 2};
+    }
+};
diff --git a/百度之星/2020/复赛/A.cpp b/百度之星/2020/复赛/A.cpp
@@ -0,0 +1,42 @@
+#include <cstring>
+#include <iostream>
+#include <cstdio>
+#include <algorithm>
+#include <vector>
+
+using namespace std;
+typedef long long ll;
+const int maxn = 1000;
+const int mod = 998244353;
+
+int inv[maxn];
+ll qpower(ll a, ll b,ll mod)
+{
+    long long ans = 1;
+    while(b > 0) {
+        if(b & 1) ans = (ans * a) % mod;
+        b >>= 1;
+        a = (a * a) % mod;
+    }
+    return ans;
+}
+
+int main(int argc, char const *argv[])
+{
+    int t;
+    inv[0] = 1;
+    for(int i = 0; i <= 1000; i++){
+        inv[i] = qpower(i, mod - 2, mod);
+    }
+    // cout << inv[100] << endl;
+    cin >> t;
+    while(t--) {
+        int m, q, p;
+        int ans = 0;
+        cin >> m >> p >> q;
+        ll tmp = 100ll * inv[p] % mod * m % mod + mod - 1;
+        ans = (m + mod - tmp * q % mod * inv[100] % mod) % mod;
+        cout << ans << endl;
+    }
+    return 0;
+}
diff --git a/百度之星/2020/复赛/B.cpp b/百度之星/2020/复赛/B.cpp
@@ -0,0 +1,53 @@
+#include <cstring>
+#include <iostream>
+#include <cstdio>
+#include <algorithm>
+#include <vector>
+
+using namespace std;
+typedef long long ll;
+const int maxn = 1e5 + 123;
+const int mod = 998244353;
+
+int sum[maxn];
+int main(int argc, char const *argv[])
+{
+    int t;
+    cin >> t;
+    while(t--) {
+        int n = 0;
+        string s, t;
+        cin >> n >> s >> t;
+        sum[n] = 0;
+        for(int i = n - 1; i >= 0; i--){
+            if(s[i] != t[i]) {
+                sum[i] = sum[i + 1] + 1;
+            }
+            else {
+                sum[i] = sum[i + 1];
+            }
+        }
+        int ans = sum[0];
+        sum[n + 1] = 0;
+        int zero = 0,  class="pl-c1">0
+        for(int i = 0; i < n; i++) {
+            if(s[i] == '0') {
+                zero++;
+            }
+            if(t[i] == '1') {
+                one++;
+            }
+            int k = 0;
+            if(t[i + 1] != '1') {
+                k++;
+            }
+            if(s[i + 1] == '1') {
+                k++;
+            }
+            int val = zero + one + sum[i + 2] + k + 1;
+            ans = min(ans, val);
+        }
+        cout << ans << endl;
+    }
+    return 0;
+}
diff --git a/百度之星/2020/复赛/C.cpp b/百度之星/2020/复赛/C.cpp
@@ -0,0 +1,71 @@
+#include <cstring>
+#include <iostream>
+#include <cstdio>
+#include <algorithm>
+#include <vector>
+
+using namespace std;
+typedef long long ll;
+const int maxn = 1e5 + 123;
+const int mod = 998244353;
+
+int c[maxn];
+int main(int argc, char const *argv[])
+{
+    int t;
+    // cin >> t;
+    scanf("%d",&t);
+    while(t--) {
+        int n, l, k;
+        // cin >> n >> l >> k;
+        scanf("%d%d%d",&n,&l,&k);
+        for(int i = 1; i <= n; i++) {
+            // cin >> c[i];
+            scanf("%d",&c[i]);
+        }
+        ll ans1 = 0;
+        sort(c + 1, c + n + 1);
+        int idx = n + 1;
+        for(int i = l - k + 1; i <= n; i += l) {
+            int minn = min(n, i + k - 1);
+            int j = i;
+            for(j = i; j <= minn; j++) {
+                if(j < minn && i - 1 > l - k) {
+                    ans1 += c[--idx];
+                    // cout << "t1 = " << ans1 << endl;
+                }
+                else {
+                    idx = idx - 1;
+                }
+            }
+            int k1 = min(n, (j - 1) + (l - k));
+            ans1 += 1LL * c[idx] * (k1 - j + 2);
+        }
+        // cout << "ans1 = " << ans1 << endl;
+        for(int i = 1; i <= n; i++) {
+            c[i] = -1 * c[i];
+        }
+        k = l - k + 1;
+        ll ans2 = 0;
+        sort(c + 1, c + n + 1);
+        idx = n + 1;
+        for(int i = l - k + 1; i <= n; i += l) {
+            int minn = min(n, i + k - 1);
+            int k1 = n, j = i;
+            for(j = i; j <= minn; j++) {
+                if(j < minn && i - 1 > l - k) {
+                    ans2 += c[--idx];
+
+                }
+                else {
+                    idx = idx - 1;
+                }
+            }
+            k1 = min(n, (j - 1) + (l - k));
+            ans2 += 1LL * c[idx] * (k1 - j + 2);
+        }
+        printf("%lld %lld\n",ans1, -1 * ans2);
+        // cout << ans1 << " " << -1 * ans2 << endl;
+    }
+    return 0;
+}