题目传送门

A 乘方

B 解密

C 逻辑表达式

D 上升点列

T1乘方

思路

直接按题目的来，但a==1要特判

代码

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

T2解密

思路

1. 题目中的m=q+p,我们要求q-p
2. n=$q \times p$,$n^2=q^2+p^2$$=q^2+2(q+p)$
3. 设q-p为z
4. $z^2=$$q^2+p^2$$-2(q+p)$
5. 4(q+p)=4m
6. $(p+q)^2−4n=p^2−2×p×q+q^2$
7. $^(p−q)^2=p^2−2×p×q+q^2$
8. $m^2-4n=(p-q)^2=z^2$
9. $z=sqrt(m^2-4n)$
10. (m+t)/2=p
11. (m−t)/2=q

    代码

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

错误与感想

考试时好多时间都花在这上面了，以后要均匀分配时间

T3 逻辑表达式

思路

直接用表达式求值写，注意要建树用搜索求短路

代码

#include<bits/stdc++.h>
using namespace std;
int idx=1,l[1111111],r[1111111];
char w[1111111];
int hg,yg;
unordered_map<char,int>rr{{'|',1},{'&',2}};
stack<int> n;
stack<char> p;
void e() {
	int b=n.top(),x;n.pop();
	int a=n.top();n.pop();
	char c=p.top();p.pop();
	w[++idx]=c;
	l[idx]=a;
	r[idx]=b;
	n.push(idx);
}
int dfs(int d){
	if(d==0)return 0;	
	if(w[d]=='0'||w[d]=='1')return w[d]-'0';
	else if(w[d]=='&'){
		if(dfs(l[d])==0){yg++;return 0;}
		else return dfs(r[d]);
	}
	else{
		if(dfs(l[d])==1){hg++;return 1;}
		else return dfs(r[d]);
	}
}
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)) {
			n.push(++idx);
			w[idx]=s[i];
		}
		else if(c=='(')p.push(c);
		else if(c==')'){
			while(p.top()!='(')e();
			p.pop();
		}
		else {
			while(p.size()&&p.top()!='('&&rr[c]<=rr[p.top()])e();
			p.push(c);
		}
	}
	while(p.size())e();
	cout<<dfs(idx)<<"\n";
	cout<<yg<<' '<<hg<<"\n";
}

错误与感想

没做，以后要挑战一下这类题 ，多积分

T4上升点列

思路

for(i:2~n)
     for(j:1~i-1)
         //求曼哈顿距离-1(x)
         //并判断
         for(l:x~k)
              f[i][l]=max(f[i][l],f[j][l-d]+d+1);

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,f[555][111],m=0;
struct P{
	int x,y;
}a[5555];
bool cmp(P a,P b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		f[i][0]=1;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			int d=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)-1;
			if(a[j].x>a[i].x||a[j].y>a[i].y)continue;
			if(d>k)continue;
			for(int l=d;l<=k;l++)f[i][l]=max(f[i][l],f[j][l-d]+d+1);
		}
	}
	for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)m=max(f[i][j]+(k-j),m);
	cout<<m;
}

错误与感想

没写，但补了后发现还可以在能力范围内，以后要多多思考