今天做的是辽宁2010年的省赛题。题目难度比昨天容易了不少。悲哀的是，我们队只把前四道水题做出来了，
后面还有两道相对容易的题没做出来。
A ：
A题是我敲的，开始看到题的时候还愣了一下，后面看到hint的提示，才发现如此之水。题意大致是给你N个盒子，
盒子里面放着一样东西，如果是餐具就输出，注意下格式就可以，餐具在hint中给出了，才四种...
#include#include #include const char table[][15] = { "bowl", "knife", "fork", "chopsticks"};int main(){ int n, cnt; char str[15]; while(scanf("%d", &n) != EOF) { cnt = 0; while(n --) { scanf("%s", str); for(int i = 0; i < 4; i ++) { if(strcmp(str, table[i]) == 0) { if(cnt ++) printf(" "); printf("%s", str); break; } } } printf("\n"); } return 0;}
B ：
这道题是隽遒学弟敲的，他跟我说大致题意是给出N对关系，判断给定的两者的长幼关系，大致就是求到公共祖先的距离，然后按照题意输出一句话来表示两者的关系。
C：
这道题是陈兴做的，一道很纯的模拟题。将四个数字按照题意输出，先弄个表，然后打印就行了。
#include#include #include using namespace std;string dig[10][4];void Prepare(){ dig[0][0] = " _ "; dig[0][1] = "| |"; dig[0][2] = "|_|"; dig[1][0] = " "; dig[1][1] = " |"; dig[1][2] = " |"; dig[2][0] = " _ "; dig[2][1] = " _|"; dig[2][2] = "|_ "; dig[3][0] = " _ "; dig[3][1] = " _|"; dig[3][2] = " _|"; dig[4][0] = " "; dig[4][1] = "|_|"; dig[4][2] = " |"; dig[5][0] = " _ "; dig[5][1] = "|_ "; dig[5][2] = " _|"; dig[6][0] = " _ "; dig[6][1] = "|_ "; dig[6][2] = "|_|"; dig[7][0] = " _ "; dig[7][1] = " |"; dig[7][2] = " |"; dig[8][0] = " _ "; dig[8][1] = "|_|"; dig[8][2] = "|_|"; dig[9][0] = " _ "; dig[9][1] = "|_|"; dig[9][2] = " _|";}int main(){ int a[4]; Prepare(); while(scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]) != EOF) { for(int i = 0; i < 3; i++) { for(int j = 0; j < 4; j++) { cout << dig[a[j]][i]; } putchar('\n'); } } return 0;}
D：
这道题是我和隽遒学弟想出来的思路，然后陈兴敲的，因为我们两个都不会用STL的map，蛋疼，等会学一下，比我想写的hash简单方便多了。
题目给出三个集合，每个集合有一些字符串，要输出同在A和B中，但不在C中的字符串，即A并B - C。先将A的元素插入hash表中，再读入B，
再将C的元素插入hash表中，然后扫一边B，不在C表在A表中的输出。
#include#include
E：
这道题比赛的时候想了很久还是不会。
F：
AC自动机 + DP，隽遒学弟用Rabin-Karp写没过。
#include#include const int MAXN = 10010;const int LEN = 32;const int X = 10010;//定义字典树struct Trie{ int end; int v; struct Trie *son[26];};int n, nx;int buf_cnt;struct Trie *root, buf[MAXN * LEN];int max[X];char x[X];//新建结点struct Trie *New_node(){ struct Trie *tmp = &buf[buf_cnt ++]; tmp -> end = 0; tmp -> v = 0; for(int i = 0; i < 26; i ++) tmp -> son[i] = 0; return tmp;}//插入字符串void insert(char *s, int v){ struct Trie *cur = root; for(int i = 0; s[i] != 0; i ++) { int id = s[i] - 'a'; if(cur -> son[id] == NULL) cur -> son[id] = New_node(); cur = cur -> son[id]; } cur -> end = 1; cur -> v = v;}//翻转字符串void reversal(char *s){ int i = 0, j = strlen(s); j --; while(i < j) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i ++, j --; }}void query(int i){ struct Trie *cur = root; for(int j = i; x[j] != 0; j --) { int id = x[j] - 'a'; if(cur -> son[id]) { if(cur -> son[id] -> end) { if(max[j - 1] != -1) { if(max[j - 1] + cur -> son[id] -> v > max[i]) max[i] = max[j - 1] + cur -> son[id] -> v; } } cur = cur -> son[id]; } else break; }}int main(){ //freopen("test0.in", "r", stdin); //freopen("test.out", "wb", stdout); x[0] = 0; while(scanf("%d %s", &n, x + 1) != EOF) { nx = strlen(x + 1); buf_cnt = 0; root = New_node(); for(int i = 0; i < n; i ++) { char s[LEN]; int v; scanf("%s %d", s, &v); reversal(s); insert(s, v); } max[0] = 0; for(int i = 1; i <= nx; i ++) { max[i] = -1; query(i); } printf("%d\n", max[nx]); } return 0;}
G：
最想吐槽的是这道题，我还傻傻的去找规律，最后问了斌牛说打表只需几秒就行。亲和数，真因子之和等于对方的一对数。开始一直在想5000000的
数据范围怎么搞定，后面发现无法搞定。我还是图样图森破...
打表和筛选素数的方法类似：
#include#include #include #include using namespace std;const int MAXN = 5000000;int sum[MAXN + 10];int main(){ freopen("data.txt", "w", stdout); int i, j; for (i = 0; i <= MAXN ; i ++) sum[i] = 1; //1是所有数的真因数所以全部置1 for (i = 2; i + i <= MAXN; i ++) { j = i + i; //因为真因数，所以不能算本身，所以从它的2倍开始 while (j <= MAXN) { //将所有i的倍数的位置上加i sum[j] += i; j += i; } } for (i = 220; i <= MAXN; i++) //扫描，O（N）。 { // 一次遍历，因为知道最小是220和284因此从220开始 if (sum[i] > i && sum[i] <= MAXN && sum[sum[i]] == i) { //去重，不越界，满足亲和 cout << i << ", " << sum[i] << "," << endl; } } return 0;}
打出表之后，直接判断这些数在不在给定的[a,b]内就行了，500万内的亲和数对也不多，才71对。
#include#include #include const int pt[][2] ={ 220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368, 10744, 10856, 12285, 14595, 17296, 18416, 63020, 76084, 66928, 66992, 67095, 71145, 69615, 87633, 79750, 88730, 100485, 124155, 122265, 139815, 122368, 123152, 141664, 153176, 142310, 168730, 171856, 176336, 176272, 180848, 185368, 203432, 196724, 202444, 280540, 365084, 308620, 389924, 319550, 430402, 356408, 399592, 437456, 455344, 469028, 486178, 503056, 514736, 522405, 525915, 600392, 669688, 609928, 686072, 624184, 691256, 635624, 712216, 643336, 652664, 667964, 783556, 726104, 796696, 802725, 863835, 879712, 901424, 898216, 980984, 947835, 1125765, 998104, 1043096, 1077890, 1099390, 1154450, 1189150, 1156870, 1292570, 1175265, 1438983, 1185376, 1286744, 1280565, 1340235, 1328470, 1483850, 1358595, 1486845, 1392368, 1464592, 1466150, 1747930, 1468324, 1749212, 1511930, 1598470, 1669910, 2062570, 1798875, 1870245, 2082464, 2090656, 2236570, 2429030, 2652728, 2941672, 2723792, 2874064, 2728726, 3077354, 2739704, 2928136, 2802416, 2947216, 2803580, 3716164, 3276856, 3721544, 3606850, 3892670, 3786904, 4300136, 3805264, 4006736, 4238984, 4314616, 4246130, 4488910, 4259750, 4445050,};int main(){ int a, b; while(scanf("%d%d", &a, &b) != EOF) { int cnt = 0; for(int i = 0; i < 71; i ++) { if(pt[i][0] >= a && pt[i][0] <= b && pt[i][1] >= a && pt[i][1] <= b) { cnt ++; } } printf("%d\n", cnt); } return 0;}
H：
推出公式是 x^2 - dy^2 = 1，传说中的佩尔方程，不会求他的最小解...
I：
#include#include #include typedef long long LL;LL PowMod(LL a, LL n, LL mod){ LL ret = 1; while(n) { if(n & 1) ret = ret * a % mod; a = a * a % mod; n >>= 1; } return ret;}LL n, m, k;int main(){ while(scanf("%lld%lld%lld", &n, &m, &k) != EOF) { if(n % 2 == 0) n ++; LL t = PowMod(2, m, n); if(t == 0) t = n; for(int i = 1; i <= k; i ++) { if(i != 1) printf(" "); LL ans = t * i % n; if(ans == 0) ans = n; printf("%lld", ans); } printf("\n"); } return 0;}