3. 织女的考验

• 下面的代码看似很正确，但忽略了一个细节，下面判断是否有字母数量不同时，用abs(cnt[i]) == 1判断，这里忽略了abs(cnt[i]) 等于其他值的情况(YES和NO都存在)

#include <iostream>
#include <cstring>
using namespace std;int n;
int cnt[30];
bool check(string s, string t) {memset(cnt, 0, sizeof cnt);if (s.size() == 1) {return true;}for(int i = 0; i < s.size(); i++) {cnt[s[i] - 'a']++;cnt[t[i] - 'a']--;}int num = 0;for (int i = 0; i < 26; i++) {if (abs(cnt[i]) == 1) num++;if (num > 2) return false;}return true;
}
int main() {cin >> n;string s, t;while(n--) {cin >> s >> t;if (check(s, t)) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

• 修改后的代码
• 猜想1： 用num += cnt[i]; 最后判断num是否等于0，来判断答案。
• 不能，因为所有长度相等的字符串都满足这条件。
• 猜想2：用num += abs(cnt[i]);最后用num是否大于0判断。
• 不能，满足题目的只有两种情况，(1)两个字符串字母数量都相同，(2) 有两个字母数量不同，且都相差1，一个相减结果-1一个1。

#include <iostream>
#include <cstring>
using namespace std;int n;
int cnt[30];
bool check(string s, string t) {memset(cnt, 0, sizeof cnt);if (s.size() == 1) {return true;}for(int i = 0; i < s.size(); i++) {cnt[s[i] - 'a']++;cnt[t[i] - 'a']--;}int num = 0;for (int i = 0; i < 26; i++) {num += abs(cnt[i]);if (num > 2) return false;}return true;
}
int main() {cin >> n;string s, t;while(n--) {cin >> s >> t;if (check(s, t)) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

4. 仙男仙女

• 我第一次想到的是用前缀和来做，但是，没有考虑好内存问题(需要开int * 1e9)。还有，应该将pos的值维护完以后，求好前缀和以后，在计算ans。

#include <iostream>
using namespace std;
const int N = 1e5 + 01, M = 1e9 + 10;
int a[N], n, p[N], b[N];
int pos[M];int main()
{int ans = 0;cin >> n;for (int i = 1; i <= n; i++) {cin >> p[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}for (int i= 1; i <= n; i++) {pos[p[i]]++;pos[i] += pos[i - 1];int l = max(0, i - b[i] - 1), r = min(n, i + b[i] + 1 );if ((pos[i - 1] - pos[l] == 0) && (pos[r] - pos[i] == 0)) {ans++;}}cout << ans;return 0;
}

• 换一种思路，可以直接用pair储存位置和距离，按位置排序，最后求ans。

#include<iostream>
#include<algorithm>using namespace std;
#define x first
#define y second
const int N = 1e5 + 10;
int n;
pair<int, int> pa[N];int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> pa[i].x;}for (int i = 1; i <= n; i++) cin >> pa[i].y;sort(pa + 1, pa + n + 1);int ans = 0;if (n > 1 && pa[1].x + pa[1].y < pa[2].x) ans++;if (n > 1 && pa[n].x - pa[n].y > pa[n-1].x) ans++;for (int i = 2; i < n; i++) {if (pa[i].x + pa[i].y < pa[i + 1].x && pa[i].x - pa[i].y > pa[i - 1].x) ans++;}cout << ans;return 0;
}

5. 牛郎的微信群

• 分析： n 最大 10^5所以最大复杂度只能是$O(nlog(n))$。
• 我想，构建一个树. f[i] = g[p1] + g[p2] …(其中，p1 p2 … 是与i直接相连的节点，f[i]表示与i距离为2的节点，g[p]表示与节点p距离为1的点)。ans = (f[1] + f[2] + … + f[n]) / 2;
• 需要注意的点，（1）e和ne的大小 (2) f[r] += g[t] - 1; 减一表示要减去他自己。

#include<iostream>
using namespace std;const int N = 2e5 + 10;
int n, ind = 0, h[N], e[N * 2], ne[N * 2], g[N], f[N];void add(int a, int b) {e[++ind] = b;ne[ind] = h[a];h[a] = ind;
}
int ans = 0;
bool bs[N];void dfs(int r) {bs[r] = true;// cout << r << " ";for (int i = h[r]; i; i = ne[i]) {int t = e[i];f[r] += g[t] - 1;if (bs[t]) continue;dfs(t);}
}int main() {cin >> n;int x, y;for (int i = 0; i < n - 1; i++) {cin >> x >> y;add(x, y);add(y, x);g[x]++;g[y]++;}dfs(1);for (int i = 1; i <= n; i++) {cout << f[i] << " ";}return 0;
}

6. 就别重逢

题意可抽象为：给你n和k，求用不小于k的任意个正整数组成和不大于n的排列(有顺序)有多少种？
分析：
看到这个问题的时候，第一个就想到的是用动态规划来做，公式推导如下。（其中，$f[i]$表示刚好达到亲密度$i$有多少种方法）

f[i] = f[0 1 2 .. i - k]
f[i + 1] = f[0 1 2 3 .. i-k i+1-k] = f[i] + f[i+1-k];
f[i] = f[i-1] + f[i-k];

通过程序如下：(题目要求达到n有多少种变化，也就是将f[k] f[k+1] … f[n] 加起来)

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
LL f[N], p = 1e9 + 7;int main()
{cin >> n >> k;f[k] = 1;LL ans = 2;for (int i = k + 1; i <= n; i++) {f[i] = (f[i-1] + f[i-k]) % p;ans = (ans + f[i]) % p;}cout << ans;return 0;
}