7个月没有刷题了，现在真的是菜到爆炸，所以来牛客水一水编程题。
一、构造回文
题意：
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子1:
abcda
google
输出例子1:
2
2
题解：
题目要求的是，最少删除多少个字符可以让剩下的串是回文串，其实就是要求字符串中的最长回文子串是多少。
我们可以考虑一下回文串的特点，那就是前半部分必须和后半部分的颠倒是相同的。那我们不妨创建一个新字符串，把原串给颠倒回来，这样我们就变成了正序匹配了。
意思就是再定义一个字符串tmp为原串的翻转，然后求一下原串和tmp的最长公共子序列即可。
代码：
#include<stdio.h>
#include<string.h>
int dp[1005][1005];
int max(int a,int b){
return a>b?a:b;
}
int main()
{
char s[1005],tmp[1005];
int len;
while(scanf("%s",s)!=EOF)
{
len=strlen(s);
for(int i=0;i<len;i++)tmp[i]=s[len-i-1];
for(int i=1;i<=len;i++)
{
for(int j=1;j<=len;j++)
{
if(s[i-1]==tmp[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
printf("%d\n",len-dp[len][len]);
}
}
二、字符移位
题意：
小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出移位后的字符串。
输入例子1:
AkleBiCeilD
输出例子1:
kleieilABCD
题解：
这题唯一的技巧就是逆向遍历（避免大写字母内部顺序被打乱），剩下的都是模拟了。我们以末尾为起点向左进发，遇到大写字母就给它往右搬就可以了。
代码：
#include<stdio.h>
#include<string.h>
int islower(char a)
{
if(a>='a'&&a<='z')return 1;
else return 0;
}
int isupper(char a)
{
if(a>='A'&&a<='Z')return 1;
else return 0;
}
int main()
{
char s[1005];
while (scanf("%s",s)!=EOF)
{
int n,j;
int len=strlen(s);
for(int i=len-1;i>0;i--)
{
if(islower(s[i]))
{
j=i;
while(islower(s[j])&&j>=1)
{
j--;
}
if(j==0&&islower(s[j]))
{
break;
}
if(isupper(s[j]))
{
char temp=s[j];
for(int k=j;k<i;k++)s[k]=s[k+1];
s[i]=temp;
}
}
}
printf("%s\n",s);
}
return 0;
}
三、有趣的数字
题意：
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
输入描述:
输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1,a2…an - 需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.
输出描述:
对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
输入例子1:
6
45 12 45 32 5 6
输出例子1:
1 2
题解：
首先看一下数据量，n是十万量级，O(n^2)的算法全部gg，所以乱序肯定是不可取的，开局应该先快排一下，变成有序的序列。
先考虑差最大，很显然的是最后一个元素和第一个元素的差一定是最大的。所以假如有a个元素和第一个元素相等，有b个元素和最后一个元素相等，那么结果就是a×b了。
但是事实上少考虑了一种情况，那就是第一个元素和最后一个元素相等的时候，这种情况下a=n,b=n,a×b=n^2显然是不对的（因为a和b计数有重叠部分），所以需要特判：当第一个元素=最后一个元素时，答案应该是在n个中任意取2个的种数：Cn2=n×(n-1)/2
再考虑差最小，同样也需要分两种情况：序列中无重复数字、序列中有重复数字。
假如序列中无重复数字，那只需要跑一遍序列，分别计算相邻两数的差，同时计一下数就好了；
假如序列中有重复数字，那我们就可以检查各个数字的重复个数，最后使用Σ(ki*(ki-1)/2)即可。(ki是指i这个数的数量)
代码：
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
return *(int *)a - *(int *)b;
}
int main()
{
int a[100005],n,ansx=0,ansy=0;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)scanf("%d",&a[i]);
qsort(a,n,sizeof(a[0]),cmp);
int tmpa=0,tmpb=0,tmpc=a[n-1]-a[0],k=0;
while(a[k]==a[0])
{
tmpa++;
k++;
}
k=n-1;
while(a[k]==a[n-1])
{
tmpb++;
k--;
}
if(a[n-1]!=a[0])ansx=tmpa*tmpb;
else ansx=n*(n-1)/2;
for(int i=1;i<n;i++)
{
if(a[i]-a[i-1]<tmpc)
{
ansy=1;
tmpc=a[i]-a[i-1];
}
else if(a[i]-a[i-1]==tmpc)ansy++;
}
if(tmpc==0)
{
ansy=0;k=0;int b=0;
while(k<n)
{
while(b<n&&a[k]==a[b])b++;
ansy+=(b-k)*(b-k-1)/2;
k=b;
}
}
printf("%d %d\n",ansy,ansx);
}
}
