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\) 个叶子点

所有叶子节点扩展出两个后继，剩下所有节点深度加一，代价 \(\sum_{k=i+1}^nA_k\) 状态是 \(f_{2i,j}\)
把第 \(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);

	}

}

巴特西

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

T1

T2

T3

T4

最新文章

热门文章

巴特西

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

T1

T2

T3

T4

最新文章

热门文章

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