「题单」IOI2020国家集训队作业 Part 1

CF505E Mr. Kitayuta vs. Bamboos

  • 给定 \(n\) 个数(竹子的高度) \(h_{1 \dots n}\)
  • 你需要进行 \(m\) 轮操作,每轮操作为 \(k\) 次修改,每次修改可以选择一个数 \(h_i\) 修改为 \(\max(h_i - p, 0)\)(砸到地下)。
  • 每轮操作后每个 \(h_i\) 将会被修改为 \(h_i + a_i\)(每天竹子会生长)。
  • 你需要最小化最终 \(h_{1 \dots n}\) 中的最大值。
  • \(n \le 10^5\)\(m \le 5 \times 10^3\)\(k \le 10\) 要求最小化最大值,考虑二分一个最大的高度,将问题转化成可行性问题,即,给出一个高度,问能否使这些竹子最终不超过这个高度。

考虑限制这个问题不平凡的因素:因为每次降低竹子高度的时候不能保证竹子一定降低 p ,也就是说,“砸竹子”这一动作存在浪费。我们考虑尽可能的让“砸竹子”这一动作更少的浪费,即:尽可能在后面的时间点砸竹子,但是无法保证到底是在哪一次砸竹子,有可能已经结束了,没有形式化的计算流程。

可以考虑反向思考,即:假设已经长到 二分的高度。每次生长操作相当于每次会下落 \(a_i\),而每次砸的操作相当于提升了 \(p\) 的高度。

开始时,对每一个竹子计算出其需要多少次会下落到负高度,用堆维护,每次取出最快的可能下落到负高度的 k 个竹子,进行 “拔高” 操作。然后判断最后的高度是否大于等于\(h_i\)

其实二分的本质是为了确定“尽可能的靠后砸竹子”的标准。反向思考是为了便于贪心处理策略。 ## code

CF505E Mr. Kitayuta vs. Bamboos

int n, m, k, p;
int H[_], A[_];
#define mp make_pair
#define fi first
#define se second
int height[_];
bool check(int MaxH){
	fill(height + 1, height + 1 + n, MaxH);
	priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > Q;
	while(!Q.empty()) Q.pop();
	for(int i = 1; i <= n; i++) if(MaxH - m * A[i] < H[i]) Q.push(mp( MaxH / A[i], i ));

	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= k; j++){
			if(Q.empty()) return true;
			pair<int, int> now = Q.top(); Q.pop(); 
			if(now.fi < i) return false;
			height[now.se] += p;
			now.fi = height[now.se] / A[now.se];
			if(height[now.se] - m * A[now.se] < H[now.se]) Q.push(now);
		}
	}
	return Q.empty();
}
signed main(){
	n = read(), m = read(), k = read(), p = read(); // 竹子数 天数 修改次数 最大降低高度 
	for(int i = 1; i <= n; i++) H[i] = read(), A[i] = read();

	int L = 0, ans = 0, R = 1LL << 60; for(int i = 1; i <= n; i++) L = min(L, A[i]);
	while(L < R){
		int mid = (L + R) >> 1;
		if(check(mid)) ans = mid, R = mid;
		else L = mid + 1;
	}
	printf("%lld\n", ans);
	return 0;
}

CF521D Shop

  • \(k\) 个正整数 \(a_{1\dots k}\)
  • \(n\) 个操作,每个操作给定正整数 \(b\),有三种可能:将 \(a_i\) 赋值为 \(b\),将 \(a_i\) 加上 \(b\),将 \(a_i\) 乘以 \(b\)
  • 你可以从 \(n\) 个操作中选择最多 \(m\) 个操作,并按照一定顺序执行。
  • 你的目标是最大化 \(\prod_{i=1}^k a_i\) 的值。
  • \(k,n \le 10^5\)

化归思想,考虑如果只有乘法,那一定是把操作数字从大到小排序,然后以此操作。

考虑操作顺序,最优的操作一定是先赋值,再加法,最后乘法。其中赋值只可能选相应位置最大的赋值,加法也是从大到小考虑。

显然赋值可以直接转化成加法,而加法如果从大到小考虑也可以直接转化成乘法(乘一个实数)。

这样就把所有操作转化成了乘法。 贪心考虑即可。

最后输出有顺序,应按照上面的策略(先赋值,再加法,最后乘法)以此输出(操作顺序)。

code

CF521D Shop

#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int _ = 1e5 + 100;
#define LL long long
int read() { int x; scanf("%d", &x); return x; }
int n, m, k;
int v[_];
pair<int, int> Give[_];
vector<pair<int, int > > add[_];
vector<pair<double, int> > mul[_];
vector<pair<double, int> > All;
int T[_];
int id[_];
#define double long double
bool ICMP  (const pair<int, int> & x, const pair<int, int> & y) { return (x > y); }
bool ICMP_D(const pair<double, int> & x, const pair<double, int> & y) { return (x > y); }
bool MAGIC(const int &x, const int &y) { return T[x] < T[y]; }
int main(){
	k = read(), n = read(), m = read();
	for(int i = 1; i <= k; i++) v[i] = read();

	for(int i = 1; i <= n; i++){
		int type = read(); T[i] = type;
		int a = read(), b = read();
		if(type == 1){
			Give[a] = max(Give[a], make_pair(b, i)); 
		} else if(type == 2){
			add[a].push_back(make_pair(b, i));
		} else {
			mul[a].push_back(make_pair((double)(b), i));
		}
	}
	for(int i = 1; i <= k; i++)
		if(Give[i].first)
			add[i].push_back(make_pair(Give[i].first - v[i], Give[i].second));
	for(int i = 1; i <= k; i++) sort(add[i].begin(), add[i].end(), ICMP);
	for(int i = 1; i <= k; i++){
		LL now = v[i];
		for(int j = 0; j < add[i].size(); j++){
			mul[i].push_back( 
				make_pair( 
					(double)(now +0ll+ add[i][j].first) / (double)(now),
					add[i][j].second
				) 
			); now += add[i][j].first;
		}
	}
	for(int i = 1; i <= k; i++) for(int j = 0; j < mul[i].size(); j++) All.push_back(mul[i][j]);
	sort(All.begin(), All.end(), ICMP_D);
	int tot = 0;
	for(int i = 0; i < All.size(); i++) if(All[i].first > 1) { tot++; }
	tot = min(tot, m);
	for(int i = 1; i <= tot; i++) id[i] = All[i - 1].second;
	sort(id + 1, id + 1 + tot, MAGIC);	printf("%d\n", tot);
	for(int i = 1; i <= tot; i++) printf("%d%c", id[i], " \n"[i == n]);
	return 0;
}

CF526F Pudding Monsters

  • 给定一个 \(n \times n\) 的棋盘,其中有 \(n\) 个棋子,每行每列恰好有一个棋子。
  • 求有多少个 \(k \times k\) 的子棋盘中恰好有 \(k\) 个棋子。
  • \(n \le 3 \times 10^5\)

每行每列恰好有一个棋子的棋盘,可以抽象成一个排列。 而操作也是对于一个排列的一段进行操作的。

题意可以转化为: - 给出一个排列 - 求连续段数量,即连续的一段,且段中的元素排好序之后必须是公差为\(1\)的等差数列.

连续段计数

考虑如何刻画“连续的一段,且段中的元素排好序之后必须是公差为\(1\)的等差数列”这个条件,可以形式化的定义:

\[\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)\]

\[f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0\]

这个条件成立的基础在于,所求数列不能有重复元素,而且也保证了函数\(f_x(L) \ge 0\), 查询时只需要维护最小值以及最小值的数量即可。

可以考虑枚举一个端点,比如右端点 \(R\),然后查找有多少符合条件的左端点 \(L\) ,用线段树维护\(f_R(x)\)在每个点处的函数值。

考虑当\(f_x(L)\) 移动到 \(f_{x + 1}(L)\) 时, 值的变化。变化的值有 \(R\) , 可能变化的有\(MaxVal, MinVal\)。用单调栈实时维护更新后会波及哪些元素的最小值。事实上,单调栈处理的过程就是在动态维护一个后缀最小。

这里有几个与其有相似之处的题目,但是可能做法并不一样,遇到不要想成一样的题目: - 算术天才⑨与等差数列 (不保证序列中一定元素不重复) - 考虑判断一个序列排好序后是否为等差数列 - 准确做法 - \(\max−\min=(r−l)k\) - 相邻两数差的绝对值的 \(\operatorname{gcd}\)\(k\) - 区间 \([l,r]\) 内的数不重复 - 概率性做法 - hash思想,维护 \(n\) 次方和 - 树上排列(ZROI) (同样不保证元素一定不重复) - 给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(A_i\) ,你需要支持以下两种操作: - 1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点(包括点 \(x\) 和点 \(y\) )的点权是否构成一个从 \(1\) 开始的排列(即若这条链长度为 \(len\) ,那么问点权集合为 \({1,2,⋯,len}\) )。 - 2、将 \(A_x\) 修改为 \(y\) 。 - 由于在树上难以判断某区间内的数字不重复,Hash维护n次方和。 - 给出一个没有重复元素的序列,询问某区间中的元素是否能加入小于\(k\)个元素使其拍好序后构成一个等差数列。 - 条件变成了 \[f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k\] - count(ZROI)已知一个集合\(S\)中的最大元素为 \(N\), 且这个集合中的元素可以构成一个等差数列,给出一些形如\(x \in S\)\(x \notin S\)的限制。求最终的集合有多少种情况。 - 考虑刻画一个等差数列需要什么参数:公差,和每个元素$$ 公差的值。枚举这两个参数,依次计数即可。

(引用正睿的两道题目,不知道是不是有版权问题,如果有,会立即删除(顺便给正睿OI打个广告))。

code

CF526F Pudding Monsters

int n;
int A[_];
#define fir first
#define sec second
namespace SegmentTree{
    const int _ = 3e6 + 100;
    struct Node{
        int MIN;
        int sMIN;
        int tar;
        Node operator + (const Node & rhs) const {
            Node res;
            res.MIN  = min(MIN, rhs.MIN);
            res.sMIN = MIN == rhs.MIN ? ( sMIN + rhs.sMIN) : (MIN < rhs.MIN ? sMIN : rhs.sMIN) ;
            return res;
        }
    }v[_];
    int tot = 0;
    int ch[_][2];
    #define ls(o) (ch[o][0])
    #define rs(o) (ch[o][1])
    #define make (tot++, ch[tot][0] = ch[tot][1] = v[tot].MIN = v[tot].sMIN = 0, tot)
    int Groot() { return make; }
    void maintain(int o) {
        v[o].MIN  = min(v[ls(o)].MIN, v[rs(o)].MIN);
        v[o].sMIN = v[ls(o)].MIN == v[rs(o)].MIN ? v[ls(o)].sMIN + v[rs(o)].sMIN : ( v[ls(o)].MIN < v[rs(o)].MIN ? v[ls(o)].sMIN : v[rs(o)].sMIN );
    }
    void tar(int o, int x) { v[o].MIN += x; v[o].tar += x; }
    void pushdown(int o){
        if(v[o].tar){
            tar(ls(o), v[o].tar); tar(rs(o), v[o].tar);
            v[o].tar = 0;
        }
    }
    void build(int o, int L, int R){
        if(L == R) { v[o].MIN = 0; v[o].sMIN = 1; return; }
        int mid = (L + R) >> 1;
        ls(o) = make; rs(o) = make;
        build(ls(o), L, mid); build(rs(o), mid + 1, R);
        maintain(o);
    }
    void update(int o, int nowl, int nowr, int L, int R, int x){
        if(L > R) return ;
        if(L <= nowl && nowr <= R) return tar(o, x);
        int mid = (nowl + nowr) >> 1;  pushdown(o);
        if(L <= mid) update(ls(o), nowl, mid, L, R, x);
        if(R  > mid) update(rs(o), mid + 1, nowr, L, R, x);
        maintain(o);
    }
    Node query(int o, int nowl, int nowr, int L, int R) {
        if(L <= nowl && nowr <= R) return v[o];
        int mid = (nowl + nowr) >> 1; pushdown(o);
        Node Ans; Ans.MIN = INT_MAX;
        if(L <= mid) Ans = Ans + query(ls(o), nowl, mid, L, R);
        if(R  > mid) Ans = Ans + query(rs(o), mid + 1, nowr, L, R);
        return Ans;
    }
    int query(int o, int L, int R){
        Node res = query(o, 1, n, L, R);
        return res.MIN == 0 ? res.sMIN : 0;
    }
}  using SegmentTree::Groot; using SegmentTree::build; using SegmentTree::query; using SegmentTree::update;
namespace Mon_Stack{
    int t0t = 0, t1t = 0;
    pair<int, int> S0[_], S1[_];
    int work(int *A, int n){
        int Ans = 0;
        int root = Groot();
        build(root, 1, n);
        S0[0].fir = S1[0].fir = 0;
        for(int i = 1; i <= n; i++) {
            update(root, 1, n, 1, i - 1, -1);
            while(t0t != 0 && S0[t0t].sec >= A[i]) { update(root, 1, n, S0[t0t - 1].fir + 1, S0[t0t].fir,  S0[t0t].sec); t0t--; }
            while(t1t != 0 && S1[t1t].sec <= A[i]) { update(root, 1, n, S1[t1t - 1].fir + 1, S1[t1t].fir, -S1[t1t].sec); t1t--; }
            update(root, 1, n, S0[t0t].fir + 1, i, -A[i]);
            update(root, 1, n, S1[t1t].fir + 1, i, A[i]);
            int t = query(root, 1, i);
            Ans += t;
            S0[++t0t] = make_pair(i, A[i]); S1[++t1t] = make_pair(i, A[i]);
        }
        return Ans;
    }
} using Mon_Stack::work;
signed main(){
    n = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(); A[x] = y; }
    printf("%lld\n", work(A, n));
    return 0;
}

count(ZROI)

#include <climits>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long 
const int MOD = 1e9 + 7;
const int _M = 2e5 + 100;
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
int MAX, m;
int have[_M], tht = 0;
int none[_M], tnt = 0;
int d[_M], tdt = 0; 
int c[_M];//tct = tdt
bool CanBe[_M];
int ToL[_M];
int ToR[_M];
void divide(int s, int x) {
    for(int i = 1; i * i <= x; i++){
        if(x % i == 0) d[++tdt] = i, c[tdt] = s % i;
        if(i * i != x) d[++tdt] = x / i, c[tdt] = s % d[tdt];
    }
    for(int i = 1; i <= tdt; i++) CanBe[i] = true;
}
signed main(){
    int t;
    MAX = read(), m = read();
    for(int i = 1; i <= m; i++){
        int type = read();
        if(type == 1) have[++tht] = read();
        else          none[++tnt] = read();
    }
    sort(have + 1, have + 1 + tht); sort(none + 1, none + 1 + tnt);
    int maxd = INT_MAX, Sta;
    for(int i = 2; i <= tht; i++) {
        if(maxd > have[i] - have[i - 1]){
            maxd = have[i] - have[i - 1];
            Sta = have[i - 1];
        }
    }
    divide(Sta, maxd);

    /* 公差 及 特征 检查   */
    for(int i = 1; i <= tht; i++){
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(have[i] % d[j] != c[j]) CanBe[j] = false;
        }
    }
    for(int i = 2; i <= tht; i++){
        int D = have[i] - have[i - 1];
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(D % d[j] != 0) CanBe[j] = false;
        }
    }
    t = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        d[++t] = d[i];
        c[  t] = c[i];
        CanBe[t] = true;
    } tdt = t;
    /* 公差 及 特征 检查   完成*/
    for(int i = 1; i <= tdt; i++) { 
        if(CanBe[i]) {
            ToL[i] = (c[i] == 0 ? d[i] : c[i]) - 1;
            int t = MAX % d[i];
            if(t == c[i]) ToR[i] = MAX + 1;
            if(t  > c[i]) ToR[i] = MAX - (t - c[i]) + 1;
            if(t  < c[i]) ToR[i] = MAX - d[i] + (c[i] - t) + 1;
        }
    }
    t = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        d[++t] = d[i];
        c[  t] = c[i];
        CanBe[t] = true;
    } tdt = t;
    int MINS = have[1], MAXE = have[tht];
    for(int i = 1; i <= tnt; i++){
        int now = none[i];
        for(int j = 1; j <= tdt; j++){
            if(!CanBe[j]) continue;
            if(now % d[j] == c[j]){
                if(now < MINS)
                    ToL[j] = max(ToL[j], now);
                else if(now > MAXE)
                    ToR[j] = min(ToR[j], now);
                else CanBe[j] = false;
            }
        }
    }
    for(int i = 1; i <= tdt; i++) if(ToL[i] > MINS || ToR[i] < MAXE) CanBe[i] = false; else ToL[i]++, ToR[i] --;
    /* 非法数字存在性检查 */
    int ans = 0;
    for(int i = 1; i <= tdt; i++){
        if(!CanBe[i]) continue;
        int k = (  (MINS - ToL[i]) / d[i] + 1) * ( (ToR[i] - MAXE) / d[i] + 1) % MOD; // TODO;
        ans = (ans + k) % MOD;
    }
    printf("%lld", ans);
    return 0;
}

A.20联赛集训day3 树上排列(维护15次方和hash)

#include <climits> 
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
using namespace std;
const int _ = 6e5 + 100;
const int base = 15;
const int MOD = 1020031005;
int SS[_];
int pow(int a, int b = base){ int ans = 1; while(b){ if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; }

int head[_];
int NodeVal[_];
struct edges{
	int node;
	int nxt;
}edge[_];
int tot = 0;
void add(int u, int v){
	tot++;
	edge[tot].node = v;
	edge[tot].nxt  = head[u];
	head[u]        = tot;
}

int n, q;
int dep[_], fa[_], dfn[_], rnk[_], top[_], son[_], si[_], dfc = 0;
void dfs0(int now, int f, int dp){
	int &S = si[now] = 1; int &Mid = son[now] = 0; fa[now] = f; dep[now] = dp;
	for(int i = head[now]; i ; i = edge[i].nxt){
		int ex = edge[i].node; if(ex == f) continue;
		dfs0(ex, now, dp + 1); S += si[ex];
		if(si[ex] > si[Mid]) Mid = ex;
	} if(!Mid) Mid = 0;
}
void dfs1(int now, int f, int tp){
	dfn[now] = ++dfc; rnk[dfc] = now;
	top[now] = tp;
	if(son[now]) dfs1(son[now], now, tp);
	for(int i = head[now]; i ; i = edge[i].nxt){
		int ex = edge[i].node; if(ex == f || ex == son[now]) continue;
		dfs1(ex, now, ex);
	}
}
void clear(){
	memset(head, 0, sizeof(head));
	dfn[0] = rnk[0] = si[0] = top[0] = fa[0] = son[0] = 0;
	tot = 0;
	dfc = 0; 
}
namespace SegmentTree{
	const int _ = 3e6 + 100;
	int tot = 0;
	int ch[_][2];
	int v[_];
	#define make (tot++, ch[tot][0] = ch[tot][1] = v[tot] = 0, tot);
	#define ls(x) (ch[x][0])
	#define rs(x) (ch[x][1])
	#define maintain(o) (v[o] = (v[ls(o)] +0ll+ v[rs(o)]) % MOD )
	void init_s() { tot = 0; }
	int  Groot(){ return make; }
	void build(int o, int L, int R){
		if(L == R) return (void)(v[o] = pow(NodeVal[rnk[L]]));
		int mid = (L + R) >> 1;
		ls(o) = make; rs(o) = make;
		build(ls(o), L, mid); build(rs(o), mid + 1, R);
		maintain(o);
	}
	void update(int o, int nowl, int nowr, int p, int x){
		if(nowl == nowr) return (void)(v[o] = pow(x));
		int mid = (nowl + nowr) >> 1;
		if(p <= mid) update(ls(o), nowl, mid, p, x);
		if(p  > mid) update(rs(o), mid + 1, nowr, p, x);
		maintain(o);
	}
	int query(int o, int nowl, int nowr, int L, int R){
		if(L > R) return 0;
		if(L <= nowl && nowr <= R) return v[o];
		int mid = (nowl + nowr) >> 1;
		int ans = 0;
		if(L <= mid) ans = (ans +0ll+ query(ls(o), nowl, mid, L, R)) % MOD;
		if(R  > mid) ans = (ans +0ll+ query(rs(o), mid + 1, nowr, L, R)) % MOD;
		return ans;
	}
} using SegmentTree::Groot; using SegmentTree::init_s; using SegmentTree::build; using SegmentTree::update; using SegmentTree::query;
int root = 0;
int LCA;
int QueryOnPath(int x, int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] > dep[top[y]]) swap(x, y);
		ans = (ans +0ll+ query(root, 1, n, dfn[top[y]], dfn[y])) % MOD;
		y = fa[top[y]];
	}
	if(dep[x] < dep[y]) swap(x, y); LCA = y;
	ans = (ans +0ll+ query(root, 1, n, dfn[y], dfn[x])) % MOD; 
	return ans;
}
void doit(){
	clear();
	n = read(), q = read();
	for(int i = 1; i <= n; i++) NodeVal[i] = read();
	for(int i = 1; i <  n; i++){ int u = read(), v = read(); add(u, v); add(v, u); }
	dfs0(1, 1, 1);
	dfs1(1, 1, 1);
	init_s(); root = Groot();
	build(root, 1, n);
	while(q--){
		int opt = read(), x = read(), y = read();
		if(opt == 1){
			int r = QueryOnPath(x, y);
			int Len = dep[x] + dep[y] - (dep[LCA] << 1) + 1;
			puts(SS[Len] == r ? "Yes" : "No");
		} else{
			update(root, 1, n, dfn[x], y);
		}
	}
}
int main(){
	for(int i = 1; i <= 3e5; i++) SS[i] = ( SS[i - 1] +0ll+ pow(i) ) % MOD;
	int T = read();
	while(T--) doit();
	return 0;
}

CF521E Cycling City

  • 给定一张 \(n\) 个点 \(m\) 条边的无向简单图。
  • 问图中能否找到两个点,满足这两个点之间有至少三条完全不相交的简单路径。
  • \(n,m \le 2 \times 10^5\),图不保证连通

考虑生成树,对原图做一个生成树,考虑每个在生成树外的边,覆盖在树上,树上边被覆盖两次的,即为一种方案

由于树的拓扑结构比图要简单很多,直接思考图的生成树解决图内问题是一个常见思路。

CF547D Mike and Fish

待填