【枚举，构造】CF1582 C D

Problem - C - Codeforces

题意：

 

思路：

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

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

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

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

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

Code：

#include <bits/stdc++.h>#define int long longusing 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

题意：

思路：

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

先去考虑特殊的情况

如果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 longusing 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;
}