D 整活导致 \(400\) 变 \(390\) 哭。
A. 乘方
其实枚举就能过，特判 \(a=1\) 就行了。
但是考场上看这题太像快速幂了就码了个快速幂。
普通的快速幂：
(long long)
tot=1;
while(b){
if(b&1){
tot*=a;
}
b>>=1;
a*=a;
}
我们发现其实有 \(2\) 个地方需要判断：
tot*=a，跳过不解释。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;
}