A.乘方

思路

完全暴力！只要判断$a=1$，因为而这样会超时

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("cf.in","r",stdin);
	freopen("cf.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a,b;
	cin>>a>>b;
	long long ans=1;
	long long us;
	for(int i=1;i<=b;i++){
		us++;
		ans*=a;
		if(ans>1000000000){
			cout<<-1;
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

解密

思路

根据特性，我们可以推成如下公式：

$$e_i*d_i=p_i*q_i-q_i-p_i+2$$

如果没学过的也没关系，我们慢慢推：

$$(p_i-1)*(q_i-1)+1$$

把$(p_i-1)$设为$A$

$$A*(q_i-1)+1$$

根据乘法分配律，可得以下公式：

$$A*q_i-A+1$$

那个$*1$省掉了 然后把$A$换为原先的公式

$$(p_i-1)*q_i-(q_i-1)+1$$

再继续用乘法分配律：

$$p_i*q_i-q_i-(q_i-1)+1$$

把括号拆了：

$$p_i*q_i-q_i-q_i+2$$

推完了

我们发现，题目中还给了个$m$，根据公式$n_i-e_i*d_i+2$这正是突破口！

我们发现$m$其实就是$q_i+p_i$，具体推理如下：

将$n_i$和$e_i*d_i$转化为$p_i q_i$形式

$$(p_i*q_i)-(p_i*q_i-q_i-q_i+2)+2$$

将括号删了，一对一对删除

$$q_i+q_i-2+2$$ $$q_i+p_i$$

这就是最终$m$代表的含义

这样，我们就只要知道可以$p_i-q_i$就可用和差问题的公式来解答了

怎么来想呢？我这里用一种乘方取值法，大家也可以用其他方法。

根据公式，我们可以得出（设t为$q_i-p_i$）$t=\sqrt{(m*m-4*n)}$

具体公式如下：

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

那么就可以按上面讲的方法得出下面公式（空间有限，先不演示了）：

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

$(p-q)^2$也一样

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

再将刚才定义的一些玩意加进去

$$m^2=p^2+2n+q^2$$

转化为$(p-q)^2$

$$m^2-4n=(p-q)^2$$

由此可得知

$$\sqrt{m^2-4n}=p-q$$

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("decode.in","r",stdin);
	freopen("decode.out","w",stdout);
	long long k;
	cin>>k;
	while(k--){
		long long n,e,d;
		cin>>n>>e>>d;
		long long m=n-e*d+2;
		if(m*m-4*n<0){
			cout<<"NO"<<endl;
			continue;
		}
		long long t=sqrt(m*m-4*n);
		if(t*t!=m*m-4*n){
			cout<<"NO"<<endl;
			continue;
		}
		long long p=(m-t)/2;
		long long q=(m+t)/2;
		if(p*q!=n||(p-1)*(q-1)+1!=e*d){
			cout<<"NO";
		}else{
			cout<<p<<" "<<q<<endl;
		}
	}
	return 0;
}

逻辑表达式

思路

将其看作一个树，来求解

我们先定义3个数组：$l_i,r_i,w_i$，分别表示：树的左端点、右端点、值。

当计算时我们就可以将这些值入数组，当最后dfs深度优先搜索时：计算，顺便统计

代码

#include<bits/stdc++.h>
using namespace std;
stack<int> ans;
stack<char> op;
unordered_map<char,int> mp;
int l[1000010],r[1000010];
char w[1000010];
string a;
int sub1=0,sub2=0;
int idx=0;
void sre(){
	int b=ans.top();ans.pop();
	int a=ans.top();ans.pop();
	char up=op.top();op.pop();
	w[++idx]=up;
	l[idx]=a;
	r[idx]=b;
	ans.push(idx);
}
bool dfs(int es){
	if('0'<=w[es]&&w[es]<='1'){
		return (bool)(w[es]-'0');
	}
	int lp=dfs(l[es]);
	if(lp==1&&w[es]=='|'){
		sub1+=1;
		return 1;
	}
	if(lp==0&&w[es]=='&'){
		sub2+=1;
		return 0;
	}
	int rp=dfs(r[es]);
	if(w[es]=='|'){
		if(lp==1||rp==1){
			return 1;
		}else{
			return 0;
		}
	}else{
		if(lp==0||rp==0){
			return 0;
		}else{
			return 1;
		}
	}
}
int main(){
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	mp['&']=2;
	mp['|']=1;
	cin>>a;
	for(int i=0;i<a.size();i++){
		if(isdigit(a[i])){
			w[++idx]=a[i];
			ans.push(idx); 
		}
		else if(a[i]=='('){
			op.push('(');
		}else if(a[i]==')'){
			while(op.top()!='('){
				sre();
			}
			op.pop();
		}else{
			while(op.size()&&op.top()!='('&&mp[op.top()]>=mp[a[i]]){
				sre();
			}
			op.push(a[i]);
		}
	}
	while(op.size()){
		sre();
	}
	bool anss=dfs(idx);
	cout<<anss<<endl<<sub2<<" "<<sub1;
	return 0;
}

上升点列

思路

就是一道DP，但是不是太难

40分

拿$k=0$的步骤分，最长上升子序列的模板

100分

dp三宝：状态表示，初始化，状态计算

状态表示：$f[i][j]$表示以$i$为结尾加上$j$个点的最大值

初始化：在进行处理时，我们只是将两个序列连接起来而已。所以所有$f[i][0]$设为1

状态计算：$f[i][j]=max(f[i][j],f[j][l-d]+d+1)$

代码

#include<bits/stdc++.h>
using namespace std;
int f[510][110];
pair<int,int> a[510];
int md(int i,int j){
	if(a[i].first-a[j].first>=0&&a[i].second-a[j].second>=0){
		return a[i].first-a[j].first+a[i].second-a[j].second;
	}
	return -1000;
}
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++){
		f[i][0]=1;
	}
	for(int bi=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			int d=md(i,j)-1;
		//	cout<<d<<" ";
			if(d<0){
				continue;
			}
			for(int l=d;l<=k;l++){
				f[i][l]=max(f[i][l],f[j][l-d]+d+1);
			}
		}
	}
	int nas=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++){
			nas=max(f[i][j]+(k-j),nas);
		}
	}
	cout<<nas;
	return 0;
}