ABC191 复盘

[ABC191C] Digital Graffiti

思路解析

求不规则图形的边数，根据题目可知多边形的内角只有 \(90^\circ\) 和 \(270^\circ\)，所以只需要从四个方向扫描一遍，求出每个方向上分别有几条边即可。

code

#include<bits/stdc++.h>
using namespace std;
int n, m;
char ch[15][15];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> ch[i][j];
		}
	}
	int ans = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 2; j <= m; j++) {
			if(ch[i][j] == '#' && ch[i + 1][j] == '.' && !(ch[i][j - 1] == '#' && ch[i + 1][j - 1] == '.')) ans++;
		}
	}
	for(int i = 1; i < n; i++) {
		for(int j = 2; j <= m; j++) {
			if(ch[i][j] == '.' && ch[i + 1][j] == '#' && !(ch[i][j - 1] == '.' && ch[i + 1][j - 1] == '#')) ans++;
		}
	}
	for(int j = 1; j < m; j++) {
		for(int i = 2; i <= n; i++) {
			if(ch[i][j] == '#' && ch[i][j + 1] == '.' && !(ch[i - 1][j] == '#' && ch[i - 1][j + 1] == '.')) ans++;
		}
	}
	for(int j = 1; j < m; j++) {
		for(int i = 2; i <= n; i++) {
			if(ch[i][j] == '.' && ch[i][j + 1] == '#' && !(ch[i - 1][j] == '.' && ch[i - 1][j + 1] == '#')) ans++;
		}
	}
	cout << ans;
	return 0;
}

[ABC191D] Circle Lattice Points

思路解析

可以根据数据范围 \(|X| \le 10^5\) 发现直接枚举两个维度肯定不行，但是我们发现可以把这个圆沿着每一条竖（或横）轴切开，然后对于每单独的一条分别统计这一条中有多少个整点，这样就可以做到 \(O(|X|)\) 完成。

注意在开方操作时会损失精度，所以可以在输入半径时先给半径加上一个很小的常数避免精度损失。

code

#include<bits/stdc++.h>
using namespace std;
#define double long double
double x, y, r;
int main() {
	cin >> x >> y >> r;
	r += 1e-14;
	long long ans = 0;
	for(int i = ceil(x - r); i <= floor(x + r); i++) {
		long long lt = (long long)ceil(y - sqrt(r * r - (x - i) * (x - i)));
		long long rt = (long long)floor(y + sqrt(r * r - (x - i) * (x - i)));
		ans += rt - lt + 1;
	}
	cout << ans;
	return 0;
}

[ABC191E] Come Back Quickly

思路解析

这题非常版，求问能否形成环，其实就是跑一遍 dijkstra，看能否再一次到达起点，若可以到达，则将答案设为第二次到达时所用的距离即可。

时间复杂度：对于每一个点都要跑一次最短路，\(O(n^2 \log n)\)。

code

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define fir first
#define sec second
const int N = 2e3 + 10;
int n, m, ind[N], tp[N], ans[N], dis[N];
vector< PII > g[N];
void dij(int st) {
	memset(dis, 0x3f, sizeof(dis));
	priority_queue< PII , vector< PII >, greater< PII > > q;
	q.push({0, st});
	while(!q.empty()) {
		int u = q.top().sec, d = q.top().fir; q.pop();
		for(auto it : g[u]) {
			int v = it.fir, w = it.sec;
			if(d + w < dis[v]) dis[v] = d + w, q.push({d + w, v});
		}
	}
	ans[st] = dis[st];
}
int main() {
	cin >> n >> m;
	memset(ans, 0x3f, sizeof(ans));
	for(int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		if(u == v) ans[u] = min(ans[u], w);
		g[u].push_back({v, w});
	}
	for(int i = 1; i <= n; i++) {
		dij(i);
	}
	for(int i = 1; i <= n; i++) {
		if(ans[i] < 1e9) cout << ans[i] << '\n';
		else cout << "-1\n";
	}
	return 0;
}

CF154C Double Profiles

思路解析

可以把题意转换成求有多少个点对 \((u,v)\) 使得两点连出的点集完全相同，这样只需要把每个点连出的点集求出来即可，如果直接用数组存肯定会超时，所以我们想把每一个与任意一点直接相连的点集进行压缩，可以想到使用字符串哈希的想法压缩一个点集。如果两点的点集哈希后相等，说明两点的点集也相等。

注意：需要特判点度为 \(0\) 的情况，以及需要分别讨论 \(i,j\) 之间有连边和没连边的情况，最后注意这题卡 map。

code

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const ull p = 13;
const int N = 1e6 + 10;
int n, m, sz[N];
ull hs[N], pw[N];
signed main() {
	cin >> n >> m;
	pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * p;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		sz[u]++; sz[v]++;
		hs[u] += pw[v];
		hs[v] += pw[u];
	}
	vector<ull> v, v1;
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		if(sz[i] > 0) v.push_back(hs[i]);
		else v.push_back(0);
		v1.push_back(hs[i] + pw[i]);
	}
	sort(v.begin(), v.end()); sort(v1.begin(), v1.end());
	for(int i = 0, j = i; i < v.size(); i = j) {
		j = i; while(j < v.size() && v[j] == v[i]) j++;
		ans += (long long)(j - i) * (long long)(j - i - 1) / 2;
	}
	for(int i = 0, j = i; i < v1.size(); i = j) {
		j = i; while(j < v1.size() && v1[j] == v1[i]) j++;
		ans += (long long)(j - i) * (long long)(j - i - 1) / 2;
	}
	cout << ans;
	return 0;
}