Atcoder&CodeForces杂题11.6

Preface

NOIP前突然不知道做什么,感觉思维有点江僵化,就在vjudge上随便组了6道ABC D+CF Div2 C/D做,发现比赛质量还不错,知识点涉及广,难度有梯度,码量稍小,思维较多. 同时发现vjudge的比赛功能很不错

A. ABC112-D-Partition

难度感觉比NOIP T1简单了些了

首先naiive的想法是枚举这个公约数$D$,但是发现有$D*N<=M$这个约束,算了算发现$M/N <=1e4$

于是开心从大到小枚举就好了

太水了

1
2
3
4
5
6
7
8
int n,m;
int main(){
	read(n),read(m);
	for(ri i=m/n;i>=1;i--){
		if(m%i==0){printf("%d\n",i);break;}
	}
	return 0;
}

B. ABC110-D-Factorization

应该有NOIP T1难度

我先考虑如果这个M是一个质数,那么就有N种可能,稍稍推广一下,如果$M = P^c$,那么就相当于你有$N$个不同的盒子,然后盒子内可以不装东西,求放$c$个物品的方案数

这个就是隔板法的经典模型

如果您不知道是什么就看这篇洛谷日报吧:https://www.luogu.org/blog/chengni5673/dang-xiao-qiu-yu-shang-he-zi

于是对于$M= \prod pi^{ci}$,由于每个$pi$是独立的,直接乘法原理相乘就好了

一开始用线性推逆元,不知道怎么回事一直最后一个点WA,最后改成阶乘版本就过了…

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
int n,m;
int c[maxn],tot=0;
ll fac[maxn],inv_fac[maxn];
ll C(int n,int m){
	return fac[m]*inv_fac[n]%P*inv_fac[m-n]%P;
}
ll ksm(ll a){
	ll ans=1;
	ll c=P-2;
	while(c){
		if(c&1)ans=ans*a%P;
		a=a*a%P;
		c=c>>1;
	}
	return ans%P;
}
int main(){
	int x,y,M;
	read(n),read(m);
	M=m;
	for(ri i=2;i*i<=M;i++){
		if(M%i==0){
			c[++tot]=1;
			M/=i;
			while(M%i==0){M/=i;c[tot]++;}
		}
	}
	if(M>1)c[++tot]=1;
	fac[0]=fac[1]=1;
	for(ri i=2;i<=size;i++)
		fac[i]=fac[i-1]*i%P;
	inv_fac[size]=ksm(fac[size]);
	for(ri i=size-1;i>=0;i--)
		inv_fac[i]=inv_fac[i+1]*1ll*(i+1)%P;
	ll ans=1;
	for(ri i=1;i<=tot;i++){
		ans=ans*C(n-1,n+c[i]-1)%P;
	}
	printf("%lld\n",ans);
	return 0;
}

C. ABC106-D-AtcoderExpress2

个人认为应该有NOIPT2难度了(天天爱跑步算了)

第一眼一看裸题啊!求一段区间内有多少个被完全包含的区间.冷静分析之后发现并不会做

从数据结构想到容斥还是毫无思路

然后下午睡了一觉之后一下子就想出个一看就不是正解的方法:我会二维数点!

我们对于询问/给出的区间都用$(l,r)$表示,那么你看这个这个东西,它是不是像炉石补偿一个平面直角坐标系上的一个点

同时发现询问区间$(l,r)$,实际上就是询问有多少个点$(l_i,r_i)$满足$l_i>=l,r_i<=r$

画一个图发现它其实就是求一个矩形内有多少个点,我们按照二维数点套路搞一波就好了

关于二维数点:https://www.cnblogs.com/Rye-Catcher/p/9823554.html

这里注意排序时的cmp就好了,代码同样短的可怕

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
int sum[maxn<<3];
int n,m,q;
inline void add(int x,int d){for(;x<=n;x+=x&(-x))sum[x]+=d;return ;}
inline int query(int x){int ans=0;for(;x;x-=x&(-x))ans+=sum[x];return ans;}
struct Pt{
	int x,y,id;
	bool operator <(const Pt &rhs)const{
		return (x==rhs.x)?(y==rhs.y?id<rhs.id:y<rhs.y):x>rhs.x;//注意cmp
	}
}pt[maxn<<2];
int tot=0,qry[maxn];
int main(){
	int x,y;
	read(n),read(m),read(q);
	for(ri i=1;i<=m;i++){
		read(x),read(y);
		pt[++tot]=(Pt){x,y,0};
	}
	for(ri i=1;i<=q;i++){
		read(x),read(y);
		pt[++tot]=(Pt){x,y,i};
	}
	std::sort(pt+1,pt+1+tot);
	for(ri i=1;i<=tot;i++){
		//printf("%d %d %d %d\n",i,pt[i].id,pt[i].x,pt[i].y);
		if(!pt[i].id)add(pt[i].y,1);
		else qry[pt[i].id]=query(pt[i].y);
	}
	for(ri i=1;i<=q;i++)printf("%d\n",qry[i]);
	return 0;
}

D.CF-EducationalRound52-C-MakeItEqual

这题应该比T1稍难一点

首先naiive的想法就是按照高度排序一遍后,不断向下拓展,但是发现操作繁琐,而且我的做法是一个错误的想法

然后这时候我看到值域居然只有2e5?!然后我们还是按照一样的思路一路向下拓展,如果不行的话切一刀就好了

代码同样很短

注意判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
int h[maxn],n,ans=0;
int sz[maxn],mx=0,mi=inf,mi_id;
ll k,sum=0;
int main(){
	read(n),read(k);
	for(ri i=1;i<=n;i++){
		read(h[i]);
		mx=max(mx,h[i]);
		mi=min(mi,h[i]);
		sz[h[i]]++;
	}
	int num=0;
	if(mx==mi){puts("0");return 0;}
	for(ri i=mx;i>=mi;i--){
		sum+=num;
		if(sum>k){
			ans++;
			sum=num;
		}
		num+=sz[i];
	}
	ans++;//最后无论如何都要切一刀
	printf("%d\n",ans);
	return 0;
}

E. CF-Round#485 div.2 D - Fair

这题昨天没想出来,今天看题解发现还挺简单的 雾)

关键还是思维太僵化了

我们可以用BFS求出每个点到某种颜色的最短路,时间复杂度$O(nk)$

然后对于每个点都$nth $_ $element$,求出前s小的颜色距离加起来就好了

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
const int maxn=100005;
const int inf=0x7fffffff;
int n,m,k,s;
int col[maxn];
vector <int> fc[105];
struct Edge{
	int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	h[f]=num_edge;
}
int dis[maxn][105];
inline void bfs(int c){
	queue <int> q;
	int u,v;
	for(ri i=0;i<fc[c].size();i++)q.push(fc[c][i]);
	while(q.size()){
		u=q.front();q.pop();
		for(ri i=h[u];i;i=edge[i].ne){
			v=edge[i].to;
			if(dis[v][c]!=inf)continue;
			dis[v][c]=dis[u][c]+1;
			q.push(v);
		}
	}
	return ;
}
int main(){
	int x,y,z;
	read(n),read(m),read(k),read(s);
	for(ri i=1;i<=n;i++){
		read(col[i]);
		fc[col[i]].push_back(i);
		for(ri c=1;c<=k;c++){
			dis[i][c]=inf;
		}
		dis[i][col[i]]=0;
	}
	for(ri i=1;i<=m;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	for(ri c=1;c<=k;c++){
		bfs(c);
	}
	int ans=0;
	for(ri i=1;i<=n;i++){
		ans=0;
		nth_element(dis[i]+1,dis[i]+s+1,dis[i]+1+k);
		for(ri j=1;j<=s;j++)ans+=dis[i][j];
		printf("%d ",ans);
	}
	puts("");
	return 0;
}

F.

咕