2016百度之星资格赛

A.前缀hash+逆元

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>

const int inf = 0x3f3f3f;
const int MAXN = 1e5+10;
const int MOD = 9973;

using namespace std;

char ts[MAXN];
int n;
int a[MAXN],rev[MOD],b[MAXN];

long long quickpow(long long base,long long n){
    long long ans = 1;
    while(n){
        if(n%2==1)ans = ans*base%MOD;
        n /= 2;
        base = base*base%MOD;
    }
    return ans;
}

int main()
{
    for(int i=1;i<MOD;i++){
        rev[i] = quickpow(i,MOD-2);
    }

    while(scanf("%d",&n)!=EOF){
        scanf("%s",ts);
        int len = strlen(ts);
        a[0] = 1;
        b[0] = rev[1];
        for(int i=0;i<len;i++){
            a[i+1] = a[i]*(ts[i]-28)%MOD;
            b[i+1] = rev[a[i+1]];
        }
        int u,v;
        for(int i=0;i<n;i++){
            scanf("%d%d",&u,&v);
            printf("%d
",a[v]*b[u-1]%MOD);
        }
    }
    //cout << "Hello world!" << endl;
    return 0;
}

D.sort+map

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

const int inf = 0x3f3f3f;
const int MAXN = 1e7+10;

using namespace std;


int main()
{
    int n;
    char ts[40];
    map<string,int>hash;
    map<string,int>::iterator li;
    while(scanf("%d",&n)!=EOF){
        hash.clear();
        for(int i=0;i<n;i++){
            scanf("%s",ts);
            int len = strlen(ts);
            sort(ts,ts+len);
            string tmp = (string)ts;
                li = hash.find(tmp);
                if(li==hash.end()){
                    cout<<0<<endl;
                    hash[tmp]++;
                }else{
                    cout<<hash[tmp]<<endl;
                    hash[tmp]++;
                }
            }

    }
    //cout << "Hello world!" << endl;
    return 0;
}