@KirinBill
2017-10-19T21:33:31.000000Z
字数 5058
阅读 1195
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
#include <cstring>
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=1e5+5;
int n,tot;
int he[MAXN],p[MAXN],id[MAXN],ans[MAXN];
struct line{int to,nex;}ed[MAXN];
class BIT{
private:
int c[MAXN];
int lowbit(int x){return x&-x;}
int qry(int r){
int ret=0;
for(;r;r-=lowbit(r))
ret+=c[r];
return ret;
}
public:
void add(int l){
for(;l<=tot;l+=lowbit(l))
++c[l];
}
int gsum(int l){return qry(tot)-qry(l);}
}ta;
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
inline void decrete(){
static int tmp[MAXN];
memcpy(tmp,p,sizeof(tmp));
sort(tmp+1,tmp+n+1);
tot=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;++i)
id[i]=lower_bound(tmp+1,tmp+tot+1,p[i])-tmp;
}
void DFS(int u){
int pre=ta.gsum(id[u]);
for(int i=he[u];i;i=ed[i].nex)
DFS(ed[i].to);
ans[u]=ta.gsum(id[u])-pre;
ta.add(id[u]);
}
int main(){
#ifdef DEBUG
setIO("a");
#endif
read(n);
for(int i=1;i<=n;++i)
read(p[i]);
decrete();
for(int i=2,fa;i<=n;++i){
read(fa);
addE(fa,i);
}
DFS(1);
for(int i=1;i<=n;++i)
write(ans[i],'\n');
return 0;
}
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
#include <cmath>
using std::ceil;
using std::min;
using std::sqrt;
const int MAXN=1e5+5;
const double EPS=1e-12;
int n;
long long k;
long long a[MAXN];
inline bool jud(double lim){
long long rest=k,c;
for(int i=1;i<=n;++i){
//lim*c^2+lim*c=a
//c=ceil(-lim+sqrt(lim*lim+4*lim)/2/lim);
c=ceil((-1+sqrt(1+4*a[i]/lim))/2);
rest-=c;
if(rest<0) return false;
}
return true;
}
inline long long bin_chop(){
double l=1e-12,r=1e12,mid;
while(r-l>EPS){
mid=(l+r)/2;
if(jud(mid)) r=mid;
else l=mid;
}
mid=(l+r)/2;
double ret=0;
long long c,sum=0;
for(int i=1;i<=n;++i){
c=ceil((-1+sqrt(1+4*a[i]/mid))/2);
ret+=(double)a[i]/c,sum+=c;
}
ret-=mid*(k-sum);
return (long long)(ret+0.5);
}
int main(){
#ifdef DEBUG
setIO("b");
#endif
read(n),read(k);
for(int i=1;i<=n;++i)
read(a[i]);
write(bin_chop());
return 0;
}
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=55;
int n;
int a[MAXN];
inline int DP(){
//val in l~r,range is i~j
static int dp[MAXN][MAXN][MAXN][MAXN];
for(int i=1;i<=n;++i){
for(int l=1;l<=a[i];++l){
for(int r=a[i];r<=50;++r)
dp[l][r][i][i]=1;
}
}
for(int len=2;len<=n;++len){
for(int i=1,j;n-i+1>=len;++i){
j=i+len-1;
for(int rge=1;rge<=50;++rge){
for(int l=1,r;50-l+1>=rge;++l){
r=l+rge-1;
dp[l][r][i][j]=max(dp[l+1][r][i][j],dp[l][r-1][i][j]);
dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j]+(a[i]==l));
dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i][j-1]+(a[j]==r));
dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j-1]+(a[i]==r)+(a[j]==l));
}
}
}
}
return dp[1][50][1][n];
}
int main(){
#ifdef DEBUG
setIO("c");
#endif
read(n);
for(int i=1;i<=n;++i)
read(a[i]);
write(DP());
return 0;
}