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

 

逆元 1001 Problem A

求前缀哈希和逆元

#include <bits/stdc++.h>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<q; ++i) {int l, r; scanf ("%d%d", &l, &r);printf ("%d\n", (ll) ha[r] * inv[ha[l-1]] % MOD);}}return 0; }

dp 1002 Problem B

状态转移方程：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 stubBigInteger[] 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 Problem C

1、insert : 往神奇字典中插入一个单词2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

字典树删除操作，按出现的次数，在前缀路径上依次删除，最后的扩展结点清空． #include <cstdio> #include <cstring> #include <algorithm>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<n; ++i) {scanf ("%s%s", oper, str);if (oper[0] == 'i') {trie.insert (str);} else if (oper[0] == 'd') {int cnt = trie._search (str);if (cnt > 0) {trie.del (str, cnt);}} else {int cnt = trie._search (str);if (cnt > 0) {puts ("Yes");} else {puts ("No");}}}}return 0; }

STL 1004 Problem D

map或者双hash

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

 

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

总结

以上是生活随笔为你收集整理的2016百度之星 - 资格赛（Astar Round1）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。