腾讯2017暑期实习生编程

第一题不说了，区间dp

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<string>
 4 #include<cstring>
 5  
 6 using namespace std;
 7  
 8 #define N 1005
 9  
10 int dp[N][N];
11 char s[N];
12 int le;
13  
14 int dfs(int l,int r)
15 {
16     if(dp[l][r] != -1) return dp[l][r];
17     if(l == r) return dp[l][r] = 1;
18     if(l + 1 == r){
19         if(s[l] == s[r] ) return 2;
20         else return 1;
21     }
22     if(l > r) return 0;
23     if(s[l] == s[r]) return dp[l][r] = dfs(l + 1,r - 1) + 2;
24     dp[l][r] = max( dfs(l + 1,r),dfs(l,r - 1) );
25     return dp[l][r];
26 }
27  
28 int main()
29 {
30     while(scanf("%s",s)!=EOF)
31     {
32         le = strlen(s);
33         memset(dp,-1,sizeof(dp));
34         dfs(0,le - 1);
35         printf("%d
",le - dp[0][le - 1]);
36     }
37     return 0;
38 }

View Code

第二题：

http://www.nowcoder.com/profile/495736/test/3572151/44803#summary

我是倒着把大写字母移到最后的，不过看讨论有更好的方案：

1.直接输出

2.正常从头开始，遇到大写字母就把后面所有的数往前挪一位。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<string>
 4 #include<cstring>
 5  
 6 using namespace std;
 7  
 8 #define N 1005
 9  
10 char s[N];
11 int le;
12  
13  
14 int main()
15 {
16     while(scanf("%s",s)!=EOF)
17     {
18         le = strlen(s);
19         int i,j;
20         for(i = le - 1;i >= 0;i--){
21             if(s[i] >= 'A' && s[i] <= 'Z'){
22                 for(j = i + 1;j < le;j++){
23                     if(s[j] >= 'A' && s[j] <= 'Z'){
24                         break;
25                     }
26                     swap(s[j],s[j-1]);
27                 }
28             }
29         }
30         printf("%s
",s);
31     }
32     return 0;
33 }

View Code

第三题：

排序 + 处理

当时脑子不知道怎么想的，竟然没考虑到有数字相同，那么最小值应该为0，，，，

[编程题]有趣的数字

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？

输入描述:

输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1,a2...an - 需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。

输入例子:

6
45 12 45 32 5 6

输出例子:

1 2

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 
 9 #define N 100005
10 #define ll long long
11 
12 ll a[N];
13 ll n;
14 ll cmi,cma;
15 ll chami;
16 
17 struct PP{
18     ll v;
19     ll c;
20 }B[N],te;
21 
22 int main()
23 {
24     //freopen("in.txt","r",stdin);
25     while(scanf("%lld",&n)!=EOF)
26     {
27         ll i,j;
28         cmi = cma = 0;
29         for(i = 1;i <= n;i++){
30             scanf("%lld",&a[i]);
31         }
32         sort(a + 1, a + 1 + n);
33         ll cl,cr;
34         cl = cr = 1;
35         if(a[1] == a[n]){
36             cmi = cma = n * (n - 1) / 2;
37         }
38         else{
39             for(i = n - 1;i >= 1;i--){
40                 if(a[i] == a[n]) cr++;
41                 else break;
42             }
43             for(i = 2;i <= n;i++){
44                 if(a[i] == a[1]) cl++;
45                 else break;
46             }
47             cma = cl * cr;
48             chami = a[n] - a[1];
49             for(i = 2;i <= n;i++){
50                 chami = min(chami,a[i] - a[i - 1]);
51             }
52             for(i = 1;i <= n;i++){
53                 for(j = i - 1;j >= 1;j--){
54                     if(chami == a[i] - a[j]){
55                         cmi++;
56                     }
57                     else{
58                         break;
59                     }
60                 }
61             }
62         }
63         printf("%lld %lld
",cmi,cma);
64     }
65     return 0;
66 }