引子-1

这套题目从今天中午开始打,到刚刚为止A掉了前4道题,从整体来说难度稍有提高,出现了一些数据结构的题(虽然是裸的),以及一些需要思维量的题。其中A题用类似于前缀和的思想搞,B题直接模拟做,C题是Trie的模板题,D题则也是模拟,但其中可能也要用到一些Hash的东西吧。

引子-2

不知道百度之星初赛难度怎么样,和这个相比会不会再难很多,反正加油啊啊啊啊!

Problem A

题解

前缀积? 好坑

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000+10;
const int prime=9973;
int n,a,b,calc[maxn],cnt[maxn],pown[maxn];
char s[maxn];
inline int quickpow(int m,int n,int k)
{
    int b=1;
    while(n)
    {
        if(n&1)
            b=(b*m)%k;
        n>>=1;
        m=(m*m)%k;
    }
    return b;
}
void make()
{
    for(int i=1;i<=prime;i++)
        pown[i]=quickpow(i,prime-2,prime);
}
int main()
{
//    freopen("1.sb","r",stdin);
    make();
    while(~scanf("%d",&n))
    {
        scanf("%s",s+1);
        //cout<<s<<endl;
        calc[0]=cnt[0]=1;
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
        {
            calc[i]=(calc[i-1]*(int(s[i])-28))%prime;
            cnt[i]=pown[calc[i]];
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",(calc[b]*cnt[a-1])%prime);
        }
    }
    return 0;
}

Problem B

题解

随便推几组下去,发现就是斐波那契嘛,然而n比较大,于是考虑高精度。

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=300+10;
int a[maxn][maxn],len[maxn],N;
void plus1(int x)    //a[x]=a[x-1]+a[x-2]
{
    int c=0;
    len[x]=len[x-1];
    for(int i=0;i<len[x];i++)
    {
        a[x][i]=a[x-1][i]+a[x-2][i]+c;
        c=a[x][i]/10;
        a[x][i]%=10;
    }
    if(c>0)
        a[x][len[x]++]=c;
}
void make()
{
    a[1][0]=1,len[1]=1;
    a[2][0]=2,len[2]=1;
    for(int i=3;i<=200;i++)
        plus1(i);        
}
void print(int x)
{
    for(int i=len[x]-1;i>=0;i--)
        printf("%d",a[x][i]);
    printf("\n");
}
int main()
{
//    freopen("1.sb","r",stdin);
    make();
    while(~scanf("%I64d",&N))
        print(N);
    return 0;
}

Problem C

题解

Trie模板题,注意Delete操作,count也要--,(一开始被坑了…)

代码

#include <stdio.h>
#include <iostream>
using namespace std;
#define  MAX    26

typedef struct TrieNode
{
    int nCount;  
    struct TrieNode *next[MAX]; 
} TrieNode;

TrieNode Memory[9000000];
int allocp = 0;


TrieNode * createTrieNode()
{
    TrieNode *tmp=&Memory[allocp++];
    tmp->nCount=1;
    for (int i=0;i<MAX;i++)
        tmp->next[i]=NULL;
    return tmp;
}

void insertTrie(TrieNode **pRoot,char *str)
{
    TrieNode *tmp=*pRoot;
    int i =0,k;
    
    while (str[i])
    {
        k=str[i]-'a'; 
        if (tmp->next[k])
            tmp->next[k]->nCount++;
        else
            tmp->next[k]=createTrieNode();
        tmp=tmp->next[k];
        i++; 
    }
}

int searchTrie(TrieNode *root,char *str)
{
    if(root==NULL)
        return 0;
    TrieNode *tmp=root;
    int i=0,k;
    while(str[i])
    {
        k=str[i]-'a';
        if(tmp->next[k])
        {
            tmp=tmp->next[k];
        }
        else
            return 0;
        i++;
    }
    return tmp->nCount; 
}
void deleteTrie(TrieNode **root,char *str)
{
    if(root==NULL)
        return;
    TrieNode *tmp=*root,*p=tmp;
    int i=0,k,kt;
    while(str[i])
    {
        k=str[i]-'a';
        if(tmp->next[k])
        {
            p=tmp;
            kt=k;
            tmp=tmp->next[k];
        }
        else
            return;
        i++;
    }
    p->next[kt]=NULL;
    p->nCount-=tmp->nCount;
    
    return;
}
int N;
char op[50],s[50];
int main()
{
//    freopen("1.sb","r",stdin);
    TrieNode *Root=createTrieNode();
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%s %s",op,s);
        //cout<<op<<' '<<s<<endl;
        if(op[0]=='i')        //insert
            insertTrie(&Root,s);
        else if(op[0]=='s')
        {
            if(searchTrie(Root,s))
                printf("Yes\n");
            else
                printf("No\n");
            //printf("%d\n",searchTrie(Root,s));
        }
        else
            deleteTrie(&Root,s);
    }
    return 0;
}

Problem D

题解

感觉最裸的一题了,直接把读进来的串排序,然后map++ 即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000;
map<string,int>cnt;
int N;
char ch[50];
string s;
inline bool my_cmp(char a,char b)
{
    return a<b;
}
int main()
{
//    freopen("1.sb","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%s",ch);
        int len=strlen(ch);
        sort(ch,ch+len,my_cmp);
        s=ch;
        printf("%d\n",cnt[s]++);
    }
}