CSP-J2022

D 整活导致 \(400\) 变 \(390\) 哭。

A. 乘方

其实枚举就能过，特判 \(a=1\) 就行了。

但是考场上看这题太像快速幂了就码了个快速幂。
普通的快速幂：

(long long)
tot=1;
while(b){
	if(b&1){
		tot*=a;
	}
	b>>=1;
	a*=a;
}

我们发现其实有 \(2\) 个地方需要判断：

1. tot*=a，跳过不解释。
2. a，若 while 未终止说明后面还要乘 \(a^x(x\ge1)\) 次方，若 \(a\) 已经 \(>lim\)，则一定会超。

#include<bits/stdc++.h>
using namespace std;
const long long lim=1000000000;
int main(){
	long long a,b;
	scanf("%lld%lld",&a,&b);
	long long tot=1;
	while(b){
		if(a>lim){
			printf("-1");
			return 0;
		}
		if(b&1){
			tot*=a;
			if(tot>lim){
				printf("-1");
				return 0;
			}
		}
		b>>=1;
		a*=a;
	}
	printf("%lld",tot);
	return 0;
}

B. 解密

可以发现 \(e\times d=pq-p-q+2\)。
所以 \(m=n-e\times d+2=p+q\le 10^9\)。

小学数学可得：和相同，两数越相近乘积越大。
于是发现具有单调性采用二分。

#include<bits/stdc++.h>
using namespace std;
const long long lim=1000000000;
void work(long long n,long long m){
	long long l=0,r=m>>1;
	while(l<=r){
		long long mid=l+((r-l)>>1);
		if(mid*(m-mid)==n){
			printf("%lld %lld\n",mid,m-mid);
			return ;
		}
		else if(mid*(m-mid)<n){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	printf("NO\n");
	return ;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		long long n,e,d;
		scanf("%lld%lld%lld",&n,&e,&d);
		work(n,n-e*d+2);
	}
	return 0;
}

C. 逻辑表达式

感觉还是挺水的？

首先我们可以模拟建表达式树，即给定区间 \([l,r]\)，找到区间内优先级最低的符号所处的位置 \(mid\)，分成 \([l,mid-1]\) 和 \([mid+1,r]\) 去解决。

但是找优先级最低的是个瓶颈，我们发现可以预处理每个点其前面最靠后的 | 和 & 为 \(lor_i,land_i\)。

我们可以先处理好其层级，即每一个括号就给他分出来一层。用桶记录最靠后的 | 和 & 位置即可。

#include<bits/stdc++.h>
using namespace std;
const int S=1000010;
char s[S];
int ce[S],lpai[S],lor[S],land[S],t[S];
int build(int l,int r,int &tor,int &tand){
	while(lpai[r]==l){
		r--;
		l++;
	}//去掉外围括号
	if(l==r&&isdigit(s[l])){
		return s[l]-'0';
	}//单个数字
	int opt=2,w=0;
	if(lor[r]>=l){
		opt=1;
		w=lor[r];
	}//|优先级偏低
	else{
		opt=0;
		w=land[r];
	}
	int lsum=build(l,w-1,tor,tand);
	if(lsum&&opt){
		tor++;
		return 1;
	}
	if((!lsum)&&(!opt)){
		tand++;
		return 0;
	}
	int rsum=build(w+1,r,tor,tand);
	if(opt){
		return lsum|rsum;
	}
	return lsum&rsum;
}
int main(){
	scanf("%s",s+1);
	int len=strlen(s+1);
	int tp=0;
	for(int i=1;i<=len;i++){
		if(s[i]=='('){
			t[++tp]=i;
		}
		else if(s[i]==')'){
			lpai[i]=t[tp--];
		}
		ce[i]=tp;//层级
	}
	for(int i=0;i<=len;i++){
		t[i]=0;
	}
	for(int i=1;i<=len;i++){
		if(s[i]=='|'){
			t[ce[i]]=i;
		}
		lor[i]=t[ce[i]];
	}
	for(int i=0;i<=len;i++){
		t[i]=0;
	}
	for(int i=1;i<=len;i++){
		if(s[i]=='&'){
			t[ce[i]]=i;
		}
		land[i]=t[ce[i]];
	}
	int tor=0,tand=0;
	printf("%d\n",build(1,len,tor,tand));
	printf("%d %d",tand,tor);
	return 0;
}

D. 上升点列

考虑 DP，设 \(dp_{i,k}\) 为第 \(i\) 个点为终点一共串联起来 \(k\) 个固定的点所需要的点数最小值。

\(dp_{i,k}=\min\{dp_{j,k-1}+(x_i+y_i-x_j-y_j)\}(i\not=j,x_i\ge x_j,y_i\ge y_j)\)。

\(O(n^3)\) 可过。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int x[N],y[N],dp[N][N];
int main(){
	int n,t;
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		dp[i][1]=0;
	}
	for(int k=2;k<=n;k++){
		for(int i=1;i<=n;i++){
			dp[i][k]=INT_MAX;
			for(int j=1;j<=n;j++){
				if(i==j||dp[j][k-1]==INT_MAX){
					continue;
				}
				if(x[i]<x[j]||y[i]<y[j]){
					continue;
				}
				int dis=x[i]+y[i]-x[j]-y[j]-1;
				if(dp[j][k-1]+dis>t){
					continue;
				}
				dp[i][k]=min(dp[i][k],dp[j][k-1]+dis);
			}
		}
	}
	for(int k=n;k>=1;k--){
		for(int i=1;i<=n;i++){
			if(dp[i][k]!=INT_MAX){
				printf("%d",t+k);
				return 0;
			}
		}
	}
	return 0;
}

原文地址：http://www.cnblogs.com/lhzawa/p/16905050.html