5/5
水了个资格赛，做了四题，后来发现最后一题是个大水题，所以补了个题解(/▽╲)！
题A hdu 5685
题意：略
题解：显然可以用线段树做啊！RE，哈哈哈，开大点，区间判不合法，又RE！！哈哈哈！！我竟无言以对，然后万般无奈之下只好用逆元来做了~~后来在hdu上交没有问题！！这可是百度之星啊！！！！！
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int maxn = 1e5 + 100, mod = 9973; 25 ll mul[maxn * 4]; 26 char s[maxn]; 27 28 void PU(int rt) { 29 mul[rt] = mul[rt * 2] * mul[rt * 2 + 1] % mod; 30 } 31 32 void build(int l, int r, int rt) { 33 if (l == r) { 34 mul[rt] = (s[l] - 28); 35 return; 36 } 37 int m = (l + r) / 2; 38 build(lson); 39 build(rson); 40 PU(rt); 41 } 42 43 ll query(int ql, int qr, int l, int r, int rt) { 44 if (ql <= l && r <= qr) { 45 return mul[rt]; 46 } 47 int m = (l + r) / 2; 48 ll ret = 1; 49 if (ql <= m) ret = ret * query(ql, qr, lson) % mod; 50 if (qr > m) ret = ret * query(ql, qr, rson) % mod; 51 return ret; 52 } 53 54 int main() { 55 // freopen("case.in", "r", stdin); 56 int q; 57 while (scanf("%d", &q) != EOF) { 58 scanf("%s", s + 1); 59 int n = strlen(s + 1); 60 build(1, n, 1); 61 for (int i = 0; i < q; i++) { 62 int l, r; 63 scanf("%d%d", &l, &r); 64 if (n == 0) puts(""); 65 else printf("%I64d\n", query(l, r, 1, n, 1)); 66 } 67 } 68 return 0; 69 } 代码君（线段树）
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int maxn = 1e5 + 100, mod = 9973; 25 ll inv[mod], mul[maxn]; 26 char s[maxn]; 27 28 ll quick(ll a, ll b, ll c) { 29 ll ret = 1; 30 while (b) { 31 if (b & 1) ret = ret * a % c; 32 b = b / 2; 33 a = a * a % c; 34 } 35 return ret; 36 } 37 38 void init() { 39 for (int i = 0; i < mod; i++) inv[i] = quick(i, mod - 2, mod); 40 } 41 42 int main() { 43 // freopen("case.in", "r", stdin); 44 init(); 45 int q; 46 while (scanf("%d", &q) != EOF) { 47 scanf("%s", s); 48 int n = strlen(s); 49 mul[0] = 1; 50 for (int i = 1; i <= n; i++) mul[i] = mul[i - 1] * (s[i - 1] - 28) % mod; 51 for (int i = 0; i < q; i++) { 52 int l, r; 53 scanf("%d%d", &l, &r); 54 printf("%I64d\n", mul[r] * inv[mul[l - 1]] % mod); 55 } 56 } 57 } 代码君（逆元）
题B hdu 5686
题意：略
题解：有个递推式：b[i] =sum{b[j] - 1} ，然后写个大数就可以过了~~
1 import java.math.BigDecimal; 2 import java.math.BigInteger; 3 import java.util.Scanner; 4 5 public class Main { 6 7 public static void main(String args[]) { 8 BigInteger[] b = new BigInteger[210]; 9 b[0] = b[1] = BigInteger.ONE; 10 for (int i = 2; i < 210; i++) { 11 b[i] = new BigInteger(i + ""); 12 for (int j = 2; j <= i - 2; j++) 13 b[i] = b[i].add(b[j].subtract(BigInteger.ONE)); 14 } 15 Scanner input = new Scanner(System.in); 16 while (input.hasNext() == true) { 17 int n = input.nextInt(); 18 if (n == 0) System.out.println(); 19 else System.out.println(b[n]); 20 } 21 } 22 23 } 代码君（Java）
题C hdu 5687
题意：略
题解：Trie树，删除就暴力删，插边过了，应该还可以优化，懒得再写了~~
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int maxn = 1e6 + 10; 25 int ch[maxn][26], sz; 26 bool isWord[maxn]; 27 char s[40]; 28 29 void init() { 30 sz = 1; 31 memset(ch[0], -1, sizeof ch[0]); 32 isWord[0] = false; 33 } 34 35 void insert() { 36 int u = 0, len = strlen(s); 37 for (int i = 0; i < len; i++) { 38 int id = s[i] - 'a'; 39 if (ch[u][id] == -1) { 40 memset(ch[sz], -1, sizeof ch[sz]); 41 isWord[sz] = false; 42 ch[u][id] = sz++; 43 } 44 u = ch[u][id]; 45 } 46 isWord[u] = true; 47 } 48 49 void change(int u) { 50 isWord[u] = false; 51 for (int i = 0; i < 26; i++) 52 if (ch[u][i] != -1) change(ch[u][i]); 53 } 54 55 void del() { 56 int u = 0, len = strlen(s); 57 for (int i = 0; i < len; i++) { 58 int id = s[i] - 'a'; 59 if (ch[u][id] == -1) return; 60 u = ch[u][id]; 61 } 62 change(u); 63 } 64 65 bool dfs(int u) { 66 if (isWord[u]) return true; 67 for (int i = 0; i < 26; i++) 68 if (ch[u][i] != -1) { 69 if (dfs(ch[u][i])) return true; 70 } 71 return false; 72 } 73 74 bool query() { 75 int u = 0, len = strlen(s); 76 for (int i = 0; i < len; i++) { 77 int id = s[i] - 'a'; 78 if (ch[u][id] == -1) return false; 79 u = ch[u][id]; 80 } 81 return dfs(u); 82 } 83 84 int main() { 85 // freopen("case.in", "r", stdin); 86 init(); 87 int T; 88 cin >> T; 89 while (T--) { 90 char op[20]; 91 scanf("%s%s", op, s); 92 if (op[0] == 'i') insert(); 93 if (op[0] == 'd') del(); 94 if (op[0] == 's') { 95 query() ? puts("Yes") : puts("No"); 96 } 97 } 98 return 0; 99 } 代码君
题D hdu 5688
题意：略
题解：排个序后用Trie记一下就过了，数据很水，可以用map来水~~
1 /*zhen hao*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <string> 8 #include <stack> 9 #include <set> 10 #include <map> 11 #include <iostream> 12 #include <algorithm> 13 using namespace std; 14 15 #define lson l, m, rt*2 16 #define rson m + 1, r, rt*2+1 17 #define xx first 18 #define yy second 19 20 typedef pair<int,int> pii; 21 typedef long long ll; 22 typedef unsigned long long ull; 23 24 const int maxn = 1e6 + 10; 25 int ch[maxn][26], sz, val[maxn]; 26 char s[50]; 27 vector<char> ns; 28 29 void init() { 30 sz = 1; 31 memset(ch[0], -1, sizeof ch[0]); 32 val[0] = 0; 33 } 34 35 int insert() { 36 int u = 0, len = ns.size(); 37 for (int i = 0; i < len; i++) { 38 int id = ns[i] - 'A'; 39 if (ch[u][id] == -1) { 40 memset(ch[sz], -1, sizeof ch[sz]); 41 val[sz] = 0; 42 ch[u][id] = sz++; 43 } 44 u = ch[u][id]; 45 } 46 return val[u]++; 47 } 48 49 int main() { 50 // freopen("case.in", "r", stdin); 51 init(); 52 int n; 53 cin >> n; 54 for (int i = 0; i < n; i++) { 55 scanf("%s", s); 56 int len = strlen(s); 57 for (int j = 0; j < len; j++) ns.push_back(s[j]); 58 sort(ns.begin(), ns.end()); 59 printf("%d\n", insert()); 60 } 61 } 代码君
题E hdu 5689
题意：给你n行，每行描述几个变量，[变量名] [操作符] [数值]，然后问你前面有多少个是和这一行所表示的变量的对应变量区间均有交集。
题解：解释一下样例以理解清楚题意：
第一个前面没有变量，所以输出unique；
第二个没有a变量，所以默认a 是[-inf,inf]，所以a有交集，c同理也有交集，所以和1有交集，输出1；
第三个b变量的区间是空集，所以和前面所有区间都没有交集；
第四个同理；
还有注意的是每一行的所有变量只存在一个区间，也就是如果a > 10，a < 9表示空集，然后只考虑整数，所以[9,10)表示空集；
当你理解题意之后发现是个大水题（实际上都是大水题）！！开一个结构体seg表示这个变量所占的区间，一开始设为[-inf,inf]，然后有一个变量表示这个区间存不存在，然后模拟一遍即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 1e3 + 100, inf = 1e5 + 10; 15 16 struct seg { 17 int l, r; 18 bool exist; 19 } S[maxn][30]; 20 21 map<string,int> mp; 22 int tot, n; 23 24 void init() { 25 tot = 0; 26 mp.clear(); 27 for (int i = 0; i < n; i++) { 28 for (int j = 0; j < 30; j++) { 29 S[i][j] = (seg){-inf, inf, true}; 30 } 31 } 32 } 33 34 int get_id(string s) { 35 if (mp.find(s) == mp.end()) return mp[s] = tot++; 36 else return mp[s]; 37 } 38 39 void set_seg(int i, int id, string op, int val) { 40 if (S[i][id].exist == false) return; 41 int l, r; 42 if (op == "==") l = r = val; 43 else if (op == "<") l = -inf, r = val - 1; 44 else if (op == ">") l = val + 1, r = inf; 45 else if (op == "<=") l = -inf, r = val; 46 else if (op == ">=") l = val, r = inf; 47 l = max(l, S[i][id].l); 48 r = min(r, S[i][id].r); 49 if (l > r) S[i][id].exist = false; 50 else S[i][id].l = l, S[i][id].r = r; 51 // cout << l << ' ' << r << ' ' << S[i][id].exist << endl; 52 } 53 54 bool check(int x, int y) { 55 for (int i = 0; i < tot; i++) { 56 if (S[x][i].exist == false || S[y][i].exist == false) return false; 57 int l = max(S[x][i].l, S[y][i].l); 58 int r = min(S[x][i].r, S[y][i].r); 59 if (l > r) return false; 60 } 61 return true; 62 } 63 64 int main() { 65 // freopen("case.in", "r", stdin); 66 scanf("%d", &n); 67 init(); 68 getchar(); 69 for (int i = 0; i < n; i++) { 70 string line, s, op; 71 int num; 72 getline(cin, line); 73 stringstream ss(line); 74 while (ss >> s >> op >> num) { 75 // cout << s << ' ' << op << ' ' << num << endl; 76 set_seg(i, get_id(s), op, num); 77 ss >> s; 78 } 79 bool ok = false; 80 for(int j = 0; j < i; j++) if (check(i, j)) { 81 if (ok) putchar(' '); 82 printf("%d", j + 1); 83 ok = true; 84 } 85 if (!ok) puts("unique"); else puts(""); 86 } 87 return 0; 88 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5531967.html
相关资源：数据结构—成绩单生成器