A. 乘方

题目类型：数学

思路

对于这道题目我们直接按照题目要求来的就行，只不过有一点要注意，那就是当$a=1$时，要输出$1$。

代码

#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;
    else{
    	long long sum=0;
    	sum=a;
    	for(int i=2;i<=b;i++){   
    		sum*=a; 
	   		if(sum>1e9){
    			cout<<-1;
    			return 0;
			}
		}
		cout<<sum;
	}
	return 0;
}

本题已AC，下一次还需要继续努力。

B. 解密

题目类型：数学

思路

最开始想时应该大家都想到了用暴力来写，但是会超时，所以要推公式。不知道大家有没有注意到，这个$m$在题目中的出现有点蹊跷，我们将$m$的公式化简，就会得到这么一个公式： （注意：以下式子$p$为$q$，$q$为$p$）

$$m=p×q−(p+q)+2$$

我们再将这个式子位移一下，就将得到下面这个式子：

$$m=p×q−p×q+p+q$$

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

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

平方差公式为：

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

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

$$m^2−4n=p^2−2×p×q+q^2$$

平方差公式为：

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

所以公式就是：

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

再加上$sqrt$就是：

$$t=sqrt(m^2−4n)$$

所以答案就是：

$$p=(m+t)/2,q=(m−t)/2$$

注意，因为有小数的情况，所以还要加上以下代码：

if(t*t!=m*m-4*n) cout<<"NO"<<endl;

代码

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

对于这道题目在考试的时候我写的代码是暴力代码，所以没AC，下一次要想一想AC的写法。

C. 逻辑表达式

题目类型：数学

思路

对于这道题目我们首先可以想到直接用栈求出值，再暴力，求出短路的值，但是会超时，所以要换一种思路。我们不妨创建一个树，如果一个符号节点左子树的值为 $1$，那么构成一个短路，或运算亦同。那怎么求解呢？我们就可以用搜索来求解（注意：此时的搜索为深搜）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int l[N],r[N],cnt_0,cnt_1,idx=1;
char w[N];
stack<int> num;
stack<char> op;
unordered_map<char,int> mp{{'|',1},{'&',2}};
void eval(){
	int b=num.top();
	num.pop();
	int a=num.top();
	num.pop();
	char c=op.top();
	op.pop();
	w[++idx]=c;
	l[idx]=a;
	r[idx]=b;
	num.push(idx);
}
int dfs(int idx){
	if(idx==0)return 0;	
	if(w[idx]=='0'||w[idx]=='1') return w[idx]-'0';
	else if(w[idx]=='|'){
		if(dfs(l[idx])==1){
		    cnt_1++;
			return 1;
		}
		else return dfs(r[idx]);
	}
	else {
		if(dfs(l[idx])==0){
		    cnt_0++;
			return 0;
		}
		else return dfs(r[idx]);
	}
}
int main(){
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		auto c=s[i];
		if(isdigit(c)){
			num.push(++idx);
			w[idx]=c;
		}
		else if(c=='(') op.push(c);
		else if(c==')'){
			while(op.top()!='(') eval();
			op.pop();
		}
		else{
			while(op.size()&&op.top()!='('&&mp[c]<=mp[op.top()]) eval();
			op.push(c);
		}
	}
	while(op.size()) eval();
	cout<<dfs(idx)<<endl;
	cout<<cnt_0<<" "<<cnt_1;
	return 0;
}

这道题目在考试的时候我写的代码是暴力解法，得了$15$分，所以没AC，下一次要想一想AC的写法。

D. 上升点列

题目类型：DP

思路

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

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

代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int> a[510];
int dp[510][110];
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;
		dp[i][0]=1;
	}
	sort(a+1,a+1+n);
	for(int i=2;i<=n;i++)
		for(int j=1;j<=i-1;j++){
			int mhd=abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second)-1;
			if(mhd>k||a[j].first>a[i].first||a[j].second>a[i].second) continue;
			else for(int t=mhd;t<=k;t++) dp[i][t]=max(dp[i][t],dp[j][t-mhd]+(mhd+1));
		}
	int ans=0;
	for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) ans=max(ans,dp[i][j]+k-j);
	cout<<ans; 
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。