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
",ans);
71     return 0;
72 }

View Code

C. 周队

当关键点个数$geq 2n-1$是任何地方都能降落，抽屉原理，对于每个点都存在两个到它距离相同的点
关键点个数$O(n)$的时候枚举两个关键点，讨论一下这两个点是不是某个正方形的对角线，差分$O(1)$修改
代码就贴个暴力算了，正解大力讨论有点烦

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define fi first
 4 #define se second
 5 #define pb push_back
 6 #define MP make_pair
 7 #define pii pair<int,int>
 8 using namespace std;
 9 typedef long long ll;
10 const int N=2010;
11 int n,a[N][N],vis[N];
12 vector <pii> vec;
13 char ans[N][N];
14 inline int ABS(int x) {return (x>0)?x:(-x);}
15 inline int dis(pii x,pii y) {return ABS(x.fi-y.fi)+ABS(x.se-y.se);}
16 int main()
17 {
18     scanf("%d",&n);
19     FOR(i,1,n) FOR(j,1,n) 
20     {
21         ans[i][j]='N';
22         scanf("%d",&a[i][j]);
23         if (a[i][j]) vec.pb(MP(i,j));
24     }
25     if (vec.size()>2*n)
26     {
27         FOR(i,1,n) {FOR(j,1,n) putchar('Y'),putchar(' ');putchar('
');}
28         exit(0);
29     }
30     random_shuffle(vec.begin(),vec.end());
31     FOR(i,1,n) FOR(j,1,n)
32     {
33         FOR(i,0,2*n) vis[i]=0;
34         FOR(k,0,(int)vec.size()-1)
35         {
36             int tmp=dis(vec[k],MP(i,j));
37             if (vis[tmp]) {ans[i][j]='Y';break;}
38             vis[tmp]=1;
39         }
40     }
41     FOR(i,1,n) {FOR(j,1,n) putchar(ans[i][j]),putchar(' ');putchar('
');}
42     return 0;
43 }

View Code