24/10/13 ABC375补题笔记

A

典，属于显而易见的水题，这数据范围直接暴力做就行了。

# include <bits/stdc++.h>
using namespace std;

int main (){
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = 0;
	if(n < 2) return cout << 0 << endl,0;
	for(int i = 0;i < s.size()-2;i++)
	{
		if(s[i] == '#' && s[i+1] == '.' && s[i+2] == '#') cnt++;
	}
	cout << cnt << endl;
	return 0;
} 

B

典，这ABC这次给的分特别玄学，\(B\)题才\(150pts\),显然简单。
直接考虑记录一个\(nowx\)和\(nowy\)然后计算欧几里得距离就可以了，最后别忘了补上回去的那段路程。
code:

# include <bits/stdc++.h>
using namespace std;

int main (){
	int n;
	scanf("%d",&n);
	double nowx = 0;
	double nowy = 0;
	double ret = 0;
	for(int i = 0;i <= n;i++)
	{
		double x,y;
		if(i != n)
		{
			cin >> x >> y;
		}
		else 
		{
			x = 0,y = 0;
		}
		ret += sqrt((x-nowx)*(x-nowx)+(y-nowy)*(y-nowy));
		nowx = x,nowy = y;
	}
	printf("%.12f",ret);
	return 0;
}

C

好题，这题出的很牛逼。
首先你直接暴力的去做的话复杂度显然是\(O(n^3)\)，所以你要考虑优化这个题。
观察整个题目的话你会发现一个性质，题目中不是要求你的\((x,y)\)要处在\(i \to i+N-1\)这个范围内吗，那么他被改变的位置是\((y,x+N-1)\)范围内对吧，也就是说，\((y,x+N-1)\)这个小方格也要在\(i \to i+N-1\)这个范围内。

那么原来一个方格的节点被映射之后会变成什么样子呢？考虑该节点变化的过程，一开始是\((x,y)\)，下一个是\((y,x+N-1)\)，再下一个是\((x+N-1,y+N-1)\)，next is \((y+N-1,x)\),在下一个就是\((x,y)\)，这时候你发现，他每四个就会变化回原来的，所以对于一个方格它的覆盖次数如果超过\(4\)次的话，可以给他优化成\(\mod 4\)的结果，那么你就可以少做一个\(N\)次的循环，而优化成\(\mod 4\)的结果，最多不会超过\(4\)次，故这个时候复杂度就是\(O(4N^2)\)，近乎于\(O(N^2)\)，那么你考虑这个变化的个数有多少次呢？显然是\(\min(x,x+N-1,y,y+N-1)\)，那么直接对这玩意进行取模，然后暴力模拟即可。
代码老好做了，直接粘一个啦：

# include <bits/stdc++.h>
using namespace std;
const int N = 3010;
char a[N][N],b[N][N]; 
int main (){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> (a[i]+1);
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			int d = min({i,n-i+1,j,n-j+1});
			int nowx = i,nowy = j;
			for(int x = 0;x < d%4;x++)
			{
				int tmp = nowx;
				nowx = nowy;
				nowy = n+1-tmp;
			}
			b[nowx][nowy] = a[i][j];
		}
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			cout << b[i][j];
		}
		cout << endl;
	}
	return 0;
}

D

直接考虑做每个字符的个数前缀和，然后寻找两个相同字符差的字符个数，然后再乘上这两个字符之间的距离，累加就是答案。
很简单的思路，就不赘述了。

F

好题，真的会做。
这题很典，跟JSOI2008 星球大战几乎思路真的是一模一样，你考虑题目中的删边操作，如果你正着顺序去做这个题的话，肯定是很难处理的，所以你考虑把问题离线下来，倒着处理所有问题，将删边改为加边。

至于上面做法的正确性，我们简单给出一个我自己的较为好理解的思路：假设最后将所有的边全部都删除完了，那么这个时候，你的最后一次操作在没删除之前，整个图相当于还拥有一条边，倒数第二个操作在操作之前，整个图还拥有\(2\)条边\(.....\)，就这样，我们不如将每个问题记录一个数组，后面倒序的去做这个问题，具体的操作其实看代码会更好理解一些。

接下来你考虑如何处理添加这条边，对于添加这条边，他的最短路会出现下面三种情况：
设此时要求的两个节点分别为\(x\)与\(y\)，这条边的起点为\(a\)，终点\(b\)。

• 从\(x\)到\(y\)的最短路不经过这条边。
• 从\(x\)这个点到\(a\)，再走\(a\)到\(b\)这个边，再从\(b\)走到\(y\)。
• 从\(x\)这个点到\(b\)，再走\(b\)到\(a\)这个边，再从\(a\)走到\(x\)。
  那么只需要把这三个取\(\min\)就可以了。

# include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 310,M = 2e5+10;
int dis[N*2][N*2];
const int inf = 1e18;
int a[M],b[M],c[M],x[M];
int vis[M];
int ans[M];
int y[M],op[M];
signed main (){
	int n,m,q;
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			if(i == j) dis[i][j] = 0;
			else dis[i][j] = inf;
		}
	}
	for(int i = 1;i <= m;i++)
	{
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]); 
	}
	for(int i = 1;i <= q;i++)
	{
		scanf("%lld%lld",&op[i],&x[i]);
		if(op[i] == 2)
		{
			scanf("%lld",&y[i]);
		}
		else 
		{
			vis[x[i]] = 1;
		}
	}
	for(int i = 1;i <= m;i++)
	{
		if(!vis[i])
		{
			dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
		}
	}
	for(int k = 1;k <= n;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
//	cout << "true" << endl;
	for(int i = q;i >= 1;i--)
	{
//		cout << i << endl;
		if(op[i] == 2)
		{
//			cout << dis[x[i]][]
//			cout << "qwq" << endl;
			ans[i] = dis[x[i]][y[i]];
//			cout << "qwq" << endl;
		}
		else
		{
//			cout << "true" <<endl;
			for(int j = 1;j <= n;j++)
			{
				for(int k = 1;k <= n;k++)
				{
//					cout << "k : " << k << endl;
//					cout << j << " " << k << endl;
					dis[j][k] = min(dis[j][k],min(dis[j][a[x[i]]]+dis[b[x[i]]][k]+c[x[i]],dis[j][b[x[i]]]+dis[a[x[i]]][k]+c[x[i]]));
//					cout << dis[j][k] << endl;
				}
			}
			/*
			for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
			{
				dis[j][k]=min(dis[j][k],min(dis[j][a[x[i]]]+dis[b[x[i]]][k]+c[x[i]],dis[j][b[x[i]]]+dis[a[x[i]]][k]+c[x[i]]));
			}
			*/
//			cout << "true" << endl;
		}
//		cout << "true" << endl;
	}
//	cout << "true" << endl;
	for(int i = 1;i <= q;i++)
	{
		if(op[i] == 2)
		{
			if(ans[i] == inf)
			{
				printf("-1\n");
			}
			else
			{
				printf("%lld\n",ans[i]);
			}
		}
	}
//	cout << "true2" << endl;
	return 0;
}

一些感悟：
我出了一个很有意思的题，留给自己做做。
有一颗\(n\)个节点\(n-1\)条边的树，拥有\(q\)个询问，每个询问可能有以下两种操作：

• 1 x y表示删除这颗树上\(x\)节点与\(y\)节点连的一条边。
• 2 x y查询此时树上\(x\)点与\(y\)点的最近公共祖先。
  其中\(q \le 2*10^4,n \le 1000\)。

思路其实很简单，跟上面的操作一样，然后对于新加入的这个边，考虑这两个点和其他点的LCA，直接倍增搞一下就可以了吧。