Code Jam 2020 Round 1A

文章目录

• A. Pattern Matching（字符串构造）
• B. Pascal Walk（二进制分解）
• C. Square Dance（跳舞链）
• • 题目
  • 样例
  • 题解

A. Pattern Matching（字符串构造）

题目：
给定$n$个字符串，每个字符串仅由大写字母和若干个$\ast$构成，其中$\ast$可以表示成任意一个字符串（或者空串）。比如$\ast FUL$，可以表示成$AWFUL,FUL$
问能不能找到一个字符串$ans$，使得这$n$个字符串将所有的$\ast$号替换后都能够表示成$ans$

输入：
第一行一个整数$T(1\le T\le 100)$，代表$T$组测试数据
第二行一个整数$n(1\le n\le 50)$，代表有$n$个字符串需要同时满足
接下来$n$行，每行一个字符串 P i ( 2 ≤ P i ≤ 100 ) P_i(2\le P_i\le 100) Pi​(2≤Pi​≤100)

输出：
如果存在，输出$ans$；否则输出$\ast$

样例：

#input
2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ#output
Case #1: COCONUTS
Case #2: *

本题有3个难度，从最简单的开始考虑。

最简单的情况是$\ast$号在字符串的最左侧，也就是要求所有的字符串都具有相同的后缀。
可以找到这$n$个字符串里最长的一个，将其去掉$\ast$号后，看作答案。然后将其他字符串依次与最长的从后到前进行比较。

难度二中，依然只有一个$\ast$，只是位置是不固定的。如果$\ast$出现在字符串最右侧，则该字符串应该是答案的前缀；如果在最左侧，应该是答案的后缀；如果出现在中间，则$\ast$以左是前缀，以右是后缀。按照$\ast$位置对字符串进行分类，找到最长的前缀与最长的后缀，拼接后就是答案。

难度三中，$\ast$不止有一个。不过通过前两个难度，不难发现：对于一个字符串，它的第一个$\ast$号左边的部分应该是答案串的前缀，最后一个$\ast$号右边的部分应该是答案串的后缀。而对于剩下的中间部分，只需要将其中的所有字母加入到答案串中，一定能够满足。
因为在去掉字符串第一个$\ast$号左边的部分与最后一个$\ast$号右边的部分后，剩下的部分可以看作是被两个$\ast$号包住的（或者没有了）。比如$A\ast B\ast C$，可以得到$\ast B\ast$。因为左右都有$\ast$，所以可以匹配任意内容，只有$\ast$里面的字母出现了，就一定能够满足

#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define endl '\n'
typedef long long ll;
const int maxn = 50 + 10;
int n;
vector<string>pre, in, suf; //对于每个字符串，将其按照*划分
void init()
{pre.clear();in.clear();suf.clear();
}
void div(string& s) //对每个字符串进行划分
{int n = s.length();//取出第一个*左边的部分int l = 0;for (int i = 0; i < n; i++) {if (s[i] == '*') break;l++;}if (l > 0) {pre.push_back(s.substr(0, l));}//取出最后一个*右边的部分int r = 0;for (int i = n - 1; i >= 0; i--) {if (s[i] == '*') break;r++;}if (r > 0) {suf.push_back(s.substr(n - r));}//取出中间部分if (n - r - 1 > l-1) {in.push_back(s.substr(l, n - r - l));}
}
bool check(string& a, string& b)
{int n = a.length();for (int i = 0; i < n; i++) {if (a[i] != b[i]) return false;}return true;
}
bool cmp(string& a, string& b)
{return a.length() < b.length();
}
void solve()
{string ans;//检查前缀sort(pre.begin(), pre.end(),cmp);string temp_pre, temp_suf;if (!pre.empty()) {temp_pre = pre.back(); //找到最长的for (int i = 0; i < (int)pre.size() - 1; i++) {if (!check(pre[i], temp_pre)) {cout << "*" << endl;return;}}ans += temp_pre;}//检查后缀sort(suf.begin(), suf.end(),cmp);if (!suf.empty()) {temp_suf = suf.back();	//找到最长的reverse(temp_suf.begin(), temp_suf.end());	//翻转以方便比较for (int i = 0; i < (int)suf.size() - 1; i++) {string a = suf[i];reverse(a.begin(), a.end());if (!check(a, temp_suf)) {cout << "*" << endl;return;}}}//补充中间部分for (int i = 0; i < (int)in.size(); i++) {for (int j = 0; j < (int)in[i].size(); j++) {if (in[i][j] != '*') ans += in[i][j]; //取出中间部分所有字母}}reverse(temp_suf.begin(), temp_suf.end());ans += temp_suf;cout << ans << endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0);int T;cin >> T;for (int t = 1; t <= T; t++) {cout << "Case #" << t << ": ";init();cin >> n;for (int i = 1; i <= n; i++) {string temp;cin >> temp;div(temp);}solve();}
}

B. Pascal Walk（二进制分解）

题目：
对于一个至多500层的杨辉三角形，要求从顶点出发，不重复的走，使得所有经过的点之和等于给定的数$N$。

输入：
第一行一个$T(1\le T\le 100)$：测试组数
接下来$T$行，每行一个整数 N ( 1 ≤ N ≤ 1 0 9 ) N(1\le N\le 10^9) N(1≤N≤109)

输出：
打印路径

样例：

#input
1
4#output
Case #1:
1 1
2 1
2 2
3 3

• 杨辉三角形每行数字之和等于2的n次幂
  

根据这一性质，可以将策略制定为：从第1行开始，对于每一行，要么不取，要么就取完。如果选择不取，$N-=1$；如果选择取完， N − = 2 i N-=2^i N−=2i

如果路径不要求连续，只要把$N$对应二进制为1的所有位对应的行取完即可。比如 N = 5 10 = 10 1 2 N=5_{10}=101_{2} N=510​=1012​，只需要选择第一行和第三行。

由于 2 30 > 1 0 9 2^{30}>10^9 230>109，所以30行之内一定能够走完。先假设一定有30行不取，让$N-=30$。接下来对$N$进行二进制分解，二进制为1的那一位所对应的行就选择取完。因为一开始是假设有30行不走的，现在前30行里面取了$x$行，就需要在30行之后补齐$30-x$行不取的。

#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define endl '\n'
typedef long long ll;
const int maxn = 40;
vector<ll>v[maxn];
void init() //预处理杨辉三角形
{v[1].push_back(1);v[2].push_back(1);v[2].push_back(1);for (int i = 3; i <= 30; i++) {for (int j = 1; j <= i; j++) {if (j == 1 || j == i) v[i].push_back(1);else v[i].push_back(v[i - 1][j - 1] + v[i - 1][j]);}}
}
void solve(int& n)
{if (n <= 30) { //如果小于等于30，每行都选择不取即可for (int i = 1; i <= n; i++) {cout << i << " " << 1 << endl;}return;}n -= 30;int vis[maxn] = {0}, r = 1;while (n) {	//找到所有要取的行if (n & 1) vis[r] = 1;r++;	//下一行n >>= 1;}int flag = 1, num = 0;for (int i = 1; i <= 30; i++) {if (vis[i]) {num++;if (flag) { //从左到右for (int j = 1; j <= i; j++) {cout << i << " " << j << endl;}}else {	//从右到左for (int j = i; j >= 1; j--) {cout << i << " " << j << endl;}}flag ^= 1;}else {if (flag) cout << i << " " << 1 << endl;else cout << i << " " << i << endl;}}for (int i = 1; i <= num; i++) { //取了多少行，就要补足多少行if (flag) cout << 30 + i << " " << 1 << endl;else cout << 30 + i << " " << 30 + i << endl;}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0);init();int t;cin >> t;for (int T = 1; T <= t; T++) {cout << "Case #" << T << ":" << endl;int n;cin >> n;solve(n);}
}

C. Square Dance（跳舞链）

题目

给定一个$R\times C$的矩阵，每个格子初始都有一个人，能力值为 v i j v_{ij} vij​。现在进行若干轮比赛，每场比赛的有趣程度为当前比赛在场的所有人的能力值之和。

对于每轮比赛，如果一个人的能力值小于他上、下、左、右四个方向寻找遇到的第一个人能力值的平均值，则被淘汰。当无法淘汰任何一人时，比赛结束。问所有轮比赛的有趣值之和为多少？

样例

#input
1		T<=100
3 3		R*C<=1e5
1 1 1
1 2 1
1 1 1#output
Case #1: 16

在第一轮比赛结束后，矩阵的情况为 [ 1 . 1 . 2 . 1 . 1 ] \left[ \begin{matrix}1 &. &1\\.&2&.\\1&.&1 \end{matrix} \right] ⎣⎡​1.1​.2.​1.1​⎦⎤​，本轮将不能淘汰任何人，比赛结束。

题解

如果一个人被淘汰了，那么他四周的人的状态就会被改变。用一个队列$(dque)$维护本轮被淘汰的人，用另一个队列$(que)$维护本轮需要被更新的人。

每轮比赛先检查$que$中的人是否会被淘汰，如果淘汰则加入$dque$中。当$que$中所有的人都检查完后，对$deque$中的人进行操作，将他们的上下左右四个邻居加入$que$中（如果存在的话），再下次比赛时进行检查。

因为每次判断一个人是否被淘汰，需要快速找到4个方向第一个遇到的人，所以采用了链式结构（跳舞链）存储。如果一个节点被删除，只需要更新其邻居的指针即可，如x->left->right=x->right，更新该节点左边节点的右指针指向该节点的右指针指向内容

#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define endl '\n'
typedef long long ll;
const int maxn = 3e5 + 10;
struct Link {int l, r, u, d;
} link[maxn];
/*
dque:当前回合被淘汰的人
que:当前回合需要更新的人
inque:是否在当前回合被淘汰的队列中
isdel:某个坐标上的人是否被淘汰
*/
queue<pair<int, int>>dque, que;
bool inque[maxn], isdel[maxn];
int n, m, val[maxn];
int gid(int x, int y) 
{ 	//二维坐标转一维return x * (m + 2) + y;	//矩阵周围多围一圈，所以每行有m+2
}
void init()
{	//初始化矩阵while (!que.empty()) que.pop();while (!dque.empty()) dque.pop();for (int i = 0; i <= n + 1; i++) {for (int j = 0; j <= m + 1; j++) {int idx = gid(i, j);link[idx].l = max(0, j - 1);link[idx].r = min(m + 1, j + 1);link[idx].u = max(0, i - 1);link[idx].d = min(n + 1, i + 1);inque[idx] = false;}}}
inline void in_que(int x, int y)
{	//将邻居节点加入判断队列中int idx = gid(x, y);if (inque[idx]) return;if (isdel[idx]) return;que.push(make_pair(x, y));inque[idx] = true;
}
void solve()
{ll ans = 0, sum = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int idx = gid(i, j);cin >> val[idx];sum += val[idx];inque[idx] = true;isdel[idx] = false;que.push(make_pair(i, j));}}for (int rt = 0;; rt++) {int eli = 0;	//记录本轮淘汰人数，为0时结束ans += sum;while (!que.empty()) { //本轮需要检查的人int x = que.front().first, y = que.front().second;int idx = gid(x, y);que.pop();inque[idx] = false;int cnt = 0, skill = 0;if (link[idx].u > 0) ++cnt, skill += val[gid(link[idx].u, y)];if (link[idx].d <= n) ++cnt, skill += val[gid(link[idx].d, y)];if (link[idx].l > 0) ++cnt, skill += val[gid(x, link[idx].l)];if (link[idx].r <= m) ++cnt, skill += val[gid(x, link[idx].r)];if (cnt * val[idx] < skill){dque.push(make_pair(x, y));isdel[idx] = true; //淘汰} }while (!dque.empty()) { //本轮被淘汰的人int x = dque.front().first, y = dque.front().second;dque.pop();int idx = gid(x, y);++eli;sum -= val[idx];//将其邻居节点入队if (link[idx].u > 0) in_que(link[idx].u, y);if (link[idx].d <= n) in_que(link[idx].d, y);if (link[idx].l > 0) in_que(x, link[idx].l);if (link[idx].r <= m) in_que(x, link[idx].r);//更新邻居节点的指针link[gid(link[idx].u, y)].d = link[idx].d;link[gid(link[idx].d, y)].u = link[idx].u;link[gid(x, link[idx].l)].r = link[idx].r;link[gid(x, link[idx].r)].l = link[idx].l;}if (eli == 0) break;}cout << ans << endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0);int T; cin >> T;for (int i = 1; i <= T; i++) {cout << "Case #" << i << ": ";cin >> n >> m;init();solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！