2018_10_29 模拟赛

解题报告

• 前言
• JZOJ 5195 A
• • 题目
  • 分析
  • 代码
• JZOJ 5196 B
• • 题目
  • 分析
  • 代码
• JZOJ 5197 C
• • 题目
  • 分析
  • 代码
• 后续

前言

生于忧患，死于安乐

JZOJ 5195 A

题目

把n个相同的弹珠放在k个相同的盒子，使每个盒子非空，问有多少种不同的方案

分析

(数的划分)很清楚的让我们知道状态转移方程 f [ n ] [ k ] = f [ n − k ] [ k ] ( 没 有 一 个 1 ， 等 同 于 把 所 有 减 去 1 ) + f [ n − 1 ] [ k − 1 ] ( 至 少 有 一 个 1 ) f[n][k]=f[n-k][k](没有一个1，等同于把所有减去1)+f[n-1][k-1](至少有一个1) f[n][k]=f[n−k][k](没有一个1，等同于把所有减去1)+f[n−1][k−1](至少有一个1)

代码

#include <cstdio>
#define rr register
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
int n,k,f[5001][5001];
int main(){
	scanf("%d%d",&n,&k); f[0][0]=1;
	for (rr int i=1;i<=n;++i)
	for (rr int j=1;j<=min(i,k);++j) f[i][j]=(f[i-1][j-1]+f[i-j][j])%998244353;
	printf("%d",f[n][k]);
	return 0;
}
           

JZOJ 5196 B

题目

在一棵树上找一条路径的边权和在范围内且最小

分析

点分治，统计的时候用set维护

代码

#include <cstdio>
#include <algorithm>
#include <set>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define rr register
using namespace std;
const int N=100000;
struct node{int y,w,next;}e[N<<1|1]; set<int>uk;
int son[N+1],ls[N+1],sz,v[N+1],root,l,r,n,f[N+1],ans,k;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (c<48||c>57) c=getchar();
	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
	return ans;
}
void groot(int u,int fa){//找出树的重心
	son[u]=1; f[u]=0;
	for (rr int i=ls[u];i;i=e[i].next)
	if (!v[e[i].y]&&e[i].y!=fa){
		groot(e[i].y,u);
		son[u]+=son[e[i].y];
		f[u]=max(f[u],son[e[i].y]);
	}
	f[u]=max(f[u],sz-son[u]);
	if (f[u]<f[root]) root=u;
}
void dfs(int u,int fa,int now,int fg){
	if (fg) uk.insert(now);
	else{
		if (l<=now&&now<=r) ans=min(ans,now);
		rr int maxx=*--uk.end();
		if (now+maxx>=l){//必然能找到答案
			int fnd=now+*uk.lower_bound(l-now);//找出一个大于等于l-now的数
			if (l<=fnd&&fnd<=r) ans=min(ans,fnd);
		}
	}
	for (rr int i=ls[u];i;i=e[i].next)
	if (!v[e[i].y]&&e[i].y!=fa)
		dfs(e[i].y,u,now+e[i].w,fg);//继续找
}
void dp(int x){
	v[x]=1; uk.clear(); uk.insert(0);//0是为了什么也不加
	for (rr int i=ls[x];i;i=e[i].next)
	if (!v[e[i].y]){
		dfs(e[i].y,x,e[i].w,0);//首先查找
		dfs(e[i].y,x,e[i].w,1);//加入该子树的贡献
	}
	for (rr int i=ls[x];i;i=e[i].next)
	if (!v[e[i].y]){
		sz=son[e[i].y];
		groot(e[i].y,root=0);//在子树找树的重心
		dp(root);//在子树继续dp
	}
}
signed main(){
	sz=n=iut(); l=iut(); r=iut();
	f[0]=ans=2147483647;
	for (rr int i=1;i<n;++i){
		rr int u=iut(),v=iut(),w=iut();
		e[++k]=(node){v,w,ls[u]}; ls[u]=k;
		e[++k]=(node){u,w,ls[v]}; ls[v]=k;
	}
	groot(1,0);
	dp(root);
	if (ans>r) printf("-1"); else printf("%d",ans);
	return 0;
}
           

JZOJ 5197 C

题目

在 [ 1 ∼ n ] [1\sim n] [1∼n]中找到无序数对 ( x , y ) (x,y) (x,y)使 g c d ( x , y ) gcd(x,y) gcd(x,y)= x x x xor y y y

分析

首先设 x > y x>y x>y，那么 g c d ( x , y ) ≤ x − y gcd(x,y)\leq x-y gcd(x,y)≤x−y

因为 g c d ( x , y ) = g c d ( x , x − y ) gcd(x,y)=gcd(x,x-y) gcd(x,y)=gcd(x,x−y)，那么 g c d ( x , y ) ≤ x − y gcd(x,y)\leq x-y gcd(x,y)≤x−y

并且 x x x xor y ≥ x − y y\geq x-y y≥x−y

因为相同的肯定会抵消掉，当 x x x某位为1且 y y y该位为0是1显然至少不少于 x − y x-y x−y，当 x x x某位为0且 y y y该位为1是1显然大于 x − y x-y x−y，综上所述，那么转换为 x x x xor y = x − y y=x-y y=x−y才能成立，那么可以枚举 y y y，同时只有它的倍数可用，时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

代码

#include <cstdio>
#define rr register
using namespace std;
int ans,n;
signed main(){
	scanf("%d",&n);
	for (rr int i=1;i<=n;++i)
	for (rr int j=2;j*i<=n;++j)
	ans+=((j*i)^i)==j*i-i;//j*i必然是i的倍数
	printf("%d",ans);
	return 0;
}
           

后续

菜出新高度