NOIP 2012

Vigenère密碼

題目
模擬。

#include <iostream>using namespace std;int main(){    string k,c;    cin>>k>>c;    for (int i=0;i<c.length();i++) {        int t=(k[i%k.length()]&31)-1;        c[i]=(c[i]&31)-t>0?c[i]-t:c[i]-t+26;    }    cout<<c<<endl;    return 0;}

國王游戲

題目
按\(a_ib_i\)升序排序,證明采用鄰項交換法即可。
垃圾出題人要我寫高精。

#include<bits/stdc++.h>using namespace std;struct BIGNUM{    int a[100001];    BIGNUM()    {        memset(a,0,100001),a[0]=1;    }    BIGNUM operator=(string s)    {        a[0]=s.length();        for(int i=1;i<=a[0];i++)            a[i]=s[a[0]-i]-'0';        return *this;    }    BIGNUM operator=(int n)    {        char x[100001];        string s;        sprintf(x,"%d",n);        s=x;        *this=s;        return *this;    }    BIGNUM (int n)    {        *this=n;    }    BIGNUM (string s)    {        *this=s;    }    BIGNUM operator*(BIGNUM b)    {        BIGNUM c;        for(int i=1;i<=a[0];i++)            for(int j=1;j<=b.a[0];j++)                c.a[i+j-1]+=a[i]*b.a[j],c.a[i+j]+=c.a[i+j-1]/10,c.a[i+j-1]%=10;        c.a[0]=a[0]+b.a[0]-1;        if(c.a[c.a[0]+1])            c.a[0]++;        return c;    }    BIGNUM operator/(int x)    {        BIGNUM b;        b.a[0]=a[0];        int tmp=0;        for (int i=a[0];i;i--)         {            tmp=tmp*10+a[i];            b.a[i]=tmp/x;            tmp%=x;        }        while(!b.a[b.a[0]]&&b.a[0]>1)            b.a[0]--;         return b;    }    bool operator<(BIGNUM b)    {        if(a[0]!=b.a[0])            return a[0]<b.a[0];        for(int i=a[0];i;i--)            if(a[i]!=b.a[i])                return a[i]<b.a[i];        return false;    }};ostream& operator <<(ostream &out,BIGNUM &x){    for(int i=x.a[0];i;i--)        cout<<x.a[i];    return out;}struct Lovelive{    int x,y;    long long z;}a[100001];bool cmp(Lovelive a,Lovelive b){    return a.z<b.z;}int n;int main(){    scanf("%d",&n);    for(int i=0;i<=n;i++)        scanf("%d%d",&a[i].x,&a[i].y),a[i].z=a[i].x*a[i].y;    sort(a+1,a+n+1,cmp);    BIGNUM ans=1,tmp,k=1;    for(int i=1;i<=n;i++)    {        k=k*a[i-1].x;        tmp=k/a[i].y;        ans=ans<tmp? tmp:ans;    }    cout<<ans;    return 0;}

同余方程

題目
exgcd。
注意exgcd求的是絕對值最小的解。

#include<bits/stdc++.h>using namespace std;int a,b,x,y,k;void exgcd(int a,int b){!b? (x=1,y=0):(exgcd(b,a%b),k=x,x=y,y=k-a/b*y);}int main(){cin>>a>>b,exgcd(a,b),cout<<(x+b)%b;}