• Codeforces Global Round 21A~D

    这里写目录标题

    A. NIT orz!

    题意：
    给定一个长度为 n n n的数组，并且给一个整数 z z z，可以进行以下操作：
    a [ i ] = z O R a [ i ] ， z = z A N D a [ i ] a[i]=z OR a[i]，z=z AND a[i] a[i]=zORa[i]，z=zANDa[i]
    求进行操作后(或不进行操作)数组a的最大值
    思路：
    如果进行操作 z z z只会越来越小，所以只有在第一次操作， a [ i ] a[i] a[i]才会尽可能的大，所以枚举所有 a [ i ] O R z a[i] OR z a[i]ORz求最大值

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,z;
const int N=2010;
int a[N];
void solve()
{
	cin>>n>>z;
	for(int i=1;i<=n;i++)cin>>a[i];
	int maxv=0;
	for(int i=1;i<=n;i++)
	{
		maxv=max(maxv,a[i]|z);
	}
	cout<<maxv<<endl;
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    B. NIT Destroys the Universe

    题意：
    给定一个数组 a a a，每次操作可以选取一个 l , r l,r l,r，对 [ l , r ] [l,r] [l,r]进行 m e x mex mex操作，使得数组 a a a全部变成0的最小操作数
    思路：
    不为0的连续元素需要进行一次操作，如果有大于两段，只需要将其看成一整段进行操作，结论是最大操作数不超过2

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
int k;
const int N=1e5+10;
int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int cnt=0;
	a[0]=0;
	for(int i=0,j=0;i<=n;i++)
	{
		if(a[i]==0)j=i;
		else
		{
			if(i==j+1)cnt++;
		}
	}
	if(cnt>1)cout<<2<<endl;
	else cout<<cnt<<endl;
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    C. Fishingprince Plays With Array

    题意：
    给定一个数组 a a a和一个整数 m m m，有以下两种操作

    1. 如果a[i] %m=0，那么可以将a[i]拆分m个a[i]/m。
    2. 可以将m个连续的a[i]合并成一个m*a[i]
      判断是否可以将a数组转换成b数组

    思路：
    将a和b数组尽可能拆，因为 a i < = 1 e 9 a_i<=1e9 ai​<=1e9所以将连续的相等的进行合并
    同理b数组也是，最后判断是否相等即可

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
int k;
const int N=5e4+10;
int a[N],b[N];
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>k;
	for(int i=1;i<=k;i++)cin>>b[i];
	vector<PII>v1,v2;
	for(int i=1;i<=n;i++)
	{
		int s=1;
		while(a[i]%m==0)s*=m,a[i]/=m;
		if(v1.size()==0||v1.back().x!=a[i])v1.pb({a[i],s});
		else v1.back().y+=s;
	}
	for(int i=1;i<=k;i++)
	{
		int s=1;
		while(b[i]%m==0)s*=m,b[i]/=m;
		if(v2.size()==0||v2.back().x!=b[i])v2.pb({b[i],s});
		else v2.back().y+=s;
	}	
	if(v1==v2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    D. Permutation Graph

    题意：
    给一定排列， 1 − n 1 - n 1−n打乱顺序，定义两个点i, j直接存在一条长度为1的边当且仅当在i, j的范围中最大值和最小值分别区在 a [ i ] a[i] a[i]和 a [ j ] a[j] a[j]，但是顺序可以交换，请问 1 − n 1 - n 1−n的最段路。
    思路：
    贪心的角度考虑，跨度越大越好，我们需要直接对区间进行处理（找一个最大值和最小值在左右两端），分治递归。

    input
10
7 4 8 1 6 10 3 5 2 9
output
6

    • 1
    • 2
    • 3
    • 4
    • 5

    在这里插入图片描述

    #include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){return (a%mod+mod)%mod;}
LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
const int N=2.5e5+10;
int a[N],pos[N];
int n,m,p;
struct node
{
	int l,r;
	int minv;
	int maxv;
}tr[4*N];
void pushup(int u)
{
	tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
	tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
}
void build(int u,int l,int r)
{
	tr[u]={l,r};
	if(l==r)
	{
		tr[u].minv=tr[u].maxv=a[r];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
int query_min(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].minv;
	int mid=tr[u].l+tr[u].r>>1;
	int v=INF;
	if(l<=mid)v=query_min(u<<1,l,r);
	if(r>mid)v=min(v,query_min(u<<1|1,l,r));
	return v;
}
int query_max(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].maxv;
	int mid=tr[u].l+tr[u].r>>1;
	int v=0;
	if(l<=mid)v=query_max(u<<1,l,r);
	if(r>mid)v=max(v,query_max(u<<1|1,l,r));
	return v;
}
int search(int l,int r)
{
	if(l+1==r)return 1;
	if(l>=r)return 0;
	int maxv=query_max(1,l,r);
	int minv=query_min(1,l,r);
	int L=pos[maxv],R=pos[minv];
	if(L>R)swap(L,R);
	return search(l,L)+1+search(R,r);
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
	if(n==1)cout<<0<<endl;
	else 
	{
		build(1,1,n);
		cout<<search(1,n)<<endl;
	}
}
signed main()
{
    io;
 	cin>>_; 
 	while(_--)
    solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
  • 相关阅读:
    最好的RabbitMQ新手入门学习笔记，我们一起来学习
    （2022版）一套教程搞定k8s安装到实战 | 生产环境关键性配置
    leetcode做题笔记174. 地下城游戏
    【国庆特辑文章】时间序列~动态时间规整(Dynamic Time Wraping)
    257. 二叉树的所有路径
    云上攻防-云原生篇&Docker安全&系统内核&版本漏洞&CDK自动利用&容器逃逸
    关于QT5和qt6的Camera不同
    手机上的动态ip流量是算自己的流量吗？
    工作流JBPM流程图说明
    【OpenCV-Python】教程：3-14 Hough 圆变换
  • 原文地址：https://blog.csdn.net/qq_52765554/article/details/125468303