C.Game Master
这种1700的题还是挺好想的,多想想哪里漏了,就修出bug了。
12.4 换了正确的方法做B题。
题意:
一共有n个人,两张地图。每个人在两张地图上都有相应的战斗力,一共进行n - 1次竞赛,最终选出胜利者。现在要你安排比赛顺序,问每个人是否能获胜。
思路:
首先很经典的将a[]排序,这时候最大战力的显然可以获胜。
然后模拟样例,发现有一个位置pos,满足b[pos] > b[n]的时候,pos ~ n的人全都能获胜。
这个思路我wa了3发,然后才想到,漏解了。
pos前可能还有pos1,满足b[pos1] > pos ~ n中的某个数。然后就改用ST表来一直更新这个pos。就做完这个题了。
struct node{
int a, b, pos;
bool operator < (const node &k) const {
return a < k.a;
}
}a[N];
int ans[N], BB[N];
struct ST
{
// 注意下标范围是0开始还是1开始,下面有提示
int f_max[N][20], lg[N];
int f_min[N][20];
void init(int a[], int n)
{
lg[0] = -1;
for (int i = 1; i <= n; i++)
{
f_max[i][0] = a[i];
f_min[i][0] = a[i];
if ((i & (i - 1)) == 0) lg[i] = lg[i - 1] + 1;
else lg[i] = lg[i - 1];
}
// 还有这里
f_max[0][0] = a[0];
int t = lg[n];
for (int j = 1; j <= t; j++)
{
// 这里
for (int i = 1; i <= n - (1ll << j) + 1; i++)
{
f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1ll << (j - 1))][j - 1]);
f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1ll << (j - 1))][j - 1]);
}
}
}
int que_max(int l, int r)
{
int k = lg[r - l + 1];
if (l == 0 && r > 0)
{
l = 1;
k = lg[r - l + 1];
return max({f_max[0][0], f_max[l][k], f_max[r - (1ll << k) + 1][k]});
}
return max(f_max[l][k], f_max[r - (1ll << k) + 1][k]);
}
int que_min(int l, int r)
{
int k = lg[r - l + 1];
if (l == 0 && r > 0)
{
l = 1;
k = lg[r - l + 1];
return min({f_max[0][0], f_min[l][k], f_min[r - (1ll << k) + 1][k]});
}
return min(f_min[l][k], f_min[r - (1ll << k) + 1][k]);
}
} S;
void solve()
{
int n;
cin >> n;
fill(ans + 1, ans + 1 + n, 0);
for (int i = 1; i <= n; i++) cin >> a[i].a;
for (int i = 1; i <= n; i++) {
cin >> a[i].b;
a[i].pos = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) BB[i] = a[i].b;
int pos = n, val = a[n].b;
S.init(BB, n);
//往左找最远的位置,这个位置的b值大于现在的val
for (int i = 1; i <= n; i++){
int l = 1, r = pos - 1;
if (l > r) break;
while(l < r){
int mid = (l + r) >> 1;
if (S.que_max(1, mid) > val) r = mid;
else l = mid + 1;
}
if (S.que_max(1, l) > val){
val = S.que_min(l, pos); //打败这个区间的最小值即可
pos = l;
}
}
for (int i = pos; i <= n; i++) ans[a[i].pos] = 1;
for (int i = 1; i <= n; i++) cout << ans[i];
cout << "\n";
}
Build the Permutation
题意:
构造一个排列,有a个峰,b个谷。
做法:
非常暴力。
12.4 换了新的方法做B题,发现从位置1开始交换,会多一个谷地;从位置n开始交换,会多一个山峰。
然后加上之前推过的结论,abs(x - y) >= 2 || x + y > n - 2就无法构造。
剩下的就是分三类讨论了,代码还是很简短的。
注意复制的时候一些细节仍要修改。
int p[N];
bool check(int n, int a, int b)
{
int cnta = 0, cntb = 0;
for (int i = 2; i <= n - 1; i++){
if (p[i - 1] < p[i] && p[i] > p[i + 1]) cnta++;
if (p[i - 1] > p[i] && p[i] < p[i + 1]) cntb++;
}
return (cnta == a && cntb == b);
}
void solve()
{
int n, a, b;
cin >> n >> a >> b;
for (auto val : {a, b}){
for (auto pos : {1, 2}){
for (auto kk : {-1, 0, 1}){
for (auto yy : {-1, 0, -2}){
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = pos, j = 1; i + 1 <= n + yy && j <= val + kk; i += 2, j++){
swap(p[i], p[i + 1]);
}
if (check(n, a, b)){
for (int i = 1; i <= n; i++) cout << p[i] << " ";
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = n, j = 1; i - 1 >= 1 && j <= val + kk; i -= 2, j++){
swap(p[i], p[i - 1]);
}
if (check(n, a, b)){
for (int i = 1; i <= n; i++) cout << p[i] << " ";
cout << "\n";
return;
}
}
}
}
}
cout << "-1\n";
}
int a[N];
void solve()
{
int n, x, y;
cin >> n >> x >> y;
for (int i = 1; i <= n; i++) a[i] = i;
if (abs(x - y) >= 2 || x + y > n - 2){
cout << "-1\n";
return;
}
if (x > y){ //多一个山峰
for (int i = n, j = 1; i - 1 >= 1 && j <= x; i -= 2){
swap(a[i], a[i - 1]);
j++;
}
}
else if (x < y){ //谷地多一个
for (int i = 1, j = 1; i + 1 <= n && j <= y; i += 2){
swap(a[i], a[i + 1]);
j++;
}
}
else {
for (int i = 2, j = 1; i <= n - 1 && j <= x; i += 2){
swap(a[i], a[i + 1]);
j++;
}
}
for (int i = 1; i <= n; i++) cout << a[i] << " ";
cout << "\n";
}