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;}