C

唔,脑洞题
给定一个01字符串$a_1,a_2,…,a_n$
进行下面操作

  • $b_1 = a_1, b_n = a_n$
  • $b_i = F(a_{i-1},a_i,a_{i+1}) \;i = 2,..,n-1 \; \text{F定义为中值}$

求最少的操作次数使字符串稳定(即操作一次字符串不变),以及稳定的字符串

我们发现对于连续两个的字符 00或11 其值始终是不变的
只有 010101… 或 10101… 这种串才会变化
若这样的串长度为奇数,最终会变成00…/11…,若长度为偶数会变成0..01..1/1..10..0
为了方便,我们把字符串改为 a[1] + a + a[n],比如 100 改为 1 100 0 这样就可以忽视第一个操作了

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 5e5 + 10;
bool a[maxn],b[maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d%*c",&n);
for(int i=1;i<=n;++i)
{
a[i] = getchar() - '0';
getchar();
}
int ans = 0;
a[0] = a[1];
a[n+1] = a[n];
for(int i=1;i<=n;)
{
if(a[i] == a[i-1] && a[i]!=a[i+1])
{
int cnt = 1,p = i;
while(a[i+1] != a[i])
{
++i;
++cnt;
}
ans = max(ans,(cnt-1)/2);
if(cnt&1) for(int j=p;j<=i;++j) b[j] = a[p];
else
{
for(int j=p;j<=p+cnt/2;++j) b[j] = a[p];
for(int j=p+cnt/2;j<=i;++j) b[j] = a[p]^1;
}
}
else
{
b[i] = a[i];
++i;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;++i) printf("%c%c",b[i]?'1':'0',i==n?'\n':' ');
return 0;
}

D

二分
一艘船从坐标系中(x1,y1)行驶到(x2,y2)
给定最大船速v,时间s
在前s秒风速为(vx,vy),以后风速为(wx,wy)
求到达(x2,y2)的最短时间

一看是求极值的题,就考虑 二分/三分
我们先不考虑船速v,在任意时刻t,船的坐标为
$$
\begin{align}
&(x_1 + t*v_x,y_1 + tv_y) \; t \leq s \\
&(x_1 + sv_x + (t-s)w_x,y_1 + sv_y + (t-s)w_y) \; t > s
\end{align}
$$
我们由坐标和速度求出时间,然后二分时间

传说很多人因为精度TLE,所以建议二分三分设定迭代次数

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;

typedef long long LL;
const double eps = 1e-8;
const double INF = 1e8;
int x[2],y[2],tx[2],ty[2];
int t,v;

inline double P(double t)
{
return t*t;
}

bool yes(double m)
{
if(m<=t)
return v*m >= sqrt(P(x[0]+m*tx[0] - x[1]) + P(y[0]+m*ty[0] - y[1]));
else
return v*m >= sqrt( P(x[0]+t*tx[0]+(m-t)*tx[1] - x[1]) + P(y[0]+t*ty[0]+(m-t)*ty[1] - y[1]));
}

double gao()
{
double l = 0, r = INF;
// while(r - l> eps)
for(int i=0;i<100;++i)
{
double mid = (l+r)/2;
if(yes(mid))
r = mid;
else
l = mid;
}
return r;
}

int main()
{
//freopen("test.txt","r",stdin);
for(int i=0;i<2;++i) scanf("%d %d",x+i,y+i);
scanf("%d %d",&v,&t);
for(int i=0;i<2;++i) scanf("%d %d",tx+i,ty+i);
printf("%.8lf\n",gao());
return 0;
}

E

唔,bfs求最短路
越来越感觉自己脑洞不够了…

给定一张m*n的地图,有三个国家
其中数字1,2,3代表三个国家的领土
. 表示空地,可以修建道路
# 表示障碍

求修建一条最短的路,使三个国家相连(一部分相连即可)
我们进行三次bfs
dp[i][x][y] 记录国家i到(x,y)需要修建的最短路

最后答案即为 min(dp[1][x][y] + dp[1][x][y] + dp[2][x][y] + s[x][y] == ‘.’)

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
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1010;
char s[maxn][maxn];
int dp[3][maxn][maxn];

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};

int main()
{
//freopen("test.txt","r",stdin);
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;++i) scanf("%s",s[i]);
memset(dp,INF,sizeof dp);
for(int k=0;k<3;++k)
{
queue<pair<int,int> > Q;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
if(s[i][j] == '1'+k)
{
Q.push(make_pair(i,j));
dp[k][i][j] = 0;
}
}

while(!Q.empty())
{
pair<int,int> u = Q.front(); Q.pop();
for(int i=0;i<4;++i)
{
int tx = u.first + dx[i],ty = u.second + dy[i];
if(tx>=0 && ty>=0 && tx<n && ty<m && s[tx][ty]!='#' && dp[k][u.first][u.second] + (s[u.first][u.second]=='.') < dp[k][tx][ty])
{
dp[k][tx][ty] = dp[k][u.first][u.second]+ (s[u.first][u.second]=='.');
Q.push(make_pair(tx,ty));
}
}
}
}
int ans = INF;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
if(dp[0][i][j] < INF && dp[1][i][j] < INF && dp[2][i][j] < INF)
{
ans = min(ans,dp[0][i][j] + dp[1][i][j] + dp[2][i][j] + (s[i][j]=='.'));
}
}
printf("%d\n",ans>=INF?-1:ans);
return 0;
}

F

DP

给定一个长度为n的序列q,交换相邻元素次数最多s次
问经过s次以内的交换,$\sum_{i=1}^k q_i$的最小值

根据排序的性质可知序列最多交换逆序对个数(最多n*(n-1)/2)次有序

然后我们假定前k个元素的位置最开始分别为$i_1 < i_2 < … < i_k$
我们将他们交换到指定位置消耗
$$
\begin{align}
&(i_1 - 1) + (i_2 - 2) + … + (i_k - k) = \sum_{p=1}^k i_p - \frac{k(1+k)}{2} \leq s \\
&\sum_{p=1}^k i_p \leq s + \frac{k(1+k)}{2}
\end{align}
$$

我们定义d[i][j][p] 为前i个元素,选择了j个,下标和为p的和的最小值
第一维滚动这样可以$O(n^4)$的时间复杂度求出来

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
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 150 + 10;
int a[maxn],tmp[maxn];
int d[2][maxn][maxn*maxn];

int main()
{
//freopen("test.txt","r",stdin);
int n,k,s;
scanf("%d %d %d",&n,&k,&s);
for(int i=0;i<n;++i) scanf("%d",a+i);
int ans,cnt = 0;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(a[i] > a[j]) ++cnt;
if(s >= cnt)
{
for(int i=0;i<n;++i) tmp[i] = a[i];
sort(tmp,tmp+n);
ans = 0;
for(int i=0;i<k;++i) ans += tmp[i];
printf("%d\n",ans);
return 0;
}
int sum = s + k*(k+1)/2,cur = 1;
memset(d,INF,sizeof d);
d[cur][0][0] = 0;
ans = INF;
for(int i=1;i<=n;++i)
{
cur ^= 1;
memset(d[cur],INF,sizeof d[cur]);
for(int j=0; j <= k;++j)
{
for(int t=0; t <= sum;++t)
{
if(j+1<=k && t+i <= sum) d[cur][j+1][t+i] = min(d[cur][j+1][t+i],d[cur^1][j][t]+a[i-1]);
d[cur][j][t] = min(d[cur][j][t],d[cur^1][j][t]);
if(j==k) ans = min(ans,d[cur][j][t]);
}
}
}
printf("%d\n",ans);
return 0;
}