2020 ICPC 上海（部分题解）

M

题目大意：给出n个文件的路径，你需要删除的，再给出m个文件的路径，你不能删除的，如果一个文件夹中的所有文件都可以删除那么就一次性删除即可，问最少删除次数
思路：map 存一下字符串 ，先处理文件标记首先为0，如果不可以删除标记为1，对于已标记为0的字符串，将其标记为2，如果后面再次出现那么整个路径都需要删除 则ans--
代码：

#include 
using namespace std;
typedef long long ll;
int t, n, m;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		int ans = n;
		map mp;
		string s, ss[105];
		for (int i = 1; i <= n + m; i++)
		{
			cin >> ss[i];
			s.clear();
			for (int j = 0; j < ss[i].size(); j++)
			{
				if (ss[i][j] == '/')
				{
					if (i > n) mp[s] = 1; //前n个文件需要删除 后面不能删除
					else mp[s] = 0;//所有m路径记为1 其他均为0
				}
				else s += ss[i][j];
			}
		}
		for (int i = 1; i <= n; i++)
		{
			s.clear();
			for (int j = 0; j < ss[i].size(); j++)
			{
				if (ss[i][j] == '/')
				{
					if (mp[s] == 0) mp[s] = 2;//说明可以删去 先标记为2 后面出现再减
					else if (mp[s] == 1) continue;//不能删去
					else //标记为2 需要删去
					{
						ans--;
						break;
					}
				}
				else s += ss[i][j];
			}
		}
		cout << ans << endl;
	}
}

B

题目大意：扫雷，一个n×m的矩阵，X代表雷，.代表没有雷。X的权值为0，.的点权值为相邻雷(X)的数目，一个图的权值为所有权值相加。
现在给你两个图A和图B，求得不超过nm/2次数修改B(.->X 或则X->.)使得sum与A得相同。（否则输出-1）。
思路：可知A图所有的X变为.，.变为X，图的权值不变，所以如果A跟B中不同元素个数大于nm/2，则直接将A图变成相反的即可，且题目一定有解。
代码

#include 
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
string a[N], b[N];
int main()
{
    int n, m, cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] != b[i][j]) cnt++;
    if (cnt > (n * m / 2))
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                if (a[i][j] == '.') a[i][j] = 'X';
                else a[i][j] = '.';
            }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << endl;
}

D

题目大意：有一个数轴，范围为[ 0 ，n ]，数轴上有两个人，位置和速度为p1,v1,p2,v2，求出两人路程覆盖数轴的最小时间。
思路：分类讨论：
三种情况：（假设p1完全在p2的左边，p1

1. p1,p2相向而行
2. p1单独走全程，或者p2单独走全程
3. p1,p2相背而行，（需要二分找到中间相遇点，由分析可知相遇点一定在p1,p2之间）
   代码:

#include 
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int t;
double n, p1, p2, v1, v2, ans;
bool check(double mid)
{
    double t1 = min(mid - p1 + mid, mid + p1) / v1;
    double t2 = min(p2 - mid + n - mid, n - p2 + n - mid) / v2;
    ans = min(ans, max(t1, t2));
    return t1 < t2;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> p1 >> v1 >> p2 >> v2;
        if (p1 > p2)
            swap(p1, p2), swap(v1, v2);
        ans = 1e9 + 10;
        //情况1
        ans = min(ans, max((n - p1) / v1, p2 / v2));
        //情况2
        ans = min(ans, min(p1 + n, n - p1 + n) / v1);
        ans = min(ans, min(p2 + n, n - p2 + n) / v2);
        //情况3
        double l = p1, r = p2;
        while (r - l > 1e-11)
        {
            double mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        printf("%.10f\n", ans);
    }
}

I

题目大意：有n个共圆心的圆，半径相差为1，有m条线通过圆心将这n个圆平分，求所有交点的距离和。
思路：1.圆心点到所有点的距离和（m条直径和），如果m为1，则不用考虑。
2.每一层的点之间的距离，（两点之间考虑是弧长近，还是走两个半径近），加上对称点的距离。
3.每层之间各点距离和。
代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const double PI = acos(-1);
double p[N], cir[N];
int main()
{
    int n, m;
    cin >> n >> m;
    double ans = 0, h = PI / m;
    if (m > 1)
        ans += n * (n + 1) * m;//圆心到每个点的距离
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            p[i] += min(2.0 * i, j * i * h);//对于一个点计算一边两点之间的距离
        }
        p[i] *= 2.0;//添加另一边
        p[i] += 2.0 * i;//加上对称点
        ans += p[i] * m;//算上整个层的距离
        ans += (cir[i - 1] + (i - 1) * 2 * m) * 2 * m;//计算本层圆到下层圆的和
        cir[i] = cir[i - 1] + (i - 1) * 2 * m + p[i];//前缀和
    }
    printf("%.10f\n", ans);
}