NOIp-75

作者:神秘网友 发布时间:2021-10-13 07:24:01

NOIp-75

RT

水博客太快乐了

RT

烤场

顺序开题。
啥也不会。。。

写了 \(t1, t3, t4\) 的暴力,t2懒就没有写,发现了 \(t4\) 的一些结论,但是不全,最终也没有什么用处。。。

最后十分钟想出 \(t3\) 正解,没来的及写,考完写了就过了。。。

总之貌似烤的挺炸的。。全是暴力。。。

分数

预估 :\(t1 \ 30pts \ + \ t2 \ 0pts \ + \ t3 \ 50pts \ + \ t4 \ 50pts \ = \ 130pts\)
实际 :\(t1 \ 30pts \ + \ t2 \ 0pts \ + \ t3 \ 50pts \ + \ t4 \ 30pts \ = \ 110pts\)

题解

A. 如何优雅的送分

本蒟蒻对这种数论的理解也并不是很深刻,建议移步巨佬 y_cx 的博客

B. 阴阳

巨佬cyh :暴力踩标算,直接暴力踩过去。

记录巨佬的方法:用主席树记录点的颜色暴力 bfs 找答案。

C. 你猜是不是找规律

提供一个不同于题解的方法。。。
考试最后 \(10min\) 想到,没来得及写。

最开始想的 \(dp\) 状态是 :\(f_{i,j}\) 表示长度为 \(i\) ,交换 \(j\) 次后变为顺序的排列数量,转移类似错排数的递推式,但是这样转移显然是 \(O(nk)\) 的,直接 \(T\) 飞。考虑优化。

发现 \(k\) 小的可怜,而 \(n\) 大的可怕,因此在最终的到的序列中,大部分的数都是有序的,只有少部分数无序,因此考虑只对无序的数进行 \(dp\) ,设计状态为 :\(f_{i,j}\) 表示长度为 \(i\) ,交换 \(j\) 次会变有序的错排列数量 (指 \(\forall i, a_i \ne i\))。
转移也类似与错排数,此处只给出转移,不加以赘述。。。

\[f_{i,j}=(i-1)(f_{i-1,j-1}+f_{i-2,j-1}) \]

不难发现只要求出 \(i \le 2k ,j \le k\) 的所有情况即可(因为总共就这么几种情况。。。),复杂度 \(O(k^2)\) 。
最终的答案就是将求出的所有无序序列插入一个有序序列即可。

\[ans=\sum_{i=0}^{2k} \binom{n}{i} \sum_{j=0}^k f_{i,j} \]
code
#includebits/stdc++.h
using namespace std;
#define int long long
const int N=3e3+10, mod=1e9+7;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int n, k, ans, f[4][N], sum[N1];
inline int qp(int n, int m){
	int ans=1;
	while(m){
		if(m1) (ans*=n)%=mod;
		m=1; (n*=n)%=mod;
	}
	return ans;
}
inline int C(int n, int m){
	int mul=1, inv=1;
	for(int i=n-m+1; i=n; ++i) (mul*=i)%=mod;
	for(int i=1; i=m; ++i) (inv*=i)%=mod;
	return mul*qp(inv, mod-2)%mod;
}
signed main(void){
	n=read(); k=read(); f[0][0]=1; sum[0]=1;
	for(int i=2; i=k1; ++i){
		memset(f[i%3], 0, sizeof(int)*(k+1));
		for(int j=1; j=k; ++j)
			f[i%3][j]=(i-1)*(f[(i-1)%3][j-1]+f[(i-2)%3][j-1])%mod;
		for(int j=0; j=k; ++j) (sum[i]+=f[i%3][j])%=mod;
	}
	for(int i=0; i=k1; ++i)
		(ans+=sum[i]*C(n, i)%mod)%=mod;
	printf("%lld\n", ans);
}

D. 小说

首先 \(a\) 很好求,依次删去每个数跑一次背包,得到能容量种类数最多的即是 \(a\) 。这一定是正确的,设当前最大容量为 \(maxn\) ,种类数量为 \(num\) ,则一定可以使 \(b=maxn+1\) ,种类数会便为 \(2num+1\)。
可以用退背包的技巧,也可以用 \(bitset\) 优化。

接下来求 \(b\) ,考虑 \(b\) 需要满足什么条件,对于任意两个合法容量 \(x, y, x \le y\) ,都有 \(x+b \ne y\),即 \(b \ne x-y\) 。
\(x, y\) 是由 \(v\) 构成的,那么 \(b\) 就不可以由 \(v\) 之间相互加减得到,也就是将所有 \(v_i, -v_i\) 放在一起跑一个背包,最小无法被构成的数即为最小的 \(b\) 。

code
#includebits/stdc++.h
using namespace std;
const int N=110, V=7e5+10;
inline int read(){
	int f=1, x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
	while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); }
	return f*x;
}
int n, a[N], maxn, a1, b1, sum;
bitsetV ul;
signed main(void){
	n=read();
	for(int i=1; i=n; ++i) sum+=a[i]=read();
	sort(a+1, a+1+n);
	for(int i=1; i=n; ++i){
		ul.reset(); ul[0]=1;
		for(int j=1; j=n; ++j){
			if(i==j) continue;
			ul|=(ula[j]);
		}
		int num=ul.count();
		if(nummaxn) maxn=num, a1=i;
	}
	ul.reset(); ul[0]=1;
	for(int i=1; i=n; ++i){
		if(i==a1) continue;
		ul|=(ula[i]);
	}
	for(int i=1; i=n; ++i){
		if(i==a1) continue;
		ul|=(ula[i]);
	}
	for(int i=1; i=sum-a[a1]+1; ++i)
		if(!ul[i]) { b1=i; break; }
	printf("%d %d\n", a[a1], b1);
	return 0;
}

summary

成为了史上最水博客。。。


本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

NOIp-75 相关文章

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词