nowcoder练习赛28

　　https://www.nowcoder.com/acm/contest/200#question

　　最近突然找到了打比赛的乐趣,于是参加了这场比赛.

　　生日宴会:https://www.nowcoder.com/acm/contest/200/A

　　按照题意模拟,没什么好说的.

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <cmath>
 5 # include <algorithm>
 6 # include <string>
 7 # define R register int
 8 
 9 using namespace std;
10 
11 const int maxn=1005;
12 char name[maxn][13];
13 int n,m,dat,x,y;
14 struct nod
15 {
16     int val,k;
17 }id[1240][maxn];
18 int h[1240];
19 
20 bool cmp (nod a,nod b)
21 {
22     return a.val<b.val;
23 }
24 
25 int main()
26 {
27     scanf("%d%d",&n,&m);
28     for (R i=1;i<=n;++i)
29     {
30         scanf("%s",name[i]);
31         scanf("%d",&dat);
32         id[dat%10000][ ++h[dat%10000] ].k=i;
33         id[dat%10000][ h[dat%10000] ].val=dat/10000;
34     }
35     for (R i=0;i<=1231;++i)
36         sort(id[i]+1,id[i]+1+h[i],cmp);
37     for (R i=1;i<=m;++i)
38     {
39         scanf("%d%d",&x,&y);
40         printf("%s
",name[ id[y][x].k ]);    
41     }
42     return 0;
43 }

　　数据结构:https://www.nowcoder.com/acm/contest/200/B

　　题意概述:维护一个区间,支持区间加,区间乘,查询区间和,区间平方和.

　　好麻烦的题目啊,本来要写线段树的,后来觉得分块可能简单点就写了分块.事实上...并没有简单,还是要打很多标记,维护起来差不多麻烦.

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # include <cmath>
  5 # include <algorithm>
  6 # include <string>
  7 # define R register int
  8 # define ll long long
  9 
 10 using namespace std;
 11 
 12 const int maxn=10004;
 13 long long x,a[maxn],s[maxn],ss[maxn],delta_a[maxn],delta_b[maxn];
 14 int b[maxn],n,m,siz,l,r,opt,si[maxn];
 15 
 16 ll read()
 17 {
 18     long long x=0,f=1;
 19     char c=getchar();
 20     while (!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
 21     while (isdigit(c)) { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
 22     return x*f;
 23 }
 24 
 25 void down (int x)
 26 {
 27     s[x]=0;
 28     ss[x]=0;
 29     for (R i=1+siz*(x-1);i<=min(x*siz,n);++i)
 30     {
 31         a[i]=a[i]*delta_a[x]+delta_b[x];
 32         s[x]+=a[i];
 33         ss[x]+=a[i]*a[i];
 34     }
 35     delta_a[x]=1;
 36     delta_b[x]=0;
 37 }
 38 
 39 long long ask1 (int l,int r)
 40 {
 41     long long ans=0;
 42     int id;
 43     if(b[l]==b[r])
 44     {
 45         id=b[l];
 46         down(id);
 47         for (R i=l;i<=r;++i) ans+=a[i];
 48     }
 49     else
 50     {
 51         id=b[l];
 52         down(id);
 53         for (R i=l;i<=siz*b[l];++i) ans+=a[i];
 54         for (R i=b[l]+1;i<=b[r]-1;++i) ans+=s[i];
 55         id=b[l];
 56         down(id);
 57         for (R i=1+siz*(b[r]-1);i<=r;++i) ans+=a[i];
 58     }
 59     return ans;
 60 }
 61 
 62 long long ask2 (int l,int r)
 63 {
 64     int id;
 65     long long ans=0;
 66     if(b[l]==b[r])
 67     {
 68         id=b[l];
 69         down(id);
 70         for (R i=l;i<=r;++i) ans+=a[i]*a[i];
 71     }
 72     else
 73     {
 74         id=b[l];
 75         down(id);
 76         for (R i=l;i<=siz*b[l];++i) ans+=a[i]*a[i];
 77         for (R i=b[l]+1;i<=b[r]-1;++i) ans+=ss[i];
 78         id=b[l];
 79         down(id);
 80         for (R i=1+siz*(b[r]-1);i<=r;++i) ans+=a[i]*a[i];
 81     }
 82     return ans;
 83 }
 84 
 85 void add (int l,int r,ll c)
 86 {
 87     int id;
 88     if(b[l]==b[r])
 89     {
 90         id=b[l];
 91         down(id);
 92         for (R i=l;i<=r;++i)
 93         {
 94             s[id]+=c;
 95             ss[id]+=c*c+2*c*a[i];
 96             a[i]=a[i]+c;
 97         }
 98     }
 99     else
100     {
101         id=b[l];
102         down(id);
103         for (R i=l;i<=siz*b[l];++i)
104         {
105             s[id]+=c;
106             ss[id]+=c*c+2*c+a[i];
107             a[i]=a[i]+c;
108         }
109         for (R i=b[l]+1;i<=b[r]-1;++i)
110         {
111             delta_a[i]+=c;
112             ss[i]+=c*c*si[i]+2*c*s[i];
113             s[i]+=si[i]*c;
114         }
115         id=b[r];
116         down(id);
117         for (R i=1+siz*(b[r]-1);i<=r;++i)
118         {
119             s[id]+=c;
120             ss[id]+=c*c+2*c+a[i];
121             a[i]=a[i]+c;
122         }
123     }    
124 }
125 
126 void mul (int l,int r,ll c)
127 {
128     int id;
129     if(b[l]==b[r])
130     {
131         id=b[l];
132         down(id);
133         for (R i=l;i<=r;++i)
134         {
135             s[id]+=a[i]*(c-1);
136             ss[id]+=(c*c-1)*(a[i]*a[i]);
137             a[i]*=c;
138         }
139     }
140     else
141     {
142         id=b[l];
143         down(id);
144         for (R i=l;i<=siz*b[l];++i)
145         {
146             s[id]+=a[i]*(c-1);
147             ss[id]+=(c*c-1)*(a[i]*a[i]);
148             a[i]*=c;
149         }
150         for (R i=b[l]+1;i<=b[r]-1;++i)
151         {
152             delta_b[i]*=c;
153             delta_a[i]*=c;
154             ss[i]*=c;
155             s[i]*=c;
156         }
157         id=b[r];
158         down(id);
159         for (R i=1+siz*(b[r]-1);i<=r;++i)
160         {
161             s[id]+=a[i]*(c-1);
162             ss[id]+=(c*c-1)*(a[i]*a[i]);
163             a[i]*=c;
164         }
165     }    
166 }
167 
168 int main()
169 {
170     scanf("%d%d",&n,&m);
171     for (R i=1;i<=n;++i) a[i]=read();
172     siz=sqrt(n);
173     for (R i=1;i<=n;++i) b[i]=(i-1)/siz+1;
174     for (R i=1;i<=n;++i) s[ b[i] ]+=a[i],ss[ b[i] ]+=a[i]*a[i];
175     for (R i=1;i<=n;++i) si[ b[i] ]=siz,delta_a[i]=1;
176     si[ b[n] ]=n-siz*(b[n]-1);
177     for (R i=1;i<=m;++i)
178     {
179         scanf("%d",&opt);
180         if(opt==1||opt==2)
181         {
182             scanf("%d%d",&l,&r);
183             if(opt==1) printf("%lld
",ask1(l,r));
184             else printf("%lld
",ask2(l,r));    
185         }
186         else
187         {
188             scanf("%d%d%lld",&l,&r,&x);
189             if(opt==3) mul(l,r,x);
190             else add(l,r,x);
191         }
192     }
193     return 0;
194 }

　　迎风舞:https://www.nowcoder.com/acm/contest/200/E

　　题意概述:物理题.

　　三分抛出方向与水平方向的夹角,解方程算出时间和落地时间即可.关于这个函数为什么是单峰的,这里提供一个不严谨的证明:首先直觉上平抛肯定是比不上上抛的,但是角度为$90$度的上抛运动等于没有抛出去,所以函数应该是满足三分性的.

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <cmath>
 5 # include <algorithm>
 6 # include <string>
 7 # define R register int
 8 
 9 using namespace std;
10 
11 const double g=9.80665;
12 const double eps=0.000001;
13 double h,v,l,r,lmid,rmid,ans,lans;
14 int T;
15 
16 double f (double si)
17 {
18     double vx,vy,a,b,c,delta,x1,x2,t;
19     vy=v*si;
20     vx=sqrt(v*v-vy*vy);
21     a=-g/2.0;
22     b=vy;
23     c=h;
24     delta=sqrt(b*b-4.0*a*c);
25     
26     x1=(-b+delta)/(2*a);
27     x2=(-b-delta)/(2*a);
28     
29     t=max(x1,x2);
30     return t*vx;
31 }
32 
33 int main()
34 {
35     scanf("%d",&T);
36     while (T--)
37     {
38         scanf("%lf%lf",&h,&v);
39         l=0,r=1;
40         while (r-l>eps)
41         {
42             lmid=l+(r-l)/3.0;
43             rmid=r-(r-l)/3.0;
44             if(f(lmid)<f(rmid))
45                 l=lmid;
46             else r=rmid;
47         }
48         printf("%.5lf
",f(l));
49     }
50     return 0;
51 }

------------------比赛时就做到这里了,以下是赛后补题------------------

　　随风飘:https://www.nowcoder.com/acm/contest/200/D

　　题意概述:给定$n$个字符串,求它们两两之间的$LCP$的长度和,此外给出$T$组询问$k$,表示有$k$个字符串消失了,求所有的消失情况下$LCP$的长度和的和.

　　其实考试时本来是有机会$A$的,但是都以为开不下存字符串的数组导致纷纷弃疗.开数组靠的是信仰...其实当时为什么不开一个$vector$呢,果然考试时智商会降低.

　　首先把字符串都串到$Trie$树上去,统计$k=0$时的答案.对于其他的询问就不能再上树了!要考虑运用组合数学.每个$LCP$有$C_{n-2}^k$种方法留下来,直接算就好了.

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <cmath>
 5 # include <algorithm>
 6 # include <string>
 7 # define R register int
 8 # define ll long long
 9 # define mod 1000000007
10  
11 using namespace std;
12  
13 const int maxs=3000006;
14 int k,n,q,len,cnt=1,c[4003][302];
15 char s[maxs];
16  
17 struct Trie
18 {
19     int ch[maxs][26];
20     int vis[maxs],s[maxs];
21     long long ans;
22     void clear()
23     {
24         ans=0;
25         memset(ch,0,sizeof(ch));
26         memset(vis,0,sizeof(vis));
27         memset(s,0,sizeof(s));
28     }
29     void ins (char *s)
30     {
31         int len=strlen(s);
32         int x=1;
33         for (R i=0;i<len;++i)
34         {
35             int c=s[i]-'a';
36             if(!ch[x][c])
37                 ch[x][c]=++cnt;
38             x=ch[x][c];
39         }
40         ans=(ans+vis[x]*len)%mod;
41         vis[x]++;
42     }
43     void upd (int x,int dep)
44     {
45         s[x]=vis[x];
46         for (R i=0;i<26;++i)
47             if(ch[x][i])
48             {
49                 upd(ch[x][i],dep+1);
50                 ans=(ans+1LL*dep*s[x]%mod*(s[ ch[x][i] ]))%mod;
51                 s[x]+=s[ ch[x][i] ];
52             }
53     }
54 }T;
55  
56 int main()
57 {
58     scanf("%d%d",&n,&q);
59     for (R i=1;i<=n;++i)
60     {
61         scanf("%s",s);
62         T.ins(s);
63     }
64     T.upd(1,0);
65     c[0][0]=1;
66     for (R i=1;i<=n;++i)
67     {
68         c[i][0]=1;
69         for (R j=1;j<=min(i,300);++j)
70             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
71     }
72     for (R i=1;i<=q;++i)
73     {
74         scanf("%d",&k);
75         printf("%lld
",1LL*c[n-2][k]*T.ans%mod);
76     }
77     return 0;
78 }