F. Inverse Manacher
题意：
给定回文半径数组，构造回文串(只包含a， b)
分析：
题目保证一定合法，我们考虑每个'|'位置上的回文半径
- 如果 r = 1：说明前一个位置与后一个位置上的字符不同
- 如果 r > 1：说明前一段位置与后一段位置回文，则要保证前后位置上的字符相同
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n;
int a[N];
char res[N];
string s;
char re(char c)
{
if (c == 'a')
return 'b';
else
return 'a';
}
void solve()
{
cin >> n;
for (int i = 0; i <= 2 * n + 1; i++)
cin >> a[i];
res[0] = '&', res[1] = '|', res[2] = 'a';
for (int i = 3; i <= 2 * n + 1; i++)
{
if (i & 1)
{
res[i] = '|';
if (a[i] == 1)
res[i + 1] = re(res[i - 1]);
else
res[i + 1] = res[i - 1];
}
}
for (int i = 2; i <= 2 * n + 1; i += 2)
cout << res[i];
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
J. Expansion
题意：
由 1 开始依次向后选择，有两种方案：
- 若选择下一个数，则将当前的总和加上选择的数的前缀和
- 若不选择，则将当前的总和加上当前的数的前缀和
要保证每一步之后的总和不能为负，且到达最后一个点之后一直加上总和的值不能为负
分析：
贪心地想：若选择加上某一前缀后总和为负，应当在此前的最大前缀位置上停留更长的时间；
此外，当前一段前缀和为负或者所有数的和为负时直接return
处理前缀和时，pre数组记录到当前位置位置的最大前缀和的位置，然后每个点都去判断一次，大于等于0就继续往后跑，小于0就要回到pre[i]使总和非负
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n;
int res;
int a[N];
int pre[N], s[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
bool f = true;
for (int i = 1; i <= n; i++)
{
if (a[i] < 0)
f = false;
else if (a[i] > 0)
break;
}
if (!f || s[n] < 0)
{
cout << "-1" << endl;
return;
}
else
{
int maxv = -INF, pos = 1;
for (int i = 1; i <= n; i++)
{
if (s[i] >= maxv)
{
maxv = s[i];
pos = i;
}
pre[i] = pos;
}
int sum = 0;
for (int i = 1; i <= n; i++)
{
res++;
sum += s[i];
if (sum < 0)
{
int add = 0;
add = abs(sum) / s[pre[i]] + (abs(sum) % s[pre[i]] != 0);
res += add;
sum += add * s[pre[i]];
}
}
}
cout << res << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
H. Binary Craziness
题意：
已知每个点的度，求每两个点度数a，b的 $ f(a, b) = (a|b)(a&b)(a^b) $ 相乘的和$ \sum_{i=1}^n \sum_{j=i}^n f(i, j) $
分析：
度数总和为 2m ，所以每个点的出度情况不会超过$ \sqrt{2m} \quad $
记录每个数出现的次数 f[i] ，枚举时乘法优化计算次数即可
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 998244353;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n, m;
int a[N], cnt[N];
int f(int x, int y)
{
return (x ^ y) * (x | y) * (x & y);
}
void solve()
{
cin >> n >> m;
for (int i = 1, x, y; i <= m; ++i)
{
cin >> x >> y;
a[x]++, a[y]++;
}
for (int i = 1; i <= n; ++i)
cnt[a[i]]++;
vector<int> v;
for (int i = 1; i <= 2 * m; ++i)
if (cnt[i])
v.push_back(i);
int res = 0;
for (int i = 0; i < v.size(); ++i)
{
for (int j = i + 1; j < v.size(); ++j)
{
res = (res + cnt[v[i]] * cnt[v[j]] % MOD * f(v[i], v[j]) % MOD) % MOD;
}
}
cout << res << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}