Educational Codeforces Round 155 (Rated for Div. 2)
A. Rigged!
解题思路:
若存在\(s[i] >= s[1]\)并且\(e[i] >= e[i]\),那么答案为\(-1\).
否则，答案为\(s[1]\).
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<int> s(n + 1), e(n + 1);
bool sus = true;
bool gs = false;
bool ge = false;
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &s[i], &e[i]);
if (i > 1)
{
if (s[i] >= s[1] && e[i] >= e[1])
{
sus = false;
}
}
}
if (!sus)
{
printf("-1\n");
}
else
{
printf("%d\n", s[1]);
}
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
B .Chips on the Board
解题思路:
要么每行选最小，要么每列选最小。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<int> a(n + 1), b(n + 1);
int mina = 1e9 + 1;
int minb = 1e9 + 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
mina = min(mina, a[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
minb = min(minb, b[i]);
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ans += b[i] + mina;
}
ll res = 0;
for (int i = 1; i <= n; i++)
{
res += a[i] + minb;
}
ans = min(ans, res);
printf("%lld\n", ans);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C. Make it Alternating
解题思路:
找到有多少个连续段\(res\).
每个段中有\(cnt_1,cnt_2,...,cnt_k\)个数。
我们从每个段中选择一个留下来的数\(cnt_1 * cnt_2* ...*cnt_k\),第\(i\)段有\(cnt_i\)中选法。
我们要删掉\(num = \sum_\limits{i = 1}^k cnt_i - res\)个数，每个段只留一个。
将这\(num\)个数进行排列\(num!\)
\(ans = (\prod\limits_{i = 1}^kcnt_i * num!) \%mod\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 998244353;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
ll f[N];
void solve()
{
string s;
cin >> s;
n = s.size();
s = ' ' + s;
ll cnt = 0;
ll ans = 1;
ll res = 0;
for (int i = 2; i <= n; i++)
{
if (s[i] == s[i - 1])
{
cnt++;
}
else
{
if (cnt)
{
ans = (ans * (cnt + 1)) % mod;
}
res += cnt;
cnt = 0;
}
}
if (cnt)
{
ans = (ans * (cnt + 1)) % mod;
res += cnt;
cnt = 0;
}
ans = (ans * f[res]) % mod;
printf("%lld %lld\n", res, ans);
}
int main()
{
int t = 1;
f[0] = 1;
f[1] = 1;
for (int i = 1; i <= N - 5; i++)
{
f[i] = (f[i - 1] * i) % mod;
}
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
D .Sum of XOR Functions
解题思路:
\[\begin{align*} s_k &= \bigoplus_{i=1}^ka_i \\ f(l,r) &= \bigoplus_{i=l}^r a_i \\ &= s_r \oplus s_{l-1} \end{align*} \]\[\begin{align*} ans &= \sum_{l= 1}^n\sum_{r=l}^n f(l,r)\cdot(r - l + 1) \\ &= \sum_{l= 1}^n\sum_{r=l}^n f(l,r)\cdot r- f(l,r)\cdot (l - 1)\\ &= \sum_{l= 0}^n\sum_{r=l}^n (\sum_{i = 1} ^ {32} 2^{i} * ((s_r \& 2^i) \oplus (s_l \&2^i))*(r - l))\\ \end{align*} \]那么对于每一个\(s_i\)来说，假设第\(j\)位为\(1\),他的左侧有\(k\)个数的第\(j\)位为\(0\)。
那么但对于这个数的这一位的和左边比对的的贡献为
\[\begin{align*} res &=2^i [(r-l_1) + (r - l_2) + ... + (r - l _k)]\\ &=2^i[kr - \sum_\limits{i = 1}^kl_i] \end{align*} \]所以，我们在遍历的时候，将所有的\(l_i\)累加，并计算\(k\)即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const int M = 2 * M;
const int mod = 998244353;
typedef pair<int, int> pii;
#define fi first
#define se second
int n, m, k;
void solve()
{
scanf("%d", &n);
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
a[i] ^= a[i - 1];
}
vector<vector<ll>> f(40, vector<ll>(4));
vector<vector<ll>> cnt(40, vector<ll>(4));
ll ans = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 32; j >= 0; j--)
{
if (a[i] >> j & 1)
{
ans = (ans + (((((cnt[j][0] * (ll)i - f[j][0]) % mod + mod) % mod) * (1ll << j)) % mod)) % mod;
f[j][1] = (f[j][1] + i) % mod;
cnt[j][1] = (cnt[j][1] + 1) % mod;
}
else
{
ans = (ans + (((((cnt[j][1] * (ll)i - f[j][1]) % mod + mod) % mod) * (1ll << j)) % mod)) % mod;
f[j][0] = (f[j][0] + i) % mod;
cnt[j][0] = (cnt[j][0] + 1) % mod;
}
}
}
printf("%lld\n", ans);
}
int main()
{
int t = 1;
// scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}