牛客小白月赛87
小苯的石子游戏
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
int x = 0;
int y = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int cur = 1;
for (int i = n; i; i--)
{
if (cur & 1)
{
x += a[i];
}
else
{
y += a[i];
}
cur++;
}
if (x > y)
{
puts("Alice");
}
else
{
puts("Bob");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的排序疑惑
解题思路：
最小在首位或最大在尾部即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
int maxa = -1e9 - 1;
int mina = 1e9 + 1;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxa = max(maxa, a[i]);
mina = min(mina, a[i]);
}
if (a[1] == mina || a[n] == maxa)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的IDE括号问题（easy）
解题思路:
双向链表删改即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
int cur = 0;
n = s.size();
s = ' ' + s;
vector<int> l(n + 1, 0), r(n + 1, n + 1);
for (int i = 1; i <= n; i++)
{
if (s[i] == 'I')
{
cur = i;
}
l[i] = i - 1;
r[i] = i + 1;
}
auto del = [&](int u)
{
if (l[u] > 0)
{
r[l[u]] = r[u];
}
if (r[u] <= n)
{
l[r[u]] = l[u];
}
};
while (q--)
{
string t;
cin >> t;
if (t[0] == 'b')
{
array<bool, 2> vis;
if (r[cur] <= n)
{
vis[0] = true;
}
if (l[cur] > 0)
{
vis[1] = true;
}
if (!vis[1])
{
continue;
}
else
{
if (vis[0] && s[l[cur]] == '(' && s[r[cur]] == ')')
{
del(l[cur]);
del(r[cur]);
}
else
{
del(l[cur]);
}
}
}
else
{
array<bool, 2> vis;
if (r[cur] <= n)
{
vis[0] = true;
}
if (vis[0])
{
del(r[cur]);
}
}
}
string ls, rs;
int t = cur;
while (true)
{
ls += s[t];
t = l[t];
if (t == 0)
{
break;
}
}
reverse(ls.begin(), ls.end());
ls.pop_back();
t = cur;
while (true)
{
rs += s[t];
t = r[t];
if (t == n + 1)
{
break;
}
}
ls += rs;
cout << ls << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的IDE括号问题（hard）
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
int cur = 0;
n = s.size();
s = ' ' + s;
vector<int> l(n + 1, 0), r(n + 1, n + 1);
for (int i = 1; i <= n; i++)
{
if (s[i] == 'I')
{
cur = i;
}
l[i] = i - 1;
r[i] = i + 1;
}
auto del = [&](int u)
{
if (l[u] > 0)
{
r[l[u]] = r[u];
}
if (r[u] <= n)
{
l[r[u]] = l[u];
}
};
while (q--)
{
string t;
cin >> t;
if (t[0] == 'b')
{
array<bool, 2> vis;
if (r[cur] <= n)
{
vis[0] = true;
}
if (l[cur] > 0)
{
vis[1] = true;
}
if (!vis[1])
{
continue;
}
else
{
if (vis[0] && s[l[cur]] == '(' && s[r[cur]] == ')')
{
del(l[cur]);
del(r[cur]);
}
else
{
del(l[cur]);
}
}
}
else if (t[0] == 'd')
{
array<bool, 2> vis;
if (r[cur] <= n)
{
vis[0] = true;
}
if (vis[0])
{
del(r[cur]);
}
}
else if (t[0] == '<')
{
if (l[cur] > 0)
{
swap(s[cur], s[l[cur]]);
cur = l[cur];
}
}
else
{
if (r[cur] <= n)
{
swap(s[cur], s[r[cur]]);
cur = r[cur];
}
}
}
string ls, rs;
int t = cur;
while (true)
{
ls += s[t];
t = l[t];
if (t == 0)
{
break;
}
}
reverse(ls.begin(), ls.end());
ls.pop_back();
t = cur;
while (true)
{
rs += s[t];
t = r[t];
if (t == n + 1)
{
break;
}
}
ls += rs;
cout << ls << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的数组构造
解题思路:
整个\(b\)数组同时加减一个数不影响答案正确性，我们先默认\(b_1 = 0\)。
若\(a_i > a_j,(i < j)\)，\(dif = abs(a_i - a_j)\)，我们有两种方法\(a_i - dif,a_j + dif\)。两种操作对于首位\(0\)带来的极差影响是一样的，我们往后统一只加不减。
所以，每个元素只需要加到和前缀最大值一样即可。
代码:
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
long long pre = a[1];
long long ans = 0;
vector<long long> b(n + 1, 0);
for (int i = 2; i <= n; i++)
{
if (a[i] < pre)
{
b[i] = pre - a[i];
}
pre = max(pre, a[i]);
}
for (int i = 1; i <= n; i++)
{
cout << b[i] << ' ';
}
cout << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的数组切分
解题思路:
\(\&\):由于是最后一段数组，该操作包含元素越多，区间总权值只可能越小，所以，最后一段只有\(a_n\)。
接下来就是两段区间和\((1,i) + (i + 1, n - 1)\)，预处理前后缀和后，枚举分界点即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
vector<int> pre(n + 1), suf(n + 1);
for (int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1] ^ a[i];
}
for (int i = n - 1; i > 0; i--)
{
suf[i] = suf[i + 1] | a[i];
}
ll ans = 0;
for (int i = 1; i <= n - 2; i++)
{
ans = max(ans, (ll)pre[i] + suf[i + 1] + a[n]);
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小苯的逆序对
解题思路:
\(g[x]:gcd 为x的倍数的数组对数\)
\(f[x]:gcd恰好为x的数组对数\)
\(f[x] = g[x] - g[2x] - g[3x] -...-g[kx],ps:(k+1)x > n\)。
\(\lfloor\frac{n}{i}\rfloor:1\sim n 内i的倍数有多少个\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 2e5 + 10;
ll f[N];
ll tr[N];
ll n;
void add(int x, int v)
{
for (int i = x; i <= n; i += (i & -i))
{
tr[i] += v;
}
}
ll query(int x)
{
ll res = 0;
for (int i = x; i; i -= (i & -i))
{
res += tr[i];
}
return res;
}
void solve()
{
cin >> n;
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
pos[x] = i;
}
for (int i = n; i; i--)
{
for (int j = i; j <= n; j += i)
{
f[i] += (j / i) - 1 - query(pos[j]);
add(pos[j], 1);
}
for (int j = i; j <= n; j += i)
{
add(pos[j], -1);
if (j != i)
{
f[i] -= f[j];
}
}
}
cout << f[1] << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}