A. Vika and Her Friends

Problem - A - Codeforces

题意：

​ 在\(n*m\)的范围内，\(a\)和她的朋友在追逐游戏，每秒\(a\)和朋友必须从当前位置移到相邻的格子里（上下左右），在这一秒结束时\(a\)不能和朋友在同一格内。现在知道\(a\)和每一个朋友的初始位置，问\(a\)是否会被朋友追上。

思路：

​ 比赛的时候手推模拟了几轮，发现当\(a\)和朋友的曼哈顿距离为奇数时，不会被追上，当曼哈顿距离为偶数时，则一定会在有限轮被追上。

​ 赛后仔细想了想，可以把每个格子进行染色，得到类似国际棋盘的棋盘格，若二者在相同颜色的格子内，则一定能被追上，否则不会。

void QAQ(){
    cin >> n >> m >> k;
    int x, y;
	cin >> x >> y;
	bool flag = true;
	for(int i = 1; i <= k; i ++){
		int xx, yy;
		cin >> xx >> yy;
		if((abs(x - xx) + abs(y - yy)) % 2 == 0){
			flag = false;
		}
	}
	if(flag) cout << "YES" << endl;
	else cout << "NO" << endl;
}

B. Vika and the Bridge

Problem - B - Codeforces

题意：

​ 一段长度为\(n\)的序列，每个位置被涂上了\(1-k\)中的一种颜色，现在需要从\(0\)走到\(n + 1\)，每次只能限定一个颜色行走。我们可以最多进行一个操作，将任意\(1-n\)的一个位置的颜色改变为我们想要的颜色，问我们每次行走跳过格子的最大值最小为多少。

思路：

​ 一开始一眼二分，敲完后意识到时间复杂度不对。于是重新思考解法。

​ 发现每次改变颜色时，将当前改变的颜色的最大跨越距离减半为最佳。那么就将减半后的距离和原来第二大的距离做比较取大者，就是当前颜色一次改变后最大的跨越距离，对每个颜色记录，取其中最小的距离即可。

void QAQ(){
    cin >> n >> m;
    vector<vector<int>> col(m + 1);
    for(int i = 1; i <= n; i ++){
    	int x;
    	cin >> x;
    	col[x].emplace_back(i);
	}
	int ans = INF;
	for(int i = 1; i <= m; i ++){
		int maxx = 0, maxxx = 0;
        //最大        次大
		col[i].emplace_back(n + 1);
		int k = 0;
		for(auto x : col[i]){
			int tmp = x - k - 1;
			k = x;
			if(tmp > maxx){
				maxxx = maxx;
				maxx = tmp;
			}
			else if(tmp > maxxx){
				maxxx = tmp;
			}
		}
		ans = min(ans, max(maxx / 2, maxxx));
	}
	cout << ans << endl;
}

C. Vika and Price Tags

C - Vika and Price Tags

题意：

​ 初始两串数列\(a, b\)，对于第\(i\)个数，令\(c_i=|a_i-b_i|\)，然后将数列\(a=b,b = c\)。重复这样的操作，问是否可能让\(a\)串全部变成0。

思路：

​ 很显然可以看出当出现第一个0之后，每三轮会有一次循环，那么我们需要计算需要多少轮会出现第一个0。

​ 进行手推模拟，若假设\(a > b\)，那么\(a, b\ \ ->\ \ b,a -b\ \ ->\ \ a-b,a-2b\ \ ->\ \ a-2b,b\)，可以发现，每隔三轮，如果\(a>2b\)，那么\(a\)就会相应的减少\(2b\)，反之亦然，那么我们可以靠这个来对计算进行加速。

void QAQ(){
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i ++){
		cin >> b[i];
	}
	int tmp = -1;
    //记录当前循环次数对3取余结果，每对数的结果相同，就可以认为能在有限轮循环内得到全为0的数列
	for(int i = 1; i <= n; i ++){
		int cnt = 0;
		if(!a[i] && !b[i]) continue;//ab全为0时无论多少轮循环都不影响
		auto cal = [&] (int &x, int &y) -> void{
			if(y && x > 2 * y) x %= 2 * y;
			else if(x && y > 2 * x) y %= 2 * x;
            //根据上面手推的结果对计算加速
			cnt = (cnt + 1) % 3;
			x = abs(y - x);
			swap(x, y);
		};
		while(a[i]){//要求a_i为0
			cal(a[i], b[i]);
		}
		if(tmp != -1 && tmp != cnt){
			cout << "NO" << endl;
			return ;
		}
		tmp = cnt;
	}
	cout << "YES" << endl;
}

tips: 当面对若干个数的运算找规律时，可以考虑限定其的大小关系（如大于或小于），使用诸如a，b之类的字母进行替换运算，更容易发现规律