A. Array Coloring
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int sum = 0;
for( int i = 1 , x ; i <= n ; i ++ )
cin >> x , sum += x;
if( sum % 2 == 0 ) cout << "YES\n";
else cout << "NO\n";
return ;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
B. Maximum Rounding
模拟一下进位就好了
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
reverse(s.begin(), s.end());
vector<int> a;
for( auto i : s )
a.push_back( i - '0' );
for( int i = 1 ; i <= 5 ; i ++ ) a.push_back(0);
int p = -1;
for( int i = 0 ; i+1 < a.size() ; i ++ ){
a[i+1] += a[i] / 10 , a[i] %= 10;
if( a[i] > 4 ) a[i+1] ++ , p = i;
}
for( int i = 0 ; i <= p ; i ++ ) a[i] = 0;
while( a.back() == 0 ) a.pop_back();
reverse(a.begin(), a.end());
for( auto i : a )
cout << i ;
cout << "\n";
return ;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
C. Assembly via Minimums
其实这里面数字的顺序是没有影响的。所以规定原始数组为递增的即可。然后比第一个数组大的数字有\(n-1\)个比，第二个数字大的有\(n-2\)个以此类推，所以比第\(i\)个数字大的有\(n-i\)个。因为读入的数字是合法的，所以我们把读入数组排序，然后每次跳\(n-i\)即可
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n , m;
cin >> n , m = n * ( n - 1 ) / 2 ;
vector<int> a(m);
for( auto & i : a ) cin >> i;
sort( a.begin(), a.end() );
for( int i = 1 , j = 0 ; i < n ; i ++ ){
cout << a[j] << " ";
j += n - i;
}
cout << a.back() << "\n";
return ;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
D. Strong Vertices
一个非常经典的套路
\[a_u-a_v\ge b_u-b_v\Rightarrow a_u-b_u\ge a_v-b_v \]所以我们把差值排序，看有多少个和最大值相同即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n;
vector<pair<int,int>> a(n);
for( int i = 0 ; i < n ; i ++ )
cin >> a[i].first , a[i].second = i+1;
for( int i = 0 , x ; i < n ; i ++ )
cin >> x , a[i].first -= x;
sort( a.begin(), a.end());
vector<int> res;
for( int i = n - 1 ; i >= 0 ; i -- ){
if( a[i].first == a.back().first ) res.push_back(a[i].second);
else break;
}
sort( res.begin(), res.end() );
cout << res.size() << "\n";
for( auto i : res )
cout << i << " ";
cout << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
E. Power of Points
这题要离线做，把区间读进来后，按照\(x_i\)排序，然后就可用前缀后缀和来做这题，具体的做法其实就是提共因式。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n;
vector<pair<int, int>> a(n + 1);
int x = 0, y = 0;
for (int i = 1; i <= n; i++)
cin >> a[i].first, a[i].second = i, y += a[i].first;
vector<int> res(n + 1);
sort(a.begin(), a.end());
for (int i = 1, cnt; i <= n; i++) {
res[a[i].second] += y - (n - i + 1) * (a[i].first - 1);
res[a[i].second] += (a[i].first + 1) * (i - 1) - x;
y -= a[i].first, x += a[i].first;
}
for( int i = 1 ; i <= n ; i ++ )
cout << res[i] << " ";
cout << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
F. Sum and Product
这题还是很好想的，设\(a=a_i,b=a_j\)
\[a+b=x,ab=y\\ a = x-b\\ (x-b)b=y\Rightarrow b^2-xb+y=0 \]解出一元二次方程，然后计算出\(a,b\)的值，就可以用组合数来统计答案。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;
cin >> n;
map<int, int> cnt;
for (int i = 1, x; i <= n; i++)
cin >> x, cnt[x]++;
int q;
cin >> q;
for (int x, y, t, a, b; q; q--) {
cin >> x >> y;
t = x * x - 4 * y;
if (t < 0) {
cout << "0 ";
continue;
}
a = (x + sqrt(t)) / 2, b = x - a;
if (a * b != y) {
cout << "0 ";
continue;
}
if (a == b) cout << cnt[a] * (cnt[a] - 1ll) / 2ll << " ";
else cout << cnt[a] * cnt[b] << " ";
}
cout << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
G. Counting Graphs
这道题我赛时没有出，还是比较惭愧的。
考虑Kruskal的过程，如果对于当前加了一条边\(u,v,w\)，那么在\(u\)所在的联通快中任意一个点和\(v\)所在的联通块中任意一个点加一条权值大于\(w\)的边都是无意义的。
所以我们可以用并查集模拟 Kruskal的过程，对于当前边\((u,v,w)\)对答案产生的贡献是\((S-w+1)^{size_u\times size_v - 1}\)
把贡献累积就是答案。
#include <bits/stdc++.h>
using namespace std;
#define int long long
class dsu {
private:
vector<int> fa;
public:
dsu(int n = 1) {
fa = vector<int>(n + 1, -1), fa[0] = 0;
}
int getfa(int x) {
if (fa[x] < 0) return x;
return fa[x] = getfa(fa[x]);
}
void merge(int x, int y) {
x = getfa(x), y = getfa(y);
if (x == y) return;
if (fa[x] > fa[y]) swap(x, y);
fa[x] += fa[y], fa[y] = x;
}
bool same(int x, int y) {
x = getfa(x), y = getfa(y);
return (x == y);
}
int size(int x) {
x = getfa(x);
return -fa[x];
}
};
template<class T>
constexpr T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a)
if (b % 2) res *= a;
return res;
}
template<int P>
struct MInt {
int x;
static int Mod;
constexpr MInt() : x(0) {};
constexpr MInt(int x) : x(norm(x % getMod())) {};
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr static int getMod() {
if (P > 0) return P;
else return Mod;
}
constexpr int norm(int x) const {
if (x < 0) x += getMod();
if (x >= getMod()) x -= getMod();
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
// 隐式类型转换把 MInt转换成 int
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) &{
x = x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) &{
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) &{
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) &{
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
int v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
using Z = MInt<998244353>;
void solve() {
int n , s ;
cin >> n >> s;
vector<tuple<int, int, int>> e(n - 1);
for (auto &[w, u, v]: e)
cin >> u >> v >> w;
sort(e.begin(), e.end());
dsu d(n);
Z res(1);
for( auto [w,u,v] : e ){
int cnt = d.size(u) * d.size(v) - 1;
res *= power( Z( s - w + 1 ) , cnt );
d.merge( u , v );
}
cout << res << "\n";
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
for (; t; t--)
solve();
return 0;
}