2019正睿CSP-S模拟赛十连测day8

link to this contest

这场题做的体验一般，没有“探索中求进步”的思考快感，会做的直接做，不会做的一点思路都没有，晚了半个小时开始，提早一个小时结束操作

$T1$转化以下题意直接模拟，$T2$完全不会，去看$T3$，看来看去都只会$50$的部分分，感觉也不少了就写完放弃了，回去把$T2$暴力写了就走人了

最终得分$100+30+50=180 (rank=15)$

A. 许强强

• 走完一步后构成一个新区域的充要条件是，这条边第一次走且去到的那个点已经去过
• 直接用$map$当作$vis$数组做即可，复杂度$O(n log n)$

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define fi first
 6 #define se second
 7 #define pb push_back
 8 #define MP make_pair
 9 #define pii pair<int,int>
10 using namespace std;
11 typedef long long ll;
12 const int N=5e5+5;
13 int n,tot=0,ans=0;
14 char s[N];
15 int fx[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
16 struct point
17 {
18     int x,y;
19 }a[N];
20 map <pair<point,point>,int> mp;
21 map <point,int> vis;
22 bool operator <(point x,point y)
23 {
24     if (x.x==y.x) return x.y<y.y;
25     return x.x<y.x;
26 }
27 bool operator ==(point x,point y)
28 {
29     if (x.x==y.x&&x.y==y.y) return 1;
30     else return 0;
31 }
32 bool operator <(pair<point,point> x,pair<point,point> y)
33 {
34     if (x.fi==y.fi) return x.se<y.se;
35     return x.fi<y.fi;
36 }
37 inline int pt(char x)
38 {
39     if (x=='L') return 0;
40     if (x=='R') return 1;
41     if (x=='U') return 2;
42     if (x=='D') return 3;
43 }
44 int main()
45 {
46 //    freopen("data.in","r",stdin);
47 //    freopen("myans.out","w",stdout);
48     mp.clear();
49     vis.clear();
50     scanf("%s",s+1);
51     n=strlen(s+1);
52     a[++tot]=(point){0,0};
53     for (register int x=0,y=0,i=1;i<=n;i++)
54     {
55         x+=fx[pt(s[i])][0],y+=fx[pt(s[i])][1];
56         a[++tot]=(point){x,y};
57     }
58     sort(a+1,a+tot+1);
59     tot=unique(a+1,a+tot+1)-a-1;
60     for (register int x=0,y=0,i=1;i<=n;i++)
61     {
62         vis[(point){x,y}]=1;
63         int nx=x+fx[pt(s[i])][0],ny=y+fx[pt(s[i])][1];
64         if (vis[(point){nx,ny}]&&!mp[MP((point){x,y},(point){nx,ny})]) ans++;
65         mp[MP((point){x,y},(point){nx,ny})]=1;
66         mp[MP((point){nx,ny},(point){x,y})]=1;
67         x=nx,y=ny;
68     }
69     ans++;
70     printf("%d\n",ans);
71     return 0;
72 }

View Code

 

这场的题都挺有意思，一定不能咕！