首页 > 其他分享 >CF1707 题解

CF1707 题解

时间：2023-10-31 20:35:43浏览次数：37  
标签：log int 题解 ans Theta CF1707 now Segment

CF1707 题解

A

考场上 1h 才出思路...弱智了。

我们将参加大于当前智商的行为叫做 “摆烂”。我们考虑如果现在摆一次，将来某一次不摆，那么现在不摆，将来那次开摆，中间过程的智商会加1。更优。所以一定一摆就摆到底。而且一定会摆到最后一个。

所以我们二分从什么时候开摆，看是否能摆到最后，中间 \(\Theta(n)\) 模拟过程。

其实可以直接从后往前递推到 \(q\) ，线性解决。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N],ans = 0,n,q,cs[N],as[N];
inline int run(int x)
{
    fill(cs + 1,cs + n + 1,0); 
    int res = 0;
    for(int i = 1;i < x;i++) if(a[i] <= q) ++res,cs[i] = 1;
    int tmp = q;
    for(int i = x;i <= n && tmp;i++)
    {
        ++res;
        cs[i] = 1;
        tmp -= (a[i] > tmp);
        if(!tmp)
        {
            if(res > ans)
            {
                for(int j = 1;j <= n;j++) as[j] = cs[j];
                ans = res;
            }
            return i;
        }
    }
    if(res > ans)
    {
        for(int j = 1;j <= n;j++) as[j] = cs[j];
        ans = res;
    }
    return n;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ans = 0;
        cin>>n>>q; fill(as + 1,as + n + 1,0);
        for(int i = 1;i <= n;i++) cin>>a[i];
        int l = 1,r = n;
        if(n == 1) {if(q > 0) as[1] = 1,ans = 1;}
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(run(mid) < n) l = mid + 1;
            else r = mid;
        } 
        for(int i = 1;i <= n;i++) cout<<as[i];
        cout<< '\n';
    }
    return 0;
 }

B

考虑暴力模拟过程，是 \(\Theta(n^2 \log n)\) 的。

差分只会让值变的越来越小，手模发现会出现一些 \(0\) ，然而 \(0\) 的差分不需要算，只需要记录 \(0\) 的个数，每次减少 \(1\) 即可，有前导 \(0\) 的时候要保留第一个差分值。

将 \(0\) 除掉过后暴力做，发现可以 AC。

考虑记 \(S\) 为所有数的和，第一次 \(S = a_n - a_1\) 。后面进行一次操作之前 \(S \geq n - 1 + a_n\) ，操作之后 \(S = a_n - a_1\) 。所以至少减去了 \(n - 1\) 。所以操作是 \(\Theta(\frac Sn)\) 次，每次 \(\Theta(n \log n)\) ，复杂度就是 \(\Theta(S\log n)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N],n,b[N];
inline int solve()
{
    int tmp,l = 1,r = n,rem0 = 0;
    for(tmp = 1;tmp <= n - 1;tmp++)
    {
        a[l - 1] = 0;
        for(int i = l;i <= r;i++) b[i] = a[i] - a[i - 1];
        if(!rem0) 
        {
            sort(b + l + 1,b + r + 1);
            for(int i = l + 1;i <= r;i++) a[i] = b[i];
            l++;
            while(a[l] == 0 && l <= r) ++l,++rem0;
        }
        else
        {
            sort(b + l,b + r + 1);
            for(int i = l;i <= r;i++) a[i] = b[i];
            while(a[l] == 0 && l <= r) ++l,++rem0;
            rem0--;
        }
        if(l > r) return 0;
    }
    return a[l];
}
int main()
{
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 1;i <= n;i++) cin>>a[i];
        cout<<solve()<< '\n';
    }
    return 0;
}

C

考虑一个点可以的条件是以它为根的搜索树就是最小生成树，由于搜索树只有树边和返祖边，考虑不在最小生成树上的边，只有两个端点的子树出发才能将这条边作为返祖边，这些点才合法。

image

image

如图，红色即为可以取的点。

所以直接将这些集合求交即可，具体方法是树上差分后子树加，最后看点值是否等于 \(m - n + 1\) 即可。复杂度 \(\Theta(m \log m + n)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge{
    int u,v,w,us;
}e[N * 4];
int head[N],n,m,dfn[N],siz[N],a[N],fa[19][N],dep[N];
vector <Edge> G[N];
struct UFS{
    int fa[N];
    inline void init() {for(int i = 1;i <= n;i++) fa[i] = i;}
    inline int find(int x) {return (x == fa[x]) ? x : fa[x] = find(fa[x]);}
    inline void unionn(int x,int y) {x = find(x); y = find(y); fa[y] = x;}
}t;
inline void Kruskal()
{
    sort(e + 1,e + m + 1,[&](Edge x,Edge y) {return x.w < y.w;});
    t.init();
    for(int i = 1;i <= m;i++)
    {
        if(t.find(e[i].u) == t.find(e[i].v)) continue;
        G[e[i].u].push_back(e[i]); G[e[i].v].push_back(e[i]);
        e[i].us = 1;
        t.unionn(e[i].u,e[i].v);
    }    
}
inline void dfs(int x,int last)
{
    siz[x] = 1;
    dep[x] = dep[last] + 1;
    fa[0][x] = last;
    for(auto in : G[x])
    {
        int to = in.u ^ x ^ in.v;
        if(to == last) continue;
        dfs(to,x);
        siz[x] += siz[to];
    }
}
inline int jump(int x,int d)
{
    for(int i = 18;i >= 0;i--) if(dep[fa[i][x]] >= d) x = fa[i][x];
    return x;
}
inline void dfs2(int x,int last)
{
    for(auto in : G[x])
    {
        int to = in.u ^ x ^ in.v;
        if(to == last) continue;
        a[to] += a[x];
        dfs2(to,x);
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1,x,y;i <= m;i++)
    {
        cin>>e[i].u>>e[i].v;
        e[i].w = i;
    }
    Kruskal();
    dfs(1,0);
    for(int i = 1;i <= 18;i++)
        for(int j = 1;j <= n;j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    for(int i = 1;i <= m;i++)
    {
        if(e[i].us) continue;
        int x = e[i].u,y = e[i].v;
        if(dep[x] < dep[y]) swap(x,y);
        if(jump(x,dep[y]) == y)
        {
            a[x]++; a[1]++;
            a[jump(x,dep[y] + 1)]--;
        }
        else
        {
            a[x]++; 
            a[y]++;
        }
    }
    dfs2(1,0); 
    for(int i = 1;i <= n;i++) if(a[i] == m - n + 1) putchar('1'); else putchar('0');
    return 0;
}

D

考虑不好处理真子集，我们将其变成子集。

这可以看作一个过程：从整棵树开始，每一个单位时间你可以删掉某些点，求每个 \(k \in [1,n - 1]\) ， \(k\) 个单位时间后将树删为 \(1\) 的方案数。

考虑恰好不好说，二项式反演，假设 \(f_{u,k}\) 为 \(u\) 的子树，\(k\) 时间后删完了的方案数。那么对于 \(k\) ，有：

\[f_{1,k} = \sum_{i = 1}^{k} \binom{k}{i}ans_i \]

表示选择 \(i\) 步做出实质性的改变，其余的都不变。

反演得到：

\[ans_k = \sum_{i = 1}^k (-1)^{k - i}\binom{k}{i} f_{1,i} \]

考虑 dp 求出 \(f_{i,k}\) ，一个子树只可能有两种顺序：

  • 先删完所有儿子，再删自己

  • 先删到只有一个儿子，再删自己，再删儿子。

对于第一种情况，有：

\[f_{i,k} = \prod_{v} \sum_{j = 1}^k f_{v,j} \]

因为儿子合法，那么相应地自己就合法，所以是乘起来。

考虑前缀和优化，设 \(s_{i,k} = \sum_{j = 1}^k f_{i,j}\)

对于第二种情况，有：

\[f_{i,k} = f_{i,k} + \sum_{v \in son(i)}f_{v,k}\sum_{p = 0}^{k - 1}\prod_{w \neq v}s_{w,p} \]

尝试优化第二种情况，我们可以在外层枚举 \(p\) ，算出对于所有儿子 ，\(s_{w,p}\) 的前后缀积。 这样对于每一个儿子，复杂度就是 \(\Theta(n)\) 级别的，总体做到了 \(\Theta(n^2)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
typedef long long ll;
int n,p;
vector <int> G[N];
ll f[N][N],g[N][N],pre[N][N],suf[N][N],s[N][N],frac[N],inv[N];
inline ll ksm(ll base,int pts)
{
	ll ret = 1;
	for(;pts > 0;pts >>= 1,base = base * base % p)
		if(pts & 1)
			ret = ret * base % p;
	return ret;
}
inline void dfs(int x,int last)
{
	vector <int> son;
	for(auto to : G[x]) if(to != last) dfs(to,x),son.push_back(to);
	if(!son.size())
	{
		for(int i = 1;i <= n - 1;i++) f[x][i] = 1,s[x][i] = i;
		return;
	}
	int cnt = son.size();
	for(int j = 1;j <= n - 1;j++)
		for(int i = 0;i < cnt;i++)
			pre[i][j] = suf[i][j] = s[son[i]][j];
	for(int j = 1;j <= n - 1;j++)
		for(int i = 1;i < cnt;i++)
			pre[i][j] = pre[i - 1][j] * pre[i][j] % p;
	for(int j = 1;j <= n - 1;j++)
		for(int i = cnt - 2;i >= 0;i--)
			suf[i][j] = suf[i + 1][j] * suf[i][j] % p;
	for(int j = 1;j <= n - 1;j++) f[x][j] = pre[cnt - 1][j];
	if(x == 1) return;
	for(int j = 1;j <= n - 1;j++)
	{
		for(int i = 0;i < cnt;i++)
		{
			f[x][j] = (f[x][j] + f[son[i]][j] * g[son[i]][j - 1] % p) % p;
			g[son[i]][j] = (g[son[i]][j - 1] + ((i == 0) ? 1 : pre[i - 1][j]) * ((i == cnt - 1) ? 1 : suf[i + 1][j]) % p) % p;
		}
		s[x][j] = (((j == 0) ? 0 : s[x][j - 1]) + f[x][j]) % p;
	}
}
inline ll C(int y,int x)
{
	if(y < 0 || x < 0 || y < x) return 0;
	return frac[y] * inv[x] % p * inv[y - x] % p;
}
int main()
{
	memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(pre,0,sizeof(pre)); memset(suf,0,sizeof(suf)); memset(s,0,sizeof(s));
	cin>>n>>p;
	for(int i = 1,x,y;i <= n - 1;i++)
	{
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	frac[0] = inv[0] = 1;
	for(int i = 1;i < N;i++) frac[i] = frac[i - 1] * i % p;
	inv[N - 1] = ksm(frac[N - 1],p - 2);
	for(int i = N - 2;i >= 0;i--) inv[i] = inv[i + 1] * (i + 1) % p;
	dfs(1,0);
	for(int i = 1;i <= n - 1;i++)
	{
		ll now = 0;
		for(int j = 1;j <= i;j++)
			now = (now + (((i - j) & 1) ? p - 1 : 1) * C(i,j) % p * f[1][j] % p) % p;
		cout<<now<< ' ';
	}
	return 0;
}

E

性质题，做完对倍增有更深的了解。

考虑每一次操作是在上一次的基础上再对区间拓宽，考虑倍增。假设 \(f_{t,i,j}\) 为 \([i,j]\) 做 \(2^t\) 次操作的区间是什么，每次由于处理好了 \(t - 1\) 的信息，直接将 \(2^{t - 1}\) 的结果区间拿去做即可。

但是这样是 \(\Theta(n^2\log n)\) 的，考虑优化，如果这个区间信息像 \(max\) 一样可以合并，我们就能够对于区间长度同样地倍增。但是貌似不能合并？

事实上发现可以，即：

\[f([l,r]) = \cup_{i = l}^{r - 1}f([i,i + 1]) \]

证明可以归纳，即新加入的一个值会刷新原来区间的左右端点，一个一个加入相当于用区间内的所有值将左右端点更新了一遍，和原来效果相同。

所以我们设 \(f_{i,j,k}\) 为 \([k,k + 2^j - 1]\) 做 \(2^i\) 次可以得到的区间，\(\Theta(n\log^2n)\) 预处理后 \(\Theta(\log n)\) 倍增回答询问即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Segment{
	int l,r;
}f[20][20][N];
Segment operator +(Segment a,Segment b) {return Segment{min(a.l,b.l),max(a.r,b.r)};}
int a[N],n,q,lg[N];
inline Segment getval(int k,int l,int r)
{
	int now = lg[r - l + 1];
	return f[k][now][l] + f[k][now][r - (1 << now) + 1];
}
int main()
{
	cin>>n>>q;
	lg[0] = -1;
	for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1;i <= n;i++) cin>>a[i];
	for(int i = 1;i <= n;i++) f[0][0][i].l = f[0][0][i].r = a[i];
	for(int i = 1;i <= 18;i++)
		for(int j = 1;j + (1 << i) - 1 <= n;j++)
			f[0][i][j] = f[0][i - 1][j] + f[0][i - 1][j + (1 << (i - 1))];
	for(int i = 1;i <= 18;i++)
		for(int j = 1;j <= 18;j++)	
			for(int k = 1;k + (1 << j) - 1 <= n;k++)
				f[i][j][k] = getval(i - 1,f[i - 1][j][k].l,f[i - 1][j][k].r);
	for(int i = 1,l,r;i <= q;i++)
	{
		cin>>l>>r;
		if(l == 1 && r == n) {puts("0"); continue;}
		Segment now = {l,r}; int tms = 0;
		for(int i = 18;i >= 0;i--)
		{
			Segment to = getval(i,now.l,now.r);
			if(!(to.l == 1 && to.r == n)) 
				now = to,tms += (1 << i);
		}
		now = getval(0,now.l,now.r);
		if(now.l != 1 || now.r != n) {puts("-1"); continue;}
		cout<<tms + 1<< '\n';
	}
	return 0;
}

F

咕。

标签：log,int,题解,ans,Theta,CF1707,now,Segment
From： https://www.cnblogs.com/TheLastCandy/p/17801253.html

相关文章

  • 题解：洛谷P3745 期末考试（整数三分）
    题解：洛谷P3745期末考试（整数三分）题目传送门题目大意：给出\(n\)个同学期望出成绩的时间限制\(a_i\)和\(m\)个学科公布成绩的初始时间\(t_i\)，1个同学每多等一天就产生A的不愉快度。问通过一番操作后最小的不愉快度之和是多少？操作有两种：1.让学科X的发布时间晚1天，学科......
  • P5404 [CTS2019] 重复 题解
    题目链接观察题目，我们发现直接计算是困难的，先构造单个合法的\(T\)分析其性质。为了构造出\(T\)，先考虑构造时\(T\)时什么时候会出现不合法的情况，此时\(T\)会有一段和\(S\)相同的前缀，且这段前缀后面跟着的字符比\(S\)所跟的小。为了避免这种情况出现，我们需要在每次添......
  • CSPRO 历届题目与题解
    官方题目链接：http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。假设一节车厢......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上，即使在\(N=5\)的情况下，也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题，就感觉是搜索，这很显然。但是我们会发现，最最最native的搜索，是\(4^{5\times5}=2^{50}\)的。感觉不大可过，但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目（然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子，掷若干次骰子，如果这一次掷骰子的点数小于等于上一次的点数，则结束。定义这若干次掷骰子的总的结果为，每次......
  • AT_abc326_f Robot Rotation 题解
    AT_abc326_fRobotRotation题解经典问题，以前遇到过一个类似的问题：[ABC082D]FTRobot。建议对比着看一看这两道题，是两种不同的思路。（那一道题不用输出方案，因此可以用bitset优化；而此题需要输出方案，因此需要双向搜索。思路注意到每次只能「左转」和「左转」。所以，偶数次走......
  • AT_abc325_f Sensor Optimization Dilemma 题解
    AT_abc325_fSensorOptimizationDilemma题解Date20231025：修复手滑公式\(\min\)、\(\max\)写反了。动态规划。类似背包问题。朴素算法记\((x,y)\)表示使用\(x\)个(1)传感器、\(y\)个(2)号传感器。设\(f(t,i,j)\)表示覆盖前\(t\)个区间，使用\((i,j)\)传感......
  • AT_abc325_g offence 题解
    AT_abc325_goffence题解一道不难但是需要想一想的区间DP。有一个比较复杂的例子：ooofofxxx，简单的分析可知，一个of后面删除多少，与其前、后都有关，于是考虑区间DP。想到这里，其实问题已经解决一半了。状态设计设\(f(l,r)\)为闭区间\([l,r]\)经过操作之后的最小长度。注......
  • [CSP-S2020] 儒略日 题解
    [CSP-S2020]儒略日今儿终于做掉困扰多年的题目了，其实想好细节也不难。容易发现儒略历和格里高利历的润年判断方式不一样，并且中间有消失的十天，计算起来相当不方便。所以我们可以首先计算出\(-4713.1.1\)～\(1582.10.4\)会经过多少天，可以通过一天一天暴力跳的方法计算出需要\(......
  • P4309 [TJOI2013] 最长上升子序列题解
    P4309[TJOI2013]最长上升子序列题解正文单调队列?单调锤子队列！！本题的操作可以省略成：单点修改区间查询好极了，此时我们有两种选择：线段树和树状数组，（平衡树，真不会，下一位因为不需要其他操作，所以我们还是选择更小巧更可爱的树状数组吧。关于vectorvector的insert操作支......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99