https://www.nowcoder.com/acm/contest/200#question
最近突然找到了打比赛的乐趣,于是参加了这场比赛.
生日宴会:https://www.nowcoder.com/acm/contest/200/A
按照题意模拟,没什么好说的.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <string>
# define R register int using namespace std; const int maxn=;
char name[maxn][];
int n,m,dat,x,y;
struct nod
{
int val,k;
}id[][maxn];
int h[]; bool cmp (nod a,nod b)
{
return a.val<b.val;
} int main()
{
scanf("%d%d",&n,&m);
for (R i=;i<=n;++i)
{
scanf("%s",name[i]);
scanf("%d",&dat);
id[dat%][ ++h[dat%] ].k=i;
id[dat%][ h[dat%] ].val=dat/;
}
for (R i=;i<=;++i)
sort(id[i]+,id[i]++h[i],cmp);
for (R i=;i<=m;++i)
{
scanf("%d%d",&x,&y);
printf("%s\n",name[ id[y][x].k ]);
}
return ;
}
A
数据结构:https://www.nowcoder.com/acm/contest/200/B
题意概述:维护一个区间,支持区间加,区间乘,查询区间和,区间平方和.
好麻烦的题目啊,本来要写线段树的,后来觉得分块可能简单点就写了分块.事实上...并没有简单,还是要打很多标记,维护起来差不多麻烦.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <string>
# define R register int
# define ll long long using namespace std; const int maxn=;
long long x,a[maxn],s[maxn],ss[maxn],delta_a[maxn],delta_b[maxn];
int b[maxn],n,m,siz,l,r,opt,si[maxn]; ll read()
{
long long x=,f=;
char c=getchar();
while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
while (isdigit(c)) { x=(x<<)+(x<<)+(c^); c=getchar(); }
return x*f;
} void down (int x)
{
s[x]=;
ss[x]=;
for (R i=+siz*(x-);i<=min(x*siz,n);++i)
{
a[i]=a[i]*delta_a[x]+delta_b[x];
s[x]+=a[i];
ss[x]+=a[i]*a[i];
}
delta_a[x]=;
delta_b[x]=;
} long long ask1 (int l,int r)
{
long long ans=;
int id;
if(b[l]==b[r])
{
id=b[l];
down(id);
for (R i=l;i<=r;++i) ans+=a[i];
}
else
{
id=b[l];
down(id);
for (R i=l;i<=siz*b[l];++i) ans+=a[i];
for (R i=b[l]+;i<=b[r]-;++i) ans+=s[i];
id=b[l];
down(id);
for (R i=+siz*(b[r]-);i<=r;++i) ans+=a[i];
}
return ans;
} long long ask2 (int l,int r)
{
int id;
long long ans=;
if(b[l]==b[r])
{
id=b[l];
down(id);
for (R i=l;i<=r;++i) ans+=a[i]*a[i];
}
else
{
id=b[l];
down(id);
for (R i=l;i<=siz*b[l];++i) ans+=a[i]*a[i];
for (R i=b[l]+;i<=b[r]-;++i) ans+=ss[i];
id=b[l];
down(id);
for (R i=+siz*(b[r]-);i<=r;++i) ans+=a[i]*a[i];
}
return ans;
} void add (int l,int r,ll c)
{
int id;
if(b[l]==b[r])
{
id=b[l];
down(id);
for (R i=l;i<=r;++i)
{
s[id]+=c;
ss[id]+=c*c+*c*a[i];
a[i]=a[i]+c;
}
}
else
{
id=b[l];
down(id);
for (R i=l;i<=siz*b[l];++i)
{
s[id]+=c;
ss[id]+=c*c+*c+a[i];
a[i]=a[i]+c;
}
for (R i=b[l]+;i<=b[r]-;++i)
{
delta_a[i]+=c;
ss[i]+=c*c*si[i]+*c*s[i];
s[i]+=si[i]*c;
}
id=b[r];
down(id);
for (R i=+siz*(b[r]-);i<=r;++i)
{
s[id]+=c;
ss[id]+=c*c+*c+a[i];
a[i]=a[i]+c;
}
}
} void mul (int l,int r,ll c)
{
int id;
if(b[l]==b[r])
{
id=b[l];
down(id);
for (R i=l;i<=r;++i)
{
s[id]+=a[i]*(c-);
ss[id]+=(c*c-)*(a[i]*a[i]);
a[i]*=c;
}
}
else
{
id=b[l];
down(id);
for (R i=l;i<=siz*b[l];++i)
{
s[id]+=a[i]*(c-);
ss[id]+=(c*c-)*(a[i]*a[i]);
a[i]*=c;
}
for (R i=b[l]+;i<=b[r]-;++i)
{
delta_b[i]*=c;
delta_a[i]*=c;
ss[i]*=c;
s[i]*=c;
}
id=b[r];
down(id);
for (R i=+siz*(b[r]-);i<=r;++i)
{
s[id]+=a[i]*(c-);
ss[id]+=(c*c-)*(a[i]*a[i]);
a[i]*=c;
}
}
} int main()
{
scanf("%d%d",&n,&m);
for (R i=;i<=n;++i) a[i]=read();
siz=sqrt(n);
for (R i=;i<=n;++i) b[i]=(i-)/siz+;
for (R i=;i<=n;++i) s[ b[i] ]+=a[i],ss[ b[i] ]+=a[i]*a[i];
for (R i=;i<=n;++i) si[ b[i] ]=siz,delta_a[i]=;
si[ b[n] ]=n-siz*(b[n]-);
for (R i=;i<=m;++i)
{
scanf("%d",&opt);
if(opt==||opt==)
{
scanf("%d%d",&l,&r);
if(opt==) printf("%lld\n",ask1(l,r));
else printf("%lld\n",ask2(l,r));
}
else
{
scanf("%d%d%lld",&l,&r,&x);
if(opt==) mul(l,r,x);
else add(l,r,x);
}
}
return ;
}
B
迎风舞:https://www.nowcoder.com/acm/contest/200/E
题意概述:物理题.
三分抛出方向与水平方向的夹角,解方程算出时间和落地时间即可.关于这个函数为什么是单峰的,这里提供一个不严谨的证明:首先直觉上平抛肯定是比不上上抛的,但是角度为$90$度的上抛运动等于没有抛出去,所以函数应该是满足三分性的.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <string>
# define R register int using namespace std; const double g=9.80665;
const double eps=0.000001;
double h,v,l,r,lmid,rmid,ans,lans;
int T; double f (double si)
{
double vx,vy,a,b,c,delta,x1,x2,t;
vy=v*si;
vx=sqrt(v*v-vy*vy);
a=-g/2.0;
b=vy;
c=h;
delta=sqrt(b*b-4.0*a*c); x1=(-b+delta)/(*a);
x2=(-b-delta)/(*a); t=max(x1,x2);
return t*vx;
} int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%lf%lf",&h,&v);
l=,r=;
while (r-l>eps)
{
lmid=l+(r-l)/3.0;
rmid=r-(r-l)/3.0;
if(f(lmid)<f(rmid))
l=lmid;
else r=rmid;
}
printf("%.5lf\n",f(l));
}
return ;
}
E
------------------比赛时就做到这里了,以下是赛后补题------------------
随风飘:https://www.nowcoder.com/acm/contest/200/D
题意概述:给定$n$个字符串,求它们两两之间的$LCP$的长度和,此外给出$T$组询问$k$,表示有$k$个字符串消失了,求所有的消失情况下$LCP$的长度和的和.
其实考试时本来是有机会$A$的,但是都以为开不下存字符串的数组导致纷纷弃疗.开数组靠的是信仰...其实当时为什么不开一个$vector$呢,果然考试时智商会降低.
首先把字符串都串到$Trie$树上去,统计$k=0$时的答案.对于其他的询问就不能再上树了!要考虑运用组合数学.每个$LCP$有$C_{n-2}^k$种方法留下来,直接算就好了.
# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <string>
# define R register int
# define ll long long
# define mod using namespace std; const int maxs=;
int k,n,q,len,cnt=,c[][];
char s[maxs]; struct Trie
{
int ch[maxs][];
int vis[maxs],s[maxs];
long long ans;
void clear()
{
ans=;
memset(ch,,sizeof(ch));
memset(vis,,sizeof(vis));
memset(s,,sizeof(s));
}
void ins (char *s)
{
int len=strlen(s);
int x=;
for (R i=;i<len;++i)
{
int c=s[i]-'a';
if(!ch[x][c])
ch[x][c]=++cnt;
x=ch[x][c];
}
ans=(ans+vis[x]*len)%mod;
vis[x]++;
}
void upd (int x,int dep)
{
s[x]=vis[x];
for (R i=;i<;++i)
if(ch[x][i])
{
upd(ch[x][i],dep+);
ans=(ans+1LL*dep*s[x]%mod*(s[ ch[x][i] ]))%mod;
s[x]+=s[ ch[x][i] ];
}
}
}T; int main()
{
scanf("%d%d",&n,&q);
for (R i=;i<=n;++i)
{
scanf("%s",s);
T.ins(s);
}
T.upd(,);
c[][]=;
for (R i=;i<=n;++i)
{
c[i][]=;
for (R j=;j<=min(i,);++j)
c[i][j]=(c[i-][j]+c[i-][j-])%mod;
}
for (R i=;i<=q;++i)
{
scanf("%d",&k);
printf("%lld\n",1LL*c[n-][k]*T.ans%mod);
}
return ;
}
D