2019GPLT
7-2 6翻了
从左到右扫描输入的句子:如果句子中有超过 3 个连续的 6,则将这串连续的 6 替换成 9;但如果有超过 9 个连续的 6,则将这串连续的 6 替换成 27。其他内容不受影响,原样输出。
题解:模拟
救命了,这么水的模拟题都过不了
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i = 0, l, j, cnt = 0;
string s;
getline(cin, s);
l = s.length();
while (i < l)
{
if (s[i] != '6')
cout << s[i++];
else
{
for (cnt = 0; i < l && s[i] == '6'; i++, cnt++)
;
if (cnt > 9)
cout << 27;
else if (cnt > 3)
cout << 9;
else
while (cnt-- > 0)
cout << 6;
}
}
return 0;
}
7-3 敲笨钟
对每一行诗句,判断其是否压“ong”韵。即上下两句末尾的字都是“ong”结尾。如果是压此韵的,就按题面方法糟改之后输出,输出格式同输入;否则输出
Skipped
,即跳过此句。
题解:
利用\(find\)函数即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10, M = 4e5 + 10;
string s;
string cmp = "qiao ben zhong.";
void solve()
{
int cnt = 0;
getline(cin, s);
if (s.find("ong,") != -1 && s.find("ong.") != -1)
{
int pos = -1;
for (int i = 1; i <= 2; ++i)
{
pos = s.rfind(" ");
s.erase(pos);
}
pos = s.rfind(" ");
for (int i = 0; i <= pos; ++i)
cout << s[i];
cout << cmp << endl;
}
else
cout << "Skipped" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
cin.ignore();
while (T--)
{
solve();
}
return 0;
}
7-9 特立独行的幸福
对一个十进制数的各位数字做一次平方和,称作一次迭代。如果一个十进制数能通过若干次迭代得到 1,就称该数为幸福数。1 是一个幸福数。此外,例如 19 经过 1 次迭代得到 82,2 次迭代后得到 68,3 次迭代后得到 100,最后得到 1。则 19 就是幸福数。显然,在一个幸福数迭代到 1 的过程中经过的数字都是幸福数,它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数,是在一个有限的区间内不依附于任何其它数字的;其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数,则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数,其独立性为 2×4=8。
另一方面,如果一个大于1的数字经过数次迭代后进入了死循环,那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环,所以 29 就不幸福。
本题就要求你编写程序,列出给定区间内的所有特立独行的幸福数和它的独立性。
\(1<A<B≤10^4\)
题解:记忆化搜索\(DFS\)
在回溯的时候将不是依附的幸福数标记即可,同时我们需要一个数组在回溯的时候记录依附于该幸福数的数
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int l, r;
int vis[N];
int pre[N];
bool isprime(int x)
{
if (x < 2)
return false;
for (int i = 2; i <= x / i; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
map<int, bool> mp;
bool dfs(int x)
{
if (pre[x] > 0)
return true;
if (x == 1)
return true;
if (vis[x])
return false;
vis[x] = 1;
int t = x;
int y = 0;
while (t)
{
y += (t % 10) * (t % 10);
t /= 10;
}
bool f = dfs(y);
if (f)
{
mp[y] = false;
pre[x] = y;
}
vis[x] = 0;
return f;
}
void solve()
{
pre[1] = 0;
cin >> l >> r;
for (int i = l; i <= r; ++i)
{
if (mp.count(i) == 0)
{
if (!dfs(i))
mp[i] = false;
else
mp[i] = true;
}
}
int flag = false;
for (int i = l; i <= r; ++i)
{
if (mp[i] == true)
{
flag = true;
int cnt = 0;
int p = pre[i];
while (p != 0)
{
cnt++;
p = pre[p];
}
if (isprime(i))
cout << i << " " << 2 * cnt << endl;
else
cout << i << " " << cnt << endl;
}
}
if (!flag)
cout << "SAD" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-10 冰岛人
冰岛人沿用的是维京人古老的父系姓制,孩子的姓等于父亲的名加后缀,如果是儿子就加 sson,女儿则加 sdottir。因为冰岛人口较少,为避免近亲繁衍,本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。
对每一个查询,根据结果在一行内显示以下信息:
- 若两人为异性,且五代以内无公共祖先,则输出
Yes
;- 若两人为异性,但五代以内(不包括第五代)有公共祖先,则输出
No
;- 若两人为同性,则输出
Whatever
;- 若有一人不在名单内,则输出
NA
。
题解:模拟
根据题意模拟即可,但是需要注意以下几点:
- 只要有一人在五代以内的祖先和另一个异性的祖先是一样的,就说明有公共祖先
- 如果超过五代依旧没有出现公共祖先,那就不用再找了,说明五代以内没有公共祖先
- 对于不是本地人,我们实际上不需要去记录它的姓名,如果记录了,我们反而会在检查本地人时出现错误,因为很有可能是同名的
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10, M = 4e5 + 10;
map<string, int> mp;
int n, q;
struct node
{
int sex; // 0 man, 1 woman
string name;
} a[N];
bool check(string x, string y)
{
int i = 1;
for (string s1 = x; !s1.empty(); ++i)
{
int j = 1;
for (string s2 = y; !s2.empty(); ++j)
{
if (i >= 5 && j >= 5)
break;
if (s1 == s2 && (i < 5 || j < 5))
return false;
s2 = a[mp[s2]].name;
}
s1 = a[mp[s1]].name;
}
return true;
}
void solve()
{
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i)
{
string t, s;
cin >> t >> s;
mp[t] = i;
if (s.back() == 'm')
a[i].sex = 0;
else if (s.back() == 'f')
a[i].sex = 1;
else if (s.back() == 'n')
{
a[i].sex = 0;
int cnt = 4;
while (cnt--)
s.erase(s.end() - 1);
a[i].name = s;
}
else if (s.back() == 'r')
{
a[i].sex = 1;
int cnt = 7;
while (cnt--)
s.erase(s.end() - 1);
a[i].name = s;
}
}
cin >> q;
while (q--)
{
string t1, s1, t2, s2;
cin >> t1 >> s1 >> t2 >> s2;
if (!mp[t1] || !mp[t2])
cout << "NA" << endl;
else if (a[mp[t1]].sex == a[mp[t2]].sex)
cout << "Whatever" << endl;
else
{
if (check(t1, t2))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-13 地铁一日游
森森喜欢坐地铁。这个假期,他终于来到了传说中的地铁之城——魔都,打算好好过一把坐地铁的瘾!
魔都地铁的计价规则是:起步价 2 元,出发站与到达站的最短距离(即计费距离)每 K 公里增加 1 元车费。
例如取 K = 10,动安寺站离魔都绿桥站为 40 公里,则车费为 2 + 4 = 6 元。
为了获得最大的满足感,森森决定用以下的方式坐地铁:在某一站上车(不妨设为地铁站 A),则对于所有车费相同的到达站,森森只会在计费距离最远的站或线路末端站点出站,然后用森森美图 App 在站点外拍一张认证照,再按同样的方式前往下一个站点。
坐着坐着,森森突然好奇起来:在给定出发站的情况下(在出发时森森也会拍一张照),他的整个旅程中能够留下哪些站点的认证照?
地铁是铁路运输的一种形式,指在地下运行为主的城市轨道交通系统。一般来说,地铁由若干个站点组成,并有多条不同的线路双向行驶,可类比公交车,当两条或更多条线路经过同一个站点时,可进行换乘,更换自己所乘坐的线路。举例来说,魔都 1 号线和 2 号线都经过人民广场站,则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站(也拍不到认证照),因此森森乘坐地铁时换乘不受限制。
N 个车站 (1 ≤ N ≤ 200),M 条线路 (1 ≤ M ≤ 1500)
题解:Floyd + DFS
首先本题很明显要用到两点之间的最短路,并且n<200,说明我们可以使用\(floyd\)求出任意两个站点之间的距离,那么接下来我们对他会出站拍照的情况进行分析:
- 当前站点是端点站,所以我们需要记录每个站点是否是端点站
- 当前站点是某个费用下可以到达的最远的车站
所以我们可以先枚举每个站点作为起点,将其每种花费下的最远的站记录下来,也就是说如果u作为起点,那么他只会到达它每种花费下最远的站和端点站,这样的话我们就可以建图了,现在图上两点之间的边都是互相可达的
然后我们在面对查询时,我们只需要对图进行dfs即可,就能求出以u为起点所能到达的所有点,然后将这些点进行排序,输出即可
下面有个重点需要注意以下:
我们如何对每种花费记录最远的站是哪个站,实际上我们只需要利用map记录每种花费的最远距离,然后再遍历一遍所有点到u的距离是不是最远的即可,因为很有可能花费一样,路程也是一样最远的有好几个点,我们不要漏掉了
其次对于不连通的两个站点,我们没有必要再去计算,不然我们加入计算的话,那最大距离不就是无穷大了嘛,显然不对
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e2 + 10, M = 4e5 + 10;
int n, m, k, q;
vector<int> g[N];
int f[N][N];
bool isEnd[N];
bool vis[N];
set<int> st;
void dfs(int u)
{
for (auto v : g[u])
{
if (!vis[v])
{
st.insert(v);
vis[v] = true;
dfs(v);
}
}
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
f[i][j] = INF;
f[i][i] = 0;
}
for (int i = 1; i <= m; ++i)
{
int pre = -1;
int cnt = 0;
int dis, u;
do
{
cnt++;
if (cnt % 2 == 0)
cin >> dis;
else
{
cin >> u;
if (pre == -1)
{
isEnd[u] = true;
pre = u;
continue;
}
f[u][pre] = min(f[u][pre], dis);
f[pre][u] = min(f[pre][u], dis);
pre = u;
}
} while (cin.get() != '\n');
isEnd[u] = true;
}
for (int k = 1; k <= n; ++k)
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
for (int i = 1; i <= n; ++i)
{
map<int, int> mp;
for (int j = 1; j <= n; ++j)
if (i != j && f[i][j] != INF)
if (!mp[2 + f[i][j] / k] || f[i][j] > mp[2 + f[i][j] / k])
mp[2 + f[i][j] / k] = f[i][j];
for (int j = 1; j <= n; ++j)
{
if (f[i][j] == INF)
continue;
if (f[i][j] == mp[2 + f[i][j] / k] || isEnd[j] == true)
g[i].push_back(j);
}
}
cin >> q;
while (q--)
{
int s;
cin >> s;
memset(vis, 0, sizeof vis);
st.clear();
st.insert(s);
dfs(s);
for (auto it = st.begin(); it != st.end(); ++it)
{
if (it != st.begin())
cout << " ";
cout << *it;
}
cout << endl;
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
标签:std,10,const,2019GPLT,int,cin,mp
From: https://www.cnblogs.com/Zeoy-kkk/p/17201341.html