目录

C. Train and Queries

Cities and States S

C. Train and Queries

Problem - C - Codeforces

思路：假如我们是有一个数组是xxxy，我们可以任意到达一个x，再到达y，但是想想发现，到达了第一个x哪怕不需要第二次回到x也是能去y的；又假设存在xyyyyyy，我们可以反复到达y，但是为了我们只需要考虑最远的一个y就好了，因为我们不知道其它的y之间有没有穿插x
所以，用两个map，一个用来记录输入的数的位置，另一个用来记录相同的数的最远的下标

完整代码：

#include <bits/stdc++.h>
#define int long long
signed main()
{int t;std::cin >> t;while(t --){int n,k;std::cin >> n >> k;std::map<int,int> a,b;for(int i = 1;i <= n;i ++){int x;std::cin >> x;if(a.find(x)==a.end()){a[x]=i;b[x]=i;}else{b[x]=std::max(b[x],i);}}for(int i = 1;i <= k;i ++){int x,y;std::cin >> x >> y;if(a.find(x)==a.end()||a.find(y)==a.end()){std::cout<<"NO\n";}else if(a[x]<b[y]){std::cout<<"YES\n";}elsestd::cout<<"NO\n";}a.clear(),b.clear();}return 0;
}

Cities and States S

P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题就是找城市和州一一对应的个数，但是也有可能是一对多，就是一个州可能有多个城市，

所以用map<string,int>mp来实现

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 2e5 + 20;
std::string g[N];
signed main() {int n;std::cin >> n;int ans = 0;std::map<std::string,int> mp;for (int i = 1; i <= n; i++) {std::string s1, s2, s3;std::cin >> s1 >> s2;s3 = s1.substr(0, 2);if (s2 != s3) {mp[s2 + s3]++;ans += mp[s3 + s2];}}std::cout << ans;return 0;
}