算法Y —— 进阶篇

算法Y —— 进阶篇"/>

算法Y —— 进阶篇

文章目录

• 往年题
• IEEEXtreme 10.0
• IEEEXtreme 11.0
• • Blackgate Penitentiary
  • 无向图 判断是否有环
  • • DFS
    • 拓扑排序
  • Running Up Stairs
  • Fibonacci
  • Rumor
  • Aeneas' cryptographic disc (4th c. B.C.)
  • BeetleBag
  • RecXor
  • Gotta Catch 'Em All
  • Let’s Cheer Up Bob
  • Shuffle
  • • 建模为 最大流问题
    • DFS
  • Octopuses with Watches
  • Fill The Pixels
  • Preparing for Xtreme 12.0
  • Orienteering
  • Collecting Gold
  • Math Challenge
  • Quipu Function
  • The Fast and the Curious
  • Jarawi and The Interview
  • Game of Life
  • Odd Cycle Check
  • Sub Array Sum Problem
  • Mister Counter
  • Maximum Sum
  • Pyramid
  • King Capture
  • Lion Territory
  • Elementary
  • Knin
• IEEEXtreme 12.0
• • Troll Coder
  • Bear Sums
  • Lemons
  • Drawing Rooted Binary Trees
  • Telescope Scheduling
  • Xplore
  • Bit Soccer
  • Xtreme Fake Coins
  • Product Rectangle
  • Barter System
  • Magic Spell
  • Barrett Reduction
  • Infinite snakes and ladders
  • Factorial Zeros
  • Tree Fun
  • Gotta ~ Catch 'Em All
  • Make Distinct
  • The Gold-diggers
  • Organizational Chart
  • Tweedledee's Split Brackets
  • Troll Coder - Escape
  • Tweedledum's Nested Brackets
  • Friendly Sequences
  • PIEEEXMan
• IEEEXtreme 13

往年题

IEEEXtreme 10.0

• 参考 - 链接

IEEEXtreme 11.0

• 参考 - 链接

Blackgate Penitentiary

• 输入信息：人名 + 身高
• 输出：按身高顺序，相同身高在同一行输出，再输出两个数字表示此行人员编号 的上下界！

#include <bits/stdc++.h>
using namespace std;
int N = 0;
map<int, vector<string>> M;int main() {cin >> N;while (N--) {string tmp;int num;cin >> tmp >> num;M[num].push_back(tmp);}int pos = 1;for (auto& [a, x] : M) {sort(x.begin(), x.end());for (string& s : x) {cout << s << " ";}cout << pos << " " << pos + x.size() - 1 << endl;pos += x.size();}
}

无向图 判断是否有环

• T个测试样例
• 顶点N，边数M
• 再来一行：a - b / c - d / e - f / … …

DFS

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Graph {
public:Graph (int n) {vertex_num = n;G.resize(vertex_num); // 邻接表isVisited.resize(vertex_num, false); // 遍历数组}void construct(int a, int b) {G[a].push_back(b); // 构建图G[b].push_back(a);}bool circle() {for (int i = 0; i < vertex_num; i++) {if (!isVisited[i]) { // 从每个未访问的节点 开始找isVisited[i] = true; // 判断每个节点是不是被其他 非父节点 访问了 if (!dfs(i, -1)) return false;}}return true;}bool dfs(int cur, int pre) {for (int i = 0; i < vertex_num; i++) {if (isConnected(cur, i)) { // cur - i// i被二次访问if (i != pre && isVisited[i]) return false; // i == fatherelse if (isVisited[i]) continue; else { // i is avalibleisVisited[i] = true;if (!dfs(i, cur)) return false;}}}return true;}bool isConnected(int i, int j) {return find(G[i].begin(), G[i].end(), j) != G[i].end();}
private:vector<vector<int>> G;vector<bool> isVisited;int vertex_num;
};int main() {int T = 0;cin >> T;while (T--) {int n, m = 0;cin >> n >> m;Graph graph(n);while (m--) {int a, b = 0;cin >> a >> b;graph.construct(a, b);}cout << !graph.circle() << endl;}return 0;
}

拓扑排序

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;class topologySorting {
public:topologySorting(int n) {vertex_num = n;G.resize(vertex_num);D.resize(vertex_num);}void construct(int a, int b) {G[a].push_back(b);G[b].push_back(a);}bool sorting() {for (int i = 0; i < vertex_num; i++) {D[i] = G[i].size(); // 度数组if (D[i] <= 1) Q.push(i);}int cnt = 0;while (!Q.empty()) {cnt++;int root = Q.front();Q.pop();for (auto cld : G[root]) {D[cld]--;if (D[cld] == 1) Q.push(cld);}}return cnt == vertex_num; // 能不能正确排序  }private:vector<vector<int>> G; // 图的邻接表queue<int> Q; // 队列vector<int> D; // 度int vertex_num;
};int main() {int T = 0;cin >> T;while (T--) {int n, m = 0;cin >> n >> m;topologySorting ts(n);while (m--) {int a, b = 0;cin >> a >> b;ts.construct(a, b);}cout << !ts.sorting() << endl;}return 0;
}

Running Up Stairs

• 斐波拉契数列问题
• 这题主要卡大数 处理

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;string addStrings(string num1, string num2) {if (num1.size() < num2.size()) swap(num1, num2);int i = num1.size() - 1, j = num2.size() - 1;int plus = 0;while (i >= 0 && j >= 0) {int sum = num1[i] - '0' + num2[j] - '0' + plus;num1[i] = (sum % 10) + '0';plus = sum / 10;i--; j--;}while (i >= 0) {int sum = num1[i] - '0' + plus;num1[i] = (sum % 10) + '0';plus = sum / 10;i--;}if (plus > 0) num1.insert(num1.begin(), plus + '0');return num1;
}string seq(ull n) {if (n <= 2) return to_string(n);string a = "1", b = "1"; // 0 1 2 3 ...for(ull i = 2; i <= n; ++i) {// 换成ull格式还是不行 用了字符串加法string c = addStrings(a, b);  a = b;b = c;}return b;
}int main() {int T = 0;cin >> T;while (T--) {ull N = 0;cin >> N;// like斐波拉契数列cout << seq(N) << endl;}
}

• 无脑python，就简单点

T = int(raw_input())
for t in range(T):val1 = 1val2 = 1;N = int(raw_input())for i in range(N - 1):val = val1 + val2val1 = val2val2 = valprint val2

Fibonacci

• 从0开始：0 1 1 2 3 5 8 13 21 34 55 89 …
• 直接用 斐波拉契数列 的通项 公式，矩阵形式，如下，（下图以0为起始元素）：
  

#include <cstdio>
#include <algorithm>
#include <vector>#define X first
#define Y second
#define mp make_pair
#define pb push_backusing namespace std;typedef pair< int, int > pii; // be 1x2 matrix
typedef pair< pii, pii > table; // be 2x2 matrixtable product( table A, table B ) {int num1 = A.X.X * B.X.X + A.X.Y * B.X.Y;int num2 = A.X.X * B.Y.X + A.X.Y * B.Y.Y;int num3 = A.Y.X * B.X.X + A.Y.Y * B.X.Y;int num4 = A.Y.X * B.Y.X + A.Y.Y * B.Y.Y;num1 %= 10;num2 %= 10;num3 %= 10;num4 %= 10;return mp( mp( num1, num3 ), mp( num2, num4 ) );
}table expo( table A, int v ) {if( v == 0 ) return mp( mp( 1, 0 ), mp( 0, 1 ) );if( v == 1 ) return A;table B = expo( A, v / 2 );if( v % 2 ) return product( product( B, B ), A );else return product( B, B );
}int main( void ) {int T;scanf("%d", &T );while( T-- ) {int N;scanf("%d", &N );// pii A = mp( 1, 0 ); // 初始条件 0 1 1 2 3 5 8 ...table B = mp( mp( 1, 1 ), mp( 1, 0 ) );B = expo( B, N ); printf("%d\n", B.X.X ); // res = (B矩阵乘法A)[0][0] }return 0;
}

Rumor

• 无限层 满二叉树，编码方式：从1开始，从左到右，1，2，3，4，5 …
• 每次输入 两个 标签，X和Y，计算两个节点之间的最短距离
• 推导：
  

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long llu;int main() {int T = 0;cin >> T;while (T--) {llu n1, n2;cin >> n1 >> n2;int res = 0;llu t1 = n1, t2 = n2;int dep1 = 0, dep2 = 0;// 1 get the depthwhile (t1 > 0) {dep1++;t1 /= 2LLU;}while (t2 > 0) {dep2++;t2 /= 2LLU;}if (dep1 > dep2) {swap(n1, n2);swap(dep1, dep2);}// 2 use depths and labels to cntn2 /= llu(1 << llu(dep2 - dep1)); // set to same depthres += (dep2 - dep1); while (n1 != n2) { // same depths find LCAn1 /= 2LLU;n2 /= 2LLU;res += 2;}cout << res << endl;}return 0;
}

• 其实类似的思想，LC上有题 名为 《二叉树中所有距离为 K 的结点》
• 其中一种 为 先算 每个节点到根节点之间的距离，使用了类似的距离计算方法：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void dfs(TreeNode* node, int dis) {if (!node) return;M[node] = dis;dfs(node->left, 2 * dis + 1);dfs(node->right, 2 * dis + 2);}int get_dist(int d1, int d2) {int res = 0;while (d1 != d2) {if (d1 > d2) d1 = (d1 - 1) / 2;else d2 = (d2 - 1) / 2;res++;}return res;}vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {if (!root) return {};dfs(root, 0);if (M.count(target) == 0) return {};vector<int> res;int T = M[target];for (auto& x : M) {if (get_dist(x.second, T) == K)res.push_back(x.first->val);}return res;}
private:unordered_map<TreeNode*, int> M;
};

Aeneas’ cryptographic disc (4th c. B.C.)

• 一个盘，有27个小洞
• 一个洞在圆心，其余洞排列在 圆上 且以 a b c d e … z 标注
• 圆心到 圆上各洞 的半径 给出 且一致
• 每个洞相对于 x轴 正半轴的 逆时针旋转 角度 给出 (度数形式)
• 之后 给出一个字符串，计算从圆心开始出发，到各个字母的总线程长度

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long llu;
#define PI 3.14159265
double coords[26][2] = {0};
double dists[27][27] = {0}; // 26下标表示圆心 double distCnt(char a, char b) {a |= ' '; b |= ' '; // convert to lower letters double x1 = coords[a - 'a'][0];double y1 = coords[a - 'a'][1];double x2 = coords[b - 'a'][0];double y2 = coords[b - 'a'][1];return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}int main() {double r = 1;cin >> r;for (int i = 0; i < 26; i++) {char c;double theta = 0;cin >> c >> theta;c |= ' '; // 全变成小写coords[c - 'a'][0] = r * cos(theta * PI / 180);coords[c - 'a'][1] = r * sin(theta * PI / 180);}for (int i = 0; i <= 26; i++) {for (int j = 0; j <= 26; j++) {if (i == j) dists[i][j] = 0;else if (i == 26 || j == 26) dists[i][j] = r;else dists[i][j] = distCnt(i + 'a', j + 'a');}}// get stringstring str;while (str.empty()) getline(cin, str); // need whileint prev = 26, cur;double res = 0;for (size_t i = 0; i < str.size(); i++) {if (!isalpha(str[i])) continue;str[i] |= ' ';cur = str[i] - 'a';res += dists[prev][cur];prev = cur;}cout << llu(ceil(res)) << endl; // rounded up
}

BeetleBag

• 01 背包问题

#include <bits/stdc++.h>
using namespace std;
int main() {int T = 0;cin >> T;while (T--) {int cap = 0, n = 0;vector<int> dp, weis, pows;cin >> cap >> n;weis.resize(n, 0);pows.resize(n, 0);dp.resize(cap + 1, 0);for (int i = 0; i < n; i++)cin >> weis[i] >> pows[i];// DPfor (int i = 0; i < n; i++) {for (int j = cap; j >= weis[i]; j--) {dp[j] = max(dp[j], dp[j - weis[i]] + pows[i]);}}cout << dp.back() << endl;}return 0;
}

RecXor

• 给一个矩阵，长 l l l 宽 h h h
• 矩阵内都是 连续的 整数编码
• 矩阵左上角起始数字 为 n n n
• 给两个数字 d 1 d1 d1, d 2 d2 d2， 以其为对角线做框
• 这两个矩阵 不公共区域 的 全部数字 的 XOR 值
  
  

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;ll xx(ll n) {// 表示[1, n]范围的连续整数异或结果if (n % 4 == 0) return n; // mod 4 = 0if (n % 4 == 1) return 1; // 1if (n % 4 == 2) return n + 1; // 2return 0; // 3
}int main( void ) {int T;scanf("%d", &T );for( int t = 1; t <= T; t++ ) {ll l, h, n, d1, d2;scanf("%lld%lld%lld%lld%lld", &l, &h, &n, &d1, &d2 );ll first = xx( n + l* h - 1 ) ^ xx( n - 1 );ll second = 0;ll x1, y1, x2, y2;// (y1,x1) -> (y2,x2) // LeftUp -> RightUpx1 = ( d1 - n ) / l + 1;y1 = (d1 - n + 1 ) - ( x1 - 1 ) * l;x2 = ( d2 - n ) / l + 1;y2 = ( d2 - n + 1 ) - ( x2 - 1 ) * l;if( x1 > x2 ) swap( x1, x2 );if( y1 > y2 ) swap( y1, y2 );// rows: x1 ~ x2// left ~ right 为每个row的连续整数范围 for( int i = x1; i <= x2; i++ ) {ll left = n + y1 - 1 + ( i - 1 ) * l;ll right = n + y2 + ( i - 1 ) * l - 1;second ^= xx( right ) ^ xx( left - 1 );}ll res = first ^ second;printf("%lld\n", res );}return 0;
}

Gotta Catch 'Em All

• 二维矩阵
• 左上和右下 都是 0，其他位置有正有负
• 路径问题，路径上每个位置 是前面的累加和
• 任意的位置 (累加) 都得 大于0
• 求可以从左上 到 右下 的 最小 初始体力
• 只能 从左往右 和 从上往下 移动

#include <bits/stdc++.h>
using namespace std;
int row, col;
vector<vector<int>> M, dp;bool isValid(int heath_val) {dp[1][1] = heath_val;for (int i = 2; i <= row; i++) {if (dp[i - 1][1] <= 0) dp[i][1] = INT_MIN;else dp[i][1] = dp[i - 1][1] + M[i][1];}for (int i = 2; i <= col; i++) {if (dp[1][i - 1] <= 0) dp[1][i] = INT_MIN;else dp[1][i] = dp[1][i - 1] + M[1][i];}for (int i = 2; i <= row; i++) {for (int j = 2; j <= col; j++) {int tmp = max(dp[i - 1][j], dp[i][j - 1]);if (tmp <= 0) dp[i][j] = INT_MIN;else dp[i][j] = tmp + M[i][j];}}return dp.back().back() > 0;
}int main() {cin >> row >> col;M.resize(row + 1, vector<int>(col + 1, 0));for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {cin >> M[i][j];}}// DP + binary Searchingdp.resize(row + 1, vector<int>(col + 1, 0));int left = 1, right = INT_MAX, ans = INT_MAX;while (left < right) {int mid = left + (right - left) / 2;if (isValid(mid)) {ans = mid;right = mid;} else {left = mid + 1;}}cout << ans << endl;return 0;
}

Let’s Cheer Up Bob

• Tic-tac-toe 游戏: 3x3 网格的3子棋
• 陪丈母娘打牌的意思
• Bob有一个下子 优先级，只按这个顺序下子
• Bob先下，你得让Bob尽快赢，输出你每次下子的位置
• 采用BFS，层定义为 Bob 下子的 多少
• 一旦结束，就代表 最快就赢了

#include <bits/stdc++.h>
using namespace std;
struct state {char board[3][3];bool bobTurn;int moveNum; // BFS的深度vector<pair<int, int>> moves;
};
int prior[9][2] = {0};
queue<state> Q;// true: label Win; false: else
int whoWins(state s, char lab = 'x') {for (int i = 0; i < 3; i++) {int cnt1 = 0;for (int j = 0; j < 3; j++) {if (s.board[i][j] == lab)cnt1++;}  if (cnt1 == 3) return true;}for (int j = 0; j < 3; j++) {int cnt1 = 0;for (int i = 0; i < 3; i++) {if (s.board[i][j] == lab)cnt1++;}  if (cnt1 == 3) return true;}int cnt1 = 0, cnt2 = 0;for (int i = 0; i < 3; i++) {if (s.board[i][i] == lab) cnt1++;if (s.board[i][2 - i] == lab) cnt2++;}if (cnt1 == 3 || cnt2 == 3) return true;return false;
}int main() {for (int i = 0; i < 9; i++) {cin >> prior[i][0] >> prior[i][1];prior[i][0]--;prior[i][1]--;}state init_state;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {init_state.board[i][j] = '.';}}init_state.moveNum = 0;init_state.bobTurn = true;Q.push(init_state);while (!Q.empty()) {auto cur_state = Q.front(); Q.pop();bool isEnd = whoWins(cur_state, 'x'); // Bob Winbool isEnd2 = whoWins(cur_state, 'o'); // I Winif (isEnd2) continue;if (isEnd) { // finishedfor (size_t i = 0; i < cur_state.moves.size(); i++) {cout << cur_state.moves[i].first + 1 << " " << \cur_state.moves[i].second + 1 << endl;}return 0;}if (cur_state.bobTurn) { // Bob's Turnsint lastMove = cur_state.moveNum;bool moveFound = false;for (int i = lastMove; i < 9 && !moveFound; i++) {int y = prior[i][0];int x = prior[i][1];if (cur_state.board[y][x] == '.') {cur_state.board[y][x] = 'x';cur_state.moveNum = i + 1;cur_state.bobTurn = false;moveFound = true;Q.push(cur_state);}}} else { // My turnfor (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (cur_state.board[i][j] != '.') continue;state new_state = cur_state;new_state.board[i][j] = 'o';new_state.bobTurn = true;new_state.moves.push_back(make_pair(i, j));Q.push(new_state);}}}}return 0;
}

Shuffle

• 有向图模型
• A > B，表示A家庭去过B家庭
• 现在要将各个家庭交换到 别的没有去过 的新家
• 判断是否可行，如果不可行，可以把部分家庭送到旅社，其住所仍参与实验，输出这个最小的家庭数（可行的话，这个数 应当就是 0 了）
• 举例（箭头表示单向，无箭头表示双向连通）
  

建模为 最大流问题

• 如下图（题中规定 N <= 200）
• 相同节点分成 上下两个 平面，把除 节点自身 和 有连接关系 的 边 容量设为 0（可以认为就是不连通）
• 那么 从源点420 到汇点 421 的最大流表示：能同时走通的 最大 可交换 家庭！
• 输出 N - maxflow 即为答案！
  
• 代码：
  • 参考1
  • 参考2

DFS

• Github

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 222;
vector<int> d[Maxn];
int par[Maxn];
int rev[Maxn];
bool vs[Maxn];
bool dfs(int i){if(i < 0) return true;if(vs[i]) return false;vs[i] =true;for(int u:d[i]) if(dfs(rev[u])){par[i] = u;rev[u] = i;return true;}return false;
}
int main() {ios_base::sync_with_stdio(false);int n;cin >> n;string s;getline(cin,s);for(int i = 0; i < n ;i++){getline(cin,s);stringstream ss(s);vector<int> mk(n,1);mk[i] = 0;int x;while(ss >> x)mk[x] = 0;for(int x = 0; x < n; x++)if(mk[x])d[i].push_back(x);}memset(par,-1,sizeof par);memset(rev,-1,sizeof rev);for(bool ok = true; ok; ){ok = false;memset(vs,0,sizeof vs);for(int i = 0; i < n; i++)if(par[i] < 0){ok |= dfs(i);}}int ans = 0;for(int i = 0 ; i < n; i++)ans += (par[i] < 0);cout << ans;
}

Octopuses with Watches

• 一个二维表 N x M
• 每个位置上 表示 表盘上面的 时针指向 1~12
• 你能做的操作：每次 单行 或 单列 上元素全部加1
• 计算你能得到的 3 6 9 12 最多的个数
• 0 < N <= M < 10!
• 理解简化题目：
  • 看似可以一直加 某行 某列，其实 最多 加{0, 1, 2}次就到头了
  • 设定 行数组 row，每个位置上 0~2，DFS 找 最大

#include <bits/stdc++.h>
using namespace std;
int N, M; // 0 < N <= M < 10
int row[11], tab[11][11], ntab[11][11];
int ans = INT_MIN;
void dfs(int c) {if (c == M) { // 行尾 int tmp = 0;for (int j = 0; j < M; j++) { // 一行从上往下扫描 for (int i = 0; i < N; i++) {ntab[i][j] = tab[i][j] + row[j];}}for (int i = 0; i < N; i++) { // 统计每行int record[3] = {0, 0, 0}; // 余数 0,1,2for(int j = 0; j < M; j++) {record[ntab[i][j] % 3]++;}tmp += max(record[0], max(record[1], record[2]));}ans = max(ans, tmp);return;}// recurrentfor (int i = 0; i < 3; i++) {row[c] = i;dfs(c + 1);}
}
// Main Loop
int main() {ios_base::sync_with_stdio(false);cin >> N >> M;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> tab[i][j];}}dfs(0);cout << ans << endl;return 0;
}

Fill The Pixels

Preparing for Xtreme 12.0

Orienteering

Collecting Gold

Math Challenge

Quipu Function

The Fast and the Curious

Jarawi and The Interview

Game of Life

Odd Cycle Check

Sub Array Sum Problem

Mister Counter

Maximum Sum

Pyramid

King Capture

Lion Territory

Elementary

Knin

IEEEXtreme 12.0

• 参考 - 链接 - Python
• 参考 - 链接 - Cpp

Troll Coder

Bear Sums

Lemons

Drawing Rooted Binary Trees

Telescope Scheduling

Xplore

Bit Soccer

Xtreme Fake Coins

Product Rectangle

Barter System

Magic Spell

Barrett Reduction

Infinite snakes and ladders

Factorial Zeros

Tree Fun

Gotta ~ Catch 'Em All

Make Distinct

The Gold-diggers

Organizational Chart

Tweedledee’s Split Brackets

Troll Coder - Escape

Tweedledum’s Nested Brackets

Friendly Sequences

PIEEEXMan

IEEEXtreme 13

• 只有题解 - 没有题目