2016"百度之星" - 资格赛（Astar Round1）-白红宇

2016"百度之星" - 资格赛（Astar Round1）

阅读量：7005 次

发布时间：2019-06-27

本文共 3998 字，大约阅读时间需要 13 分钟。

逆元 1001

求前缀哈希和逆元

#include 
     
      typedef long long ll;const int MOD = 9973;const int N = 1e5 + 5;int inv[MOD+5];int ha[N];char str[N];int n;void Inv(int n, int p) {    inv[1] = 1;    for (int i=2; i<=n; ++i) {        inv[i] = (ll) (p - p / i) * inv[p%i] % p;    }}void init_hash() {    ha[0] = 1;    for (int i=1; i<=n; ++i) {        ha[i] = (ll) ha[i-1] * (str[i] - 28) % MOD;    }}int main() {    Inv (MOD, MOD);    int q;    while (scanf ("%d", &q) == 1) {        scanf ("%s", str + 1);        n = strlen (str + 1);        init_hash ();        for (int i=0; i

dp 1002

状态转移方程：dp[i] = dp[i-1] + dp[i-2]，Java写大数

import java.math.*;import java.io.*;import java.util.*;public class Main {	public static void main(String[] args) {		// TODO Auto-generated method stub		BigInteger[] dp = new BigInteger[205];		dp[1] = BigInteger.ONE;		dp[2] = BigInteger.ONE.add(BigInteger.ONE);		for (int i=3; i<=200; ++i) {			dp[i] = dp[i-1].add(dp[i-2]);		}				Scanner cin = new Scanner (System.in);		int n;		while (cin.hasNext ()) {			n = cin.nextInt ();			System.out.println (dp[n]);		}	}		static class InputReader {        public BufferedReader reader;        public StringTokenizer tokenizer;        public InputReader(InputStream stream) {            reader = new BufferedReader(new InputStreamReader(stream), 32768);            tokenizer = null;        }        public String next() {            while (tokenizer == null || !tokenizer.hasMoreTokens()) {                try {                    tokenizer = new StringTokenizer(reader.readLine());                } catch (IOException e) {                    throw new RuntimeException(e);                }            }            return tokenizer.nextToken();        }        public int nextInt() {            return Integer.parseInt(next());        }    }}

字典树 1003

1、insert : 往神奇字典中插入一个单词2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串 字典树删除操作，按出现的次数，在前缀路径上依次删除，最后的扩展结点清空．

#include 
     
      #include 
      
       #include 
       
        const int N = 1e5 + 5;char oper[10];char str[35];const int NODE = N * 30;struct Trie {    int ch[NODE][26], val[NODE];    int sz;    void clear() {        memset (ch[0], 0, sizeof (ch[0]));        sz = 1;    }    int idx(char c) {        return c - 'a';    }    void insert(char *s) {        int u = 0;        for (int c, i=0; s[i]; ++i) {            c = idx (s[i]);            if (!ch[u][c]) {                memset (ch[sz], 0, sizeof (ch[sz]));                val[sz] = 0;                ch[u][c] = sz++;            }            u = ch[u][c];            val[u]++;        }    }    void del(char *s, int num) {        int u = 0;        for (int c, i=0; s[i]; ++i) {            c = idx (s[i]);            u = ch[u][c];            val[u] -= num;        }        memset (ch[u], 0, sizeof (ch[u]));    }    int _search(char *t) {        int u = 0;        for (int c, i=0; t[i]; ++i) {            c = idx (t[i]);            if (!ch[u][c]) {                return 0;            }            u = ch[u][c];        }        return val[u];    }};Trie trie;int main() {    int n;     while (scanf ("%d", &n) == 1) {        trie.clear ();        for (int i=0; i
        
          0) {                    trie.del (str, cnt);                }            } else {                int cnt = trie._search (str);                if (cnt > 0) {                    puts ("Yes");                } else {                    puts ("No");                }            }        }    }    return 0;}

STL 1004

map或者双hash

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;const int N = 1e6 + 10;const int MOD = 1e9 + 7;char str[45];int a[45];std::map
          
            mp;int main() { int n; scanf ("%d", &n); mp.clear (); string str; for (int i=0; i
           
            > str; sort (str.begin (), str.end ()); printf ("%d\n", mp[str]); mp[str]++; } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/5493006.html

你可能感兴趣的文章