如何做后台网站增删改,做类似淘宝的网站要多少钱,适合学生做的网站类型,重庆网站制作套餐上链接#xff1a;P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3405
上题干#xff1a; 题目描述 Farmer John 有若干头奶牛。为了训练奶牛们的智力#xff0c;Farmer John 在谷仓的墙上放了一…上链接P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3405
上题干 题目描述 Farmer John 有若干头奶牛。为了训练奶牛们的智力Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码前两位大写字母。 由于奶牛在谷仓里花了很多时间看这张地图他们开始注意到一些奇怪的关系。例如FLINT 的前两个字母就是 MIAMI 所在的 FL 州MIAMI 的前两个字母则是 FLINT 所在的 MI 州。 确切地说对于两个城市它们的前两个字母互为对方所在州的名称。 我们称两个城市是一个一对「特殊」的城市如果他们具有上面的特性并且来自不同的省。对于总共 N 座城市奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题 输入格式 输入共 N1 行。 第一行一个正整数 N表示地图上的城市的个数。 接下来 N 行每行两个字符串分别表示一个城市的名称2∼102∼10 个大写字母和所在州的代码22 个大写字母。同一个州内不会有两个同名的城市。 输出格式 输出共一行一个整数代表特殊的城市对数。 输入输出样例 输入 #1复制 6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL 输出 #1复制 1 说明/提示 数据规模与约定 对于 100%100% 的数据1≤N≤2×10^5城市名称长度不超过 10。 这道题其中思路很简单我们只要把每一个城市的名称的前两个字符以及它的代号分别存储在结构体里面然后再遍历一遍找出所有的特殊字符就可以了。 但是
有个问题在我们进行上面的操作会发现复杂度是On^2)的显然无法通过本题。
所以我们必须减少无效的遍历次数。
那这样的话我们就必须给所有的数据定义某个性质并且使得每对特殊城市之间都满足这个性质从而进行精确查找。
也就是说我们只要给每个数据定义某个性质然后只需要遍历一次每次查询这个性质是否在之前出现过如果出现过第二次出现的时候答案就说明多了一对这样的特殊城市。
那么怎么定义这个性质才能只让特殊城市之间相同
我们可以观察到一对特殊城市MI FA ————FA MI
只要把其中一个反过来那么这两个标记就相同了。我们可以利用哈希表
给每个数据都定义一个独一无二的哈希值这个哈希值就是我们所说的性质。
然后只要把代号和城市名字的前俩个字符反过来查询就可以了 上代码
using namespace std;
const int N 2e5 10;
const int base 27;
#define mod 1007
typedef long long LL;
int ans;
bool times 1;
struct city {string city, id;
};
city a[N];int fn[mod][mod];int main()
{int n;cin n;int ans 0;for (int i 1; i n; i){int hash1 0, hash2 0;cin a[i].city a[i].id;string t a[i].city.substr(0, 2);for(int j0;jt.size();j)hash1 (hash1*basea[i].city[j]) % mod;for (int j 0; j a[i].id.size(); j)hash2 (hash2 * base a[i].id[j]) % mod;if (hash1 ! hash2){fn[hash1][hash2];ans fn[hash2][hash1];}}cout ans;
}
