2016 Personal Training #11 Div.2 B G J

UVALive 5963

题意：给你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");
      }
    }
  }
}

题意：给你一个字符串然后输出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);
  }
  }
}

题意：给定一个数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]);
  }
}