8.30

• 树的直径
• 树的重心
• gcd 和 exgcd
• 乘法逆元

照常：

• ：火柴棒等式/机器翻译/P1079 Vigenère 密码

• noip DP

  火柴棒等式

#define N 1111

int biao[]={6,2,5,5,4,5,6,3,7,6};
int n,ans;

int get_num(int x){
    int ans=0;
    if(x==0)ans=biao[0];//特判x==0的情况！
    while(x){
        ans+=biao[x%10];
        x/=10;
    }
    return ans;
}

int main(){
    freopen("huochai.txt","r",stdin);
    rd(n);
    //printf("%d\n",get_num(0));
    rep(i,0,N){
        rep(j,0,N){
            if(get_num(i)+get_num(j)+get_num(i+j)+4==n){
                ans++;
                //printf("%d %d %d %d %d %d \n",i,get_num(i),j,get_num(j),i+j,get_num(i+j));
            }
        }
    }
    printf("%d",ans);
    return 0;
}

---

机器翻译

先进先出，队列裸题，
注意queue的size好像只能返回01……还是开一个变量来记录数组的大小吧。

#define N 1010

int m,n,ans,cnt;
int a[N];
queue<int>q;
map<int,int>mp;

int main(){
    rd(m),rd(n);
    rep(i,1,n){
        rd(a[i]);
        if(cnt<m){
            if(mp[a[i]])continue;
            ++cnt;
            if(mp[a[i]]==0)
                ans++;
            q.push(a[i]);
            mp[a[i]]=1;
        }
        else if(cnt>=m){
            if(mp[a[i]])continue;///////////题目条件，你怎么能不写呢？
            int u=q.front();
            mp[u]=0;
            q.pop();
            if(mp[a[i]]==0)ans++;
            q.push(a[i]);
            mp[a[i]]=1;
        }
    }
    printf("%d",ans);
    return 0;
}

P1079 Vigenère 密码

真是累死宝宝了…… 码了接近一小时，得了10pts哈哈哈哈哈
不过学到了新技巧：如何快速将大写转化为小写？
x&31就好啦

/*
map<char,int>mp;
string k,mi;

inline void init(){
    mp['a']=mp['A']=0;
    mp['b']=mp['B']=1;
    mp['c']=mp['C']=2;
    mp['d']=mp['D']=3;
    mp['e']=mp['E']=4;
    mp['f']=mp['F']=5;
    mp['g']=mp['G']=6;
    mp['h']=mp['H']=7;
    mp['i']=mp['I']=8;
    mp['j']=mp['J']=9;
    mp['k']=mp['K']=10;
    mp['l']=mp['L']=11;
    mp['m']=mp['M']=12;
    mp['n']=mp['N']=13;
    mp['o']=mp['O']=14;
    mp['p']=mp['P']=15;
    mp['q']=mp['Q']=16;
    mp['r']=mp['R']=17;
    mp['s']=mp['S']=18;
    mp['t']=mp['T']=19;
    mp['u']=mp['U']=20;
    mp['v']=mp['V']=21;
    mp['w']=mp['W']=22;
    mp['x']=mp['X']=23;
    mp['y']=mp['Y']=24;
    mp['z']=mp['Z']=25;
}

int main(){
    init();
    //printf("%c",'f'-mp['b']);
    cin>>k>>mi;
    int lenk=k.length(),lenmi=mi.length();
    if(lenk<lenmi){
        int times=lenmi/lenk;
        string yuan=k;
        rep(i,2,times)
            k+=yuan;
        rep(i,times*lenk+1,lenmi)
            k+=k[i%(lenk+1)];
    }
    cout<<k<<endl;
    for(int i=0;i<lenmi;++i){
        if(mp[mi[i]]-mp[k[i]]<0)
            printf("%c",mi[i]+(26-mp[k[i]]));
        else
            printf("%c",mi[i]-mp[k[i]]);
    }
    return 0;
}*/


int main(){
    //freopen("A.txt","r",stdin);
    string k,c;
    cin>>k>>c;
    for(int i=0;i<c.length();++i){
        int now=(k[i%k.length()]&31)-1;
        if(((c[i]&31)-now)>0)
            c[i]-=now;
        else
            c[i]-=now-26;
    }
    cout<<c<<endl;
    return 0;
}