PTA天梯赛2017GPLT
7-6 整除光棍
给定一个不以5结尾的奇数\(x\)，求出数字\(n\)使得\(n*x=11...111\)，输出数字n和1的位数
题解：模拟竖式除法
我们一开始发现n只要一直往后*10+1一定就会出现\(n\%x=0\)，但是很显然n一定会很大，所以我们可以试着优化；我们在模拟竖式除法时发现：我们每次的被除数可以用前一次计算的余数表示，即\((n\%x)×10+1\),那么这样就解决了n很大的问题，\(n/x\)就是答案的每一位，但是我们要注意很有可能会有前导0，所以我们可以先让\(n>x\)
#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 x;
void solve()
{
cin >> x;
ULL n = 1;
int num = 1;
ULL ans = 0;
while (n < x)
{
n = n * 10 + 1;
num++;
}
while (1)
{
cout << n / x;
if (n % x == 0)
break;
n %= x;
n = n * 10 + 1;
num++;
}
cout << " ";
cout << num << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-10 重排链表
给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
Input 00100 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218Output 68237 6 00100 00100 1 99999 99999 5 12309 12309 2 00000 00000 4 33218 33218 3 -1
题解：单链表
考察数据结构单链表的使用，我们使用数组模拟即可，我们只需要通过\(address\)数组记录每个节点的地址即可，然后通过题目可以知道我们可以使用双指针
#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 head, e[N], ne[N];
int n;
int add[N];
void solve()
{
cin >> head >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i)
{
int idx, val, next;
cin >> idx >> val >> next;
e[idx] = val;
ne[idx] = next;
}
int pos = head;
while (pos != -1)
{
add[++cnt] = pos;
pos = ne[pos];
}
int l = 1, r = cnt;
head = add[cnt];
while (l < r)
{
ne[add[r]] = add[l];
r--;
ne[add[l]] = add[r];
l++;
ne[add[r]] = add[l];
}
ne[add[r]] = -1;
pos = head;
while (pos != -1)
{
if (~ne[pos])
printf("%05d %d %05d\n", pos, e[pos], ne[pos]);
else
printf("%05d %d -1\n", pos, e[pos]);
pos = ne[pos];
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-11 图着色问题
图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。
题解：dfs染色法
注意该图很有可能不是连通图，可能是由许多连通块组成的，所以我们需要对每一个连通块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 = 1e5 + 10, M = 4e5 + 10;
vector<int> g[N];
int n, m, k, q;
int vis[N];
int a[N];
bool dfs(int u, int col)
{
vis[u] = col;
for (auto v : g[u])
{
if (!vis[v])
{
if (!dfs(v, a[v]))
return false;
}
else if (vis[v] == col)
return false;
}
return true;
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1, u, v; i <= m; ++i)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> q;
while (q--)
{
set<int> st;
for (int i = 1; i <= n; ++i)
vis[i] = 0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
st.insert(a[i]);
}
int cnt = 0;
for (auto i : st)
cnt++;
if (cnt > k || cnt < k)
{
cout << "No" << endl;
continue;
}
bool flag = flag;
for (int i = 1; i <= n; ++i) //我们需要对每一个连通块dfs
if (!vis[i])
{
flag = dfs(i, a[i]);
if (!flag)
break;
}
if (!flag)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-13 二叉搜索树的结构
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。
题解：
首先我们要知道二叉搜索树的概念，我们将一系列整数插入一颗初始为空的二叉搜索树，根据定义得知，我们每次插入一个点，必须从根节点开始遍历
我们来讲一讲二叉搜索树的建树过程：
首先第一个数一定是二叉搜索树的根，然后我们对数组中的每一个数进行dfs，假设当前插入的数为\(val\)，那么如果\(val\)比当前\(dfs\)遍历到的节点\(u\)的值小，那么\(val\)应该位于它的左子树范围内，如果说u节点没有左儿子，那么我们就找到了要插入的地方，所以我们新建一个点，\(idx++\)（idx代表当前树上节点的数量，类似单链表），同时我们可以利用\(map\)存储每个节点对应的下标，这样方便处理询问，比如样例中的1对应下标为2，即\(mp[1]=2\)，
如果说u节点有左儿子，那么我们可以直接递归u节点的左儿子；
同理对于\(val\)比当前\(dfs\)遍历到的节点\(u\)的值大，也是一样，不再赘述
- 我们来讲一下节点需要存储的信息：
深度\(dep\)，父亲节点的下标\(fa\)，左儿子的下标\(lson\)，右儿子的下标\(rson\)，当前节点的值\(val\)
#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 = 1e3 + 10, M = 4e5 + 10;
int n;
int a[N];
struct node
{
int val;
int dep;
int fa;
int lson;
int rson;
} e[N];
int idx;
map<int, int> mp;
void dfs(int u, int val)
{
if (val < e[u].val)
{
if (!e[u].lson)
{
e[u].lson = ++idx;
e[idx] = {val, e[u].dep + 1, u, 0, 0};
mp[val] = idx;
return;
}
else
dfs(e[u].lson, val);
}
else
{
if (!e[u].rson)
{
e[u].rson = ++idx;
e[idx] = {val, e[u].dep + 1, u, 0, 0};
mp[val] = idx;
return;
}
else
dfs(e[u].rson, val);
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
e[++idx] = {a[1], 1, 0, 0, 0};
mp[a[1]] = idx;
for (int i = 2; i <= n; ++i)
dfs(1, a[i]);
int rt = a[1];
int q;
cin >> q;
while (q--)
{
int u, v;
string s;
cin >> u;
cin >> s;
if (s == "is")
{
cin >> s;
cin >> s;
if (s == "root")
{
if (u == rt)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else if (s == "parent")
{
cin >> s;
cin >> v;
if (e[mp[v]].fa == mp[u] && mp[u] != 0 && mp[v] != 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else if (s == "left")
{
cin >> s;
cin >> s;
cin >> v;
if (e[mp[v]].lson == mp[u] && mp[u] != 0 && mp[v] != 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else if (s == "right")
{
cin >> s;
cin >> s;
cin >> v;
if (e[mp[v]].rson == mp[u] && mp[u] != 0 && mp[v] != 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
else if (s == "and")
{
cin >> v;
cin >> s;
cin >> s;
if (s == "siblings")
{
if (e[mp[u]].fa == e[mp[v]].fa && mp[u] != 0 && mp[v] != 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else
{
if (e[mp[u]].dep == e[mp[v]].dep && mp[u] != 0 && mp[v] != 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
cin >> s;
cin >> s;
cin >> s;
}
}
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-14 森森快递
森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N个城市，这些城市从左到右依次从0到(N−1)编号。由于道路限制，第i号城市（i=0,⋯,N−2）与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过\(C_i\)公斤。
公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从\(S_j\)号城市运输到\(T_j\)号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。
为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。
题解： 贪心+线段树维护区间最小值和区间修改
首先对于两端区间\([a,b],[c,d]\)来说，对答案产生贡献会存在三种情况：
- \([a,b]和[c,d]\)之前不存在交集，那么这两个订单可以同时执行，不存在冲突和限制
- \(若[c,d]内含于[a,b]\)，那么我们只能执行\([c,d]\)这个订单
- \(若[c,d]和[a,b]的交集为[b,c]\),那么此时最大运输货物重量为\(min(min[b,c],min[a,c]+min[b,d])\)
综上所述：我们发现我们只要对询问区间按照区间右端点升序排列，然后对于排序之后的区间从左到右遍历，我们每次利用线段树求出区间最小值后，再将这段区间所有承重全部减去最大货物重量，即可贪心求出答案
#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;
int n, q;
struct Node
{
int l, r;
bool operator<(const Node &t) const
{
if (r != t.r)
return r < t.r;
else
return l < t.l;
}
};
vector<Node> a;
int w[N];
struct info
{
int minn;
};
struct node
{
int l, r, lazy;
info val;
} seg[N << 2];
info operator+(const info &a, const info &b)
{
info c;
c.minn = min(a.minn, b.minn);
return c;
}
void settag(int id, int tag)
{
seg[id].val.minn += tag;
seg[id].lazy += tag;
}
void up(int id)
{
seg[id].val = seg[lson].val + seg[rson].val;
}
void down(int id)
{
if (seg[id].lazy == 0)
return;
settag(lson, seg[id].lazy);
settag(rson, seg[id].lazy);
seg[id].lazy = 0;
}
void build(int id, int l, int r)
{
seg[id].l = l, seg[id].r = r;
int mid = l + r >> 1;
if (l == r)
{
seg[id].val.minn = w[l];
return;
}
build(lson, l, mid);
build(rson, mid + 1, r);
up(id);
}
void modify(int id, int ql, int qr, int val)
{
int l = seg[id].l, r = seg[id].r;
int mid = l + r >> 1;
if (ql <= l && r <= qr)
{
settag(id, val);
return;
}
down(id);
if (qr <= mid)
modify(lson, ql, qr, val);
else if (ql > mid)
modify(rson, ql, qr, val);
else
{
modify(lson, ql, qr, val);
modify(rson, ql, qr, val);
}
up(id);
}
info query(int id, int ql, int qr)
{
int l = seg[id].l, r = seg[id].r;
int mid = l + r >> 1;
if (ql <= l && r <= qr)
return seg[id].val;
down(id);
if (qr <= mid)
return query(lson, ql, qr);
else if (ql > mid)
return query(rson, ql, qr);
else
return query(lson, ql, qr) + query(rson, ql, qr);
}
void solve()
{
cin >> n >> q;
for (int i = 1; i < n; ++i)
cin >> w[i];
build(1, 1, n - 1);
while (q--)
{
int l, r;
cin >> l >> r;
if (l > r)
swap(l, r);
l++;
a.push_back({l, r});
}
sort(all(a));
int ans = 0;
for (auto [l, r] : a)
{
int tmp = query(1, l, r).minn;
ans += tmp;
modify(1, l, r, -tmp);
}
cout << ans << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
7-15 森森美图
给定你坐标矩阵中起始点A和终点B，让你求出两条互不经过A,B之间连线的点的两条最短路径之和
题解： 最短路+计算几何（叉积）
很显然是最短路问题，我们可以选择spfa或者dijstra求解，但是我们这边如何去引导spfa要么往上走要么往下走呢，我们可以利用叉积，虽然叉积是三维向量的乘积，但是我们只需让z坐标为0即可，设起点为A，终点为B，图上任意一点为C：
- 如果\(\vec{AB}×\vec{AC}>0\),说明C在向量AB逆时针旋转<180°的方向上，或者在样例中是直线AB的右上方
- 如果\(\vec{AB}×\vec{AC}<0\),说明C在向量AB逆时针旋转>180°的方向上，或者在样例中是直线AB的左下方
- 如果\(\vec{AB}×\vec{AC}=0\),说明C于直线AB共线
那么我们只要进行两次spfa即可，第二次只要交换起始点位置即可，但是我们要注意起点和终点对答案的贡献多加了一次，最后需要减去。
#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 = 1e2 + 10, M = 4e5 + 10;
int n, m;
double a[N][N];
int sy, sx, ey, ex;
int vis[N][N];
double dis[N][N];
int dir1[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int dir2[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
const double k = sqrt(2) - 1;
double ans = 0.0;
int cal(pii p1, pii p2)
{
auto [x1, y1] = p1;
auto [x2, y2] = p2;
return (x1 * y2 - y1 * x2);
}
void spfa(int sx, int sy)
{
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
dis[i][j] = inf;
queue<pii> q;
q.push({sx, sy});
dis[sx][sy] = a[sx][sy];
vis[sx][sy] = 1;
while (q.size())
{
auto [x, y] = q.front();
// cout << x << " " << y << endl;
q.pop();
vis[x][y] = 0;
for (int i = 0; i < 4; ++i)
{
int nx = x + dir1[i][0];
int ny = y + dir1[i][1];
if ((nx >= 0 && nx < n && ny >= 0 && ny < m && cal(mpk(ex - sx, ey - sy), mpk(nx - sx, ny - sy)) > 0) || (nx == ex && ny == ey))
{
if (dis[nx][ny] > dis[x][y] + a[nx][ny])
{
dis[nx][ny] = dis[x][y] + a[nx][ny];
if (!vis[nx][ny])
q.push({nx, ny}), vis[nx][ny] = 1;
}
}
}
for (int i = 0; i < 4; ++i)
{
int nx = x + dir2[i][0];
int ny = y + dir2[i][1];
if ((nx >= 0 && nx < n && ny >= 0 && ny < m && cal(mpk(ex - sx, ey - sy), mpk(nx - sx, ny - sy)) > 0) || (nx == ex && ny == ey))
{
if (dis[nx][ny] > dis[x][y] + a[nx][ny] + (a[x][y] + a[nx][ny]) * k)
{
dis[nx][ny] = dis[x][y] + a[nx][ny] + (a[x][y] + a[nx][ny]) * k;
if (!vis[nx][ny])
q.push({nx, ny}), vis[nx][ny] = 1;
}
}
}
}
ans += dis[ex][ey];
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> a[i][j];
cin >> sy >> sx >> ey >> ex;
spfa(sx, sy);
swap(sx, ex), swap(sy, ey);
spfa(sx, sy);
cout << fixed << setprecision(2) << ans - a[sx][sy] - a[ex][ey] << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}