题目描述：
水题，三种方案求最小值即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 int main () 7 { 8 int n, m, q, p, t; 9 scanf ("%d", &t); 10 while (t --) 11 { 12 scanf ("%d %d %d %d", &n, &m, &p, &q); 13 int num1, num2, ans; 14 num1 = p * n; 15 num2 = n / m * q; 16 ans = n % m * p; 17 if (ans > q) 18 num2 += q; 19 else 20 num2 += ans; 21 printf ("%d ", min(num1, num2)); 22 } 23 return 0; 24 }
题目描述：
在一个长串里面找到三个不交叉的子串，这三个不交叉的子串按照顺序相连与"anniversary"相等，问能不能求出来三个这样的子串？
解题思路：
暴力水题，"anniversary"有11个字母，在10个间隔里面枚举出两个间隔，然后在长串中按照顺序找这三个子串。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 110; 7 char str[maxn], S[20] = "anniversary"; 8 bool solve (); 9 int main () 10 { 11 int t; 12 scanf ("%d", &t); 13 while (t --) 14 { 15 scanf ("%s", str); 16 if (solve()) 17 printf("YES "); 18 else 19 printf ("NO "); 20 } 21 return 0; 22 } 23 bool solve () 24 { 25 int len = strlen(str), a[10]; 26 a[0] = 0; 27 a[3] = 11; 28 for (a[1]=1; a[1]<10; a[1]++) 29 for (a[2]=a[1]+1; a[2]<11; a[2]++) 30 { 31 int num = 0; 32 for (int k=0; k<len;) 33 { 34 int i = a[num], j = a[num+1]; 35 while (S[i] != str[k] && k<len) 36 k ++; 37 while (S[i]==str[k] && i<j && k<len) 38 { 39 i ++; 40 k ++; 41 } 42 if (i == j) 43 num ++; 44 } 45 if (num == 3) 46 return true; 47 } 48 return false; 49 }
题目描述：
有一组数为3*n*(n-1),(n>=1)。给出一个m，问至少需要这组数里面的几个相加才能等于m。
解题思路：
这个题目成功把Bestcoder变身成为Hackcoder，出题人题面上给出的两个实例推导，以及Simple Input都在有意无意的想表明这个题目就是贪心，贪心也可以过掉，真是出题良心啊！！！！题目做不出来，也可以让你Hack拿高分。真是感动到死。
只要了解了三角形数，这个也是水题。任何一个自然数都可以用三个三角形数相加得来，在枚举由两个数组合而来的时候，可以用经典的相向搜索把复杂度变为O(n),O(n*n)的复杂度TLE估计稳稳的。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 18500; 7 int a[maxn]; 8 void init () 9 { 10 for (int i=0; i<maxn; i++) 11 a[i] = 3*i*(i-1)+1; 12 } 13 int solve (int n) 14 { 15 int ans = n % 6; 16 if (ans == 1) 17 { 18 for (int i=0; i<maxn; i++) 19 if (a[i] == n) 20 return 1; 21 return 7; 22 } 23 if (ans == 2) 24 { 25 int j = maxn - 1; 26 for (int i=1; i<=j; i++) 27 { 28 while (a[i]+a[j]>n) 29 j --; 30 if (a[i] + a[j] == n) 31 return 2; 32 } 33 return 8; 34 } 35 return (n - 1) % 6 + 1; 36 } 37 int main () 38 { 39 int t; 40 scanf ("%d", &t); 41 init (); 42 while (t --) 43 { 44 int n; 45 scanf ("%d", &n); 46 printf ("%d ", solve(n)); 47 } 48 return 0; 49 }
题目描述：
给出一个无环，无重边的二分图，问最多加几条边可以使所给二分图变成一个完全二分图。
解题思路：
求出连通块，并对连通块中的节点进行标记，然后把每个连通块中不同的节点分别放在x，y集合中，使得||x| - |y||最小即可，最终答案就是x*y-m。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 10010; 7 struct node 8 { 9 int to, next; 10 } edge[maxn*20]; 11 int head[maxn], vis[maxn], used[maxn]; 12 int x, y, tot, n, m; 13 void init () 14 { 15 tot = x = y = 0; 16 memset (used, 0, sizeof(used)); 17 memset (head, -1, sizeof(head)); 18 memset (vis, -1, sizeof(vis)); 19 } 20 void Add (int from, int to) 21 { 22 edge[tot].to = to; 23 edge[tot].next = head[from]; 24 head[from] = tot ++; 25 } 26 void dfs (int u, int c, int &a, int &b) 27 { 28 b ++; 29 if (c) 30 a ++; 31 vis[u] = c; 32 for (int i=head[u]; i!=-1; i=edge[i].next) 33 { 34 int v = edge[i].to; 35 if (vis[v] == -1) 36 dfs(v, c^1, a, b); 37 } 38 } 39 int main () 40 { 41 int t; 42 scanf ("%d", &t); 43 while (t --) 44 { 45 init (); 46 scanf ("%d %d", &n, &m); 47 for (int i=0; i<m; i++) 48 { 49 int u, v; 50 scanf ("%d %d", &u, &v); 51 used[u] = used[v] = 1; 52 Add (u, v); 53 Add (v, u); 54 } 55 int num = 0; 56 for (int i=1; i<=n; i++) 57 { 58 int a = 0; 59 int b = 0; 60 if (!used[i]) 61 { 62 num ++; 63 continue; 64 } 65 if (vis[i] == -1) 66 dfs (i, 0, a, b); 67 b -= a; 68 x += max (a, b); 69 y += min (a, b); 70 if (x > y) 71 swap (x, y); 72 } 73 if (num >= y - x) 74 { 75 num -= y - x; 76 x = y; 77 } 78 x += num / 2; 79 y += num - num / 2; 80 printf ("%d ", x*y-m); 81 } 82 return 0; 83 }