题意：给你n个数，如果这n个数满足：例如n=4第一个数前面有0个数后面有三个数那么这第一个位置数可以为0或者3，第二个位置可以为1或2等等。给出的n个数满足则输出yes否则no
思路：将所有的数转换为前一半n/2的数，然后遍历数看看是否都出现两次，当然还有奇偶判断毕竟中间那个数可能只有一个。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
int a[1000005],vis[1000005];
int main()
{
int n,t,Case=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
vis[min(a[i],n-1-a[i])]++;
}
int flag=0;
for(int i=0;i<(n-1)/2;i++)
{
if(vis[i]!=2)
{
flag=1;break;
}
}
printf("Case %d: ",Case++);
if(flag) printf("no\n");
else
{
if(n%2)
{
if(vis[(n-1)/2]!=1)
printf("no\n");
else printf("yes\n");
}
else
{
if(vis[n/2-1]!=2) printf("no\n");
else printf("yes\n");
}
}
}
}
UVALive 5968
题意：给你一个字符串然后输出X/Y，X表示有多少个字符'S'后面跟着'S'，Y表示有多少个字符'S'后面连着其他字符并且最后连着一个'S'。
思路：直接遍历处理即可。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
char str[105];
int vis[105];
int main()
{
int n;
while(~scanf("%d",&n))
{
int Case=1;
for(int k=0;k<n;k++)
{
cin>>str;
int len=strlen(str);
int a=0,b=0;memset(vis,0,sizeof(vis));
for(int i=0;i<len;i++)
{
if(vis[i]) continue;
if(str[i]=='S')
{
vis[i]=1;
for(int j=i+1;j<len;j++)
{
if(str[j]=='S')
{
if(j==i+1) a++;
else
b++;
break;
}
if(j==len-1) b++;
vis[j]=1;
}
}
}
printf("Case %d: %d / %d\n",Case++,a,b);
}
}
}
UVALive 5971
题意：给定一个数n，求1~n这些数构成的排列并且排列中不允许有x和x+1连在一起，输出这样的排列有多少个。
思路：模拟几次之后发现是有规律的即公式：x[i-2]*（i-2）+x[i-1]*(i-1),其中x[1]=1,x[2]=1;
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
LL M=1000000007;
LL a[1000005];
int main()
{
int t,n,Case=1;
a[1]=1;a[2]=1;
for(int i=3;i<=1000001;i++)
{
a[i]=((a[i-1]*(i-1))%M+(a[i-2]*(i-2))%M)%M;
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("Case %d: %lld\n",Case++,a[n]);
}
}