cf2009 Codeforces Round 971 (Div. 4)
A. Minimize!
签到题。计算\((c-a)+(b-c)\)的最小值，其实值固定的，等于\(b-a\)。
int a, b;
void solve()
{
cin >> a >> b;
cout << b - a << endl;
}
B. Osu!mania
签到题。给定一个4k下落式的网格，求#下落顺序。直接数组记录就好了。
int n;
const int N = 500;
char s[N][4];
int v[N];
void solve(void)
{
cin >> n;
int vlen = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 4; ++j)
{
cin >> s[i][j];
if (s[i][j] == '#')
{
v[vlen++] = j + 1;
}
}
}
for (int i = vlen - 1; i >= 0; --i)
{
cout << v[i] << " \n"[i == 0];
}
}
C. The Legend of Freya the Frog
签到题。一个人从\((0,0)\)出发跳跃到\((x,y)\)。每步只能跳\(d\)格，\(0\leq d \leq k\)。并且，当朝着\(x/y\)方向跳了一次后，下次就会朝着\(y/x\)方向。这个人初始朝向\(x\)方向。给定\((x,y),k\)求跳的最小次数。
小学数学算一下是x->y->x->y->x还是x->y->x->y就行了。
ll x, y, k;
void solve()
{
cin >> x >> y >> k;
ll dx = (x + k - 1) / k, dy = (y + k - 1) / k;
ll res = -1;
if (dx > dy)
{
res = (dx << 1) - 1;
}
else
{
res = dy << 1;
}
cout << res << endl;
}
D. Satyam and Counting
水题。现在有一个1xn的网格，给出\(n\)个这个网格上已有的格点坐标。求这些格点能组成多少个直角三角形。分情况讨论再加起来就行。
-
两个点能组成一条竖边，则剩下的\(n-2\)个点都可以和它们组成三角形。遍历所有点，记录竖边数量\(c_1\)，则这种三角形就有\(c_1\times (n-2)\)个。
-
两个点能组成一条斜边。然后它们中间也有一个点。不要忘记
(1,1)(2,0)(3,1)这样颠倒过来也能组成三角形就行了。遍历的时候记录一下即可。
int n;
const int N = 2e5 + 5;
int a[N][2];
void solve()
{
scanf("%d", &n);
for (int i = 0; i <= n + 1; ++i)
{
a[i][0] = a[i][1] = 0;
}
int p, q;
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &p, &q);
a[p][q] = 1;
}
ll one = 0, two = 0, three = 0;
for (int i = 0; i <= n; ++i)
{
if (a[i][0] && a[i][1])
{
one = one + n - 2;
}
if (i + 2 <= n && a[i][0] && a[i + 1][1] && a[i + 2][0])
{
two++;
}
if (i + 2 <= n && a[i][1] && a[i + 1][0] && a[i + 2][1])
{
three++;
}
}
printf("%lld\n", one + two + three);
}
E. Klee's SUPER DUPER LARGE Array!!!
Klee有一个长度为n的序列[k,k+1,...,k+n-1]，他想选定一个下标\(i\)，使得\(x=|a_1+a_2+..+a_i-a_{i+1}-...-a_n|\)最小。\(2\leq n,k\leq 10^9\)。
水题，这个\(x\)随着\(i\)变大，必是单调增加的，所以二分即可。（狼狈回忆二分）
ll n, k;
ll check(ll x)
{
ll right = (n + k - 1) * (n + k) / 2LL - (x + 1) * x / 2LL;
ll left = (x + 1) * x / 2LL - (k - 1) * k / 2LL;
return right - left;
}
void solve()
{
cin >> n >> k;
ll res = 1e18;
ll l = 1, r = n + k - 1;
while (l < r)
{
ll mid = (l + r) >> 1;
ll cur = check(mid);
res = min(res, abs(cur));
if (cur <= 0)
{
r = mid;
}
else
{
l = mid + 1;
}
}
cout << res << endl;
}
F. Firefly's Queries
小水题。有一个长度为\(n\)的数组\(a[n]\)。然后定义了一个cyclic shift的操作。（The x-th\((1\leq x\leq n)\) cyclic shift of the array a is \(a_x,a_{x+1},...,a_n,a_1,a_2,...,a_{x-1}\)）。\(c_i\)就代表了\(a\)的第\(i\)个cyclic shift数组。然后又创建数组\(b\)等于\(c_1,c_2,...,c_n\)（所有的\(c_i\) concatenation到一起）。现有\(q\)次查询，每次查询输出\(b[l:r]\)的元素和。
包含整个\(c_i\)的部分就是\(a[1:n]\)，然后再加上一个小尾巴就行了。
int n, q;
const int N = 2e5 + 5;
int a[N];
ll pre[N];
ll cal(ll x)
{
if (x < 0LL)
return 0LL;
ll p = x / n, q = x % n;
if (p == 0)
{
return pre[x];
}
ll left = pre[n - 1] * p;
ll pos = (p + q) % n;
ll right = 0;
if (pos >= p)
{
right = pre[pos] - pre[p - 1];
}
else
{
right = pre[n - 1] - pre[p - 1] + pre[pos];
}
return left + right;
}
void solve()
{
cin >> n >> q;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
pre[i] = (i == 0) ? (a[i]) : (pre[i - 1] + a[i]);
}
ll l, r;
while (q--)
{
cin >> l >> r;
ll lres = cal(l - 2), rres = cal(r - 1);
cout << rres - lres << endl;
}
}
G1. Yunli's Subarray Queries (easy version)
有点思维的水题。题面：
对于任意数组\(b\)（下标从1开始），Yunli可以执行以下操作任意次：
- 选择下标\(i\)，令\(b[i]=x\)，\(x\)可以是任意整数。
设\(f(b)\)为她把\(b\)变成一个满足以下条件的数组的最小操作次数：存在长度\(\geq k\)的子序列\(b_{sub}\)（下标从1开始），\(\forall j>1, b_{sub}[j]=b_{sub}[j-1]+1\)。（consecutive subarray）
现给定数组\(a[n]\)以及\(q\)次查询，在每次查询时，输出\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。在easy version中，\(r\equiv l+k-1\)。也就是说，输出的是\(f([a_l,a_{l+1},..,a_j])\)。
数据范围：\(n\leq 2\times 10^5, q\leq 2\times 10^5, 1\leq a[i]\leq n\)。
思路：
首先，我们要知道这样一件事：怎么找一个consecutive subarray？
(1)(2)(3)(4)(5)(6) k=3
2 3 4 9 6 11
对于这个\(a[n]\)，我们知道可以把2，3，4，x，6中的x改为5，也可以将9，x，11中的x改为10。或者我们可以换一种角度看问题：2，3，4，(x)，6是属于一组的，9，(x)，11是属于另一组的。想要判断数与数之间有没有属于同一组的机会，我们只要对数组\(a\)做一个简单的操作。
令\(a'[i]=a[i]-i\)，此时
(1)(2)(3)(4)(5)(6) k=3
1 1 1 5 1 5
能看出这件事，这道题就结束了。做一个长度为\(k\)的滑动窗口，记录目前的窗口中数量最多的元素即可。
int n, k, q;
const int N = 2e5 + 5;
int a[N], res[N];
void solve()
{
cin >> n >> k >> q;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
int last = a[0];
map<int, int> mp;
set<pii, greater<pii>> s;
for (int i = 0; i < n; ++i)
{
if (i >= k)
{
res[i - k] = k - s.begin()->first;
}
// add nxt
if (mp.count(a[i] - i))
{
pii cur = pii(mp[a[i] - i], a[i] - i);
if (s.count(cur))
s.erase(cur);
}
mp[a[i] - i]++;
s.insert(pii(mp[a[i] - i], a[i] - i));
// erase last
if (i >= k)
{
s.erase(pii(mp[last - i + k], last - i + k));
if (mp[last - i + k] == 1)
{
mp.erase(last - i + k);
}
else
{
mp[last - i + k]--;
s.insert(pii(mp[last - i + k], last - i + k));
}
last = a[i - k + 1];
}
}
res[n - k] = k - s.begin()->first;
while (q--)
{
int l, r;
cin >> l >> r;
cout << res[l - 1] << endl;
}
}
G2. Yunli's Subarray Queries (hard version)
这题是上题的困难版本，其中\(r\)的条件改变为\(r\geq l+k-1\)，求\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。
这题需要用到上一题的结论，令\(p_i\)为滑动窗口的起始位置为\(i\)时，记录的\(a'[i:i+k-1]\)重复数量最多的元素数。\(c_i=k-p_i\)，也就是\(c_i=f([a_l,a_{l+1},..,a_{l+k-1}])\)。则\(f([a_l,a_{l+1},..,a_j])=\min(c_l, c_{l+1},..,c_{j-k+1})\)。
区间求最值可以用线段树or树状数组来做，但是还要解决另一个事情，我们要求的是\(\sum\limits^r_{j=l+k-1}\min\{c[l:j-k+1]\}\)，还有个区间求和。再进一步观察，可以看到另一条性质。假设数组\(c\)如下：
(1)(2)(3)(4)(5)(6)(7)
1 3 7 4 5 3 6
现在我们算\(c[4]\sim c[7]\)这段的值
(1)(2)(3)(4)(5)(6)(7)
4 4 3 3
可以看到，值是单调非增的。也就是说，当\(l=4\)时，\(c[4]=4\)，这个值会一直覆盖后面的值，直到发现了\(c[6]<4\)，则再往后更新就用\(c[6]\)的值更新后面的。那我们就可以想到用一个单调栈来解决这件事。从后往前遍历，当遍历到\(c[cur]\)时，弹出栈顶元素\(c[top]\)，直到\(c[top]<c[cur]\)。然后将\(c[cur]\sim c[top-1]\)的值都更新为\(c[cur]\)。然后再通过区间求和算出此时的\(\sum\limits _{i=cur} ^{r}c_i\)即可，时间复杂度\(O(n\log n)\)。
int n, k, q;
const int N = 2e5 + 5;
ll a[N], c[N];
ll res[N];
struct node{
int l, r;
ll v, lz;
};
node seg[N<<2];
void pushup(int oo){
seg[oo].v = seg[ls].v + seg[rs].v;
}
void pushdown(int oo){
int mid = seg[oo].l + seg[oo].r >> 1;
seg[ls].v = seg[oo].lz * (mid - seg[oo].l + 1LL);
seg[rs].v = seg[oo].lz * (seg[oo].r - mid);
seg[ls].lz = seg[rs].lz = seg[oo].lz;
seg[oo].lz = 0;
}
void build(int oo, int l, int r){
seg[oo] = node{l, r, 0LL, 0LL};
if (l >= r) return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
pushup(oo);
}
void update(int oo, int x, int y, ll val){
int l = seg[oo].l, r = seg[oo].r;
if (x <= l && y >= r){
seg[oo].v = val * (r - l + 1);
seg[oo].lz = val;
return;
}
int mid = l + r >> 1;
if (seg[oo].lz) pushdown(oo);
if (mid >= x) update(ls, x, y, val);
if (y > mid) update(rs, x, y, val);
pushup(oo);
}
ll query(int oo, int x, int y){
int l = seg[oo].l, r = seg[oo].r;
if (x <= l && y >= r){
return seg[oo].v;
}
ll ans = 0;
int mid = l + r >> 1;
if (seg[oo].lz) pushdown(oo);
if (x <= mid) ans += query(ls, x, y);
if (y > mid) ans += query(rs, x, y);
return ans;
}
void calc(){
map<int, int> mp;
set<pii, greater<pii> > st;
for (int i = 1; i <= n; ++i){
// pop last
if (i > k){
int last = a[i - k] - i + k;
st.erase(pii(mp[last], last));
mp[last]--;
if (mp[last] == 0) mp.erase(last);
else st.insert(pii(mp[last], last));
}
// push cur
st.erase(pii(mp[a[i] - i], a[i] - i));
mp[a[i] - i]++;
st.insert(pii(mp[a[i] - i], a[i] - i));
// calculate c value
if (i >= k){
pii x = *st.begin();
c[i - k + 1] = - x.first;
}
}
}
void solve(){
cin >> n >> k >> q;
vector<vector<pii> > vec(n - k + 2);
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
int l, r;
for (int i = 1; i <= q; ++i){
cin >> l >> r;
vec[l].push_back(pii(r - k + 1, i));
}
calc();
build(1, 1, n - k + 1);
stack<int> stk;
for (int i = n - k + 1; i >= 1; --i){
while (!stk.empty() && c[i] <= c[stk.top()]){
stk.pop();
}
int ed = stk.empty() ? (n - k + 1) : (stk.top() - 1);
stk.push(i);
update(1, i, ed, c[i]);
for (auto p: vec[i]){
res[p.second] = 1LL * (p.first - i + 1) * k + query(1, i, p.first);
}
}
for (int i = 1; i <= q; ++i){
cout << res[i] << endl;
}
}