B
关于这道题首先有一个结论：最少交换次数是多少，取决于置换图的环的个数，最少交换次数最多是 n – cnt（cnt是环的个数）。其次，每个环里最多只能放一个相同的值。证明，然后是怎么构造b，要使环的数尽可能的少，就要让相同的元素分散开，所以要让整个数组偏移mx个位置，最后直接输出
int a[N],b[N],cnt[N];
vector<int> g[N];//定义在外面，防止栈溢出
void solve() {
memset(cnt,0,sizeof(cnt));
int n,mx = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
cnt[a[i]]++;
mx = max(mx,cnt[a[i]]);
}
sort(b + 1,b + n + 1);
for(int i = 1; i <= n; i++) {
g[b[i]].push_back(b[(i + mx - 1) % n + 1]);
}
for(int i = 1; i <= n; i++) {
cout << g[a[i]].back() << ' ';
g[a[i]].pop_back();
}
cout << endl;
}
D
最多进行2n次询问，对于取余，如果是一个小的数取余一个大的数，得到的余数就是小的数，所以我们对i，j和j，i分别进行询问，得到的较大的那个数就是i，j里较小的数，接下来每次都用较大的数和一个未知的数询问，每次都可以知道较小数的具体值和较大数的索引，最后没有确定的数一定是n
int ans[N];
void ask(int a,int b) {
cout << "? " << a << ' ' << b << endl << flush;
}
void solve() {
int n; cin >> n;
int mx = 1;
for(int i = 2; i <= n; i++) {
int a,b;
ask(mx,i); cin >> a;
ask(i,mx); cin >> b;
if(a > b) {
ans[mx] = a;
mx = i;
}
else {
ans[i] = b;
}
}
for(int i = 1; i <= n; i++) {
if(!ans[i]) {
ans[i] = n;
break;
}
}
cout << "! ";
for(int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << endl;
}
E
给出的字符串很短，所以可以直接搜索，但不是记忆化搜索会超时，也可以动态规划，这里不多赘述。唯一要注意的是一条命令可以更改多次。
bool f[110][3][110][220];
int n,ans = 0;
string s;
void dfs(int u, int d, int k, int dis) {//处理到的命令，方向，改变数，距离
if(f[u][d][k][dis + 100] || k > n || u > sz(s)) return;
if(u == sz(s) && k == n) {
ans = max(ans,abs(dis));
return;
}
f[u][d][k][dis + 100] = 1;
if(s[u] == 'T') {
int c = d == 0 ? 1 : -1;
dfs(u + 1,1 - d,k,dis);
dfs(u + 1,d,k + 1,dis + c);
}
else {
int c = d == 0 ? 1 : -1;
dfs(u + 1,d,k,dis + c);
dfs(u + 1,1 - d,k + 1,dis);
}
dfs(u,d,k + 2,dis);
}
void solve() {
cin >> s >> n;
dfs(0,0,0,0);
cout << ans << endl;
}
G
虽然给你的语句不超过50，但要是直接模拟的话，也会爆，所以除了原来已经有的“haha”，只要再考虑给出的两个字符串首尾的三个字符，看有没有新的“haha”形成，用map来存储结果
struct S{
string pre,suf;
int cnt;
};
int count(string s) {
int res = 0;
for(int i = 0; i + 3 < sz(s); i++) {
if(s.substr(i, 4) == "haha") res++;
}
return res;
}
string getpre(string s) {
return s.substr(0, min(3LL, sz(s)));
}
string getsuf(string s) {
return s.substr(max(0LL, sz(s) - 3), 3);
}
void solve() {
map<string,S> mp;
int n; cin >> n;
string st,op;
S ans;
for(int i = 1; i <= n; i++) {
cin >> st >> op;
if(op == ":=") {
string s3;
cin >> s3;
mp[st].pre = getpre(s3);
mp[st].suf = getsuf(s3);
mp[st].cnt = count(s3);
}
else {
string t1,t2,x;
cin >> t1 >> x >> t2;
string res = mp[t1].suf + mp[t2].pre;
mp[st].cnt = mp[t1].cnt + mp[t2].cnt + count(res);
mp[st].pre = getpre(mp[t1].pre + mp[t2].pre);
mp[st].suf = getsuf(mp[t1].suf + mp[t2].suf);
}
if(i == n) cout << mp[st].cnt << endl;
}
}
I
显然最小的三角形面积的三个顶点一定是三个相邻的顶点，直接暴力比较就行
struct node {
int x,y;
}a[N];
void solve() {
int n,ans = inf;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
for(int i = 0; i < n; i++) {
int t = (a[(i + 1) % n].x - a[i].x) * (a[(i + 2) % n].y - a[i].y) - (a[(i + 1) % n].y - a[i].y) * (a[(i + 2) % n].x - a[i].x);
ans = min(t,ans);
}
cout << ans << endl;
}
难难难，补了5题就溜了🏃
