A：给你n个数（正负都有），让你添加 n-1个符号，使得它能够被 k整除
解题思路：显然我们把所有树MOD k 然后 -a[i] or + a[i] 背包处理就行了
解题代码：
1 // File Name: a.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月11日 星期四 20时09分52秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int a[10005]; 28 int dp[10005][102]; 29 int main(){ 30 int n, m; 31 scanf("%d %d",&n,&m); 32 for(int i = 1;i <= n;i ++) 33 { 34 scanf("%d",&a[i]); 35 a[i] = a[i] % m; 36 } 37 memset(dp,0,sizeof(dp)); 38 dp[1][abs(a[1])] = 1; 39 for(int i = 2;i <= n;i ++) 40 { 41 for(int j = 0 ;j < m;j ++) 42 { 43 if(dp[i-1][j]) 44 { 45 dp[i][abs(j-a[i])%m] = 1; 46 dp[i][abs(j+a[i])%m] = 1; 47 } 48 } 49 } 50 if(dp[n][0]) 51 printf("Divisible "); 52 else printf("Not divisible "); 53 54 return 0; 55 }
F：给你n个字符串，要你在每个字符串前面加空格，每个字符串的空格等于与前面数的最大相同前缀，如果 num[i] > num[i-1] 则 num[i] = num[i-1] + 1;
解题代码：
1 // File Name: f.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月11日 星期四 22时33分10秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 28 char str[100005][20]; 29 int solve(int k ) 30 { 31 int mi = min(strlen(str[k]),strlen(str[k-1])); 32 for(int i = 0;i <= 15;i ++) 33 { 34 if(str[k][i] != str[k-1][i]) 35 return i; 36 } 37 return mi; 38 } 39 int hs[100004]; 40 int main(){ 41 memset(hs,0,sizeof(hs)); 42 int t = 1 ; 43 hs[1] = 0 ; 44 while(gets(str[t])) 45 { 46 if(t!= 1) 47 { 48 int temp = solve(t); 49 if(temp == 0 ) 50 { 51 hs[t] = 0 ; 52 }else{ 53 else if(temp == hs[t-1]) 54 { 55 hs[t] = hs[t-1]; 56 } 57 else hs[t] = hs[t-1] + 1; 58 } 59 } 60 t++; 61 } 62 for(int i = 1;i <= t;i ++) 63 { 64 for(int j = 1 ;j <= hs[i];j ++) 65 printf(" "); 66 puts(str[i]); 67 } 68 69 return 0; 70 }
L:给你n头牛，每头牛有 wi（重量） 和 si（承受值） 两个值 ，现在需要你安排 n头牛迭在一起 每个牛的崩溃值为 它上面所有的牛的重量减去它本身的承受值。
解题思路：假设 w1 s1 w2 s2 编号1的牛放上面的最优解，a = sum - s1 , b = sum +w1 - s2 ,如果交换以后可得 a'= sum - s2 , b' = sum + w2 - s1
可知 max(a,b) < max(a',b') 讨论一下情况就可以知道 是要按照 wi + si 排序了
解题代码：
1 // File Name: L.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月11日 星期四 20时45分36秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 struct node{ 28 LL x, y ; 29 }a[50005]; 30 bool cmp(node a, node b) 31 { 32 return a.x + a.y < b.x + b.y; 33 } 34 int main(){ 35 LL n ; 36 scanf("%lld",&n); 37 for(int i = 1;i <= n;i ++) 38 { 39 scanf("%lld %lld",&a[i].x,&a[i].y); 40 } 41 sort(a+1,a+1+n,cmp); 42 LL sum = 0 ; 43 LL ans = -2*1e9 ; 44 for(int i = 1;i <= n;i ++ ) 45 { 46 if(sum -a[i].y > ans) 47 { 48 ans = sum - a[i].y; 49 } 50 sum += a[i].x ; 51 } 52 printf("%lld ",ans); 53 return 0; 54 }