• 上午
  • 模擬考試
    • Prob.1（AC）一道簡單的博弈題，找到必勝態，反推普遍情況是否可以達到必勝態即可。
    • Prob.2（AC）做到原題了呢。入門OJ 2092: [Noip模擬題]舞會
    • Prob.3（WA了3個點）一道高精度的dp題，為減少狀態，我把數據按某一權值分為了兩類，對于一類反著dp，狀態很少，只用到高精度加法。對于另一類（30分），要用到高精度乘法，然后進位時少打了一個+號，然后就沒有然后了……
  • 然后整理了三個模板，貼上！ //maybe have no mistakes,^_^//1.Big_Int //only support + , * , = , < , <= , > , >= between Big_Int and Big_Int as well as Big_Int and int #define MAXN 1000 struct Big_Int{int len,a[30];Big_Int(){len=1; memset(a,0,sizeof(a));}void operator =(int val){len=0;do{a[++len]=val%MAXN;val/=MAXN;}while(val);}Big_Int operator +(const Big_Int &rtm) const{Big_Int now; int l=max(len,rtm.len);for(int i=1;i<=l;i++){now.a[i]+=a[i]+rtm.a[i];now.a[i+1]=now.a[i]/MAXN;now.a[i]%=MAXN;}if(now.a[l+1]) l++; now.len=l;return now;}Big_Int operator +(const int &val) const{Big_Int now,rtm;rtm=val; now=(*this)+rtm;return now;}Big_Int operator *(const Big_Int &rtm) const{Big_Int now; int l=len+rtm.len;for(int i=1;i<=len;i++)for(int j=1;j<=rtm.len;j++){now.a[i+j-1]+=a[i]*rtm.a[j];now.a[i+j]+=now.a[i+j-1]/MAXN;now.a[i+j-1]%=MAXN;}while(!now.a[l]) l--; now.len=l;return now;}Big_Int operator *(const int &val) const {Big_Int now,rtm;rtm=val; now=(*this)*rtm;return now;}bool operator ==(const Big_Int & rtm) const{if(len!=rtm.len) return 0;for(int i=len;i>=1;i--) if(a[i]!=rtm.a[i]) return 0;return 1;}bool operator <(const Big_Int &rtm) const{if(len!=rtm.len) return len<rtm.len;for(int i=len;i>=1;i--) if(a[i]!=rtm.a[i]) return a[i]<rtm.a[i];return 0;}bool operator >(const Big_Int &rtm) const{return rtm<(*this);}bool operator <=(const Big_Int &rtm) const{return (*this)<rtm||(*this)==rtm;}bool operator >=(const Big_Int &rtm) const{return (*this)>rtm||(*this)==rtm;}bool operator ==(const int &val) const{Big_Int rtm; rtm=val;return (*this)==rtm;}bool operator <(const int &val) const{Big_Int rtm; rtm=val;return (*this)<rtm;}bool operator >(const int &val) const{Big_Int rtm; rtm=val;return (*this)<rtm;}bool operator <=(const int &val) const{Big_Int rtm; rtm=val;return (*this)<=rtm;}bool operator >=(const int &val) const{Big_Int rtm; rtm=val;return (*this)>=rtm;}void print(){printf("%d",a[len]);for(int i=len-1;i>=1;i--){printf("%03d",a[i]);}} };//2.Fraction //only support + , * and reduction for fraction struct Fraction{ll Numerator,Denominator;ll Gcd(ll a,ll b){while(a^=b^=a^=b%=a);return b;}bool Zero(){return Numerator==0;}void Clear(){Numerator=Denominator=0;}void Reduction(){ll g=Gcd(Numerator,Denominator);Numerator/=g;Denominator/=g;}Fraction operator +(Fraction &rtm){Fraction New;if(!Numerator&&!Denominator) New.Numerator=rtm.Numerator,New.Denominator=rtm.Denominator;else{ll g=Gcd(Denominator,rtm.Denominator);ll a=Denominator/g,b=rtm.Denominator/g;New.Denominator=a*b*g;New.Numerator=Numerator*b+rtm.Numerator*a;}New.Reduction();return New;}Fraction operator *(Fraction &rtm){Fraction New;New.Denominator=Denominator*rtm.Denominator;New.Numerator=Numerator*rtm.Numerator;New.Reduction();return New;}void Read(){cin>>Numerator;Denominator=1;}void Write(){cout<<Numerator;if(Denominator!=1&&Denominator!=0) cout<<"/"<<Denominator<<endl;} }//3.Maxtrix //noly supprt * , ^(quick pow) for Maxtrix struct Maxtrix{int r,c;int val[75][75];Maxtrix(){r=c=0;memset(val,0,sizeof(val));}void identity(int l){r=c=l;for(int i=1;i<=l;i++) val[i][i]=1;}Maxtrix operator * (Maxtrix const b){ // c==b.rMaxtrix now; now.r=r; now.c=b.c;for(int i=1;i<=r;i++)for(int j=1;j<=b.c;j++)for(int k=1;k<=c;k++)now.val[i][j]=(now.val[i][j]+val[i][k]*b.val[k][j])%mod; return now;} Maxtrix operator ^ (int b){Maxtrix base,now; base=*this;now.identity(this->r); while(b){if(b&1) now=now*base;base=base*base;b>>=1; }return now;} }//____________________________________________________________________by *ZJ

?

• 下午
  • 入門OJ 2069: [Noip模擬題]貪吃的CWT

    對拍了一下，改出來了呢。

    知道了錯誤在哪兒的我想打人……

    這是我原來錯誤的dis函數：

    （真不知道是什么鬼樣例數據，dis沒開根都過了）

    代碼：

    #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct edge{int u,v; double val;bool operator<(const edge &rtm) const{return val<rtm.val;} }e[1005*1005]; struct hamburger{int x,y,val; }p[1005]; int fa[1005],bh[1005]; int n,ent; double tot,ans; double dis(int i,int j){return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)); } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } int main(){scanf("%d",&n);for(int i=1,a,b,c;i<=n;i++){scanf("%d%d%d",&a,&b,&c);p[i]=(hamburger){a,b,c};}for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)e[++ent]=(edge){i,j,dis(i,j)};sort(e+1,e+ent+1);for(int i=1;i<=n;i++) fa[i]=i;int fu,fv,u,v,need=n-1;for(int i=1;i<=ent&&need;i++){u=e[i].u; v=e[i].v;fu=find(u); fv=find(v);if(fu==fv) continue;tot+=e[i].val;fa[fv]=fu;need--;}for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++) bh[i]=p[i].val;need=n-1;for(int i=1;i<=ent&&need;i++){u=e[i].u; v=e[i].v;fu=find(u); fv=find(v);if(fu==fv) continue;ans=max(ans,1.0*(bh[fu]+bh[fv])/(tot-e[i].val));bh[fu]=max(bh[fu],bh[fv]);fa[fv]=fu;need--;}printf("%.2lf",ans);return 0; }

• 入門OJ 2073: [Noip模擬題]古巴比倫

  一個皮皮題。

  我直接跑了個n²就過了，應該是數據水了……，

  但erge說if語句和++操作常數很小，跑10⁸可以過！

  他的做法是：因為數據完全隨機，所以當兩個串的重疊部分長度小于某個值時，就可以直接跳出，

  至于小于哪個值，他說：“就自己估摸吧，我定的不能小于90%的長度。”

  ……

  代碼：

  #include<cstdio> #include<cstring> #include<iostream> using namespace std; char s1[10005],s2[10005]; int ls1,ls2,cnt,ans; void doit(char *A,int LA,char *B,int LB){for(int i=0;i<LA;i++){cnt=0;for(int j=0;j<LB&&i+j<LA;j++) if(A[i+j]==B[j]) cnt++;ans=max(ans,cnt);} } int main(){scanf("%d",&ls1); scanf(" %s",s1);scanf("%d",&ls2); scanf(" %s",s2);doit(s1,ls1,s2,ls2);doit(s2,ls2,s1,ls1);printf("%d",ans);return 0; }

• 晚上
  • 回家了，lalala
• End

  • 沒有end，只有放假！

轉載于:https://www.cnblogs.com/zj75211/p/7629216.html

總結

以上是生活随笔為你收集整理的17.10.05的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。