8.12题解

2019-08-14

以后的反思大概会在题解里顺带提一嘴,都写的话时间有点长

T1

暴力模拟,考场上我打的模拟进行了太多已经计算过的计算,过于冗余,调用函数太多,导致代码及其的慢,而实质上这就是个模拟,考场两小时,考后一小时,不过如果$while$过多,打的时候一定注意边界,说不准哪个$while$就死了

分享图片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue>
 5 #define maxn 1010
 6 using namespace std;
 7 int n,m,x1,y1;
 8 char a[maxn][maxn];
 9 void xian(int x,int y);
10 void search(int x,int y);
11 void xian(int x,int y)
12 {
13     int lsx=x,lsy=y,ad;
14     if(a[lsx][lsy-1]==|)  ad=1;
15     else if(a[lsx][lsy+1]==|)  ad=-1;
16     while(1)
17     {
18         if(a[lsx][lsy]==|&&a[lsx+1][lsy]==-)
19         {
20             lsx++;
21             while(a[lsx][lsy]!=+)  lsy--;
22             search(lsx,lsy);
23             break;
24         }
25         while(a[lsx][lsy+ad]==-)  lsy+=ad;
26         if(a[lsx][lsy+ad]==+)  lsy+=ad;
27         while(a[lsx+1][lsy]==|)  lsx++;
28         if(a[lsx+1][lsy]==+)
29         {
30             lsx+=1;
31             if(a[lsx][lsy-1]==-)  ad=-1;
32             else if(a[lsx][lsy+1]==-)  ad=1;
33         }
34     }
35 }
36 void search(int x,int y)
37 {
38     int lsx=x+1,lsy=y+1;
39     while(a[x][lsy]!=+)  lsy++;
40     while(a[lsx][y]!=+)  lsx++;
41     int i=x,e=0,j;
42     while(1)
43     {
44         if(e!=0)  break;
45         j=y;
46         while((a[i][j]<0||a[i][j]>9)&&j<lsy)  j++;
47         if(j==lsy)  {i++;  continue;}
48         while(a[i][j]>=0&&a[i][j]<=9&&j<lsy)
49             {e=(e<<3)+(e<<1)+(a[i][j]^48);  j++;}
50         i++;
51     }
52     for(int i=lsx;i>=x;--i)
53     {
54         if(a[i][y-1]==-)  xian(i,y-1);
55         if(a[i][lsy+1]==-)  xian(i,lsy+1);
56     }
57     printf("%d\n",e);
58 }
59 int main()
60 {
61     scanf("%d%d",&n,&m);
62     for(int i=1;i<=n;++i)  scanf("%s",a[i]+1);
63     for(int i=1;i<=n;++i)
64     {
65         int bj=0;
66         for(int j=1;j<=m;++j)
67             if(a[i][j]==1)  {x1=i;  y1=j;  bj=1;  break;}
68         if(bj==1)  break;
69     }
70     while(a[x1][y1]!=|)  y1--;
71     while(a[x1][y1]!=+)  x1--;
72     search(x1,y1);
73     return 0;
74 }
模拟飞快

T2

复杂度正确的dp我没看懂,打了个暴力,其实考场上也打的暴力,但是不够优,考场上我是一步一步的挪,但实施上一个一个小精灵的挪会更快,而且不会错,当然考场上我还想了想贪心。。。一个小精灵一个小精灵的挪的话,只需找到当前小精灵左右两侧第一个合法的可达小精灵,跳过去即可

分享图片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define maxn 110
 6 using namespace std;
 7 int n,k,m,ans,maxx;
 8 struct node{
 9     int pos,num,tim;
10     bool operator <(const node &a)const
11     {
12         return pos<a.pos;
13     }
14 }a[maxn];
15 int val[1010];
16 void sou(int po,int ti,int sum)
17 {
18     ans=max(ans,sum);
19     int tot=0,ls=0;
20     for(int i=1;i<=m;++i)
21         if(a[i].tim>=ti)  tot+=a[i].num;
22     if(tot==0||sum+tot<=ans||ti>maxx)  return;
23     if(val[po]!=0&&a[val[po]].num==0)  return ;
24     if(val[po]!=0&&a[val[po]].tim>=ti)
25     {
26         ls=a[val[po]].num;  a[val[po]].num=0;
27         ans=max(ans,sum+ls);
28     }
29     for(int i=1;i<=m;++i)
30     {
31         if(a[i].num==0)  continue;
32         if(abs(a[i].pos-po)>a[i].tim-ti)  continue;
33         if(a[i].pos>po&&a[i].num!=0)  {sou(a[i].pos,ti+abs(a[i].pos-po),sum+ls);  break;}
34     }
35     for(int i=m;i>=1;--i)
36     {
37         if(a[i].num==0)  continue;
38         if(abs(a[i].pos-po)>a[i].tim-ti)  continue;
39         if(a[i].pos<po&&a[i].num!=0)  {sou(a[i].pos,ti+abs(a[i].pos-po),sum+ls);  break;}
40     }
41     if(ls)  a[val[po]].num=ls;
42 }
43 int main()
44 {
45     scanf("%d%d%d",&n,&k,&m);
46     for(int i=1;i<=m;++i)
47     {
48         scanf("%d%d%d",&a[i].pos,&a[i].num,&a[i].tim);
49         maxx=max(maxx,a[i].tim);
50     }
51     sort(a+1,a+m+1);
52     for(int i=1;i<=m;++i)  val[a[i].pos]=i;
53     sou(k,1,0);
54     printf("%d\n",ans);
55     return 0;
56 }
暴力碾标算

T3

什么斯特林数,斯特林反演的,只能咕咕咕了

这次考试,T1调试时间稍长,心态有点崩,$pdf$开考就死了,所以没看到T3测试点,骗分都没骗,打暴力不想优化和剪枝也很可怕,所以这场,还是炸了