T1 乘方
方法 \(1\)：使用快速幂，判断答案是否 \(\geq 10^9\)。
方法 \(2\)：特判 \(1\) 的情况，其余的可以直接乘。
此处给出方法 \(2\) 的代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
int main(){
cin>>a>>b;
if(a==1) cout<<1;
else{
ll res=1;
for(int i=1;i<=b;i++){
res*=a;
if(res>1e9){cout<<-1;return 0;}
}
cout<<res;
}
return 0;
}
T2 解密
思路：
记 \(m_i=n_i-e_i \times d_i +2\)。
根据已知信息，可以推出 \(p_i \times q_i=n_i\)，\(p_i+q_i=n_i-e_i \times d_i+2=m_i\)。
而 \(n_i,e_i,d_i\) 均为已知数，因此本题转换为：
已知 \(p_i+q_i=m_i\)，\(p_i \times q_i=n_i\)，求 \(p_i,q_i\)。
\(p_i-q_i=\sqrt{(p_i+q_i)^2-4 \times p_i \times q_i}=\sqrt{{m_i}^2-4n_i}\)
\({p_i}^2-{q_i}^2=(p_i+q_i)(p_i-q_i)=m_i \times \sqrt{{m_i}^2-4n_i}\)
\({p_i}^2+{q_i}^2=({p_i}+q_i)^2-2p_iq_i={m_i}^2-2n_i\)
\(\therefore 2{p_i}^2=m \times \sqrt{{m_i}^2-4n_i}+{m_i}^2-2n_i\)
\({p_i}^2=\frac{m \times \sqrt{{m_i}^2-4n_i}+{m_i}^2-2n_i}{2}\)
\({p_i}=\sqrt{\frac{m \times \sqrt{{m_i}^2-4n_i}+{m_i}^2-2n_i}{2}}\)
\(p_i=\frac{\sqrt{2m_i \times \sqrt{{m_i}^2-4n_i}+2{m_i}^2-4n_i}}{2}\)
注意到 \(2m_i \times \sqrt{{m_i}^2-4n_i}+2{m_i}^2-4n_i\) 是个完全平方公式。
继续化简得 \(p_i=\frac{m_i+\sqrt{{m_i}^2-4n_i}}{2}\)
\(q_i=m_i-p_i=m_i-\frac{m_i+\sqrt{{m_i}^2-4n_i}}{2}=\frac{m_i-\sqrt{{m_i}^2-4n_i}}{2}\)
综上，
\(
\begin{cases}
p_i=\frac{m_i+\sqrt{{m_i}^2-4n_i}}{2}\\
q_i=\frac{m_i-\sqrt{{m_i}^2-4n_i}}{2}
\end{cases}
\)
注意如果 \(p_i\) 比 \(q_i\) 大则交换 \(p_i,q_i\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
ll k,n,d,e;
int main(){
cin>>k;
for(int i=1;i<=k;i++){
cin>>n>>d>>e;
ll m=n-e*d+2;
ll tmp1=m*m-4*n;
if(tmp1<0){
cout<<"NO"<<endl;
continue;
}
ll p=(m+sqrt(tmp1))/2;
ll q=m-p;
if(p>q) swap(p,q);
if(p*q==n&&p>0) cout<<p<<" "<<q<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
根据这道题，还可以得出一个普遍的结论：
已知 \(a+b=n,a \times b=m\)，
则
\(\begin{cases}
a=\frac{n+\sqrt{n^2-4m}}{2}\\
b=\frac{n-\sqrt{n^2-4m}}{2}
\end{cases}
\)
T3 逻辑表达式
考场上没有考虑到优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
string str;
int ch1[200009],ch2[200009],t1[200009],t2[200009],ans1,ans2,ans;
int solve(int l,int r){
if(l==r) return (str[l]-'0');
if(ch2[r]>=l){
int anst=solve(l,ch2[r]-1);
if(anst==1){
ans2++;
return 1;
}
else return solve(ch2[r]+1,r);
}
else if(ch1[r]>=l){
int anst=solve(l,ch1[r]-1);
if(anst==0){
ans1++;
return 0;
}
else return solve(ch1[r]+1,r);
}
else return solve(l+1,r-1);
}
int main(){
cin>>str;
for(int i=0;i<str.size();i++) ch1[i]=ch2[i]=t1[i]=t2[i]=-1;
int flr=0;
for(int i=0;i<str.size();i++){
if(str[i]=='(') flr++;
if(str[i]==')') flr--;
if(str[i]=='&') t1[flr]=i;
if(str[i]=='|') t2[flr]=i;
ch1[i]=t1[flr];
ch2[i]=t2[flr];
}
ans=solve(0,str.size()-1);
cout<<ans<<endl<<ans1<<" "<<ans2<<endl;
return 0;
}
T4 上升点列
我是傻逼。
我把 \(x\) 写成 \(y\) 了。
每个大样例都过了。
\(100pts \to 65pts\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct star{
ll x,y;
};
ll n,k,f[509][109];
star s[509];
bool cmp(const star&a,const star&b){
return a.x<b.x||a.x==b.x&&a.y<=b.y;
}
int main(){
cin>>n>>k;
for(ll i=1;i<=n;i++){
cin>>s[i].x>>s[i].y;
}
sort(s+1,s+1+n,cmp);
ll ans=0;
for(ll i=1;i<=n;i++){
f[i][k]=1;
for(ll j=1;j<i;j++){
if(s[j].x>s[i].x||s[j].y>s[i].y) continue;
ll dis=abs(s[i].x-s[j].x)+abs(s[i].y-s[j].y)-1;
for(ll l=0;l+dis<=k;l++){
if(f[j][l+dis]){
f[i][l]=max(f[i][l],f[j][l+dis]+dis+1);
}
}
}
}
for(ll i=1;i<=n;i++){
for(ll j=0;j<=k;j++){
ans=max(ans,f[i][j]+j);
}
}
cout<<ans;
return 0;
}