牛客小白月赛62

比赛链接：牛客小白月赛62_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A: 幼稚园的树

方法：模拟

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e6+10;
typedef pair<int,int>PII;
int h[N];
 
inline void solve(){
	int a,k,b,n,m;cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	cin>>a>>k>>b>>m;
	m--;
	while(m--){
		for(int i=1;i<=n;i++) h[i]+=a;
		for(int i=1;i<=n;i++){
			if(h[i]>k) h[i]=b;
		}
	}
	for(int i=1;i<=n;i++) cout<" ";
	cout<<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

B:剩下的数

方法：数论——>结论

分析：先通过手撸几组样例过后，我们会发现，答案只有0或1。

证明：

ps：定义整个环的和为sum      询问值为x

如果sum%x==0，那么我们就可以删掉整个环。则ans=0

如果sum%x！=0，ans=1。为什么？

我们发现，L~R中的每个数 mod x，会出现余数，而这些余数值的区间刚好为[0,X-1]。那么L~R中，一定会存在一个数是跟sum同余的。所以，我们任意选出一个数，删掉剩余的数即可。此时ans=1.（可能有点懵？看组样例吧）

ps：现在应该懂了吧？（Q.Q)

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e6+10;
typedef pair<int,int>PII;
 
inline void solve(){
	int l,r,m;cin>>l>>r>>m;
	int sum=(l+r)*(r-l+1)/2;//等差数列求和公式
	while(m--){
		int x;cin>>x;
		if(sum%x==0) cout<<"0\n";
		else cout<<"1\n";
	}
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

C:数列的划分

思路：质因数分解

分析：用set存a数组里面每个数的质因数。再判断b数组的每个质因数是否在set里面出现过。为什么呢？因为如果要互相独立，那么P（b数组中每个数的质因数）set。如果一旦属于了，就一定存在两个对应的数的gcd！=1。

代码：

#include
#define all(v) v.begin(),v.end()
//#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e6+10;
typedef pair<int,int>PII;
int a[N],b[N];
inline void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
    set<int> aa;
	for(int i=1;i<=n;i++){
		int x=a[i];
		for(int j =2;j<=x/j;j++){//筛质因数
			while(x%j==0){
				aa.insert(j);
				x/=j;
			}
		}
		if(x>1) aa.insert(x);//最后筛完，剩余的质因数（如果为1，没有必要放入set）
	}
	for(int i=1;i<=n;i++){
		int x=b[i];
		for(int j=2;j<=x/j;j++){
			while(x%j==0){
				if(aa.count(j)){
					cout<<"No\n";return;
				}	
				x/=j;
			}	
		}
		if(x>1&&aa.count(x)){
			cout<<"No\n";return;
		} 
	}
	cout<<"Yes\n";
}
 
int main(){
	fast; solve();
}

D:子树的大小

思路：思维

分析：一开始我以为用DFS搜索。然而遇到不会建树的问题，且还会TLE。看大佬的题解，才发现这题很简单。

我们拿三叉树进行举例： 

我们定义：L为所要查询跟节点的子树最右边的位置  R跟L同理

所以，在给定一个需要查询的节点时，就可以算出子树每一层的节点数。最后累加即可。 

代码： 

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e6+10;
typedef pair<int,int>PII;
 
inline void solve(){
	int n,m,k;cin>>n>>k>>m;
	n--;
	while(m--){
		int q;cin>>q;
		if(k==1){//可以当作链表结构
			cout<1<<"\n";continue;
		}
		int ans=0;
		int l=q,r=q;
		while(l<=n){
			ans+=min(n,r)-l+1;
			l=l*k+1;//下一层的最左边
			r=r*k+k;//下一层的最右边
		}
		cout<"\n";
	}
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

E:剖分

思路：树上差分

题解：具体看代码注释

代码：

#include
#define all(v) v.begin(),v.end()
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e7+10;
typedef pair<int,int>PII;
int add[N],sum[N],st[N];/*add：以i为根节点的子树     sum：i号节点的权重     st：存答案*/
ps：add[i]：也表示了i号节点的权重
 
inline void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		int x;cin>>x;
		if(op==1) add[x]++;//以x为根节点的子树都+1
		else if(op==2) add[x]--,add[1]++;//可以看作，以x为根节点的子树都先-1，再使整个树+1
		else if(op==3){//路径上各个节点的权重+1
			while(x) sum[x]++,x/=2;	
		}
		else{//跟op==2的操作同理
		    add[1]++;
			while(x) sum[x]--,x/=2;			
		}
	}
	for(int i=1;i<=n;i++){
		int l=2*i;//左子树（儿子）
		int r=2*i+1;//右子树（儿子）
		sum[i]+=add[i];//i号节点的权重=以i为根的权重
		add[l]+=add[i];//这里给图说明一下
		add[r]+=add[i];
	}
	for(int i=1;i<=n;i++) st[sum[i]]++;//记录答案
	for(int i=0;i<=m;i++) cout<" ";//输出答案
}
 
signed main(){
	fast;solve();
}

仔细思考一下。如果B节点被加了X次，那么他的子树（节点）D也被加了X次 。所以D的权重=D本身的权重加上他父亲的权重=add[D]+add[B]。B是D的父亲，根据二叉树的基本知识，节点i的左儿子是2*i，右儿子 2*i+1。那么给定儿子的节点k。他的父亲节点就是k/2。

PS：再次深刻理解add和sum数组的含义！！！