欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2021.04.03【NOIP提高B组】模拟 总结

程序员文章站 2024-03-18 22:12:10
...

T1

题目大意:求最小的 \(n\in[0,lim]\) 使得区间 \([L,R]\) 在线段树建树 \(build(0,n)\) 的区间内

考场时想到了正解,结果推式子退错了。。。

其实就是从下往上搜索,可以转到父节点为 \([l,2(l-1)-r],[l,2(l-1)-r+1],[r,2r-l],[r,2r-l+1]\)

如果 \(l=0\) 那么 \(r\) 就是当前答案

但是这样会时超,原因:如果无法将 \(l\) 缩小,那么 \(r\) 会一直扩大到 \(lim\) 才返回,会浪费许多时间

其实如果 \(2l<r\) 就是不行的

#include<bits/stdc++.h>
using namespace std;
const int inf=2100000000;
int ql,qr,n,T,ans;
void fnd(int l,int r) {
	if(l<0||r>n||r<0||r>ans)return;
	if(!l) { ans=r; return; }
	if(2*l<r)return;
	fnd(2*l-r-2,r);
	fnd(2*l-r-1,r);
	fnd(l,r*2-l);
	fnd(l,r*2+1-l);
}
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d",&ql,&qr,&n);
		ans=inf;
		if(ql^qr)fnd(ql,qr);
		else if(qr<=n)ans=qr;
		printf("%d\n",ans<inf?ans:-1);
	}
}

希望以后式子不要退错

T2

题目大意: \(n\le 18\) 个桶,一次只能挑两个桶。每次有话费,问最小话费

状压 dp 板子。

T3

题目大意:给你一个括号串,定义若 \(A,B\) 是合法串,则 \(AB\)\((A)\) 都是合法串。

​ 设经过 \(i\) 的合法串个数 \(ans_i\) ,求 \(\sum_{i=1}^n i\times ans_i\mod 100000007\)

将一对括号合成一块,记 \(f_i,g_i\) 为第 \(i\) 个括号在左边、右边同级括号的个数

则第 \(i\) 块的答案为 \(f_i*g_i\)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000005,P=1000000007;
int T,n,top,st[N],fl[N],nxt[N],lst[N],f[N],g[N]; char x[N]; LL ans[N],res;
inline void add(int l,int r,LL v) { ans[l]+=v,ans[r+1]-=v; }
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%s",x+1);
		n=strlen(x+1);
		top=res=0,fl[0]=1;
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		memset(nxt,0,sizeof(nxt));
		memset(lst,0,sizeof(lst));
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=n;i++)
			if(x[i]=='(')st[++top]=i,fl[top]=0;
			else {
				if(fl[top])++top,st[top]=i,fl[top]=1;
				else lst[i]=st[top],nxt[st[top]]=i,--top;
			}
		for(int i=1;i<=n;i++)f[i]=lst[i]?f[lst[i]-1]+1:0;
		for(int i=n;i>=1;i--)g[i]=nxt[i]?g[nxt[i]+1]+1:0;
		for(int i=1;i<=n;i++)if(lst[i])add(lst[i],i,1LL*f[i]*g[lst[i]]);
		for(int i=1;i<=n;i++)ans[i]+=ans[i-1],res+=1LL*i*ans[i]%P;
		printf("%lld\n",res);
	}
}

T4

题目大意: \(A\) 数组降序,\(B_i=\sum_{j=i}^n A_i\) ,现在要从 \((n,1)\) 走到 \((1,1)\),每次可以从 \((x,y)\) 走到 \((x+1,y-1)\)\((x,\lfloor\dfrac{y+1}{2}\rfloor)\)

​ 若选择后者,花费为 \(B_x\)。问最小代价

因为数组有序,所以在哈夫曼树中深度单调不减。考虑 \(dp\) 构建哈夫曼树

\(f_{i,j}\) 为放入下标所有下标比 \(i\) 小的点,剩下 \(j\) 个叶子点

  1. 所有叶子节点扩展出两个后继,剩下所有节点深度加一,代价 \(\sum_{k=i+1}^nA_k\) 状态是 \(f_{2i,j}\)
  2. 把第 \(i\) 个数放到一个叶子上,无代价,状态是 \(f_{i+1,j-1}\)

最后答案是 \(f_{n+1,k}\)

把以上过程倒过来,就是模拟走路,所以直接用贪心构建哈夫曼树。 \(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int T,n,h[N],tot;
LL ans;
inline void ins(int vl) {
	register int x=++tot,fa=x>>1;
	while(fa) {
		if(vl<h[fa]) h[x]=h[fa],x=fa,fa>>=1;
		else break;
	} h[x]=vl;
}
inline void pop() {
	register int x=1,sn=2,vl=h[tot--];
	while(sn<=tot) {
		if(sn<tot&h[sn|1]<h[sn]) sn|=1;
		if(h[sn]<vl) h[x]=h[sn],x=sn,sn<<=1;
		else break;
	} h[x]=vl;
}
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n),tot=0;
		for(int i=1,x;i<=n;i++)
			scanf("%d",&x),ins(x);
		ans=0;
		for(int i=1,f,g;i<n;i++) {
			f=h[1],pop(),g=h[1],pop();
			ans+=1LL*f+1LL*g,ins(f+g);
		}
		printf("%lld\n",ans);
	}
}

上一篇: Morse Mismatches

下一篇: UVA - 712 S-Trees