前言：没想到那么快就打了第二场，题目难度比CF Round #509 (Div. 2)这场要难些，不过我依旧菜，这场更是被\(D\)题卡了，最后\(C\)题都来不及敲了。。最后才\(A\)了\(3\)题，幸好\(Rating\)没掉。
A. Benches
Description
有\(n\)个位置，给出每个位置上原本有\(a[i]\)个人。现有\(m\)个人，把他们安排到这\(n\)个位置上，设安排完后位置上人数最多的位置有\(k\)个人，求最大的\(k\)和最小的\(k\)。
Solution
官方正解复杂度为\(O(mn)\)
而我机房里有大佬写了二分答案的做法（传送门）
这里给出我的\(O(n)\)做法。
最大值显然就是\(n\)个位置上原有的最多的人数加上\(m\)。
对于最小值，其实就是去填\(n\)个位置，使得每个位置的人数尽量平均，设原有最多人数为\(maxn\)，则一共可以填\(\sum\limits_{i=1}^n maxn-a[i]\)个人。
若填完后没有剩余，则答案就是\(maxn\)；若有剩余，则将剩余的人平均分配到\(n\)个位置即可。
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 110;
int a[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
int main()
{
int i, n, m, ma = 0, s = 0;
n = re();
m = re();
for (i = 1; i <= n; i++)
{
a[i] = re();
ma = maxn(ma, a[i]);
}
for (i = 1; i <= n; i++)
s += ma - a[i];
if (s >= m)
printf("%d %d", ma, ma + m);
else
printf("%d %d", ma + (int)ceil(1.0 * (m - s) / n), ma + m);
return 0;
}
B. Vitamins
Description
有\(n\)杯果汁，每个果汁需要花费\(a[i]\)，同时会提供维生素，维生素有\(ABC\)三种类型，而每种果汁会提供其中的几种维生素，而\(Petya\)希望获得\(ABC\)三种维生素，求达成目标的最小花费。
Solution
我机房里的大佬写的和正解是一样的（传送门）
而我写了个记忆化搜索，算是玄学复杂度，不过也能过。
对于维生素的储存可以使用压位的方法，并在搜索中记录在已经获得某些维生素的最小花费即可。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int a[N], b[N], f[10], n;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline char re_l()
{
char c = getchar();
for (; c != 'A' && c != 'B' && c != 'C' && c != '\n' && c != '\r' && c > 0; c = getchar());
return c;
}
void dfs(int x, int nw, int se)
{
int i;
if (nw > f[se])
return;
f[se] = nw;
for (i = x; i <= n; i++)
if ((se | b[i]) ^ se)
dfs(i + 1, nw + a[i], se | b[i]);
}
int main()
{
int i, k = 0;
char c;
n = re();
for (i = 1; i <= n; i++)
{
a[i] = re();
while (1)
{
c = re_l();
if (c != 'A' && c != 'B' && c != 'C')
break;
if (c == 'A')
b[i] |= 1;
else
if (c == 'B')
b[i] |= 1 << 1;
else
b[i] |= 1 << 2;
}
k |= b[i];
}
if (k ^ 7)
{
printf("-1");
return 0;
}
memset(f, 60, sizeof(f));
dfs(1, 0, 0);
printf("%d", f[7]);
return 0;
}
C. Array Product
Description
给出一个有\(n\)项的序列\(a\)， 有两种操作
- 选择两个数\(a_i, a_j\)，把\(a_j\)更新为\(a_i\times a_j\)， 将\(a_i\)删去
- 直接删去数\(a_i\) （ 该种操作最多只能进行\(1\)次）
求如何操作才能使\(n-1\)次操作后剩下的那个数最大， 输出操作的方案。
Solution
比赛时因为被\(D\)题卡了，所以没来得及打，赛后才\(A\)的。
显然正数可以忽略，考虑负数和\(0\)，有\(4\)种情况。
- 奇数个负数，存在\(0\)。将\(0\)和绝对值最小的负数相乘，才删去得到的\(0\)，剩下的全部乘起来。
- 奇数个负数，不存在\(0\)。直接删去\(0\)，剩下的全部乘起来。
- 偶数个负数，存在\(0\)。将所有\(0\)乘起来并删去最后得到的\(0\)，剩下的全部乘起来。
- 偶数个负数，不存在\(0\)。直接全部乘起来。
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int ze[N], zer, k;
set<int>se;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
void dze()
{
int i;
for (i = 2; i <= zer; i++)
{
se.erase(ze[i - 1]);
printf("1 %d %d\n", ze[i - 1], ze[i]);
}
if (se.size() ^ 1)
{
se.erase(ze[zer]);
printf("2 %d\n", ze[zer]);
}
}
void alc()
{
int x, s = se.size();
while (s ^ 1)
{
set<int>::iterator it = se.begin();
x = *it;
++it;
printf("1 %d %d\n", x, *it);
se.erase(x);
s--;
}
}
int main()
{
int i, x, n, ma = -1e9, o, fsh = 0;
n = re();
for (i = 1; i <= n; i++)
{
x = re();
if (x < 0)
{
++fsh;
if (ma <= x)
{
ma = x;
o = i;
}
}
else
if (!x)
ze[++zer] = i;
se.insert(i);
}
if (fsh & 1 && zer)
{
printf("1 %d %d\n", o, ze[zer]);
se.erase(o);
dze();
}
else
if (fsh & 1)
{
printf("2 %d\n", o);
se.erase(o);
}
else
if (zer)
dze();
alc();
return 0;
}
D. Petya and Array
Description
给出一个含\(n\)个数的序列\(a\)，和一个数\(t\)，求序列中有多少区间满足\(\sum\limits_{i=l}^{r}a_i<t\)
Solution
求一个后缀和，将问题转化为有多少个子段满足\(S[j]-S[i+1]<t\rightarrow S[j]<t+S[i+1]\)，枚举\(i\)，前面的和用数据结构维护即可。
机房大佬写的是求前缀和，再用树状数组求逆序对维护，道理是差不多的（传送门）
而我比较菜，直接去把我的平衡树板子复制过来，实时插入并求排名来维护。
不过我的\(Splay\)板子出了奇怪的锅，导致在这题上浪费很多时间，还未通过\(4\)次，最后一气之下换了\(Treap\)板子，然后才\(A\)了。。
另外，因为我写平衡树板子的时候没有打空格的习惯，所以代码显得很奇怪。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
struct trp{
ll l,r,s,v,si,rd;
};
trp tr[N];
ll S[N], ro, nu, an;
int a[N];
inline ll re()
{
ll x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
void pp(ll r)
{
tr[r].si=tr[tr[r].l].si+tr[tr[r].r].si+tr[r].s;
}
void rt(ll& r)
{
ll k=tr[r].l;
tr[r].l=tr[k].r;
tr[k].r=r;
tr[k].si=tr[r].si;
pp(r);
r=k;
}
void lt(ll& r)
{
ll k=tr[r].r;
tr[r].r=tr[k].l;
tr[k].l=r;
tr[k].si=tr[r].si;
pp(r);
r=k;
}
void is(ll& r,ll x)
{
if(!r)
{
r=++nu;
tr[r].v=x;
tr[r].s=tr[r].si=1;
tr[r].rd=rand();
return;
}
tr[r].si++;
if(tr[r].v==x)
tr[r].s++;
else
{
if(tr[r].v<x)
{
is(tr[r].r,x);
if(tr[tr[r].r].rd<tr[r].rd)
lt(r);
}
else
{
is(tr[r].l,x);
if(tr[tr[r].l].rd<tr[r].rd)
rt(r);
}
}
}
void qu_fo(ll r,ll x)
{
if(!r)
return;
if(tr[r].v<x)
{
an=r;
qu_fo(tr[r].r,x);
}
else
qu_fo(tr[r].l,x);
}
ll qu_rk(ll r,ll x)
{
if(!r)
return 0;
if(tr[r].v==x)
return tr[tr[r].l].si+tr[r].s;
if(tr[r].v<x)
return tr[tr[r].l].si+tr[r].s+qu_rk(tr[r].r,x);
return qu_rk(tr[r].l,x);
}
ll qu_nu(ll r,ll x)
{
if(!r)
return 0;
if(x<=tr[tr[r].l].si)
return qu_nu(tr[r].l,x);
else
if(x>tr[tr[r].l].si+tr[r].s)
return qu_nu(tr[r].r,x-tr[tr[r].l].si-tr[r].s);
return tr[r].v;
}
int main()
{
srand(20021113);
int i, n;
ll m, qj = 0, j;
n = re();
m = re();
for (i = 1; i <= n; i++)
a[i] = re();
for (i = n; i; i--)
S[i] = S[i + 1] + a[i];
for (i = 1; i <= n; i++)
{
is(ro, S[i]);
an = -1e18;
qu_fo(ro, m + S[i + 1]);
if (an == -1e18)
continue;
j = tr[an].v;
qj += qu_rk(ro, j);
}
printf("%I64d", qj);
return 0;
}