1. C - Scc Puzzle
计算scc的个数，先判断s个数需要多少个cc，多的cc，每四个可以组成一个scc。注意数据范围，使用long long.
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
void solve() {
ll x, y;
while(cin >> x >> y) {
ll res = ;
if(y >= * x) {
res = x + (y - * x) / ;
} else {
res = y / ;
}
cout << res << endl;
}
}
int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios::sync_with_stdio();
cin.tie(); cout.tie();
solve();
return ;
}
2. D - Menagerie
读完题目，感觉是无从下手，3 <= n <= 1e5，暴力判断每一个字符串，肯定会tle，然后就要想其他方法了。
然后突然想到:固定前2个数，然后其他的位置可以推导出来，最后判断第一个和最后一个位置是否合法就可以了。
我写的又长又臭，哎，先这样吧，慢慢改进。
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
int n;
vector<bool> res;
bool work(const string &s) {
for (int i = ; i < n - ; i++) {
if(s[i] == 'o') {
if(res[i]) {
res[i + ] = !res[i - ];
} else {
res[i + ] = res[i - ];
}
} else {
if(res[i]) {
res[i + ] = res[i - ];
} else {
res[i + ] = !res[i - ];
}
}
}
bool f1, f2;
f1 = f2 = ;
if(s[n - ] == 'o') {
if(res[n - ]) {
f1 = res[n - ] != res[];
} else {
f1 = res[n - ] == res[];
}
} else {
if(res[n - ]) {
f1 = res[n - ] == res[];
} else {
f1 = res[n - ] != res[];
}
} if(s[] == 'o') {
if(res[]) {
f2 = res[n - ] != res[];
} else {
f2 = res[n - ] == res[];
}
} else {
if(res[]) {
f2 = res[n - ] == res[];
} else {
f2 = res[n - ] != res[];
}
}
return f1 && f2;
}
void pr() {
for (int i = ; i < n; i++) {
if(res[i]) cout << 'W';
else cout << 'S';
}
cout << endl;
}
void solve() {
string s;
while(cin >> n) {
cin >> s;
res.clear();
res.resize(n);
res[] = res[] = ;
bool f = work(s);
if(f) {
pr();
continue;
}
res[] = res[] = ;
f = work(s);
if(f) {
pr();
continue;
}
res[] = ; res[] = ;
f = work(s);
if(f) {
pr();
continue;
}
res[] = ; res[] = ;
f = work(s);
if(f) {
pr();
continue;
}
cout << - << endl;
}
}
int main() {
// freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios::sync_with_stdio();
cin.tie(); cout.tie();
solve();
return ;
}
3. E - Frequency
1<=n<=1e5,1<=a<=1e9,数据范围很大，不可能一个一个的模拟。注意结果可能需要long long来保存。
考虑最大的数，然后递减到次大的数，然后每次维护一下这些数的index的最小值，依次统计，最后输出。
使用set来维护数的顺序，同时记录index.
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + ;
int a[maxn];
set<int> se;
map<int, vector<int>> tag;
map<int, int> sz;
ll res[maxn];
int n;
void solve() {
cin >> n;
for (int i = ; i < n; i++) {
cin >> a[i];
se.insert(a[i]);
sz[a[i] ]++;
tag[a[i] ].pb(i + );
}
while(se.size() > ) {
int t = *se.rbegin();
se.erase(t);
int nt = *se.rbegin();
int mi = tag[t][];
for (int x : tag[t]) {
mi = min(mi, x);
}
tag[nt].pb(mi);
res[mi] += 1ll * (t - nt) * sz[t];
sz[nt] += sz[t];
}
int t = *se.begin();
int mi = tag[t][];
for (int x : tag[t]) mi = min(mi, x);
res[mi] += 1ll * t * sz[t];
for (int i = ; i <= n; i++)
cout << res[i] << endl;
}
int main() {
// freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios::sync_with_stdio();
cin.tie(); cout.tie();
solve();
return ;
}
4。 F - Flags
题目很简短，不知道怎么做。官方题解只有日语的，没有进一步用翻译去看，有时间，搞一下。