【枚举，构造】CF1582 C D

旧城等待， 2024-03-23 18:48 101阅读 0赞

[Problem - C - Codeforces][]

题意：

![41aba6a6704a46188f11720ce4b622e5.png][]

![35a7376cd6d84eeb9329391b7fdad262.png][]

思路：

思路很简单，只删除一种，直接枚举删除的是哪一种即可

但是回文子序列的判定我vp的时候写的很答辩，也不知道为什么当时要从中间往两边扫，纯纯自找麻烦

然后就越改越复杂，两小时的时候才过C

**所以有新想法的时候还是把new idea整合一下，再去写代码**

直接从两边往中间扫就行了，然后把该删的都删掉

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 2e5 + 10;
    const int M = 3e6 + 10;
    const int P = 131;
    
    void solve() {
        int n;    
        string s;
    
        cin >> n >> s;
        s = " " + s;
    
        set<char> S;
        for (int i = 1; i <= n; i ++) {
            S.insert(s[i]);
        }
    
        int ans = 1e9;
        for(auto c: S) {
            int l = 1, r = n;
            int cnt = 0;
            while(l <= r) {
                if (s[l] == s[r]) {
                    l ++;
                    r --;
                }else if (s[l] == c) {
                    cnt ++;
                    l ++;
                }else if (s[r] == c) {
                    cnt ++;
                    r --;
                }else {
                    cnt = 1e9;
                    break;
                }
            }
            ans = min(ans, cnt);
        }
        if (ans == 1e9) {
            cout << -1 << "\n";
        }else {
            cout << ans << "\n";
        }
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int t = 1;
        cin >> t;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[Problem - D - Codeforces][]

题意：

![f69ead642fab4397a2a2dc16faca2c27.png][]

思路：

构造题，看样例发现什么都看不出来

先去考虑特殊的情况

如果N = 2，那么

a \* x + b \* y = 0

x = - b

y = a

如果N = 3

有三种情况，以一种举例：

x = - c

y = - c

z = a + b

当然这里的c和-c可以替换成b和-b，a和-a，所以是三种情况

然后考虑将特殊情况“组合”到一般情况中去

可以发现，如果n是奇数，那么就分组成3+2+2+2+....的形式

否则就可以是2+2+2+....的形式

这样就做完了

**这道题的启发是：可以用特殊情况“组合”成一般情况进行考虑**

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 2e5 + 10;
    const int M = 3e6 + 10;
    const int P = 131;
    
    int a[N], b[N];
    
    void solve() {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
        }
        if (n % 2 == 1) {
            if (a[1] + a[3]) {
                b[1] = -a[2];
                b[3] = -a[2];
                b[2] = a[1] + a[3];
            }else if (a[1] + a[2]) {
                b[1] = -a[3];
                b[2] = -a[3];
                b[3] = a[1] + a[2];
            }else if (a[2] + a[3]) {
                b[2] = -a[1];
                b[3] = -a[1];
                b[1] = a[2] + a[3];
            }
            for (int i = 4; i <= n; i += 2) {
                b[i] = -a[i + 1];
                b[i + 1] = a[i];
            }
        }else {
            for (int i = 1; i <= n; i += 2) {
                b[i] = -a[i + 1];
                b[i + 1] = a[i];
            }
        }
        for (int i = 1; i <= n; i ++) {
            cout << b[i] << " \n" [i == n];
        }
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int t = 1;
        cin >> t;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1582/problem/C
[41aba6a6704a46188f11720ce4b622e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/50d05147928a4620b9fa3201dceaa6f1.png
[35a7376cd6d84eeb9329391b7fdad262.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/92c2277e079f4e27ae757bff0b7840ed.png
[Problem - D - Codeforces]: https://codeforces.com/contest/1582/problem/D
[f69ead642fab4397a2a2dc16faca2c27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8f8c73a500354b8a92037f0976c18bed.png