2019杭电多校第5场总结

换到了一支纯女生队伍

?前面几次杭电多校一直爆零。虽然这回倒数，倒也出题了。

?5个小时基本上只看了一道题，还是到找规律题。

?那么就进入正题吧！

?首先是我唯一做出的题1007.

?题意大概是给出n，x，y让你求满足下列条件的n的全排列的个数。

1. p1=x?
2. pn=y
3. 对于所有的1<=i<n,|pi-pi+1|<=2
   

   ?看到这道题提交ac的人的时间大多0ms、15ms这怕是到找规律题。然而我太菜了找规律找了好久。

   
   

   ?首先发现的是对于x前的数字和y后的数字和x+1，y-1在排列里是固定的。什么意思呢？就比如n=12,x=4,y=10,对于x前的数以及x+1，(1,2,3,5)只能4,2,1,3,5这么排。对y后的数字和y-1,(11,12,9)只能9,11,12,10这么排。也就是这些地方都只有唯一的可能。而中间那些(6,7,8),则可以按照第3个条件计算个数。

   
   

   ?所以主要任务就是找出中间那些可活动数字的个数与排列数的关系。

   
   

   ?我就手动开始打表找规律。

   
   

   ?1 = 1

   
   

   ?2 = 2

   
   

   ?3 = 3

   
   

   ?4 = 4

   
   

   ?5 = 6

   
   

   ?6 = 9

   
   

   ?7 = 13

   
   

   ?8 = 19

   
   

   ?9 = 28

   
   

   ?10 = 41

   
   

   ?11 = 60

   
   

   ?看着数字脑子疼看都看不出来，于是叫队友帮忙，她一看f[n]=f[n-1]+f[n-3]

   
   

   ?试了一波样例吻合了。于是当然是开心 冲动的交题啦。结果收获首wa。

   
   

   ?想应该是啥特殊情况，忘说了x==1和y==n的时候中间可活动数字个数要特判，然而我wa的不是这里。一波瞎搞又提交了两次又收获2wa??。
   

   ?这个时候队友发现当中间没有数字可活动时且y与x只相差1时，是没有解的。

   
   

   ?于是特判一波终于ac。

   
   

   ?代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double lb;
const int maxn=5;
const int mod=998244353;
const double eps=1e-10;
const ll inv2=499122177;
ll n,x,y,Ans,fn[100005];
void clan()
{
    fn[0]=1;
    fn[1]=1;
    fn[2]=2;
    fn[3]=3;
    fn[4]=4;
    for(ll i=5;i<=100005;i++)
    {
        fn[i]=(fn[i-1]+fn[i-3])%mod;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    clan();
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&x,&y);
        if(x==1)
            x=0;
        if(y==n)
            y=n+1;
        Ans=y-2-x-1;
        if(Ans<0)
            Ans=0;
        if(Ans==0&&y-x==1)
            printf("0\n");
        else
            printf("%lld\n",fn[Ans]%mod);
    }
    return 0;
}

 另一队友在看1006扩展kmp，最近学长刚上过，然鹅，没人做过这个专题。。。虽然知道是kmp却不会用。。。。die

 1005看了一下感觉可做，然而时间来不及了。到时候补了再说吧。

 我好菜??

2019杭电多校第5场总结

原文：https://www.cnblogs.com/like-a-dog/p/11304791.html