CF907 div2
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
题意
给出一个长度为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
题意
这里有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
题意
给出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
题意
有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
题意
有一颗树，初始只有一个节点，有两种操作。
操作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.
记录两个失误。
- Add(k , l , r , val)函数中，val的类型没有设为long long，因为觉得只有输入的数据，不会超long long。但其实还有Down操作中，会用到Tag[k]。
- 多组数据清空时，用的是将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;
}