\[
Time Limit: 1 s\quad Memory Limit: 256 MB
\]
直接按照题意模拟即可。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
char s[maxn];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%s", s+1);
n = strlen(s+1);
reverse(s+1, s+1+n);
if(s[1]=='o' && s[2]=='p') {
puts("FILIPINO");
} else if(s[1]=='u'&&s[2]=='s'&&s[3]=='e'&&s[4]=='d') {
puts("JAPANESE");
} else if(s[1]=='u'&&s[2]=='s'&&s[3]=='a'&&s[4]=='m') {
puts("JAPANESE");
} else if(s[1]=='a'&&s[2]=='d'&&s[3]=='i'&&s[4]=='n'&&s[5]=='m') {
puts("KOREAN");
}
}
return 0;
}\[
Time Limit: 2 s\quad Memory Limit: 256 MB
\]
用 \(p[]\) 记录第一个字符串从 \(i\) 往后最小的字母在哪里。
枚举一对交换字符较左的位置，每次判断的时候只需要把 \(s[i]\) 和 \(s[p[i]]\) 交换，就可以让这个字符串尽量小，然后和第二个字符串比较，看能否满足条件即可。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
string s1, s2;
int p[maxn];
int main() {
scanf("%d", &T);
while(T--) {
cin >> s1 >> s2;
n = s1.size(), m = s2.size();
for(int i=0; i<n; i++) p[i] = i;
int pos = n-1;
for(int i=n-2; i>=0; i--) {
if(s1[i] < s1[pos]) pos = i;
p[i] = pos;
}
int flag = 0;
for(int i=0; i<min(n, m); i++) {
swap(s1[i], s1[p[i]]);
if(s1 < s2) {
flag = 1;
cout << s1 << endl;
break;
}
swap(s1[i], s1[p[i]]);
}
if(!flag) cout << "---" << endl;
}
return 0;
}\[
Time Limit: 2 s\quad Memory Limit: 256 MB
\]
由于 \(1 \leq x \leq 10^6\)，所以可以暴力知道前 \(x\) 个字符串长什么样。
当字符串长度超过 \(x\) 时，往后字符串长什么样并不重要，因为光标永远不会到达这里，所以对长度的影响可以直接计算出来。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
string s, ss;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
cin >> s;
int p = -1;
ll len = s.size();
int flag = 0;
for(int i=1; i<=n; i++) {
p++;
if(!flag) ss = s.substr(p+1, s.size()-1);
int t = s[p]-'0';
ll tlen = len-p-1;
tlen = (tlen%mod+mod)%mod;
for(int j=2; j<=t; j++) {
if(!flag) s += ss;
if(len + tlen>=n) flag = 1;
len = (len+tlen)%mod;
}
}
printf("%lld\n", len);
}
return 0;
}\[
Time Limit: 2 s\quad Memory Limit: 256 MB
\]
首先可以发现，只要存在一个 \(A\)，我最多只需要花 \(4\) 步就可以到达最终状态，所以答案一定是 \(0、1、2、3、4、MORTAL\)。
分析一下可以发现:
暴力讨论每种情况就可以。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
char s[70][70];
int solve() {
int ans = 4;
if(s[1][1]=='A' || s[1][m]=='A' || s[n][1]=='A' || s[n][m]=='A') ans = min(ans, 2);
{
bool f1 = true, f2 = true, f = false;
for(int j=1; j<=m; j++) {
if(s[1][j] == 'P') f1 = false;
if(s[n][j] == 'P') f2 = false;
if(s[1][j] == 'A') f = true;
if(s[n][j] == 'A') f = true;
}
if(f1 || f2) ans = min(ans, 1);
bool f3 = true, f4 = true;
for(int i=1; i<=n; i++) {
if(s[i][1] == 'P') f3 = false;
if(s[i][m] == 'P') f4 = false;
if(s[i][1] == 'A') f = true;
if(s[i][m] == 'A') f = true;
}
if(f3 || f4) ans = min(ans, 1);
if(f) ans = min(ans, 3);
}
{
bool f = true;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(s[i][j] == 'P') f = false;
}
if(!f) break;
}
if(f) ans = min(ans, 0);
}
{
for(int i=1; i<=n; i++) {
int cnt = 0;
for(int j=1; j<=m; j++) {
cnt += s[i][j]=='A';
}
if(cnt == m) ans = min(ans, 2);
}
for(int j=1; j<=m; j++) {
int cnt = 0;
for(int i=1; i<=n; i++) {
cnt += s[i][j]=='A';
}
if(cnt == n) ans = min(ans, 2);
}
}
return ans;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
int flag = 0;
for(int i=1; i<=n; i++) {
scanf("%s", s[i]+1);
if(flag) continue;
for(int j=1; j<=m; j++) {
if(s[i][j] == 'A') flag = 1;
}
}
if(flag == 0) printf("MORTAL\n");
else printf("%d\n", solve());
}
return 0;
}\[
Time Limit: 3 s\quad Memory Limit: 256 MB
\]
思路对了...代码写搓了没写完，我太难了
想要让 \(\sum f(i)\) 最大，那么肯定每次是取最远的两个点做一对。如果想要让其尽量小，那么尽量每次让相邻的两个点做一对，那么我们可以考虑每条边的贡献。
假设有一条连接 \(u\) 和 \(v\) 的边，权值为 \(w\)，那么如果 \(u\) 侧有 \(x\) 个点，\(v\) 侧有 \(y\) 个点
求最大时，我肯定尽量从 \(u\) 侧连一条路到 \(v\) 侧，那么这条边就会被用上 \(min(x, y)\) 次。
求最小时，假如 \(x\) 为偶数，那么 \(y\) 肯定也是偶数，而我又希望让同一对的点靠的尽量近，那么肯定时 \(u\) 侧的点两两凑对，\(v\) 侧的点两两凑对。因为如果我选 \(u\) 和 \(v\) 凑一对，那么两侧都少了一个点，必然要在凑一对，这样多计算了两次 \(w\)，显然亏了。
假如 \(x\) 为奇数，\(y\) 肯定也是奇数，这时候肯定要选一对从 \(u\) 侧到 \(v\) 侧，那么我可以选 \(u\) 和 \(v\) 凑一对，然后两次剩余的又都是偶数，可以各自凑起来。
view
#include <map>
#include <set>
#include <list>
#include <tuple>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
ll ans1, ans2;
vector<pii> g[maxn];
ll sz[maxn];
void dfs(int u, int fa) {
sz[u] = 1;
for(auto v : g[u]) if(v.fi != fa) {
dfs(v.fi, u);
sz[u] += sz[v.fi];
if(sz[v.fi]&1) ans1 += v.se;
ans2 += min(sz[v.fi], n-sz[v.fi])*v.se;
}
}
int main() {
scanf("%d", &T);
while(T--) {
int k;
scanf("%d", &k);
n = 2*k;
for(int i=1; i<=n; i++) g[i].clear();
for(int i=2, u, v, w; i<=n; i++) {
scanf("%d%d%d", &u, &v, &w);
g[u].pb({v, w});
g[v].pb({u, w});
}
ans1 = ans2 = 0;
dfs(1, 0);
printf("%lld %lld\n", ans1, ans2);
}
return 0;
}\[
Time Limit: 4 s\quad Memory Limit: 256 MB
\]
留坑
Codeforces Round #607 (Div. 2) 题解
原文：https://www.cnblogs.com/Jiaaaaaaaqi/p/12052180.html