NOIp2018集训test-10-15 (bike day1)

B 君的第一题

求斐波那契数列模n的循环节。

1、暴力bsgs，毕姥爷好像说循环节最大是6*n还是多少的，反之比较小，直接bsgs这题是可以过的。但是我非常蠢重载运算符的时候把相等返回成了小于，然后根本把结构体放不进map里去（我以为按道理只有等于的时候会炸，但事实上我根本放不进去啊）。然后改成不小于就可以过这题。

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=1e7+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int T,p,sz=;

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct jz {

     LL a[][];

     friend bool operator <(const jz&A,const jz&B) {

         For(i,,) For(j,,) if(A.a[i][j]!=B.a[i][j])

             return A.a[i][j]<B.a[i][j];

         return ;

     }

     friend bool operator ==(const jz&A,const jz&B) {

         return A.a[][]==B.a[][]&&A.a[][]==B.a[][]&&A.a[][]==B.a[][]&&A.a[][]==B.a[][];

     }

     friend jz operator *(const jz&A,const jz&B) {

         jz rs;

         For(i,,) For(j,,) {

             rs.a[i][j]=;

             For(k,,) (rs.a[i][j]+=A.a[i][k]*B.a[k][j]%p)%=p;

         }

         return rs;

     }

 }tp,now,bs;

 map<jz,int>mp;

 void solve() {

     tp.a[][]=,tp.a[][]=,tp.a[][]=,tp.a[][]=;

     bs.a[][]=,bs.a[][]=,bs.a[][]=,bs.a[][]=;

     now=bs;

     mp.clear();

     For(i,,sz) {

         now=now*tp;

         if(!mp[now]) mp[now]=i;

         //cout<<mp[now]<<endl;

         if(now==bs) {

             printf("%d\n",i);

             return;

         }

     }

     jz x=now;

     For(i,,sz) {

         if(mp[x]) {

             LL ans=(LL)i*sz-mp[x];

             if(ans!=) {

                 printf("%lld\n",ans);

                 return;

             }

         }

         x=x*now;

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("shijiazhuang.in","r",stdin);

     freopen("shijiazhuang.out","w",stdout);

 #endif

     read(T);

     while(T--) {

         read(p);

         solve();

     }

     Formylove;

 }

bsgs

2、我最讨厌的斐波那契的一坨性质

传送门

hdu题目传送门

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int T;

 LL n,p;

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct jz {

     LL a[][];

     friend jz operator *(const jz&A,const jz&B) {

         jz rs;

         For(i,,) For(j,,) {

             rs.a[i][j]=;

             For(k,,) (rs.a[i][j]+=A.a[i][k]*B.a[k][j]%p)%=p;

         }

         return rs;

     }

 }bs,rs;

 void jzksm(LL b) {

     rs.a[][]=rs.a[][]=;

     rs.a[][]=rs.a[][]=;

     bs.a[][]=; bs.a[][]=bs.a[][]=bs.a[][]=;

     while(b) {

         if(b&) rs=rs*bs;

         bs=bs*bs;

         b>>=;

     }

 }

 LL ksm(LL a,LL b,LL p) {

     LL rs=,bs=a%p;

     while(b) {

         if(b&) rs=rs*bs%p;

         bs=bs*bs%p;

         b>>=;

     }

     return rs;

 }

 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }

 LL lcm(LL a,LL b) {    return a/gcd(a,b)*b; } 

 LL solve() {

     if(p==) return ;

     if(p==) return ;

     if(p==) return ;

     LL a;

     if(ksm(,(p-)/,p)==) a=p-;

     else a=(p+)*;

     LL ans=a;

     for(LL x=;x*x<=a;x++) if(a%x==) {

         LL tp=x;

         jzksm(tp);

         if(rs.a[][]==&&rs.a[][]==&&rs.a[][]==&&rs.a[][]==) ans=min(ans,tp);

         tp=a/x;

         jzksm(tp);

         if(rs.a[][]==&&rs.a[][]==&&rs.a[][]==&&rs.a[][]==) ans=min(ans,tp);

     }

     return ans;

 }

 LL work(LL n) {

     if(n==) return ;

     LL tp=n,rs=;

     for(LL x=;x*x<=n;x++) if(tp%x==) {

         LL m=;

         while(tp%x==) {

             tp/=x; m++;

         }

         p=x;

         rs=lcm(rs,solve()*ksm(p,m-,1e18));

     }

     if(tp!=) {

         p=tp;

         rs=lcm(rs,solve());

     }

     return rs;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("shijiazhuang.in","r",stdin);

     freopen("shijiazhuang.out","w",stdout);

 #endif

     read(T);

     For(cs,,T) {

         read(n);

         printf("%lld\n",work(n));

         //printf("Case #%d: %lld\n",cs,work(n));

     }

     Formylove;

 }

B 君的第二题

1、我并没有想到的70分做法，开个堆把1~n的i/1放进去，每次取出最大i/x的然后把i/(x+1)放进堆即可。有人用这个A了这道题我也不知道他是怎么做到的。

2、100分做法，二分答案。二分被选上的最低分数，大于这个分数的都得被选，等于这个分数的可选可不选，判断一下是否合法就好了。

毕姥爷比较优秀用整数二分，我比较菜用实数二分但是过了我也没办法。

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=1e5+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,ans[N],fl[N];

 db p[N];

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 int ck(db pt) {

     LL t1=,t2=;

     For(i,,n) {

         int l=,r=m,rs=;

         while(l<=r) {

             int mid=((l+r)>>);

             if(p[i]>=pt*mid) rs=mid,l=mid+;

             else r=mid-;

         }

         fl[i]=ans[i]=;

         if(rs) {

             if(p[i]==pt*rs) { ans[i]=rs-; fl[i]=; t1+=rs-; t2++; }

             else { ans[i]=rs; t1+=rs; }

         }

     }

     if(m>=t1&&m<=t1+t2) {

         For(i,,n) if(fl[i]&&t1<m) {

             ans[i]++; t1++;

         }

         return ;

     }

     if(m<t1) return -;

     if(m>t1+t2) return ;

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("taiyuan.in","r",stdin);

     freopen("taiyuan.out","w",stdout);

 #endif

     read(n); read(m);

     db l=0.0,r=0.0;

     For(i,,n) {

         read(p[i]);

         r=max(r,p[i]);

     }

     for(;;) {

         db mid=(l+r)/2.0;

         if(ck(mid)==) break;

         if(ck(mid)==-) l=mid;

         else r=mid;

     }

     For(i,,n) printf("%d\n",ans[i]);

     Formylove;

 }

B 君的第三题

曼哈顿距离和切比雪夫距离的相互转换

题目转换为求一点到所有点的切比雪夫距离最小，再转换坐标变成求曼哈顿距离最小。于是x,y分开考虑，每一维取中位数就好了。

然后要求点数，就是中位数围成的矩形中的整点个数。因为现在的坐标转回去的时候是(x+y)/2,(x-y)/，2所以实际上是这个矩形中横轴坐标奇偶相同的整点个数。特判当矩形只剩下一个点，而这个点奇偶不同时，要抖动一下找四周的点作为实际答案。

 //Achen

 #include<bits/stdc++.h>

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 #define Formylove return 0

 const int N=1e5+;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,anstot;

 LL xx[N],yy[N],ansnum=1e18;

 template<typename T> void read(T &x) {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 void calc(LL x,LL y) {

     LL rs=;

     For(i,,n)

         rs+=abs(xx[i]-x)+abs(yy[i]-y);

     if(rs<ansnum) ansnum=rs,anstot=;

     else if(rs==ansnum) anstot++;

 }

 LL odd(LL l,LL r) {

     if((l&)&&(r&)) return (r-l+)/;

     else return (r-l+)/;

 }

 LL even(LL l,LL r) {

     if(!(l&)&&!(r&)) return (r-l+)/;

     else return (r-l+)/;

 }

 void solve(LL xl,LL xr,LL yl,LL yr) {

     if(xl==xr&&yl==yr&&(xl+yl)%!=) {

         calc(xl-,yl);

         calc(xl+,yl);

         calc(xl,yl-);

         calc(xl,yl+);

     }

     else {

         calc(xl,yl);

         anstot=odd(xl,xr)*odd(yl,yr)+even(xl,xr)*even(yl,yr);

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("zhengzhou.in","r",stdin);

     freopen("zhengzhou.out","w",stdout);

 #endif

     read(n);

     For(i,,n) {

         LL x,y;

         read(x); read(y);

         xx[i]=x+y;

         yy[i]=x-y;

     }

     sort(xx+,xx+n+);

     sort(yy+,yy+n+);

     solve(xx[(n+)/],xx[(n+)/],yy[(n+)/],yy[(n+)/]);

     printf("%lld\n%d\n",ansnum/,anstot);

     Formylove;

 }

其实我特别后悔当年第一次见到毕姥爷之后没有立刻退役。

要是人生重来，不学OI了，也不学理了，我就想安安静静地当个文科生。说实话我对史地都挺感兴趣的，政治无感但好歹是我高一学得最好的每次月考帮我拉分的一个科目，而理化生，抱歉半毛钱兴趣都没有，如果不是竞赛应该会认真考虑读文吧。虽然读文好像不能学计算机了，那就不学了吧，大概多读书多到处走以后当个写东西的，这样的人生可能更适合我？

我邪在沙海说过里有一句话

对于弱者的帮助有时候只能让他变得更弱，在这个社会里，在自己不擅长的行业被淘汰，有时候是一种幸运，你可以去寻找真正适合自己的生活，而帮助弱者，把他们在自己不擅长的行业中抬到一个太高的位置，往往会让他们死无葬身之地。

这一次无论能走到哪里，都是最后一次了，我未来再不会碰算法竞赛相关了。忘了从哪听到的一句话大概是“所有的热爱最终都变成执念”，我现在在干的事情已经完全脱离我的初衷了，我和之前的我状态完全不一样了。而且我更是清晰且悲哀地认识到，竞赛可能真的并不适合我。当然，不适合和不做是两码事，于是现在OI对于我已经从目的变成仅仅手段了，这有违我的初心，是我所不喜欢的，也是让现在的我难受的，但是我没有别的办法。现在的我能做的只有尽我所能地去做我能做到的所有事情。

巴特西

NOIp2018集训test-10-15 (bike day1)

最新文章

热门文章