好久没有fst题了。。。比赛先A了前4题然后发现room里有人已经X完题了没办法只能去打E题，结果差一点点打完。。。然后C题fst掉了结果就掉rating 了。。。下面放题解

题目大意：给定n道题和时间t，每完成第i道题需花$5*i$ 分钟，求在$240-t$分钟内完成的最大题数。

直接模拟，求完成i道题所花时间$t_i+t\leq 240$ 的最大值

Code :

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int main(){ 7     int n,k; 8     scanf("%d%d",&n,&k); 9     k=240-k;10     for (int i=1;i<=n;i++) {11         k-=i*5;12         if (k<0) {13             printf("%d\n",i-1);14             return 0;15         }16     }17     printf("%d\n",n);18     return 0;19 }
         
        
       
      

题目大意：从北极点出发，按指令指示走，求指示是否合法，同时能否在最后走回北极点。

要求在北极点只能向南走，在南极点只能向北走。 直接模拟咯，然后判断是否在南北极点就完了。

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int main(){ 7     int n,d,t=0; 8     char o[20]; 9     scanf("%d",&n);10     for (int i=1;i<=n;i++) {11         scanf("%d%s",&d,o);12         switch(o[0]) {13             case 'S' :14                 t+=d;15                 break;16             case'N':17                 t-=d;18                 break;19         }20         if (t<0||t>20000) {printf("NO\n");return 0;}21         if (t==0||t==20000) {22             if (o[0]=='E'||o[0]=='W') {23                 puts("NO\n");return 0;24             }25         }26     }27     if (t==0) printf("YES\n");else puts("NO");28     return 0;29 }
         
        
       
      

题目大意：给定每场比赛的div以及rating升降，问结束时可能的最大rating

可以先2分分数然后判断是否合法，当然也可以求前缀和然后看div1的最低和div2的最高，然后吧div2的最高设为1899即可。（我TM吧数组开小了啊啊啊）

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define maxn 200010  7 int n,s[maxn],a[maxn]; 8 #define inf 1e9 9 int mn=inf,mx=-inf;10 int main(){11     scanf("%d",&n);12     for (int i=1;i<=n;i++) {13         scanf("%d%d",s+i,a+i-1);14         s[i]+=s[i-1];15     }16     for (int i=0;i
         
        
       
      

题目大意：放烟花，每条烟火向一个方向前进$t_i$步然后向$45^\circ$扩散出2条烟火，求一共染了多少格子。

考虑直接模拟，由于最多有$2^{30}$条轨迹看上去并不可行，但我们可以发现向上下左右最大只能扩展150个方块，也就是说去重之后最多只有$300*300*4$条路径，可以接受。去重后模拟即可。

Code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define maxn 330 7 int f[maxn][maxn][8]; 8 int b[maxn][maxn]; 9 int w[8][2]={
    {
    1,0},{
    1,1},{
    0,1},{-1,1},{-1,0},{-1,-1},{
    0,-1},{
    1,-1}};10 int main(){11     f[160][160][0]=1;12     int n;13     scanf("%d",&n);14     for (int l=1;l<=n;l++) {15         int t;16         scanf("%d",&t);17         for (int i=1;i<=320;i++) 18             for (int j=1;j<=320;j++) 19                 for (int k=0;k<8;k++) {20                     if (f[i][j][k]!=l) continue;21                     for (int l=1;l<=t;l++) 22                         b[i+w[k][0]*l][j+w[k][1]*l]=1;23                     f[i+w[k][0]*t][j+w[k][1]*t][(k+1)%8]=f[i+w[k][0]*t][j+w[k][1]*t][(k-1+8)%8]=l+1;24                 }25     }26     int sum=0;27     for (int i=1;i<=320;i++) 28         for (int j=1;j<=320;j++) sum+=b[i][j];29     printf("%d\n",sum);30     return 0;31 }
         
        
       
      

题目大意：给定一个字符串，每次求l～r中要删去多少字符才能使字符串中有2017而没有2016

很明显是个区间RMQ，考虑如何进行区间合并，考虑每个区间我们记录出现2017的所有子串需要删去的字符数（例如1的话就后面不能有6和7，但前面可以有0），然后就能非常复杂的转移了。。

Code：代码较糟请慢慢看。。。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define minn 210000 7 #define mink 19 8 int n,m; 9 char s[minn];/*10 string a[15];11 a[0]="2";12 a[1]="0";13 a[2]="1";14 a[3]="7";15 a[4]="6";16 a[5]="20";17 a[6]="01";18 a[7]="17";19 a[8]="201";20 a[9]="017";21 a[10]="2017";*/22 struct node {23     int f[11],s[5];24 };25 #define inf 100000026 node update(node x,node y) {27     node ans;28     for (int i=0;i<=10;i++) ans.f[i]=inf;29     ans.f[0]=min(ans.f[0],min(x.f[0]+y.s[1],y.f[0]+x.s[0]));30     ans.f[1]=min(ans.f[1],min(x.f[1]+y.s[2],x.s[1]+y.f[1]));31     ans.f[2]=min(ans.f[2],min(x.f[2]+y.s[3]+y.s[4],x.s[2]+y.f[2]));32     ans.f[3]=min(ans.f[3],min(x.f[3]+y.s[4],x.s[3]+y.f[3]+x.s[4]));33     ans.f[5]=min(ans.f[5],min(x.f[5]+y.s[2],min(x.s[0]+y.f[5],x.f[0]+y.f[1])));34     ans.f[6]=min(ans.f[6],min(x.f[6]+y.s[3]+y.s[4],min(x.s[1]+y.f[6],x.f[1]+y.f[2])));35     ans.f[7]=min(ans.f[7],min(x.f[7]+y.s[4],min(x.s[2]+y.f[7],x.f[2]+y.f[3])));36     ans.f[8]=min(ans.f[8],min(min(x.f[8]+y.s[3]+y.s[4],x.s[0]+y.f[8]),37                 min(x.f[5]+y.f[2],x.f[0]+y.f[6])));38     ans.f[9]=min(ans.f[9],min(min(x.f[9]+y.s[4],x.s[1]+y.f[9]),39                 min(x.f[6]+y.f[3],x.f[1]+y.f[7])));40     ans.f[10]=min(ans.f[10],min(min(x.f[10]+y.s[4],x.s[0]+y.f[10]),41                 min(x.f[0]+y.f[9],min(x.f[5]+y.f[7],x.f[8]+y.f[3]))));42     for (int i=0;i<5;i++) ans.s[i]=x.s[i]+y.s[i];43     return ans;44 }45 node build(int x) {46     node ans;47     memset(ans.s,0,sizeof(ans.s));48     for (int i=0;i<=10;i++) ans.f[i]=inf;49     switch (x){50         case 2:51             ans.s[0]=1;ans.f[0]=0;break;52         case 0:53             ans.s[1]=1;ans.f[1]=0;break;54         case 1:55             ans.s[2]=1;ans.f[2]=0;break;56         case 7:57             ans.s[3]=1;ans.f[3]=0;break;58         case 6:59             ans.s[4]=1;break;60     }61     return ans;62 }63 void print(node x){64     for (int i=0;i<=10;i++) printf("%d ",x.f[i]);65     printf("\n");66     for (int i=0;i<=5;i++) printf("%d ",x.s[i]);67     printf("\n");68 }69 node f[mink][minn];70 int main(){71     scanf("%d%d",&n,&m);72     scanf("%s",s+1);73     for (int i=1;i<=n;i++) f[0][i]=build(s[i]-'0');74     for (int i=1;(1<
          
           <=n;i++) 75         for (int j=1;j+(1<
           
            <=n;j++){76 f[i][j]=update(f[i-1][j],f[i-1][j+(1<<(i-1))]);77 }78 for (int i=1;i<=m;i++) {79 int l,r;80 scanf("%d%d",&l,&r);81 node ans;82 int flag=0;83 for (int j=mink-1;j>=0;j--) {84 if (l+(1<
            
             <=r) {85 if (!flag) {ans=f[j][l];flag=1;}86 else ans=update(ans,f[j][l]);87 l+=(1<