比赛链接：Dashboard - Educational Codeforces Round 163 (Rated for Div. 2) - Codeforces
C
题意：有一个 $2\times n$ 的网格，每个格子有一个指向左或右的箭头。有一机器人从 $(1,1)$ 开始，每次的操作如下：先向上下左右走到任一个网格(不能超出地图)，然后根据该格箭头走一步。问能否走到 $(2,n)$ 。
dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
using namespace std;
int mp[3][200005];
int v[3][200005];
int n;
bool flag=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool check(int x,int y)
{
if(x<1 || x>2 || y<1 ||y>n)return 0;
return 1;
}
void dfs(int x,int y)
{
if(v[x][y])
{
return;
}
if(x==2 && y==n)
{
flag=1;
return ;
}
v[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(!check(nx,ny))continue;
ny+=mp[nx][ny];
dfs(nx,ny);
if(flag)return ;
}
}
void solve()
{
cin>>n;
flag=0;
for(int i=1;i<=n;i++)v[1][i]=0,v[2][i]=0;
for(int i=1;i<=2;i++)
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
if(c=='>')mp[i][j]=1;
else mp[i][j]=-1;
}
dfs(1,1);
if(flag)cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D
给一个由小写字母和问号组成的字符串 $s$，问号可以表示任何字母。求最大的偶数长度的连续子串，其前半部分与后半部分相同。$n\leq 5000$
一开始考虑区间dp，发现不能转移，然后换了思路。。
枚举一半的子串长度 $len$，处理某一位置后 $len$ 的位置是否与此相同，然后找连续相同的元素，若连续超过 $len$ 那么长度为 $2\times len$ 的子串存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
void solve()
{
char s[5005];
cin>>s+1;
int n=strlen(s+1);
int ans=0;
for(int len=1;len*2<=n;len++)
{
int q[n+2]={0};
for(int i=1;i+len<=n;i++)
{
if(s[i]==s[i+len] || s[i]=='?' || s[i+len]=='?')q[i]=1;
else q[i]=0;
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(q[i])cnt++;
else
{
if(cnt>=len)
{
ans=max(ans,len*2);
}
cnt=0;
}
}
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
E
题意：给两个整数 $n$ 和 $k$ ，$n$ 个顶点上有一个图。现在需要给每一个顶点分配一个 $1-n$ 整数 $a_i$ ，对于两个顶点，如果 $|i - j| + |a_i - a_j| ≤ k$ ，那么在这两个点之间添加一条边。现在需要把这个图分割成尽量少的群，对于每一个群，任两个顶点之间存在一条边。求每个顶点分配的整数、最小群的数量以及每个顶点属于哪一个群。
好妙的贪心
- 不要从整个图开始考虑，从每个群开始考虑。在限制条件中 $|i - j|$ 是固定的因此要使得满足条件，选择序号连续的点构成一个群是最优的。
- 对于一个群，分配整数时，同样选择一段连续的整数进行分配是最优的。因此从1开始依次选择连续的整数段分配给对应的群。
- 考虑大小为 $n$ 的群能否满足 $|i - j| + |a_i - a_j| ≤ n$ 。假设序号为 $1-n$ 的点对应整数 $1-n$ ，考虑将数列对半分，即对序号为 $1-\lceil \frac{n}{2}\rceil$ 的点，依次分配 $\lceil \frac{n}{2}\rceil,\lceil \frac{n}{2}\rceil-1,…,2,1$ ，对序号为 $\lceil \frac{n}{2}\rceil+1-n$ 的点，依次分配 $n,n-1,…,\lceil \frac{n}{2}\rceil+2,\lceil \frac{n}{2}\rceil+1$ 。这样保证每个半区内部的最大值为 $n-2$ ，不同半区的任两个元素的差均为 $n$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
int a[k+5]={0};
int ans[n+5]={0};
int c[n+5]={0};
int tot=(n-1)/k+1;
for(int i=1;i<=(k-1)/2+1;i++)
{
a[i]=(k-1)/2+1-i+1;
}
for(int i=(k-1)/2+2;i<=k;i++)
{
a[i]=k-i+(k-1)/2+2;
}
for(int i=1;i<=tot;i++)
{
if(i!=tot || i==tot && tot*k==n)
{
for(int j=1;j<=k;j++)
{
ans[k*(i-1)+j]=a[j]+k*(i-1);
c[k*(i-1)+j]=i;
}
}
else
{
int r=n%k;
int b=n/k*k;
for(int j=1;j<=(r-1)/2+1;j++)
{
ans[b+j]=(r-1)/2+1-j+1+b;
c[b+j]=tot;
}
for(int j=(r-1)/2+2;j<=r;j++)
{
ans[b+j]=r-j+(r-1)/2+2+b;
c[b+j]=tot;
}
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
cout<<tot<<endl;
for(int i=1;i<=n;i++)cout<<c[i]<<" ";cout<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
微信
支付宝
