8月集训 DAY13
乘方
错误原因
res没开longlong
思路
直接快速幂 res超过1e9或a>1e9&&b>1 输出-1 否则 输出res
#include<bits/stdc++.h>
using namespace std;
long long qim(long long a,long long b)
{
long long res=1;
while(b)
{
if(b%2==1) res=res*a;
a=a*a;
b=b/2;
if(res>1e9||(a>1e9&&b>1))
{
return -1;
}
}
return res;
}
int main()
{
freopen("cf.in","r",stdin);
freopen("cf.out","w",stdout);
long long a,b,z;
cin>>a>>b;
z=qim(a,b);
cout<<z;
}
解密
错误原因
二分写错了
思路
推公式 见下图
$$n=p\times q \\ e\times d=(p-1)\times (q-1)+1=p\times q-(p+q)+2 \\ n-e\times d=p\times q-p\times q+p+q-2 \\ n-e*d+2=p\times q-p\times q+p+q=p+q \\ m=p+q \\ (p+q)^2=p^2+2\times p\times q+q^2 \\ (p-q)^2=p^2-2\times p\times q+q^2 \\ (p+q)^2-4\times =p^2-2\times p\times q+q^2 \\ (p-q)^2=p^2-2\times p\times q+q^2 \\ m^2-4\times =(p-q)^2 \\ sqrt(m^2-4\times )=p-q \\ sqrt(m^2-4n)=p-q \\ t=p-q \\ (m+t)/2=p \\ (m-t)/2=q$$代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("decode.in","r",stdin);
freopen("decode.out","w",stdout);
long long k,n,e,d,m,t;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>n>>e>>d;
m=n-e*d+2;
t=sqrt(m*m-4*n);
if(t*t!=m*m-4*n) cout<<"NO"<<endl;
else cout<<(m-t)/2<<" "<<(m+t)/2<<endl;
}
}
逻辑表达式
错误原因
只去骗长度为三和五时的分 没去想正解
思路
代码
#include<bits/stdc++.h>
using namespace std;
int l[1000010],r[1000010],hd,yd,idx;
char w[1000010];
stack<char> op;
stack<int> num;
map<char,int> mp={{'&',2},{'|',1}};
void yx()
{
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 u)
{
if(w[u]=='0') return 0;
if(w[u]=='1') return 1;
if(w[u]=='&')
{
if(dfs(l[u])==0)
{
hd++;
return 0;
}
else return dfs(r[u]);
}
else
{
if(dfs(l[u])==1)
{
yd++;
return 1;
}
else return dfs(r[u]);
}
}
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
char ch=s[i];
if(ch>='0'&&ch<='1')
{
w[++idx]=ch;
num.push(idx);
}
else if(ch=='(') op.push(ch);
else if(ch==')')
{
while(op.top()!='(') yx();
op.pop();
}
else
{
while(op.size()&&mp[ch]<=mp[op.top()]) yx();
op.push(ch);
}
}
while(op.size()) yx();
cout<<dfs(idx)<<endl;
cout<<hd<<" "<<yd;
}
上升点列
错误原因
想到了40分的最长上升子序列 但没写对
思路
状态表示 代表 第个点放个点的最长符合条件的序列
状态计算: d是曼哈顿距离
l是放的点的个数
代码
#include<bits/stdc++.h>
using namespace std;
int f[510][110],mx;
struct zb
{
int x;
int y;
};
bool cmp(zb a,zb b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
zb xy[510];
int md(int i,int j)
{
return xy[i].x-xy[j].x+xy[i].y-xy[j].y-1;
}
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>>xy[i].x>>xy[i].y;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
f[i][j]=1;
}
}
sort(xy+1,xy+n+1,cmp);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if((xy[i].x<xy[j].x||xy[i].y<xy[j].y)||md(i,j)>k) continue;
int d=md(i,j);
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++)
{
mx=max(mx,f[i][j]+k-j);
}
}
cout<<mx;
}
