首页 > 代码库 > ACdream原创群赛__15
ACdream原创群赛__15
这场感觉题目确实还算可以，不过，说好的每题10s效果上却不理想。这个时限还算比较紧。因为时间不是按绝对的多出几秒来计算，而是几倍来计算的。
比赛做的不好，后面又去做了一下。
A：典型的数位DP，一直坑在这里。
E：求f(f(f(n)))%p。f()表示斐波那契数。关于求斐波那契数模的循环节是有特定的数学定理和方法的。我也不知道，但是看了结论之后自己会实现了。首先，把p因数分解，ai^pi，显然最终的循环节就等于这些单独因子计算循环节的lcm。同时ai^pi的循环节又是G(ai)*ai^(pi-1)。G()表示单个质数作用的循环节。单个质数的循环节可以这样来判断，如果power_mod(5,(p-1)/2,p)==1那么该循环节是ai-1的一个约数，否则该循环节是2*ai+2的一个约数。关于剩下的约数，直接暴力枚举判断即可。整个实现过程比较复杂，但是也算是思路清晰，调试难度并不大。
/** this code is made by 092000* Problem: 1124* Verdict: Accepted* Submission Date: 2014-07-12 00:02:47* Time: 3812MS* Memory: 3924KB*/#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <map>#include <algorithm>#define maxn 100100typedef long long ll;using namespace std; struct mat{ ll f[2][2]; void Z() { memset(f,0,sizeof f); } void E() { f[0][0]=f[1][1]=1,f[0][1]=f[1][0]=0; } void F() { f[0][0]=f[1][0]=f[0][1]=1,f[1][1]=0; }}; ll pri[maxn],b[maxn],pnum=0;ll fac[500],fnum[500],Fac;ll ffac[500],FFac;ll F1,F2;map<ll,ll> GG; ll gcd(ll A,ll B) { return B==0?A:gcd(B,A%B); }ll lcm(ll A,ll B) { return A/gcd(A,B)*B; } void getprim(){ for (int i=2; i<maxn; i++) if (!b[i]) { pri[++pnum]=i; for (int j=i+i; j<maxn; j+=i) b[j]=j; }} ll power(ll A,ll B,ll P){ ll tot=1; while (B) { if (B&1) tot=(tot*A)%P; A=(A*A)%P,B>>=1; } return tot;}ll power(ll A,ll B){ ll tot=1; for (;B;A=A*A,B>>=1) if (B&1) tot=tot*A; return tot;}mat mul(mat A,mat B,ll P){ mat tot; tot.Z(); for (int i=0; i<2; i++) for (int j=0; j<2; j++) for (int k=0; k<2; k++) { tot.f[i][j]+=A.f[i][k]*B.f[k][j]; tot.f[i][j]%=P; } return tot;}mat power(mat A,ll B,ll P){ mat tot; tot.E(); while (B) { if (B&1) tot=mul(tot,A,P); A=mul(A,A,P),B>>=1; } return tot;}ll fib(ll N,ll P){ mat tot; tot.F(); tot=power(tot,N,P); return tot.f[0][0];} void divide(ll P){ Fac=0; for (int i=1; pri[i]<=P/pri[i]; i++) if (P%pri[i]==0) { fac[++Fac]=pri[i],fnum[Fac]=0; while (P%pri[i]==0) P/=pri[i],fnum[Fac]++; } if (P>1) fac[++Fac]=P,fnum[Fac]=1;} ll G(ll P){ if (GG[P]) return GG[P]; ll num; if (power(5,(P-1)>>1,P)==1) num=P-1; else num=2*P+2; FFac=0; for (int i=1; i<=num/i; i++) if (num%i==0) { ffac[++FFac]=i; ffac[++FFac]=num/i; } sort(ffac+1,ffac+1+FFac); for (int i=1; i<=FFac; i++) if (fib(ffac[i]+1,P)==F1 && fib(ffac[i]+2,P)==F2) { GG[P]=ffac[i]; return ffac[i]; } return -1;} ll getloop(ll P){ ll Lp=1; F1=1%P,F2=2%P; divide(P); for (int i=1; i<=Fac; i++) Lp=lcm(Lp,G(fac[i])*power(fac[i],fnum[i]-1)); return Lp;} int main(){ getprim(); GG[2]=3,GG[3]=8,GG[5]=20; ll n,p,T,ans; scanf("%lld",&T); while (T--) { scanf("%lld%lld",&n,&p); if (p==1) { puts("0"); continue; } ll mod1=p; ll mod2=getloop(mod1); ll mod3=getloop(mod2); ans=fib(n,mod3); ans=fib(ans,mod2); ans=fib(ans,mod1); printf("%lld\n",ans); } return 0;}
H：有N段路，每段路有两个值si，bi。si表示长度，单位长度汽车耗油量为max(0,0.5*v+bi)。出发是总共有f量的油。现在问题是如果想尽快通过这N段路最段需要的时间是多少呢？很显然，题目说开得越慢耗油越少，看题解是二分速度，每次判断耗油是否够不够，知道达到精度要求。不过。。。。。在需要耗油的路段，能确定所有的速度都是一样大的时候所用的时间最短吗？每段路的系数不一样，在最优的情况下其速度会一样吗？这些问题我不确定，但是按照题解，我写的A了。不明真相。
/** this code is made by 092000* Problem: 1129* Verdict: Accepted* Submission Date: 2014-07-12 14:02:50* Time: 2612MS* Memory: 3240KB*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#define maxn 100100#define eps 1e-9using namespace std; double s[maxn],b[maxn],vm,f;int n; bool check(double cur){ double tot=0; for (int i=1; i<=n; i++) tot+=max(0.0,0.5*cur+b[i])*s[i]; return tot<=f;} double count(double v){ double tot=0; for (int i=1; i<=n; i++) tot+=s[i]/min(vm,max(v,-2*b[i])); return tot;} int main(){ while (scanf("%d",&n)!=EOF) { scanf("%lf%lf",&f,&vm); for (int i=1; i<=n; i++) scanf("%lf%lf",&s[i],&b[i]); double l=0,r=vm,mid; while (r-l>eps) { mid=(l+r)/2; if (check(mid)) l=mid; else r=mid; } if (l>0 && check(l)) printf("%.3f\n",count(l)); else printf("Bad Luck!\n"); }}
I：签到题。每次你可以从已经出现过的字符串里面取出一个串（也可以不取），构成当前这个串，最少需要进行多少次操作？很贱单，全场tire维护即可。多加一个标签数组啦。
/** this code is made by 092000* Problem: 1121* Verdict: Accepted* Submission Date: 2014-07-04 20:56:29* Time: 6720MS* Memory: 117580KB*/#include <iostream>#include <cstdio>#include <cstring>#define maxn 1050300using namespace std; int next[maxn][26],least[maxn],tag[maxn],N;char s[maxn];int ans,n,m,T,L; int add(){ N++; for (int i=0; i<26; i++) next[N][i]=0; least[N]=4*maxn,tag[N]=0; return N;} int insert(){ int cur=0,tmp=0,last=4*maxn; L=strlen(s); for (int i=0; s[i]; i++) { int k=s[i]-‘a‘; if (!next[cur][k]) next[cur][k]=add(); cur=next[cur][k]; last=min(last,L-tag[cur]); last=min(last,least[cur]-i-1+L-i-1); least[cur]=min(least[cur],L); } tag[cur]=L; return min(last,L-tmp);} int main(){ scanf("%d",&T); while (T--) { scanf("%d%s",&n,s); N=-1,N=add(); m=insert(); for (int i=1; i<=n; i++) { scanf("%s",s); int tmp=insert(); printf("%d\n",min(L,tmp+1)); } } return 0;}
J：好题。两个发射站，以及若干个接受站。求两个发射站的覆盖半径分别为r1和r2的时候，能覆盖多少个点？机智的人一看就知道把与两个发射站的距离看成是二维坐标，剩下的点的处理就相当于是一个平面覆盖问题了。直接顺序维护一维，另一维用树状数组统计即可。
/** this code is made by 092000* Problem: 1127* Verdict: Accepted* Submission Date: 2014-07-12 07:27:12* Time: 5000MS* Memory: 15772KB*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define maxn 300200using namespace std; struct point{ double dis1,dis2; int rk;}p[maxn]; struct query{ int id,r1,r2,ans,pos;}q[maxn]; int n,Q,m,x1_,x2_,y1_,y2_,ttx,tty;int c[maxn];double tx,ty; bool cmp1(point p1,point p2) { return p1.dis2<p2.dis2; }bool cmp2(query q1,query q2) { return q1.r2<q2.r2; }bool cmp3(point p1,point p2) { return p1.dis1<p2.dis1; }bool cmp4(query q1,query q2) { return q1.r1<q2.r1; }bool cmp5(query q1,query q2) { return q1.id<q2.id; } int lowbit(int x) { return x&(-x); }void add(int x,int v) { while (x<maxn) c[x]+=v,x+=lowbit(x); }int sum(int x){ int tmp=0; while (x>0) tmp+=c[x],x-=lowbit(x); return tmp;} void _init_point(){ scanf("%d",&n); for (int i=1; i<=n; i++) { scanf("%d%d",&ttx,&tty); tx=ttx,ty=tty; p[i].dis1=sqrt((tx-x1_)*(tx-x1_)+(ty-y1_)*(ty-y1_)); p[i].dis2=sqrt((tx-x2_)*(tx-x2_)+(ty-y2_)*(ty-y2_)); } memset(c,0,sizeof c); sort(p+1,p+1+n,cmp1); for (int i=1; i<=n; i++) p[i].rk=i,add(i,1);} void _init_query(){ scanf("%d",&Q); for (int i=1; i<=Q; i++) { scanf("%d%d",&q[i].r1,&q[i].r2),q[i].id=i; } sort(q+1,q+1+Q,cmp2); int cur=0; for (int i=1; i<=Q; i++) { while (cur<n && q[i].r2>p[cur+1].dis2) cur++; q[i].pos=cur; }} int main(){ while (scanf("%d%d%d%d",&x1_,&y1_,&x2_,&y2_)!=EOF) { _init_point(); _init_query(); int tot=0,cur=0; sort(p+1,p+1+n,cmp3); sort(q+1,q+1+Q,cmp4); for (int i=1; i<=Q; i++) { while (cur<n && q[i].r1>p[cur+1].dis1) { cur++,tot++; add(p[cur].rk,-1); } q[i].ans=sum(q[i].pos)+tot; } sort(q+1,q+1+Q,cmp5); for (int i=1; i<=Q; i++) printf("%d\n",n-q[i].ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。