Problem_A(591A):
题意：
有一段长度为l的路，两个人分别在两个端点，1, l。 现在已知每个人的速度为p,q. 求第一个人(初始位置在1)在他们第二次相遇的时候的位置。
当他们相遇的时候， 他们会掉头返回走， 走到端点再返回来。
思路：
首先可以确定的是， 这两个人每次相遇的地点都是一样的。
然后， 设他们相遇时时间为t, 所以有：p * t + q * t = l
即：t = l / (p + q)
第一个人位置即为：t * p = l / (p + q) * p;
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int l, p, q; int main()
{
scanf("%d %d %d", &l, &p, &q);
printf("%.4lf\n", (double)(l * 1.0 / (p * 1.0 + q * 1.0)) * (p * 1.0));
return ;
}
Problem_B(591B):
题意：
给一个长度为n的字符串， 然后进行m次操作。
每次操作(ch_a, ch_b)：将当前字符串中所有的字符ch_a替换成ch_b, 所有的ch_b替换成ch_a
求操作完后的字符串。
思路：
乍一看是个模拟， 再一看数据量2* 10 ^5 有点大， 不能直接模拟。
题目中有个条件：所有字母均为小写字母！！！
小写字母只有26个， 每次对这26个字母进行操作即可。
设 f[i] = j 为初始字母为i + 'a'的字符 当前变换成j + 'a' 字符
每次找出值为ch_a, ch_b的字符， 然后对其进行赋值操作即可。
这样一来就成了O(m * 26) 妥妥的1s
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 200010
#define MAXM 30
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n, m;
int name[MAXN];
int f[MAXM];
char read_char()
{
char ch;
while(ch = getchar())
{
if(ch >= 'a' && ch <= 'z') return ch;
}
}
int find_char(int x)
{
for(int i = ; i < MAXM; i ++)
if(f[i] == x) return i;
return -;
} int main()
{
scanf("%d %d", &n, &m);
for(int i = ; i < n; i ++)
name[i] = (read_char() - 'a');
for(int i = ; i < MAXM; i ++)
f[i] = i;
char ch_a, ch_b;
for(int i = ;i < m; i ++)
{
ch_a = read_char();
ch_b = read_char();
int pos_a = find_char(ch_a - 'a');
int pos_b = find_char(ch_b - 'a');
f[pos_a] = ch_b - 'a';
f[pos_b] = ch_a - 'a';
}
for(int i = ; i < n; i ++)
printf("%c", f[name[i]] + 'a');
printf("\n");
return ;
}
Problem_C(590A):
题意：
给一个长度为n的数组a[]， 它有如下变化：
1：b[0] = a[0], b[n-1] = b[n - 1]
2：b[i] = （a[i - 1] ， a[i], a[i + 1])的中位数
且a[i] = 0 || a[i] = 1
求出最少多少次变化之后， 此数组不能再变化(即变化后和变化前一样)
思路：
有一个规律不难发现：如果有两个以上连续相同的数 如11, 00 那么这两个数在接下来的变化中会保持不变！！！
很简单， 因为是中位数， 而且只有0 1 那么如果a[i]的左右两边有一个或以上相同的数 那么a[i]就不会变。
然后再来看看那些不连续的数的规律：
1 1 0 1 0 1 0 1 0 0
这个数最后会变成 1 1 1 1 1 0 0 0 0 0！ 对称了， 再来看一个
0 0 1 0 1 0 1 0 0
变化后： 0 0 0 0 0 0 0 0 0 全变成0 了！ 再改变一下两端连续的那个值找找规律 就会发现
如果不连续串的长度为奇数， 那么它的左右两端肯定是相等的， 那么它中间的这段不连续的串最后都会变成它。且次数为(len / 2 + len % 2)
如果不连续串的长度为偶数， 那么它的左右两端肯定是不等的，最后中间这段不连续的串都会对半变化！ 左边的与左端点相等， 右边的与右端点相等。次数为 len /2
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n;
int a[MAXN];
void read()
{
for(int i = ; i < n; i ++)
scanf("%d", &a[i]);
} void solve()
{
int cnt = ;
for(int i = ; i < n;)
{
int j = i;
while(j + < n && a[j] != a[j + ])
j ++;
j ++;
cnt = max(cnt, (j - i - ) / + (j - i - ) % );
if((j - i) % == )
{
for(int k = i + ; k < j; k ++)
a[k] = a[i];
}
else
{
for(int k = i + ; k < (i + j) / ; k ++)
a[k] = a[i];
for(int k = (i + j) / ; k < j; k ++)
a[k] = a[j - ];
}
i = j;
}
printf("%d\n", cnt);
for(int i = ; i < n - ; i ++)
printf("%d ", a[i]);
printf("%d\n", a[n - ]);
}
int get_ans(int l, int r)
{
if(l == r) return ;
if(a[l] == a[r])
{
for(int i = l + ; i < r; i ++)
a[i] = a[l];
return (r - l) / ;
}
else
{
for(int i = l + ; i < (l + r + ) / ; i ++)
a[i] = a[l];
for(int i = (l + r + ) / ; i < r; i ++)
a[i] = a[r];
return (r - l - ) / ;
}
}
void solve_2()
{
int l = , ans = ;
for(int i = ; i < n; i ++)
if(i == n - || a[i] == a[i + ])
{
ans = max(ans, get_ans(l, i));
l = i + ;
}
printf("%d\n", ans);
for(int i = ; i < n; i ++)
printf(i == n - ? "%d\n" : "%d ", a[i]);
} int main()
{
scanf("%d", &n);
read();
// solve();
solve_2();
return ;
}
Problem_D(590B):
题意：
在一个二维坐标系上， 给两个点， 一个起点(x1, y1)， 一个终点(x2, y2).
一个时间t, 一个最大速度vmax
然后给两个速度向量（vx, vy）, (wx, wy).
从起点飞到终点， 方向和速度可以在任何时刻随意变换， 速度不超过vmax即可。
在前t秒， 会受到风的阻力(vx, vy). t秒风的速度变成(wx, wy)。 求到终点的最短时间。
思路：
首先， 不考虑方向和风的影响， 以最大速度前进， 那么ts内的移动的距离就是vmax * t。 如果再加上方向呢？
是不是就成了一个圆：
圆心 O = (x1, y1)
半径 r = vmax * t
再加上风的影响呢？
是不就就是将这个圆整体位移(vx*t, vy*t) ？
此时圆为：
圆心 O = (x1 + vx * t, y1 + vy * t)
半径 r = vmax * t
如果此时， 终点在圆内， 是否代表在ts内可以到达？
如果终点在圆外， 那么设时间为w， 此时这个圆:
圆心O = (x1 + vx * t + wx * (w - t), y1 + vy * t + wy * (w - t))
半径r = vmax * w
所以， 对时间进行二分， 找到最小的满足终点在圆内的时间即可。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
double x[], y[];
double v, t;
double vx, vy, wx, wy;
double sqr(double x)
{
return x * x;
}
double dis(double x1, double y1, double x2, double y2)
{
return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
bool is_ok(double tmp_t)
{
double tx, ty;
if(tmp_t > t)
{
tx = x[] + t * vx + wx * (tmp_t - t);
ty = y[] + t * vy + wy * (tmp_t - t);
}
else
{
tx = x[] + tmp_t * vx;
ty = y[] + tmp_t * vy;
}
double ans = dis(tx, ty, x[], y[]);
if(ans < v * tmp_t) return true;
return false;
} int main()
{
scanf("%lf %lf %lf %lf", &x[], &y[], &x[], &y[]);
scanf("%lf %lf", &v, &t);
scanf("%lf %lf %lf %lf", &vx, &vy, &wx, &wy);
double ans_l = , ans_r = 1e8, mid;
while((ans_r - ans_l) >= eps)
{
mid = (ans_l + ans_r) / 2.0;
if(is_ok(mid)) ans_r = mid;
else ans_l = mid;
}
printf("%.7lf\n", ans_l);
return ;
}
Porblem_E(590C):
题意：
一个n * m的网格， #代表不能走， .代表沼泽，1 2 3 分别代表一类区域
现在要将这三个区域连通， 你可以把沼泽变成路。 求变化最少的沼泽， 使得三个区域连通起来。
思路：
因为1,2,3 可以看成三个块， 也可以看成三类起点。
将所有的1, 2, 3记录下来， 以此为起点， 搜索三次。
然后枚举它们三个区域的交点， 算出到三个区域的长度(沼泽数量)，取最小值即可。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 1000100
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1010
#define MAXM 3
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n, m;
int step[MAXM][MAXN][MAXN];
int dir[][] = {{-, }, {, }, {, -}, {, }};
int grid[MAXN][MAXN];
int read_ch()
{
char ch;
while(ch = getchar())
{
if(ch >= '' && ch <= '') return (int)(ch - '');
if(ch == '.') return -;
if(ch == '#') return -;
}
}
bool check(int i, int j)
{
if(i < || i >= n || j < || j >= m || grid[i][j] == -) return false;
return true;
}
void bfs(int pos)
{
queue <int> Q;
while(!Q.empty()) Q.pop();
for(int i = ; i < n; i ++)
for(int j = ; j < m; j ++)
if(grid[i][j] == pos)
{
Q.push(i);
Q.push(j);
step[pos][i][j] = ;
}
while(!Q.empty())
{
int x = Q.front();
Q.pop();
int y = Q.front();
Q.pop(); for(int i = ; i < ; i ++)
{
int xx = x + dir[i][];
int yy = y + dir[i][];
if(!check(xx, yy)) continue;
if(step[pos][xx][yy] > step[pos][x][y] + (grid[x][y] == -))
{
step[pos][xx][yy] = step[pos][x][y] + (grid[x][y] == -);
Q.push(xx);
Q.push(yy);
}
}
}
} void show(int pos)
{
printf("%d\n", pos);
for(int i = ; i < n; i ++, printf("\n"))
for(int j = ; j < m; j ++)
printf("%d ", step[pos][i][j]);
printf("\n");
} int main()
{
mes(grid, );
for(int k = ; k < MAXM; k ++)
for(int i = ; i < MAXN; i ++)
for(int j = ; j < MAXN; j ++)
step[k][i][j] = INF; scanf("%d %d", &n, &m);
for(int i = ; i < n; i ++)
for(int j = ; j < m; j ++)
grid[i][j] = read_ch(); for(int i = ; i < MAXM; i ++)
bfs(i); int ans = INF * ;
for(int i = ; i < n; i ++)
for(int j = ; j < m; j ++)
ans = min(ans, step[][i][j] + step[][i][j] + step[][i][j] + (grid[i][j] == -));
if(ans >= INF) ans = -;
printf("%d\n", ans);
return ;
}