乘方（模拟）

思路

1. 一定要开long long！！！
2. 如果a等于1，直接输出1；
3. 直接循环乘肯定会溢出，所以要判断ans是否大于1e9/a，满足，输出-1；
4. 不满足，ans*=a。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("cf.in","r",stdin);
	freopen("cf.out","w",stdout);
	long long a,b;
    cin >>a>>b;
    if(a==1){
        cout <<"1";
        return 0;
    }
    long long ans=1;
    for (int i=1;i<=b;i++){
        if(ans>1e9/a){
            ans=-1;
            break;
        }
        else ans*=a;
    }
    cout <<ans;
    return 0;
}

解密（数学）

思路

一道很简单的数学题。我们已知：

$n=p*q$

$e*d=(p-1)(q-1)+1$

$m=n-e*d+2$

这是你就会发现$m$就等于$p+q$的和。这时候我们就要用到平方和与平方差了公式了，我们先来复习一下平方和与平方差公式：

$(p+q)^2=p^2+q^2+2pq$

$(p+q)^2=p^2+q^2-2pq$

我们发现因为$m$就等于$p+q$，再减去$2pq$，那这两个公式就成为了：

$m^2-4n=p^2-2*q+q^2$

$(p-q)^2=p^2-2*p*q+q^2$

那么$p-q$的式子：

$ans=\sqrt{(m^2-4*n)}$

$ans$表示$p-q$

那么为什么有$4$这个系数呢？

举个栗子🌰：

$n=12,p+q=7$

$7^2=49$

$49/12=4......1$

再举个栗子🌰：

$n=6,p+q=5$

$5^2=25$

$25/6=4......1$

所以$4$这个数字就是我们要找的系数。

然后，因为$m$与$n$都是正整数，所以要判断一下$ans$是否为完全平方数。

是完全平方数，输出$(m-ans)/2$与$(m+ans)/2$。

不是完全平方数，输出$NO$。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("decode.in","r",stdin);
	freopen("decode.out","w",stdout);
    int k;
    cin >>k;
    while(k--){
        long long n,d,e;
        cin >>n>>d>>e;
        long long m=n-e*d+2;//求p+q的和
        long long ans=sqrt(m*m-4*n);
        if(ans*ans==m*m-4*n){
            cout <<(m-ans)/2<<" "<<(m+ans)/2<<endl;
        }else{
            cout <<"NO"<<endl;
        }
    }
    return 0;
}

逻辑表达式（dfs深搜）

思路没想到的原因

当时想的是碰到符号就$cnt++$，看题不仔细，还沉浸在写出来第二题的喜悦里。

思路

乍一看，其实跟中缀表达式求值没啥区别，但要求出电路的数量，所以我们要构造一棵树。定义左子树与右子树的数组，再做如下操作：

1. 循环$str$字符串，如果$str[i]$为左括号，存入符号栈；
2. $str[i]$为数字，存入树里，并且存入数字栈
3. $str[i]$为右括号，开始计算答案；
4. $str[i]$为符号，按照计算优先级来计算。

接下来就是$dfs$函数了。

1. 如果当前的字符为数字，返回数字；
2. 如果当前的字符为或运算，判断左子树是否返回$1$，满足，$cnt2++$，并且返回$1$；
3. 不满足，$cnt2++$查找右子树是否返回$1$；
4. 如果当前的字符为或运算，判断左子树是否返回$0$，满足，$cnt1++$，并且返回$0$；
5. 不满足，$cnt1++$查找右子树是否返回$0$；
6. 最后输出$dfs(idx)$，$cnt1$与$cnt2$。

代码

#include <bits/stdc++.h>
using namespace std;

stack<int> num;
stack<char> op;
const int tt=1e6+10;
int l[tt],r[tt];
char w[tt];
int cnt1=0,cnt2=0;
int idx=1;

void eval(){
	int b=num.top();
	num.pop();
	int a=num.top();
	num.pop();
	w[++idx]=op.top();
	op.pop();
	l[idx]=a;
	r[idx]=b;
	num.push(idx);
}

bool f(char z){
	return z>='0'&&z<='1';
}

int dfs(int x){
	if(f(w[x])){
		return w[x]-'0';
	}
	if(w[x]=='|'){
		if(dfs(l[x])==1){
			cnt2++;
			return 1;
		}else{
			return dfs(r[x]);
		}
	}
	if(w[x]=='&'){
		if(dfs(l[x])==0){
			cnt1++;
			return 0;
		}else{
			return dfs(r[x]);
		}
	}
}

unordered_map<char,int> pr{{'|',1},{'&',2}};

int main(){
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	string str;
	cin >>str;
	for(int i=0;i<str.size();i++){
		auto c=str[i];
		if(isdigit(c)){
			w[++idx]=c;
			num.push(idx);
		}
		else if(c=='(') op.push(c);
		else if(c==')'){
			while(op.top()!='(') eval();
			op.pop();
		}else{
			while(op.size()&&op.top()!='('&&pr[c]<=pr[op.top()]){
				eval();
			}
			op.push(c);
		}
	}
	while(op.size()) eval();
	int ans=dfs(idx);
	cout <<ans<<endl<<cnt1<<" "<<cnt2;
	return 0;
}

上升点列（DP）

思路没想到的原因

题目都险些没有看懂，想到了最长上升子序列，但没有写出来。

思路

套用最长上升子序列的代码可以骗到$45$分，现在我们来说一说正解：

状态表示：$f[i][j]$表示第$i$个点用$j$个点能组成的满足条件的序列的最大长度。

状态计算：

• 当前如果满足$d<=k\&\&a[j].first<=a[i].first\&\&a[j].second<=a[i].second$，那么$f[i][l]=max(f[i][l],f[j][l-d]+d+1)$；
• 否则$continue$。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=510;
int f[tt][tt];

pair<int,int> a[tt];

int mhd(int i,int j){
	return abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second);
}

int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	int n,k;
	cin >>n>>k;
	for(int i=1;i<=n;i++){
		cin >>a[i].first>>a[i].second;
		f[i][0]=1;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i-1;j++){
			int d=mhd(i,j)-1;
			for(int l=d;l<=k;l++){
				if(d<=k&&a[j].first<=a[i].first&&a[j].second<=a[i].second){
					f[i][l]=max(f[i][l],f[j][l-d]+d+1);
				}else{
					continue;
				}
			}
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			mx=max(mx,f[i][j]+k-j);
		}
	}
	cout <<mx;
	return 0;
}

谢谢