$T1$

考试错误：无。

思路：

暴力！！！

代码：

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

$T2$

考试错误：不知道（用二分写的，不知道咋的就错了）。

思路：

$∵n=pq$

$∵ed=(p-1)(q-1)+1$

$∴(p-1)(q-1)=q(p-1)-(p-1)=pq-q-(p-1)=pq-q-p+1$

$∴ed=(p-1)(q-1)+1=pq-q-p+1+1=pq-(q+p-2)$

$∴n-ed=pq-[pq-(q+p-2)]=pq-pq+(q+p-2)=q+p-2$

$∴n-ed+2=q+p$

设 $m=n-ed+2=q+p;$

$∵n=pq$

$∵m=p+q$

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

$∴m^2-4pq=p^2-2pq+q^2=(p-q)^2$

设 $t=\sqrt{m^2-4pq}=\sqrt{m^2-4n}=\sqrt{(p-q)^2}=p-q$

$∵p-q=t$

$∵p+q=m$

$∴(m+t) \div 2=(p-q+p+q)\div 2=2p\div 2=p$

$∴(m-t)\div 2=[p+q-(p-q)]\div 2=(p+q-p+q)\div 2=2q\div 2=q$

总结：

$p=n-ed+2+\sqrt{(n-ed+2)^2-4n}$

$q=n-ed+2-\sqrt{(n-ed+2)^2-4n}$

代码：

#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,e,d,m;
		cin >> n >> e >> d;
		m=n-e*d+2;
		int t=sqrt(m*m-4*n);
		if(t*t==m*m-4*n){
			cout << (m-t)/2 << " " << (m+t)/2 << endl;
		}else{
			cout << "NO\n";
		}
	}
}

$T3$

考试错误：只是单纯的去算表达式的值，没有用语法树，导致只拿了$40$.

思路：用语法树出结果，求的途中，顺便可以计算一下短路。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
stack<int> num;
stack<char> jc;
const int N=1e6+50;
int l[N],r[N];
char w[N];
unordered_map<char,int> mp={{'&',2},{'|',1}};
int idx=1;
string s;
int yu,huo;
bool pd(char s){
	return s>='0'&&s<='9';
}
int dfs(int u){
	if(pd(w[u])){
		return bool(w[u]-'0');
	}
	if(w[u]=='|'){
		if(dfs(l[u])==1){
			huo++;
			return 1;
		}else{
			return dfs(r[u]);
		}
	}if(w[u]=='&'){
		if(dfs(l[u])==0){
			yu++;
			return 0;
		}else{
			return dfs(r[u]);
		}
	}
}
void JS(){
	int b=num.top();
	num.pop();
	int a=num.top();
	num.pop();
	w[++idx]=jc.top();
	jc.pop();
	l[idx]=a;
	r[idx]=b;
	num.push(idx);
}
void solve(){
    for(int i=0;i<s.size();i++){
        char c=s[i];
        if(isdigit(c)){
        	w[++idx]=c;
        	num.push(idx);
        }else if(c=='('){
            jc.push(c);
        }else if(c==')'){
            while(jc.top()!='(') JS();
			jc.pop();
        }else{
            while(jc.size()&&jc.top()!='('&& mp[jc.top()]>=mp[c])
				JS();
			jc.push(c);
        }
    }while(jc.size()) JS();
    int ans=dfs(idx);
    cout << ans << endl << yu << " " << huo;
}
signed main(){
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	getline(cin,s);
	solve();
}

$T4$

考试错误：无，没做。

**₯**思路：

状态表示：$f[i][j]$:用前$i$个点，增加$j$次的最长序列。

初始化：$f[i(1...n)][0]=1$

状态计算：

$1$.$int$ $d=i$和$j$的曼哈顿距离

$2$.$f[i(1...n)][l(d...k)]=max(f[i][l],f[j][l-d]+d+1)$

答案：$\max\{f[i(1..n)][j(1...k)]+k-j\}$

代码：

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=555;
int f[N][N];
pair<int,int> a[N];
int n,k;
int md(int p,int q){
	return abs(a[p].x-a[q].x)+abs(a[p].y-a[q].y);
}
int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
    cin >> n >> k;
    for(int i=1;i<=n;i++){
    	f[i][0]=1;
	}
    for(int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++){
        	int d=md(i,j)-1;
        	for(int l=d;l<=k;l++){
        		if(a[i].x<a[j].x||a[i].y<a[j].y){
        			continue;
				}else{
					f[i][l]=max(f[i][l],f[j][l-d]+d+1);
				}
            }
        }
    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;
}