每日作者附：第二题也太难了吧 是第二题的难度吗(╬▔皿▔)╯
T1乘方（暴力）
总结（自己）
老师让写思路（虽然本来就要自主写）balabala写了一堆 主要就几点
思路
- 开long long
- a=1要特判
- 循环不会超时 不用快速幂
附Ac代码：
#include<bits/stdc++.h>
using namespace std;
long long ans=1,a,b;
void fropn(string a){
string t1=a+".in",t2=a+".out";
freopen(t1.c_str(),"r",stdin);
freopen(t2.c_str(),"w",stdout);
}
int main()
{
fropn("cf");
cin>>a>>b;
if(a==1){
cout<<1;
return 0;
}
for(int i=1;i<=b;i++){
ans*=a;
if(ans>1e9){
cout<<-1;
return 0;
}
}
if(ans>1e9){
cout<<-1;
return 0;
}
cout<<ans;
return 0;
}
T2解密（数学）
总结（自己）
二分算法本来能写出来的 但模板错了（这么短还能忘）所以复习吧(＠_＠;)
思路
数学解法：
$$(p+q)^2=p^2+q^2+2pq \\ (p-q)^2=p^2+q^2-2pq \\ (p+q)^2-4pq=p^2+q^2-2pq \\ m^2-4n=(p-q)^2 \\ sqrt(m^2-4n)=p-q=t \\ p=(m-t)/2 \\ q=(m+t)/2$$附Ac代码
#include<bits/stdc++.h>
using namespace std;
long long n,p,q,e,d,m;
void fropn(string a){
string t1=a+".in",t2=a+".out";
freopen(t1.c_str(),"r",stdin);
freopen(t2.c_str(),"w",stdout);
}
int main()
{
fropn("decode");
int h;
cin>>h;
while(h--){
cin>>n>>d>>e;
long long m=n-e*d+2;
long long t=sqrt(m*m-4*n);
if(m*m-4*n!=t*t){
cout<<"NO"<<endl;
}
else{
cout<<(m-t)/2<<" "<<(m+t)/2<<endl;
}
}
return 0;
}
小彩蛋：
(╯‵□′)╯💣(￣ー￣*|||
me···················墨
T3逻辑表达式（树）
总结（自己）
做了50分 剩下的考试也没想到（就没把表达式求值往树上靠）
思路
建一个表达式树 再dfs便利 顺便判断短路即可
附Ac代码：
#include<bits/stdc++.h>
using namespace std;
stack<int> a;
stack<char> f;
unordered_map<char,int> yx{{'|',1},{'&',2}};
string n;
int l[1000100],idx,hd,yd,r[1000100];
char w[1000010];
void js()
{
int s2=a.top();
a.pop();
int s1=a.top();
a.pop();
char fh=f.top();
f.pop();
w[++idx]=fh;
l[idx]=s1;
r[idx]=s2;
a.push(idx);
}
void fropn(string a){
string t1=a+".in",t2=a+".out";
freopen(t1.c_str(),"r",stdin);
freopen(t2.c_str(),"w",stdout);
}
int dfs(int d)
{
if(w[d]=='0') return 0;
if(w[d]=='1') return 1;
int ll=dfs(l[d]);
if(w[d]=='|'){
if(ll==1){
hd++;
return 1;
}
return dfs(r[d]);
}
else{
if(ll==0){
yd++;
return 0;
}
return dfs(r[d]);
}
}
int main()
{
fropn("expr");
cin>>n;
for(int i=0;i<n.size();i++){
char c=n[i];
if(c=='1'||c=='0'){
w[++idx]=c;
a.push(idx);
}
else if(c=='(') f.push(c);
else if(c==')'){
// for(int ii=1;ii<=tt;ii++){
// cout<<f[ii]<<" ";
// }
// cout<<endl;
while(f.top()!='(') js();
f.pop();
}
else
{
while(f.size()&&f.top()!='('&&yx[c]<=yx[f.top()]) js();
f.push(c);
}
}
while(f.size()) js();
cout<<dfs(idx);
cout<<endl<<yd<<" "<<hd;
return 0;
}
T4[上升点列](dp)
总结（自己）
输样例错了
思路
dp三要素：
f[i][j]定义:前i个点用j个自由点的方案取max
初始化：f[i][j]=0
递推式：f[i][l]=max(f[i][l],f[j][l-d]+d+1);
附Ac代码：
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int f[510][110],n,k;
pair<int,int> a[510];
int mhd(int i,int j)
{
return abs(a[i].first-a[j].first)+abs(a[i].second-a[j].second);
}
void fropn(string a){
string t1=a+".in",t2=a+".out";
freopen(t1.c_str(),"r",stdin);
freopen(t2.c_str(),"w",stdout);
}
int main()
{
fropn("point");
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].first>>a[i].second;
}
for(int i=1;i<=n;i++){
f[i][0]=1;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
int d=mhd(i,j)-1;
if(a[i].y-a[j].y<0) continue;
for(int l=d;l<=k;l++){
f[i][l]=max(f[i][l],f[j][l-d]+d+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
ans=max(f[i][j]+k-j,ans);
}
}
cout<<ans;
return 0;
}
