526互联

CF907 div2

发布时间 2023-11-14 13:59:30作者: 沙野博士

CF907 div2

A.Sorting with Twos

A.Sorting with Twos
题意
给一个长度为n的序列，可以进行的操作是，选取一个i，令前\(2^i\)个元素减1,问若干次操作之后能否使得序列成为不降序列。
数据范围
多组数据\(1<=T<=10^4\),\(1 <= n <= 20\),\(0 <= a_i <= 1000\)
输入样例

8
5
1 2 3 4 5
5
6 5 3 4 4
9
6 5 5 7 5 6 6 8 7
4
4 3 2 1
6
2 2 4 5 3 2
8
1 3 17 19 27 57 179 13
5
3 17 57 179 92
10
1 2 3 4 0 6 7 8 9 10

输出样例

YES
YES
YES
NO
NO
NO
YES
YES

题解
易知，这样的操作只会改变\(a_{2^i}\)与\(a_{2^i + 1}\)处的大小关系，对其它的地方没有影响，所以只需判断不符合\(a_i <= a_{i+1}\)的位置是不是只出现在这些可以修改的位置上，如果是则可行，反之则不行。

#include<iostream>
using namespace std;
const int N = 25;
int n;
int A[N] , Visit[N];
void Solve()
{
	cin >> n;
	for(int i = 1 ; i <= n ; ++i)
		cin >> A[i];
	for(int i = 1 ; i < n ; ++i)
		if(A[i] > A[i + 1])
			if(!Visit[i]) { cout << "NO" << '\n'; return ;}
	cout << "YES" << '\n';
}

int main()
{
	for(int i = 0 ; (1 << i) <= 20 ; ++i) Visit[1 << i] = 1;
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}

B.Deja Vu

B.Deja Vu
题意
给出一个长度为n的数据序列和一个长度为Q的操作序列，每次操作给出一个x（\(1<=x<=30\)）要求令所有\(a_i \% (2^x) == 0\)的数字加上\(a^{i-1}\).
问操作之后最终的数据序列是什么样子
数据范围
多组数据,\(1<=n,q<=10^5,1<=a_i<=10^9,1<=x_i<=30\).
样例输入

4
5 3
1 2 3 4 4
2 3 4
7 3
7 8 12 36 48 6 3
10 4 2
5 4
2 2 2 2 2
1 1 1 1
5 5
1 2 4 8 16
5 2 3 4 1

样例输出

1 2 3 6 6 
7 10 14 38 58 6 3 
3 3 3 3 3 
1 3 7 11 19

题解
如果之前操作过了x，那么之后的对于所有满足\(y>=x\)的y，都是无效操作。
也就是说最多只会操作30次，暴力处理即可。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n;
int Array[N];

int Solve()
{
	int Q , x , lst = 66;
	cin >> n >> Q;
	for(int i = 1 ; i <= n ; ++i)
		cin >> Array[i];
	while(Q--)
	{
		cin >> x;
		if(x >= lst) continue;
		for(int i = 1 ; i <= n ; ++i)
			if(Array[i] % (1ll << x) == 0)
				Array[i] += (1ll << (x - 1));
		lst = x;
	}
	for(int i = 1 ; i <= n ; ++i)
		cout << Array[i] << ' '; cout << '\n';
	return 0;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}

C.Smilo and Monsters

C.Smilo and Monsters
题意
这里有n个部落，第i个部落中有\(a_i\)只怪兽，现在要尽快消灭所有的怪兽。
有两种操作可以选择，每种操作每次消耗一个单位时间。
操作1,选择一个部落然后消灭其中一个怪物，然后蓄力值加1.
操作2,对一个部落清空蓄力，也就是说消灭该部落中等于蓄力值的怪物数。
数据范围
多组数据，\(1<=n<=2*10^5\) , \(1 <= a_i <= 10^9\)
样例输入

4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6

样例输出

4
4
11
5

题解
贪心的想，最后蓄力值不能留着，用光了才是最优。并且蓄力爆发操作要尽量的少，太过频繁也会浪费时间。
将部落按照含有的怪物数量从小到大排序，维护左右两个指针，左侧用操作1消耗，如果蓄力值等于右侧指针部落中怪物数量，那么就爆发一次。
最后等到左右两个指针汇聚到一起时，比较一下是先消耗一半然后蓄力爆发解决另一半好，还是只用操作1消耗好。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n;
int Array[N];

int Solve()
{
	int Q , x , lst = 66;
	cin >> n >> Q;
	for(int i = 1 ; i <= n ; ++i)
		cin >> Array[i];
	while(Q--)
	{
		cin >> x;
		if(x >= lst) continue;
		for(int i = 1 ; i <= n ; ++i)
			if(Array[i] % (1ll << x) == 0)
				Array[i] += (1ll << (x - 1));
		lst = x;
	}
	for(int i = 1 ; i <= n ; ++i)
		cout << Array[i] << ' '; cout << '\n';
	return 0;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}

D.Suspiciout logarithms

D.Suspiciout logarithms
题意

\[f(x) = max\{y | 2^y <= x , y\in Z \} \\ g(x) = max\{z | f(x)^z <= x , z\in Z\} \]

给出Q个询问，每次询问一个区间[l , r]的g(x)的和,对\(10^9+7\)取模。
数据范围
\(1 <= Q <= 1e5 , 4<=l_i <= r_i <= 10^{18}\)
样例输入

12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625

样例输出

6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692

题解
f(x),g(x)都是一大段一大段相同的样式。
先按照f的值分段，然后在每一段中在对g分段即可。
f最多可以分\(log_2(1e18)\)段，每一段中g的段数也是这个级别，但是常数比这个要小许多。

#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 1e9+7;

inline void Add(int &A , int B) { A += B; A = A > mod ? A - mod : A; }

int Calc(long long pos)
{
	int f = 2 , g , Answer = 0;
	long long l , r;
	__int128 tmp , nex;
	while((1ll << f) <= pos)
	{
		l = (1ll << f); r = min((1ll << (f + 1)) - 1 , pos);
		g = 0; tmp = 1;
		while(tmp * f <= l) g++ , tmp *= f;
		while(l <= r)
		{
			nex = tmp * f;
			if(nex - 1 > r) nex = r + 1;
			Add(Answer , (nex - l) * g % mod);
			l = nex; tmp = nex;
			g++;
		}
		f++;
	}
	return Answer;
}

void Solve()
{
	long long l , r;
	cin >> l >> r;
	cout << (Calc(r) - Calc(l - 1) + mod) % mod << '\n';
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}

E.Brukhovich and Exams

E.Brukhovich and Exams
题意
有n场考试，每场考试都有一个难度\(a_i\)，考完之后的Smilo的伤心值等于满足\(gcd(a_i,a_{i+1}) == 1\)的i的个数。
若最多可以将k个数字置0,那么伤心值最小是多少？
gcd(x,0) = gcd(0,x) = x
数据范围
多组数据，\(1<=k<=n<=10^5 , 0 <= a_i <= 10^9\)
样例输入

9
5 2
1 3 5 7 9
5 2
3 5 7 9 11
8 2
17 15 10 1 1 5 14 8
5 3
1 1 1 1 1
5 5
1 1 1 1 1
19 7
1 1 2 3 4 5 5 6 6 7 8 9 10 1 1 1 2 3 1
15 6
2 1 1 1 1 2 1 1 2 1 1 1 2 1 2
5 2
1 1 1 1 2
5 2
1 0 1 0 1

样例输出

1
0
2
2
0
5
5
2
1

题解
将一个数字置0,那么只会影响左右两个。那么就有可能让伤心值减少2,减少1,或者不减少。
那么可以进行3次扫描，第一次找能减少2的位置，第二次找能减少1的位置，第三次找用2次操作减少1的位置。
但是在第二次扫描的时候，可能会新增出来能减少2的位置。
这样的位置满足，非1 ， 1 ， 1 ， 非1,这样的形式，将4个数中第一个1删去之后，可以减少。这时再删去第二个1,则可以减少2。
再扩展一下，发现连续的1,删完之后会有一个“爆发”，就是突然减2.
再考虑一下边界情况，如果连续的1贴左右边界，则不会爆发。贴1个边界不爆发，贴2个边界倒赔一个。（贴两个边界也就是全为1）
那么可以将流程修改。
先找能减2的位置。
然后找连续的1,先弄不贴边的,不贴边的先弄短的,贴边的从不贴边的那一侧开始.
最后,再扫一遍,处理减1的位置.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5+10;
int n , k;
int Array[N];

/*
1. 先取2个，再取1个，再取半个。   取1个时可能会改变2个，新增。
2. 只有连续的1，才会新增成为2个。 且连续的1取完的时候有个爆发
3. 贴墙的一边不会爆发。且贴墙的段应从另一端开始。
*/

void Solve()
{
	int Wall;
	pair<int,int> NearWall[2];
	vector< pair<int,int> > Vec;
	cin >> n >> k;
	for(int i = 1 ; i <= n ; ++i)
		cin >> Array[i];
	for(int i = 1 ; i <= n - 2 ; ++i)
	{
		if(__gcd(Array[i] , Array[i+1]) == 1 && __gcd(Array[i+1] , Array[i+2]) == 1)
		if(Array[i] != 1 && Array[i+2] != 1)
		{
			Array[i+1] = 0;
			k--;
			if(k == 0) goto bk;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		int j = i;
		while(Array[j] == 1 && j <= n)
			j++;
		if(j > i)
			Vec.push_back(make_pair(j - i , i)) , i = j - 1;
	}
	Wall = 0;
	sort(Vec.begin() , Vec.end());
	for(auto v:Vec)
	{
		if(v.second == 1)
		{
			NearWall[0] = v;
			Wall |= 1;
			continue;
		}
		if(v.second + v.first - 1 == n)
		{
			NearWall[1] = v;
			Wall |= 2;
			continue;
		}
		for(int i = v.second ; i <= v.second + v.first - 1 ; ++i)
		{
			Array[i] = 0;
			k--;
			if(k == 0) goto bk;
		}			
	}
	if(Wall & 1)
	{
		for(int i = NearWall[0].first ; i >= 1 ; --i)
		{
			Array[i] = 0;
			k--;
			if(k == 0) goto bk;			
		}
	}
	if(Wall & 2)
	{
		for(int i = n - NearWall[1].first + 1 ; i <= n ; ++i)
		{
			Array[i] = 0;
			k--;
			if(k == 0) goto bk;
		}
	}
	for(int i = 1 ; i <= n - 1 ; ++i)
	{
		if(__gcd(Array[i] , Array[i+1]) == 1)
		{
			Array[i] = 0;
			k--;
			if(k == 0) goto bk;
		}
	}
	bk:;
	int Answer = 0;
	for(int i = 1 ; i <= n - 1 ; ++i)
		if(__gcd(Array[i] , Array[i+1]) == 1) Answer++;
	cout << Answer << '\n';
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}
/*
19 7
1 1 2 3 4 5 5 6 6 7 8 9 10 1 1 1 2 3 1
0 0 2 0 4 5 5 6 6 0 8 0 10 0 1 1 2 3 0
*/

G.A Growing Tree

G.A Growing Tree
题意
有一颗树，初始只有一个节点，有两种操作。
操作1,1 v，给节点v增加一个子节点，编号为sz + 1,初值为0,sz是当前节点数。
操作2,2 v x,给节点v的子树中每个节点都加上x。
最后输出树中每个节点的值。
数据范围
多组数据，\(1<=q<=5*10^5\)
输入样例

3
9
2 1 3
1 1
2 2 1
1 1
2 3 2
1 3
2 1 4
1 3
2 3 2
5
2 1 1
1 1
2 1 -1
1 1
2 1 1
5
1 1
1 1
2 1 1
2 1 3
2 2 10

输出样例

7 5 8 6 2 
1 0 1 
4 14 4

题解
先把完整的数建立出来，按照完整的树操作。当碰到新建节点时，再将改节点的值修改为0.
记录两个失误。

  1. Add(k , l , r , val)函数中，val的类型没有设为long long，因为觉得只有输入的数据，不会超long long。但其实还有Down操作中，会用到Tag[k]。
  2. 多组数据清空时，用的是将1~n每个点做一次单点修改置0。这样写忘记将最后的单点处的Tag清空，到了下一组样例中，本样例的单点可能就是一段区间了，所以必须清理干净。
#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5+10;
#define int long long
int n , Dfn_Number;
int Dfn[N] , Size[N];
long long Tr[N<<2] , Tag[N<<2];
vector<int> Vec[N];
struct Options{
	int opt , v , x;
}Array[N];

void Dfs(int x)
{
	Dfn[x] = ++Dfn_Number; Size[x] = 1;
	for(auto v:Vec[x])
		Dfs(v) , Size[x] += Size[v];
}

#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r

void Add(int k , int l , int r , long long val)
{
	Tag[k] += val;
	Tr[k] += 1ll * (r - l + 1) * val;
}

void Down(int k , int l , int r)
{
	if(Tag[k])
	{
		Add(lson , Tag[k]);
		Add(rson , Tag[k]);
		Tag[k] = 0ll;
	}
}

void Modify(int k , int l , int r , int pos)
{
	if(l == r) { Tr[k] = 0ll; return ; }
	Down(k , l , r);
	if(pos <= mid)
		Modify(lson , pos);
	else
		Modify(rson , pos);
	Tr[k] = Tr[k<<1] + Tr[k<<1|1];
}

void Modify(int k , int l , int r , int x , int y , int val)
{
	if(x <= l && r <= y) return Add(k , l , r , val);
	Down(k , l , r);
	if(x <= mid)
		Modify(lson , x , y , val);
	if(y >  mid)
		Modify(rson , x , y , val);
	Tr[k] = Tr[k<<1] + Tr[k<<1|1];
}

long long Query(int k , int l , int r , int pos)
{
	if(l == r) return Tr[k];
	Down(k , l , r);
	if(pos <= mid)
		return Query(lson , pos);
	else
		return Query(rson , pos);
}

void Solve()
{
	int Q;
	cin >> Q;
	for(int i = 1 ; i <= Q ; ++i)
	{
		cin >> Array[i].opt >> Array[i].v;
		if(Array[i].opt == 2) cin >> Array[i].x;
	}
	n = 1;
	for(int i = 1 ; i <= Q ; ++i) 
		if(Array[i].opt == 1)
			Vec[Array[i].v].push_back(++n) , Array[i].v = n;
	Dfs(1);
	for(int i = 1 ; i <= Q ; ++i)
	{
		if(Array[i].opt == 1)
			Modify(1 , 1 , n , Dfn[Array[i].v]);
		else
			Modify(1 , 1 , n , Dfn[Array[i].v] , Dfn[Array[i].v] + Size[Array[i].v] - 1 , Array[i].x);		
	}
	for(int i = 1 ; i <= n ; ++i)
		cout << Query(1 , 1 , n , Dfn[i]) << ' ';
	cout << '\n';
	Dfn_Number = 0;
	for(int i = 1 ; i <= n ; ++i)
		Vec[i].clear();
	for(int i = 0 ; i <= (n << 2) ; ++i)
		Tr[i] = Tag[i] = 0ll;
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T; while(T--) Solve();
	return 0;
}