CF2189

A. Table with Numbers

code

#include<bits/stdc++.h>
using namespace std;
const int NN = 108;
int a[NN];
void solve(){int n,h,l;cin >> n >> h >> l;if(h > l) swap(h,l);for(int i = 1; i <= n; ++i) cin >> a[i];sort(a+1,a+1+n);int pos = upper_bound(a+1,a+1+n,h) - a,pos2 = upper_bound(a+1,a+1+n,l) - a;int lw = pos - 1, up = pos2 - pos;if(up > lw) cout << lw << '\n';else cout << (up+lw) / 2 << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(0);int T;cin >> T;while(T--){solve();}
} 

B. The Curse of the Frog

tag: 贪心

我们首先把所有免费额度全部跳完 \(\sum a_i \times (b_i-1)\)

之后便是每次跳跃都会花费一个额度，向前跳 \(w_i = a_i \times b_i - c_i\)

所以每次贪心选择 \(w_i\) 最大的进行跳跃即可

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 2e18;
void solve(){ll n,x;cin >> n >> x;ll now = 0,maxn = -INF;for(int i = 1; i <= n; ++i){ll a,b,c;cin >> a >> b >> c;now += a * (b-1);maxn = max(a * b - c, maxn);}if(now >= x){cout << "0\n";return;}else{if(maxn <= 0) cout << "-1\n";else{cout << (x - now + maxn - 1) / maxn << "\n";}}
}
int main()
{ios::sync_with_stdio(false),cin.tie(0);int T;cin >> T;while(T--){solve();}return 0;
}

C1. XOR Convenience (Easy Version)

直接让 \(a_n = 1\) 即可，剩下的 \(a_i = i \oplus 1(2\leq i \leq n-1)\)

code

#include<bits/stdc++.h>
using namespace std;
void solve(){int n;cin >> n;if(n == 1){cout << "1\n";}else if(n % 2 == 0){cout << n << " ";for(int i = 2; i < n; ++i){cout << (i ^ 1) << " ";}cout << "1\n";}else{cout << n-1 << " ";for(int i = 2; i < n; ++i){cout << (i ^ 1) << " ";}cout << "1\n"; }
}
int main()
{ios::sync_with_stdio(false),cin.tie(0);int T;cin >> T;while(T--){solve();}return 0;
}

C2. XOR-convenience (Hard Version)

如果 \(n\) 为奇数，那么 \(f_{n-1} = 1,\ f_1 = n-1,\ f_n = n,\ f_i = i \oplus 1\)

\(n\) 为 \(2^k\) 无解

如果 \(n\) 为偶数，C1 的基础上交换 \(a_1, a_{lowbit(n)}\) 即可

code

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int a[NN];
inline int lowbit(int x){return x & (-x);}
int main()
{ios::sync_with_stdio(false),cin.tie(0);int T;cin >> T;while(T--){int n;cin >> n;int m = n; while((m&1) == 0){m >>= 1;}if(m == 1 && n != 1) cout << -1 << '\n';else if(n == 1){cout << "1\n";continue;}else if(n % 2 == 0){for(int i = 2; i <= n-1; ++i){a[i] = i ^ 1;}a[1] = n;a[n] = 1;swap(a[1],a[lowbit(n)]);for(int i = 1; i <= n; ++i) cout << a[i] << " ";cout << "\n";}else{cout << n - 1 << " ";for(int i = 2; i <= n-2; ++i){cout << (i ^ 1) << " ";}cout << "1 " << n << '\n';}}return 0;
}