C. Ivan the Fool and the Probability Theory
题意：
给出一个\(n*m\)的方格，现在要给方格中的元素黑白染色，要求任一颜色最多有一个颜色相同的格子和它相邻。问多少种方案。
思路：
- 观察到若第一行含有两个相同的颜色相邻，那么之后所有格子的状态都可以确定；
- 若第一行不含有两个相同的颜色相邻，那么下一行至多有两种状态。
根据这两个观察，可以发现状态数其实不多，我们再推导一下：
- 对于第一种情况，假设第一个格子为白色，第二个格子有黑白两种选择：若选择白，则第三个格子只有一种选择；否则第三个格子有两种选择；
- 对于第二种情况，第一行不妨为黑白交错，那么若第二行也为黑白交错，第三行只有一种情况；否则第三行能有两种情况。
发现这两个有类似之处，并且都是一到二或者二到一，在纸上画一下可以发现随着行数/列数的增加，状态数为斐波那契数。
所以这个题求一下斐波那契数就行了。
答案为\(2*(F_m-1+F_n)\)
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 1e9 + 7;int n, m;void run() {
int ans = 0;
int pre = 1, now = 1;
for(int i = 2; i <= m; i++) {
int tmp = now;
now = (pre + now) % MOD;
pre = tmp;
}
ans = 2ll * (now - 1) % MOD;
pre = 1, now = 1;
for(int i = 2; i <= n; i++) {
int tmp = now;
now = (pre + now) % MOD;
pre = tmp;
}
ans = (ans + 2ll * now) % MOD;
cout << ans << '\n';
}int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> m) run();
return 0;
}
D2. The World Is Just a Programming Task (Hard Version)
题意：
给出一个括号序列，现在可以选择两个括号进行交换，使得合法的\(shift\)最多。
定义\(shift_i\)合法：将序列后\(i\)个放到前面后，形成的新的括号序列合法，\(1\leq i<n\)。
思路：
这个题有很重要的两个观察，首先令\((\)为\(1\)，\()\)为\(-1\)，\(sum_i\)为序列的前缀和，并且\(min=min\{sum_i\}\)。我们先将\(sum_n\not ={0}\)的情况排除，然后：
- 观察1: 若\(sum_i=min\)，那么\(shift_{n-i}\)一定为一个合法序列；
- 观察2: \(shift\)具有传递性，多次\(shift\)可以合并为一次\(shift\)。
观察\(2\)比较好理解（就是不好注意到这一个性质QAQ），观察\(1\)之所以正确，是因为因为\(sum_i\)为最小值，那么对于\(j>i,sum_j-sum_i\geq 0\)并且有\(sum_j-sum_i=-min\)。那么我们将后面这部分放到前面，首先前面这一块始终合法，然后后面最小值为\(min\)，也不能使序列非法。
因为观察2，我们可以任选一个合法\(shift\)并且得到新序列，之后我们的任务就是使得新序列的\(sum’_i=min’=0\)的个数最多（观察1+观察2）。
然后还有一个比较重要的地方，就是我们改变一对括号序列，会使得一段数中的前缀值减少\(2\)。
那么我们首先统计新序列中\(sum’_i=0\)的个数，然后还要统计连续段中\(sum’_i=2\)的个数，因为将其减少\(2\)之后会得到\(0\)；
之后再统计一下连续段中\(sum’_i=1\)的个数即可，减去之后最小值会为\(-1\)。
对于\(sum’_i>2\)的其余位置，就算减去\(2\)也不会对答案尝试贡献。
刚才说的一段数，是这样一段数:\(sum_i=1,sum_j=1,i< k\leq j,sum_j\geq 2\)这样的一段数（以第一种情况举例），此时我们选择交换\(i+1,j\)这两个位置，如果我们不改变\(j\)这个位置的括号，那么就会多出一个\()\)就不合法了。
说了这么多，本质还是贪心。。
还是代码清楚点：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 300005;int n;
char s[N], t[N];
int sum[N];void run() {
cin >> (s + 1);
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1];
sum[i] += (s[i] == '(' ? 1 : -1);
}
if(sum[n] != 0) {
pt(0); pt(1, 1);
return;
}
int Min = *min_element(sum + 1, sum + n + 1);
int all = 0, shift;
for(int i = 1; i <= n; i++) {
if(sum[i] == Min) shift = i;
}
for(int i = shift + 1; i <= n; i++) {
t[i - shift] = s[i];
}
for(int i = 1; i <= shift; i++) {
t[n - shift + i] = s[i];
}
t[n + 1] = '\0';
strcpy(s + 1, t + 1);
auto srcp = [&](int p) {
return (p + shift - 1) % n + 1;
};
// dbg(n, shift, srcp(2));
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1];
sum[i] += (s[i] == '(' ? 1 : -1);
if(sum[i] == 0) ++all;
}
vector <int> ans = {all, 1, 1};
int last = 0, cnt = 0;
//Case 1: min = 0
for(int i = 1; i <= n; i++) {
if(sum[i] == 2) ++cnt;
else if(sum[i] <= 1) {
ans = max(ans, std::vector<int>{all + cnt, srcp(last + 1), srcp(i)});
last = i;
cnt = 0;
}
}
dbg(ans[0], ans[1], ans[2]);
//Case 2: min = -1
last = cnt = 0;
for(int i = 1; i <= n; i++) {
if(sum[i] == 1) ++cnt;
else if(sum[i] <= 0) {
ans = max(ans, std::vector<int>{cnt, srcp(last + 1), srcp(i)});
last = i;
cnt = 0;
}
}
pt(ans[0]);
pt(ans[1], ans[2]);
}int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n) run();
return 0;
}
F. Catowice City
题意：
给出一个二分图，保证\(i\)和\(i’\)有边相连。
输出一个最大独立集的方案。
思路：
- 显然，我们选择的两个点之间没有边相连；
- 我们可以将\(i\)到\(i’\)的边看作从右向左，其余边为从左向右，那么我们求出每一个强连通分量。
- 若强连通分量个数为\(1\)，根据题意不存在解；否则，不同强连通分量之间不存在边相连（若存在，则不满足“极大子图”）。那么直接按照强连通分量来划分了。
代码如下：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
// #define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5;int n, m;stack <int> s;
int T, num;
int col[N], dfn[N], low[N];
std::vector<int> scc[N], g[N];
void Tarjan(int u){
dfn[u] = low[u] = ++T;
s.push(u);
for(auto v : g[u]){
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if(!col[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]){
num++; int now;
do{
now = s.top(); s.pop();
col[now] = num;
scc[num].push_back(now);
}while(!s.empty() && now!=u);
}
}void init() {
for(int i = 1; i <= n; i++) {
scc[i].clear();
g[i].clear();
col[i] = dfn[i] = 0;
}
num = T = 0;
}void run() {
cin >> n >> m;
init();
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) {
Tarjan(i);
}
}
if(n == 1 || num == 1) {
cout << "No" << '\n';
return;
}
std::vector<int> ans[2];
ans[0] = scc[1];
for(int i = 2; i <= num; i++) {
for(auto it : scc[i]) ans[1].push_back(it);
}
cout << "Yes" << '\n';
cout << sz(ans[0]) << ' ' << sz(ans[1]) << '\n';
for(auto it : ans[0]) cout << it << ' ';
cout << '\n';
for(auto it : ans[1]) cout << it << ' ';
cout << '\n';
}int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
int T; cin >> T;
while(T--) run();
return 0;
}
