打铁了QAQ
D. Journey to Un'Goro
知识点：贪心 找规律 乱搞
如果字符串全r肯定最优(将任意r换成b不会增加贡献) 问题前半部分直接计算即可
问题后半部分我通过打表寻找规律
首先打个DFS
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define reg register
using namespace std;
const int MAXN = (int)1e5 + 5;
int n, ans = 0, cnt = 0, c[2], res = 0;
bool sum[MAXN];
inline bool Judge() {
c[0] = 1, c[1] = 0;
res = 0;
//for(reg int i = 1; i <= n; ++i) cout << sum[i] << " "; cout << endl;
for(reg int i = 1; i <= n; ++i) {
res += c[sum[i] ^ 1];
++c[sum[i]];
}
//cout << "res : " << res << endl;
//cout << "ans : " << ans << endl;
if(res == ans) return true;
else return false;
}
void DFS(int x) {
if(cnt >= 100) return ;
if(x == n + 1 && cnt < 100) {
if(Judge()) {
for(reg int i = 1; i <= n; ++i) {
if(sum[i] == sum[i - 1]) putchar('b');
else putchar('r');
}
putchar('\n');
++cnt;
}
return ;
}
sum[x] = sum[x - 1];
DFS(x + 1);
sum[x] = sum[x - 1] ^ 1;
DFS(x + 1);
return ;
}
signed main()
{
scanf("%d", &n);
ans = 0;
for(int i = n; i >= 1; --i, --i) ans += i;
printf("%lld", ans);
putchar('\n');
cnt = 0;
sum[0] = 0;
DFS(1);
return 0;
}
简简单单打个50和49的表
//input : 50
650
bbbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbrrbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbrrbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbrrbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbrrbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbrrbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbrrbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbrrbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbrrbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbrrbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbbrrbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbbrrbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrbrrbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbrrrbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrbrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrbrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrbrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrbrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrbrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrbrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrbrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrbrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrbrbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbrrbbb
//input : 49
625
bbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbrrbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbrrbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbrrbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbrrbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbrrbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbrrbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbbrrbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbbrrbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbbrrbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbbrrbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbbrrbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrbrrbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbrrrbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbrrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrbrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbrrrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrbrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbrrrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrbrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbrrrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrbrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbrrrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrbrbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbrrrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrbrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbrrrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrbrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbrrrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrbrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrrrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrbrbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbbrrbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbbrrbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrbrrbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbrrrrbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrbrbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbbbbr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbbbrr
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbbrrb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbbrrbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbbrrbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbbrrbbbb
bbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbrrbbbbrrbbbbb
这边规律需要感性理解 我不好说 带伙看看代码吧
正解
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define reg register
#define JUDGE if(cnt >= 100) return 0;
using namespace std;
const int MAXN = (int)1e5 + 5;
int n, ans = 0, cnt = 0, c[2], res = 0;
bool sum[MAXN];
inline bool Judge() {
c[0] = 1, c[1] = 0;
res = 0;
//for(reg int i = 1; i <= n; ++i) cout << sum[i] << " "; cout << endl;
for(reg int i = 1; i <= n; ++i) {
res += c[sum[i] ^ 1];
++c[sum[i]];
}
//cout << "res : " << res << endl;
//cout << "ans : " << ans << endl;
if(res == ans) return true;
else return false;
}
void DFS(int x) {
if(cnt >= 100) return ;
if(x == n + 1 && cnt < 100) {
if(Judge()) {
for(reg int i = 1; i <= n; ++i) {
if(sum[i] == sum[i - 1]) putchar('b');
else putchar('r');
}
putchar('\n');
++cnt;
}
return ;
}
sum[x] = sum[x - 1];
DFS(x + 1);
sum[x] = sum[x - 1] ^ 1;
DFS(x + 1);
return ;
}
signed main()
{
//freopen("r.in", "r", stdin);
//freopen("d.out", "w", stdout);
scanf("%d", &n);
ans = 0;
for(int i = n; i >= 1; --i, --i) ans += i;
printf("%lld", ans);
putchar('\n');
cnt = 0;
if(n <= 30) {
DFS(1);
return 0;
}
int l = ceil(1.0 * (n - 1) / 2), r = floor(1.0 * (n - 1) / 2);
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r; i++) putchar('b'); putchar('\n');
cnt++; JUDGE
l--; r++;
if(n % 2 == 0) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r; i++) putchar('b'); putchar('\n');
cnt++; JUDGE
}
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i < r; i++) putchar('b'); putchar('r'); putchar('\n');
cnt++; JUDGE
for(int k = 0; r - 2 - k >= 0; k++) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r');
for(int i = 1; i <= r - 2 - k; i++) putchar('b');
putchar('r'); putchar('r');
for(int i = 1; i <= k; i++) putchar('b');
putchar('\n'); cnt++; JUDGE
}
l--; r++;
if(n % 2 == 0) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 2; i++) putchar('b'); putchar('b'); putchar('r'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 2; i++) putchar('b'); putchar('r'); putchar('b'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 2; i++) putchar('b'); putchar('r'); putchar('r'); putchar('\n');
cnt++; JUDGE
} else {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 3; i++) putchar('b'); printf("brb\n");
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 3; i++) putchar('b'); printf("rbr\n");
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - 3; i++) putchar('b'); printf("rrr\n");
cnt++; JUDGE
}
if(n % 2 == 1) {
for(int k = 0; r - k - 3 >= 0; k++) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i < r - k - 3; i++) putchar('b'); printf("rbr"); for(int i = 1; i <= k; i++) putchar('b'); putchar('b'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i < r - k - 3; i++) putchar('b'); printf("rrb"); for(int i = 1; i <= k; i++) putchar('b'); putchar('r'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - k - 3 - 1; i++) putchar('b'); printf("rr"); for(int i = 1; i < k + 1; i++) putchar('b'); putchar('r'); putchar('r'); putchar('\n');
//printf("\n");
cnt++; JUDGE
for(int kk = 0; k + 1 - 2 - kk >= 0; kk++) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r');
for(int i = 1; i < r - (k + 1) - 2; i++) putchar('b'); putchar('r'); putchar('r');
for(int i = 1; i <= k + 1 - 2 - kk; i++) putchar('b');
putchar('r'); putchar('r');
for(int i = 1; i <= kk + 1; i++) putchar('b');
putchar('\n'); cnt++; JUDGE
}
}
} else {
for(int k = 0; r - k - 3 >= 0; k++) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - k - 3; i++) putchar('b'); printf("rbr"); for(int i = 1; i <= k; i++) putchar('b'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - k - 3; i++) putchar('b'); printf("rrb"); for(int i = 1; i <= k; i++) putchar('b'); putchar('\n');
cnt++; JUDGE
for(int i = 1; i <= l; i++) putchar('b'); putchar('r'); for(int i = 1; i <= r - k - 3; i++) putchar('b'); printf("rr"); for(int i = 1; i <= k; i++) putchar('b'); putchar('r'); putchar('\n');
cnt++; JUDGE
for(int kk = 0; k + 1 - 2 - kk >= 0; kk++) {
for(int i = 1; i <= l; i++) putchar('b'); putchar('r');
for(int i = 1; i <= r - (k + 1) - 2; i++) putchar('b'); putchar('r'); putchar('r');
for(int i = 1; i <= k + 1 - 2 - kk; i++) putchar('b');
putchar('r'); putchar('r');
for(int i = 1; i <= kk; i++) putchar('b');
putchar('\n'); cnt++; JUDGE
}
}
}
return 0;
}
F. Kobolds and Catacombs
知识点：模拟
先对数组离散化一下 找到每个数排序后的位置
关键在于每个数排序后应该放在哪个位置
这样我们可以通过遍历数组 用区间中每个数的排序后位置扩展maxr得到一个区间的右边界 每次maxr=-1(已经得出一个区间，重新初始化maxr)时答案++即可
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
//#define int long long
using namespace std;
const int MAXN = (int)1e6 + 5;
struct Node {
int val, idx, hval;
}a[MAXN];
int n;
bool cmp1(Node &a, Node &b) {
if(a.val == b.val) return a.idx < b.idx;
return a.val < b.val;
}
bool cmp2(Node &a, Node &b) {
return a.idx < b.idx;
}
void Init() {
sort(a + 1, a + 1 + n, cmp1);
for(int i = 1; i <= n; i++) {
a[i].hval = i;
}
sort(a + 1, a + 1 + n, cmp2);
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i].val);
a[i].idx = i;
}
int ans = 0;
Init(); //离散化
int maxr = -1;
for(int i = 1; i <= n; i++) {
maxr = max(maxr, a[i].hval);
if(i >= maxr) {
maxr = -1;
ans++;
}
}
printf("%d", ans);
return 0;
}
K. Scholomance Academy
知识点：模拟 贪心
当θ变大时 TPR和FPR变大
注意到AUC函数满足单调性（当r较大时 我们让FPR尽量大 这样可以让θ尽量大 使得TPR变大）
且为若干段斜率为0的直线（当r在一段较小的区间内波动时 FPR不会变化 如果让TPR尽量大 就令θ尽量大 此时TPR也不会变化）
我们可以分割成一个个矩形求面积
在遍历的时候将函数分成\(TN+FP\)段 每一段长度为\(\frac{1}{TN+FP}\qquad\)
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define int long long
#define eps 1e-9
using namespace std;
const int MAXN = (int)1e6 + 5;
struct Node {
char op;
int val;
}a[MAXN];
int n, TNFP, TPFN, TP, FP;
bool cmp(Node& a, Node& b) {
if(a.val == b.val) {
if(b.op == '+') return false;
if(a.op == '+') return true;
}
return a.val < b.val;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].op >> a[i].val;
if(a[i].op == '+') {
TPFN++;
} else {
TNFP++;
}
}
sort(a + 1, a + 1 + n, cmp);
TP = TPFN, FP = 0;
int tot = 0;
for(int i = 1; i <= n; i++) {
if(a[i].op == '+') {
TP--;
} else {
tot += TP;
}
}
long double ans = 1.0 * tot / (TPFN * TNFP);
printf("%.9Lf", ans);
//cout << ans;
return 0;
}
/*
3
+ 2
- 3
- 1
6
+ 7
- 2
- 5
+ 4
- 2
+ 6
8
+ 34
+ 33
+ 26
- 34
- 38
+ 39
- 7
- 27
*/