大部分简单题会使用 ruby 编写，除非输入比较难处理或者 C++ 写起来更方便.
HJ108 最小公倍数
=begin # 公式
gcd(a, b) = !b ? a : gcd(a % b, a)
lcm(a, b) = a * b / gcd(a, b)
=end
p gets.split.map(&:to_i).reduce :lcm HJ107 求解立方根 二分
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
double i, o;
cin >> i;
if (i == 0 || i == -1 || i == 1) o = i;
else {
// 二分模板: l 左端点, r 右端点, t 临时变量
double l = i > 0 ? 0 : i, r = i > 0 ? i : 0, t;
while ((r - l) >= 0.02) { // 当求解区域不够小时
o = (l + r) / 2, t = o * o * o; // 取中间点, 和目标比较
if (t > i) r = o;
else if (t < i) l = o;
else break; // 正好
}
}
printf("%.1f\n", o);
} HJ106 字符逆序
puts gets.chomp.reverse
HJ105 记负均正II
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int i, k = 0, n = 0;
double d;
while (cin >> i) {
if (i < 0) k++;
else d += i, n++;
}
cout << k << endl;
printf("%.1f\n", n ? d / n : 0.0);
} HJ104 字符串分割
#include <stdio.h>
#include <string.h>
int main() {
int i, j, n;
char s[100], a[20]; // s 输入, a 存储每 8 个字符
while (scanf("%d", &n) == 1)
for (i = 0; i < n; ++i) {
scanf("%s", s);
int len = strlen(s);
int r = len % 8; // 最后一行有几个有效字符
int m = len / 8 + (r != 0); // 一共输出 m 行
for (j = 0; j < m; ++j) {
sscanf(s + j * 8, "%8s", a); // 扫(最多) 8 个字符
printf("%s", a);
if (j == m - 1 && r != 0) { // 如果是最后一行, 补 0
printf("%0*d", 8 - r, 0); // 输出 8 - r 个 0
}
printf("\n");
}
}
} HJ103 Redraiment的走法 最大上升子序列
设 a(i) = i 格高度, f(i) = 到 i 格最多有几步, 显然 f(0) = 1;
以后每格，是保持上升规律的前提下最大的 f(k) + 1, 即 f(i) = (f(0)..f(i-1)).filter_by_index { |k| a[i] > a[k] }.max + 1.
#include <iostream>
using namespace std;
int a[10000], dp[10000];
int main() {
int n, m;
while (cin >> n) {
m = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
dp[i] = 1; // 最少也有 1 步
for (int j = 0; j < i; ++j) {
if (a[i] > a[j]) { // 保持上升规律
dp[i] = max(dp[i], dp[j] + 1);
}
}
m = max(m, dp[i]);
}
cout << m << endl;
}
return 0;
} HJ102 字符统计
本来是一个统计 + 自定义排序 (sort_by { |e| [-e.count, e[0].ord] }), 不过看到字符类问题, 可以用一个 int count[128] 顺便完成字典序, 下面是暴力写法.
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
int count[256];
while (cin >> s) {
for (int i = 0; i < 256; ++i) count[i] = 0;
for (char c : s) count[int(c)]++;
char a; int max;
do {
max = 0;
for (int i = 0; i < 256; ++i)
if (count[i] > max) max = count[i], a = char(i);
if (max > 0) {
count[int(a)] = 0;
cout << a;
}
} while (max > 0);
cout << endl;
}
} HJ101 简单排序
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define all(r) begin(r), end(r)
int main() {
int n;
while (cin >> n) {
vector<int> v;
for (int i = 0, a; i < n; ++i) {
cin >> a;
v.push_back(a);
}
bool desc;
cin >> desc;
sort(all(v));
if (desc) reverse(all(v));
copy(all(v), ostream_iterator<int>(cout, " "));
cout << endl;
}
}HJ100 等差数列求和
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
cout << (3 * n + 1) * n / 2 << endl;
}
return 0;
} HJ99 自守数
本来是一个 (i**2).to_s.end_with?(i.to_s), 不过 int 也就 10 位, 平方能进 int 的就更少了, 可以暴力.
#include <iostream>
using namespace std;
int main() {
int n, k;
while (cin >> n) {
k = 0;
for (int i = 0, j; i <= n; ++i) {
j = i * i;
if ((i >= 10000 && j % 100000 == i) ||
(i >= 1000 && j % 10000 == i) ||
(i >= 100 && j % 1000 == i) ||
(i >= 10 && j % 100 == i) ||
(i >= 0 && j % 10 == i)) k++;
}
cout << k << endl;
}
return 0;
} HJ98 自动收货系统
辣鸡题, bug 多, 8做.
HJ97 记负均正
HJ105 的代码可以直接过.
HJ96 数字前后加上 *
while s = gets
puts s.scan(/\d+|\D+/).map { |e| e =~ /\d/ ? "*#{e}*" : e }.join
endHJ95 人民币转换
辣鸡题, 8做.
HJ94 记票统计
while gets
k = {}
gets.split.each { |a| k[a] = 0 }
gets; i = 0
gets.split.each { |a| k.key?(a) ? k[a] += 1 : i += 1 }
k.each { |c, n| puts "#{c} : #{n}" }
puts "Invalid : #{i}"
end HJ93 JAVA 0-1 相等分组
由于 3, 5 必须分在两组, 先把他们分开, 剩下的数字暴力搜到 abs(sum3 - sum5).
#include <iostream>
#include <vector>
using namespace std;
bool dfs(int sumR, int target, vector<int> &v, int index) {
if (index == v.size()) return sumR == target;
return dfs(sumR + v[index], target, v, index + 1) ||
dfs(sumR - v[index], target, v, index + 1);
}
int main() {
for (int n; cin >> n;) {
int sum3 = 0, sum5 = 0;
vector<int> R;
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (x % 5 == 0) sum5 += x;
else if (x % 3 == 0) sum3 += x;
else R.push_back(x);
}
bool result = dfs(0, abs(sum5 - sum3), R, 0);
cout << boolalpha << result << endl;
}
} HJ92 连续最长数字串
while s = gets
a = s.scan(/\d+/).group_by(&:length)
n = a.keys.max
puts "#{a[n].join},#{n}"
end HJ91 JAVA 2-3 走棋盘方法数
本题如果棋盘是方的, 那么是一个卡特兰数问题, 卡特兰数通式.
不过本题暴力 dfs 即可.
#include <iostream>
using namespace std;
int m, n, count;
void dfs(int i, int j) {
if (i == m && j == n) count++;
else {
if (i < m) dfs(i + 1, j);
if (j < n) dfs(i, j + 1);
}
}
int main() {
while (cin >> m >> n) {
count = 0;
dfs(0, 0);
cout << count << endl;
}
} HJ90 合法IP
这题可以很难, 用正则做. (x
while s = gets
if s.chomp =~ /^(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3}$/
puts 'YES'
else
puts 'NO'
end
end HJ89 24点
难题, 8做.
HJ88 扑克牌大小
这题的输入用 C++ 比较麻烦, 本身是个简单分类讨论问题.
order = '345678910JQKA2jokerJOKER'
while s = gets
a, b = s.chomp.split ?-
c, d = a.split, b.split
if c.size != d.size
if [a, b].include? 'joker JOKER'
puts 'joker JOKER'
elsif c.size == 4
puts a
elsif d.size == 4
puts b
else
puts 'ERROR'
end
else
if order.index(c[0]) > order.index(d[0])
puts a
else
puts b
end
end
end HJ87 密码强度等级
水时间的辣鸡题, 不过我做了.
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main() {
for (string a; cin >> a;) {
int score = 0;
if (a.length() <= 4) score += 5;
else if (a.length() <= 7) score += 10;
else score += 25;
int lower = 0, upper = 0, digit = 0, punct = 0;
for (char c : a) {
if (islower(c)) lower++;
else if (isupper(c)) upper++;
else if (isdigit(c)) digit++;
else if (ispunct(c)) punct++;
}
if (lower == 0 && upper == 0) score += 0;
else if (lower * upper == 0) score += 10;
else score += 20;
if (digit == 1) score += 10;
else if (digit > 1) score += 20;
if (punct == 1) score += 10;
else if (punct > 1) score += 25;
int alpha = lower + upper;
if (lower && upper && digit && punct) score += 5;
else if (alpha && digit && punct) score += 3;
else if (alpha && digit) score += 2;
string result;
if (score >= 90)
result = "VERY_SECURE";
else if (score >= 80)
result = "SECURE";
else if (score >= 70)
result = "VERY_STRONG";
else if (score >= 60)
result = "STRONG";
else if (score >= 50)
result = "AVERAGE";
else if (score >= 25)
result = "WEAK";
else
result = "VERY_WEAK";
cout << result << endl;
}
} HJ86 最大连续bit数
本身应该是个位运算魔法题, 想不到魔法就暴力吧.
while i = gets
p i.to_i.to_s(2).scan(/1+/).map(&:size).max || 0
end HJ85 最大回文子串长度
本题暴力可做, 但是复杂度是平方, 或者可以看成和逆序的最大公共子串问题.
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int lcs(string a, string b) {
if (a.length() > b.length()) swap(a, b);
int m = 0, s = 0;
vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
for (int i = 1; i <= a.length(); ++i)
for (int j = 1; j <= b.length(); ++j)
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > m) {
m = dp[i][j];
s = i - m;
}
}
return m;
}
int main() {
for (string a, b; cin >> a;) {
b = a; reverse(b.begin(), b.end());
cout << lcs(a, b) << endl;
}
return 0;
} HJ84 大写字母个数
while s = gets
p s.scan(/[A-Z]/).size
end HJ83 二维数组操作
本质维护俩数, 辣鸡题, 8做.
HJ82 分解埃及分数
辣鸡题, bug 多, 8做.
HJ81 字符串匹配
while s = gets and l = gets
p (s.delete l).empty?
end HJ80 整型数组合并
排序 + 去重, HJ101 加一行即可.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define all(v) begin(v), end(v)
int main() {
for (int n, m; cin >> n;) {
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
cin >> m; v.resize(n + m);
for (int i = 0; i < m; ++i) cin >> v[n + i];
sort(all(v));
auto last = unique(all(v));
v.erase(last, v.end());
for (int x : v) cout << x;
cout << endl;
}
} HJ79 编辑距离
设 f(a, b) 是字符串 a, b 的最短编辑距离, 显然有
f("", b) = b.size
f(a, "") = a.size
f("aa", "ba") = f("a", "b") # 最后一个字符相同
f("aa", "ab") = [ # 最后一个字符不同
f("a" , "ab") + 1,
f("aa", "a" ) + 1,
f("a" , "a" ) + 1,
].min 套一个记忆化搜索.
#include <map>
#include <tuple>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string a, b;
map<tuple<int, int>, int> dp;
int f(int i, int j) {
if (i == -1) return j + 1;
if (j == -1) return i + 1;
auto t = make_tuple(i, j);
auto iter = dp.find(t);
if (iter != dp.end()) return iter->second;
int result;
if (a[size_t(i)] == b[size_t(j)]) result = f(i - 1, j - 1);
else result = min(min(f(i, j - 1) + 1, f(i - 1, j) + 1), f(i - 1, j - 1) + 1);
return dp[t] = result;
}
int main() {
while (cin >> a >> b) {
dp.clear();
int result = f(int(a.length() - 1), int(b.length() - 1));
if (result <= 0)
cout << 1 << endl;
else
cout << "1/" << (result + 1) << endl;
}
return 0;
} HJ78 大整数加法
本来是手动模拟进位, 不过可以用 ruby 我就不客气了.
while a = gets and b = gets
p a.to_i + b.to_i
end HJ77 火车进站
全排列 + 判断是否由序列生成.
#include <stack>
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define all(r) begin(r), end(r)
bool is_pushpop(vector<int> a, vector<int> v) {
size_t j = 0;
stack<int> s;
for (int i : a) {
s.push(i);
while (j < v.size() && !s.empty() && v[j] == s.top())
s.pop(), ++j;
}
return s.empty();
}
int main() {
for (int n; cin >> n;) {
vector<int> v, a;
for (int i = 0, x; i < n; ++i) {
cin >> x;
v.push_back(x);
}
a = v;
sort(all(v));
vector<vector<int>> w;
do {
if (is_pushpop(a, v)) {
copy(all(v), ostream_iterator<int>(cout, " "));
cout << endl;
}
} while (next_permutation(all(v)));
}
return 0;
} HJ76 尼科彻斯定理
等差数列求和的结果一般是一个二次多项式, 可以猜测三次多项式是由二次多项式数列求和得来. 观察规律, 整数 m 的立方的对应数列第一个是 m * m - m + 1, 数列有 m 个元素.
f = -> x { x * x - x + 1 }
while a = gets
a = a.to_i
b = f[a]
c = Array.new(a) { |i| b + i * 2 }
puts c.join('+')
end HJ75 最长公共字串
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int lcs(string a, string b) {
if (a.length() > b.length()) swap(a, b);
int m = 0, s = 0;
vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
for (int i = 1; i <= a.length(); ++i)
for (int j = 1; j <= b.length(); ++j)
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > m) {
m = dp[i][j];
s = i - m;
}
}
return m;
}
int main() {
string a, b;
while (cin >> a >> b) {
cout << lcs(a, b) << endl;
}
return 0;
} HJ74 参数解析
特殊处理一下双引号, 剩下的按空格分隔.
while s = gets
s.chomp!
result = []
while i = s.index(/[" ]/)
result << s.slice!(0, i)
if s[0] == ?"
s.slice!(0)
result << s.slice!(0, s.index(?"))
s.slice!(0)
end
s.lstrip!
end
result << s unless s.empty?
puts result.size, result
end HJ73 日期到天数
#include <iostream>
using namespace std;
bool isleap(int year) {
return year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
}
int main() {
int mm[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
for (int y, m, d, c; cin >> y >> m >> d; ) {
c = 0;
for (int i = 1; i < m; ++i) {
c += mm[i];
if (i == 2 && isleap(y)) c++;
}
cout << c + d << endl;
}
} HJ72 百钱买百鸡
#include <iostream>
using namespace std;
int main() {
for (int _; cin >> _;) {
for (int i = 0; i < 14; ++i) {
for (int j = 0; j <= 25; ++j) {
if (7 * i + 4 * j == 100) {
int k = 100 - i - j;
cout << i << " " << j << " " << k << endl;
}
}
}
}
} HJ71 字符串通配符
可以简单转为正则匹配.
while w = gets and s = gets
escaped = Regexp.escape(w.chomp).gsub('\?', '.').gsub('\*','.*?')
r = Regexp.new "^#{escaped}$"
p !!r.match(s.chomp)
end HJ70 矩阵乘法计算量
还好不是问最小计算量. ;w; 本质带括号的计算器问题, 加一个栈即可.
while n = gets
n = n.to_i
rc = n.times.map { gets.split.map(&:to_i) }
env = [[]]
result = 0
a = gets.chomp
a.each_char do |c|
case c
when '(' then env.push []
when ')' then
next if env.size == 1
a, b = env.pop
result += a[0] * a[1] * b[1]
env[-1].push [a[0], b[1]]
when 'A'..'Z' then
i = c.ord - 'A'.ord
env[-1].push rc[i]
end
end
p result
end HJ69 矩阵乘法
#include <iostream>
using namespace std;
void solve(int x, int y, int z) {
int a[x][y], b[y][z]; // C++ 并不支持 VLA, 不过 vector 有点长.
for (int i = 0; i < x; ++i)
for (int j = 0; j < y; ++j)
cin >> a[i][j];
for (int i = 0; i < y; ++i)
for (int j = 0; j < z; ++j)
cin >> b[i][j];
for (int i = 0; i < x; ++i) {
for (int j = 0; j < z; ++j) {
int c = 0;
for (int k = 0; k < y; ++k) {
c += a[i][k] * b[k][j];
}
cout << c << " ";
}
cout << endl;
}
}
int main() {
for (int x, y, z; cin >> x >> y >> z;) {
solve(x, y, z);
}
} HJ68 成绩排序
还记得看到字符想到 int count[128] 吗, 这里也是, 一共只有 0..100 种成绩.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n, t;
string name;
while (cin >> n >> t) {
vector<string> names[101];
for (int i = 0, g; i < n; ++i) {
cin >> name >> g;
names[g].push_back(name);
}
for (int i = t ? 0 : 100; t ? i <= 100 : i >= 0; t ? ++i : --i)
for (name : names[i])
cout << name << " " << i << endl;
}
} HJ67 24点
上面 24 点没做, 这道比较容易, 可以暴搜 3 个运算符的全排列, 利用栈计算器求解.
#include <iostream>
using namespace std;
int seq[7]; // 7 2 + 1 - 10 *
double target = 24.0;
bool calc() {
int top = 0;
double stack[4];
for (int i = 0; i < 7; ++i) {
if (1 <= seq[i] && seq[i] <= 10) stack[top++] = seq[i];
else {
if (top < 2) return false;
double a = stack[--top], b = stack[--top];
if (seq[i] == '+') stack[top++] = a + b;
if (seq[i] == '-') stack[top++] = a - b;
if (seq[i] == '*') stack[top++] = a * b;
if (seq[i] == '/') {
if (b > 0) stack[top++] = a / b;
else return false;
}
}
}
return top == 1 && stack[0] == target;
}
bool permute(int start, int end) {
if (start == end) return calc();
else {
for (int i = start; i < end; ++i) {
swap(seq[start], seq[i]);
if (permute(start + 1, end)) return true;
swap(seq[start], seq[i]);
}
}
return false;
}
bool solve() {
char op[] = "+-*/";
for (int i = 0; i < 4; ++i) {
for (int j = 0, k = 4; j < 4; ++j) {
if (j == i) continue;
seq[k++] = op[j];
}
if (permute(0, 7)) return true;
}
return false;
}
int main() {
while (cin >> seq[0] >> seq[1] >> seq[2] >> seq[3]) {
cout << boolalpha << solve() << endl;
}
return 0;
} HJ66 配置文件恢复
commands = (<<-F).lines.map { |e| a, b = e.split(?\t); [a.split, b.chomp] }
reset reset what
reset board board fault
board add where to add
board delet no board at all
reboot backplane impossible
backplane abort install first
F
unknown = 'unkown command'
while s = gets
s = s.split
w = commands.select { |a, b| a.size == s.size and a.zip(s).all? { |x, y| x.start_with? y } }
if w.size == 1
puts w[0][1]
else
puts unknown
end
end HJ65 最长公共字串
HJ75 改几个字.
#include <vector>
#include <string>
#include <iostream>
using namespace std;
string lcs(string a, string b) {
if (a.length() > b.length()) swap(a, b);
int m = 0, s = 0;
vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
for (int i = 1; i <= a.length(); ++i)
for (int j = 1; j <= b.length(); ++j)
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > m) {
m = dp[i][j];
s = i - m;
}
}
return a.substr(s, m);
}
int main() {
string a, b;
while (cin >> a >> b) {
cout << lcs(a, b) << endl;
}
return 0;
} HJ64 MP3光标位置
#include <iostream>
using namespace std;
int main() {
for (int n; cin >> n;) {
int l = 0, cur = 0;
string s;
cin >> s;
for (char c : s) {
if (n > 4) {
if (c == 'U' && l == cur) l--;
if (c == 'D' && l + 3 == cur) l++;
if (l < 0) l = n - 4;
else if (l + 3 >= n) l = 0;
}
if (c == 'U') cur = (cur + n - 1) % n;
else if (c == 'D') cur = (cur + 1) % n;
}
for (int i = l + 1, end = l + (n > 4 ? 4 : n); i <= end; ++i) {
cout << i;
if (i < end) cout << " ";
else cout << endl;
}
cout << cur + 1 << endl;
}
return 0;
} HJ63 DNA序列
calc = -> s { s.chars.count { |c| c == 'G' || c == 'C' }.fdiv s.size }
while s = gets
s.chomp!
n = gets.to_i
i = (0..(s.size - n)).max_by { |i| calc[s[i, n]] }
puts s[i, n]
end HJ62 二进制1的个数
经典位运算: i &= i - 1 可以清掉 i 末尾的一个 1.
#include <iostream>
using namespace std;
#define all(r) begin(r), end(r)
int main() {
for (int i, k; cin >> i;) {
for (k = 0; i; i &= i - 1)
k++;
cout << k << endl;
}
return 0;
} HJ61 放苹果
把 m 个苹果放在 n 个盘子里, 有以下几种情况:
f(m, n) =
m = 0 && n = 1 => 1
m < n => f(m, m)
_ => f(m, n - 1) + f(m - n, n) - 1 个盘子, 0 个苹果 -> 1 种方法
- 盘子比苹果多, 等价于盘子和苹果一样多时的方法
- (苹果比盘子多), 等于 n-1 个盘子的方法加每个盘子都放一个之后的方法
#include <iostream>
using namespace std;
#define all(r) begin(r), end(r)
int f(int a, int b) {
if (a == 0 || b == 1)
return 1;
if (b > a)
return f(a, a);
else
return f(a, b - 1) + f(a - b, b);
}
int main() {
for (int a, b; cin >> a >> b;) {
cout << f(a, b) << endl;
}
return 0;
} HJ60 最接近的素数和
从中间往两边找.
require 'prime'
while a = gets
a = a.to_i
i = a / 2
until i.zero?
j = a - i
if i.prime? and j.prime?
p i, j
break
end
i -= 1
end
end HJ59 找出字符串中第一个只出现一次的字符
while s = gets
a = s.chomp.chars.group_by(&:itself)
if a.each { |k, v| if v.size == 1 then break puts k end }
p -1
end
end HJ58 输入n个整数，输出其中最小的k个
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define all(r) begin(r), end(r)
int main() {
for (int n, m; cin >> n >> m;) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
sort(all(v));
copy(v.begin(), v.begin() + m, ostream_iterator<int>(cout, " "));
cout << endl;
}
return 0;
} HJ57 无线OSS－高精度整数加法
手打大整数进位/借位的话, 这题就长了.
while a = gets and b = gets
p a.to_i + b.to_i
endHJ56 iNOC产品部--完全数计算
def count n
ret = 0
2.upto(n) { |i|
sum = 1
2.upto(Math.sqrt(i)) { |j|
if i % j == 0
sum += j
sum += i / j if i / j != j
end
}
ret += 1 if sum == i
}
ret
end
while s = gets
p count s.to_i
end HJ55 （练习用）挑7
#include <iostream>
using namespace std;
int main() {
int n, a;
while (cin >> n) {
a = 0;
for (int i = 1; i <= n; ++i)
if (i % 7 == 0) a++;
else {
int t = i;
do {
if (t % 10 == 7) {
a++;
break;
}
} while (t /= 10);
}
cout << a << endl;
}
} HJ54 表达式求值
p eval gets
HJ53 iNOC产品部-杨辉三角的变形
本题暴力也可以过, 不过答案有个规律.
while i = gets
i = i.to_i
case
when i < 3 then p -1
when i % 2 == 1 then p 2
when i % 4 == 0 then p 3
else p 4
end
end HJ52 计算字符串的距离
这题出现几次了?
#include <map>
#include <tuple>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string a, b;
map<tuple<int, int>, int> dp;
int f(int i, int j) {
if (i == -1) return j + 1;
if (j == -1) return i + 1;
auto t = make_tuple(i, j);
auto iter = dp.find(t);
if (iter != dp.end()) return iter->second;
int result;
if (a[size_t(i)] == b[size_t(j)]) result = f(i - 1, j - 1);
else result = min(min(f(i, j - 1) + 1, f(i - 1, j) + 1), f(i - 1, j - 1) + 1);
return dp[t] = result;
}
int main() {
while (cin >> a >> b) {
dp.clear();
cout << f(int(a.length() - 1), int(b.length() - 1)) << endl;
}
return 0;
} HJ51 输出单向链表中倒数第k个结点
打一遍链表太累了, 其实就是原地构造一个(头插法)新链表.
while gets
v = gets.split
n = gets.to_i
if 0 < n and n <= v.size
puts v[-n]
else
p 0
end
end HJ50 四则运算
这题创造性地引入了两种新括号, 不过他又没错误输入, 所以直接.
p eval gets.tr('{[', '}]') HJ49 多线程
其实就是给四个线程加同步锁, 最后一个线程给资源给第一个线程; 8做.
HJ48 从单向链表中删除指定值的节点
本身要构建链表挺麻烦的, 得写个 find_and_insert(p, x) delete_value(x).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define all(v) begin(v), end(v)
int main() {
for (int n; cin >> n;) {
vector<int> v(1);
cin >> v[0];
for (int i = 0, x, y; i < n - 1; ++i) {
cin >> x >> y;
v.insert(find(all(v), y) + 1, x);
}
cin >> n;
v.erase(find(all(v), n));
for (int n : v) cout << n << " "; cout << endl;
}
} HJ47 线性插值
没看懂题, 算了8.
HJ46 按字节截取字符串
这题还就只有部分语言能做.
#include <string>
#include <iostream>
using namespace std;
int main() {
for (string s; cin >> s;) {
int n; cin >> n;
cout << s.substr(0, n) << endl;
}
} HJ45 名字的漂亮度
类似霍夫曼编码一开始要将频率高的字分配比较高的权重.
d = [*1..26].reverse
while s = gets
s.to_i.times {
a = gets.chomp.chars.group_by(&:itself)
b = a.values.map(&:count).sort.reverse.zip(d)
c = b.map { |e| e.reduce :* }.reduce :+
p c
}
end HJ44 Sudoku-Java
简单 dfs, 稍微压一下行.
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define all(v) begin(v), end(v)
#define F(i,a,z) for (int i = a; i < z; ++i)
#define G(k,i) F(k, i / 3 * 3, i / 3 * 3 + 3)
#define P(v) copy(all(v), ostream_iterator<int>(cout, " ")), cout << endl
int a[9][9];
void print() { F(i, 0, 9) P(a[i]); }
bool check(int i, int j, int x) {
F(k, 0, 9) if (a[i][k] == x || a[k][j] == x) return false;
G(k, i) G(l, j) if (a[k][l] == x) return false;
return true;
}
bool dfs(int k) {
if (k == 81) return print(), true;
int i = k / 9, j = k % 9;
if (a[i][j] > 0) return dfs(k + 1);
F(x, 1, 10) if (check(i, j, x)) {
a[i][j] = x; if (dfs(k + 1)) return true;
a[i][j] = 0;
} return false;
}
int main() {
F(i, 0, 9) F(j, 0, 9) cin >> a[i][j];
dfs(0);
} HJ43 迷宫问题
寻路当然是 A* 啦.
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
using namespace std;
#define F(i,a,z) for (int i = a; i < z; ++i)
#define T(k,l,b) do { if (passable(k, l)) p[k][l] = b, q.push({ k, l, step + 1 }); } while (0)
#define P(b,k,l) do { if (p[i][j] == b) print(k, l); } while (0)
int m, n, a[10][10], p[10][10]; // a 迷宫, p 每个点的上一个点在哪(用小键盘标方向)
struct pt { int i, j, k; int h() const { return i + j + k; } };
bool passable(int i, int j) {
return 0 <= i && i <= m && 0 <= j && j <= n && a[i][j] == 0 && p[i][j] == 0;
}
void print(int i, int j) {
P(2, i + 1, j); P(4, i, j - 1); P(6, i, j + 1); P(8, i - 1, j);
printf("(%d,%d)\n", i, j);
}
int main() {
auto cmp = [](const pt &a, const pt &b) { return a.h() > b.h(); };
while (cin >> m >> n) {
F(i, 0, m) F(j, 0, n) cin >> a[i][j], p[i][j] = 0;
priority_queue<pt, vector<pt>, decltype(cmp)> q(cmp);
q.push({ 0, 0, 0 }); a[0][0] = 1; // 标记起点不可通行
for (int i, j, step; !q.empty();) {
auto pt = q.top(); q.pop(); i = pt.i, j = pt.j, step = pt.k;
T(i - 1, j, 2); T(i, j + 1, 4); T(i, j - 1, 6); T(i + 1, j, 8);
}
print(m - 1, n - 1);
}
} HJ42 学英语
辣鸡题, 8做.
HJ41 称砝码
希尔伯特空间展开.
#include <set>
#include <vector>
#include <iostream>
using namespace std;
int main() {
for (int n; cin >> n;) {
set<int> s, t;
vector<int> a, v;
a.resize(size_t(n));
for (int i = 0; i < n; ++i) cin >> a[size_t(i)];
for (int i = 0, x; i < n; ++i) {
cin >> x;
for (int j = 0; j < x; ++j) v.push_back(a[size_t(i)]);
}
s.insert(0);
for (int x : v) {
t = s;
for (int y : t) s.insert(x + y);
}
cout << s.size() << endl;
}
return 0;
} HJ40 输入一行字符，分别统计出包含英文字母、空格、数字和其它字符的个数
建议大家都去用 ctype.h 里的东西.
#include <cctype>
#include <string>
#include <iostream>
using namespace std;
int main() {
string ss;
while (getline(cin, ss)) {
int a = 0, s = 0, d = 0, o = 0;
for (char c : ss) {
if (isalpha(c)) a++;
else if (isspace(c)) s++;
else if (isdigit(c)) d++;
else o++;
}
cout << a << endl << s << endl << d << endl << o << endl;
}
return 0;
} HJ39 判断两个IP是否属于同一子网
相同子网的 IP & 掩码 相同.
#include <iostream>
#include <cstdio>
using namespace std;
int ip1[4], ip2[4], ip3[4];
int comp() {
for (int i = 0; i < 4; ++i) {
if (!(0 <= ip1[i] && ip1[i] <= 255 &&
0 <= ip2[i] && ip2[i] <= 255 &&
0 <= ip3[i] && ip3[i] <= 255))
return 1;
if ((ip1[i] & ip3[i]) != (ip2[i] & ip3[i]))
return 2;
}
return 0;
}
int main() {
while (true) {
if (scanf("%d.%d.%d.%d", &ip1[0], &ip1[1], &ip1[2], &ip1[3]) != 4) break;
if (scanf("%d.%d.%d.%d", &ip2[0], &ip2[1], &ip2[2], &ip2[3]) != 4) break;
if (scanf("%d.%d.%d.%d", &ip3[0], &ip3[1], &ip3[2], &ip3[3]) != 4) break;
cout << comp() << endl;
}
return 0;
} HJ38 求小球落地5次后所经历的路程和第5次反弹的高度
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
double h;
while (cin >> h) {
double sum = 0, h5 = h;
for (int i = 0; i < 5; ++i) {
sum += h5;
h5 /= 2;
sum += h5;
}
sum -= h5;
printf("%.6f\n%.6f\n", sum, h5);
}
} HJ37 统计每个月兔子的总数
老斐波那契了.
#include <stdio.h>
int f[50];
int fib(int i) {
if (i <= 1) return i;
if (f[i]) return f[i];
return f[i] = fib(i - 1) + fib(i - 2);
}
int main() {
int i;
f[1] = 1;
while (scanf("%d", &i) == 1)
printf("%d\n", fib(i));
} HJ36 字符串加密
while w = gets and s = gets
s.chomp!
w = w.chomp.chars.uniq.join.downcase
t = [*'a'..'z'].join
u = w + (t.delete w)
r = s.downcase.tr t, u
s.each_char.with_index { |c, i| r[i] = r[i].upcase if c =~ /[A-Z]/ }
puts r
end HJ35 蛇形矩阵
可以观察到, 第一行是自然数列的和.
f = Array.new(101) { |i| (1 + i) * i / 2 }
while n = gets
n = n.to_i
a = f[1..n]
puts a.join ' '
(n - 1).times { puts a.tap(&:shift).map! { |e| e - 1 }.join ' ' }
end HJ34 图片整理
while s = gets
puts s.chomp.chars.sort.join
end HJ33 整数与IP地址间的转换
上面也有一道 IP 题, 不过这题是保证输入正确的, 可以直接瞎搞.
while a = gets and b = gets
p a.split('.').map(&:to_i).pack('C*').unpack('N')[0]
puts [b.to_i].pack('N').unpack('C*').join('.')
end HJ32 【中级】字符串运用-密码截取
最长回文字串, 上面也有, 这里暴力.
def helper s, l, r
while 0 <= l && r < s.size && s[l] == s[r]
l -= 1
r += 1
end
return r - l - 1
end
while s = gets
s.chomp!
max = 0
s.size.times { |i| max = [max, helper(s, i, i), helper(s, i, i + 1)].max }
p max
end HJ31 【中级】单词倒排
puts gets.tr('^a-zA-Z', ' ').split.reverse.join(' ') HJ30 字符串合并处理
这种题, 用 ruby 都要方便很多.
rev = -> a { ('%04b' % a).reverse.to_i 2 }
while s = gets
a = s.split.join.chars.group_by.with_index { |c, i| i.even? }
b = a.each_value(&:sort!).values.reduce(&:zip).flatten
c = b.map { |e| e =~ /\h/ ? rev[e.to_i(16)].to_s(16).upcase : e }
puts c.join
end HJ29 字符串加解密
while s = gets and u = gets
puts s.chomp.tr 'a-zA-Z0-9', 'B-ZAb-za1-90'
puts u.chomp.tr 'B-ZAb-za1-90', 'a-zA-Z0-9'
end HJ28 素数伴侣
二分图的最大匹配, 匈牙利算法. 简单地说, 对于二分图左侧的每个点, 找一个右侧的点与他匹配,
匹配逻辑是: 对于每个右侧的点, 如果他没有匹配过, 直接选他, 如果他已经匹配了张三, 看看能不能让张三匹配到另一个人(递归).
#include <vector>
#include <iostream>
#define all(v) begin(v), end(v)
using namespace std;
bool primes_not[60005];
bool is_prime(int a) {
return !primes_not[a];
}
bool dfs(int odd, vector<int> &evens, vector<int> &choose, vector<bool> &visit) {
for (int i = 0; i < evens.size(); ++i) {
if (visit[i] || !is_prime(odd + evens[i])) continue;
visit[i] = true;
if (choose[i] == 0 || dfs(choose[i], evens, choose, visit)) {
choose[i] = odd;
return true;
}
}
return false;
}
int main() {
primes_not[0] = primes_not[1] = true;
for (int i = 2; i < 60005; ++i)
if (!primes_not[i])
for (int j = i * 2; j < 60005; j += i)
primes_not[j] = true;
for (int n; cin >> n;) {
vector<int> odds, evens;
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (x & 1) odds.push_back(x);
else evens.push_back(x);
}
vector<int> choose(evens.size(), 0);
int result = 0;
for (int odd : odds) {
vector<bool> visit(evens.size(), false);
if (dfs(odd, evens, choose, visit)) result++;
}
cout << result << endl;
}
} HJ27 查找兄弟单词
while u = gets
_, *a, w, i = u.split
i = i.to_i - 1
s = -> x { x.chars.sort.join }
e = -> a, b { a != b && s[a] == s[b] }
c = a.select { |x| e[x, w] }.sort
p c.size
puts c[i] if c.size > i
end HJ26 字符串排序
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
size_t len = s.length();
vector<char> v;
for (int j = 0; j < 26; ++j) {
for (size_t i = 0; i < len; ++i) {
if (isalpha(s[i]) && tolower(s[i]) == 'a' + j) {
v.push_back(s[i]);
}
}
}
for (size_t i = 0, k = 0; i < len && k < v.size(); ++i) {
if (isalpha(s[i])) s[i] = v[k++];
}
cout << s << endl;
}
} HJ25 数据分类处理
辣鸡题, 题意说不清.
while s = gets and u = gets
_, *t = s.split.map(&:to_i)
_, *r = u.split.map(&:to_i)
r.sort!.uniq!
o = []
r.each { |aa|
a = aa.to_s
c = 0
tt = []
t.each_with_index { |b, i|
if b.to_s.include?(a)
c += 1
tt << i << b
end
}
tt.unshift(aa, c) if c > 0
o.push(*tt)
}
puts [o.size, *o].join(' ')
end HJ24 合唱队
分别从两端找最长上升序列, 然后找中间一个点使两侧加起来最大.
#include <iostream>
#include <algorithm>
using namespace std;
int a[10000], dp1[10000], dp2[10000];
int main() {
int n, m;
while (cin >> n) {
for (int i = 0; i < n; ++i) {
cin >> a[i];
dp1[i] = 1;
for (int j = 0; j < i; ++j) {
if (a[i] > a[j]) {
dp1[i] = max(dp1[i], dp1[j] + 1);
}
}
}
for (int i = n - 1; i >= 0; --i) {
dp2[i] = 1;
for (int j = n - 1; j >= i; --j) {
if (a[i] > a[j]) {
dp2[i] = max(dp2[i], dp2[j] + 1);
}
}
}
m = 0;
for (int i = 0; i < n; ++i) {
m = max(m, dp1[i] + dp2[i] - 1);
}
cout << n - m << endl;
}
return 0;
} HJ23 删除字符串中出现次数最少的字符
while s = gets
a = s.chomp.chars.group_by(&:itself)
a.each { |k, v| a[k] = v.count }
b = a.values.min
c = a.keys.select { |k| a[k] == b }
puts s.delete c.join
end HJ22 汽水瓶
本身是个递归题,
f(n) = n < 2 ? 0 :
n == 2 ? 1 :
n / 3 + f(n / 3 + n % 3) 不过实际上还是个找规律.
#include <stdio.h>
int main() {
int a;
while (scanf("%d", &a) == 1) {
if (a == 0) break;
printf("%d\n", a / 2);
}
return 0;
} HJ21 简单密码破解
np = [2] * 3 + [3] * 3 + [4] * 3 + [5] * 3 +
[6] * 3 + [7] * 4 + [8] * 3 + [9] * 4
t = "b-za#{np.join}"
while s = gets
puts s.tr 'A-Za-z', t
end HJ20 密码验证合格程序
前面有一个更复杂的密码程序, 8做了.
HJ19 简单错误记录
log = Hash.new { |h, k| h[k] = 0 }
last = -> a, n { a[-n..-1] || a }
STDIN.read.split.each_slice(2) do |f, l|
f = last[f.split('\\').last, 16]
log[[f, l]] += 1
end
last[log.to_a, 8].each { |(f, l), c| puts [f, l, c].join(' ') } HJ18 识别有效的IP地址和掩码并进行分类统计
水时间题, 8做.
HJ17 坐标移动
while s = gets
pos = [0, 0]
s.chomp.split(?;).each { |a|
if m = a.match(/^([ASDW])(\d+)$/)
n = m[2].to_i
case m[1]
when ?A then pos[0] -= n
when ?S then pos[1] -= n
when ?D then pos[0] += n
when ?W then pos[1] += n
end
end
}
puts pos.join ?,
end HJ16 购物单
01 背包, 好难, 8做了.
HJ15 求int型数据在内存中存储时1的个数
#include <stdio.h>
int main() {
int a, i;
scanf("%d", &a);
for (i = 0; a; ++i) a &= (a - 1);
printf("%d\n", i);
} HJ14 简单排序
while n = gets
puts n.to_i.times.map { gets.chomp }.sort
end HJ13 句子逆序
while s = gets
puts s.split.reverse.join(' ')
end HJ12 字符串反转
#include <stdio.h>
#include <string.h>
char s[1001];
int main() {
char t;
int i, len;
scanf("%s", s);
len = strlen(s);
for (i = 0; i < len / 2; ++i) {
t = s[i];
s[i] = s[len - i - 1];
s[len - i - 1] = t;
}
printf("%s\n", s);
} HJ11 数字颠倒
#include <stdio.h>
int main() {
int a, i = 0;
char s[20];
scanf("%d", &a);
do {
s[i++] = '0' + (a % 10);
} while (a /= 10);
s[i] = '\0';
printf("%s\n", s);
} HJ10 字符个数统计
while s = gets
p s.chomp.chars.uniq.size
end HJ9 提取不重复的整数
while s = gets
puts s.chomp.reverse.chars.uniq.join
end HJ8 合并表记录
while s = gets
h = Hash.new { |h, k| h[k] = 0 }
s.to_i.times { k, v = gets.split.map(&:to_i); h[k] += v }
h.sort_by { |k, v| k }.each { |k, v| puts "#{k} #{v}" }
end HJ7 取近似值
#include <stdio.h>
int main() {
double a;
scanf("%lf", &a);
printf("%d\n", (int)(a + 0.5));
} HJ6 质数因子
#include <iostream>
using namespace std;
int main() {
long a;
cin >> a;
for (int i = 2; a > 1; ++i)
while (a % i == 0) {
cout << i << " ";
a /= i;
}
} HJ5 进制转换
对了, C++ 可以用 cin >> hex >> i.
while s = gets
p eval s
end HJ4 字符串分隔
#include <stdio.h>
#include <string.h>
int main() {
char s[20];
while (scanf("%8s", s) == 1) {
printf("%s", s);
for (size_t i = 0; i < 8 - strlen(s); ++i)
printf("0");
printf("\n");
}
} HJ3 明明的随机数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
for (int n; cin >> n;) {
vector<int> v;
for (int i = 0, x; i < n; ++i) {
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
auto last = unique(v.begin(), v.end());
v.erase(last, v.end());
for (int x : v)
cout << x << endl;
}
} HJ2 计算字符个数
#include <string>
#include <iostream>
#include <cctype>
using namespace std;
int main() {
int i = 0;
string s, a;
getline(cin, s);
cin >> a;
for (char c : s)
if (toupper(c) == toupper(a[0]))
i++;
cout << i << endl;
} HJ1 字符串最后一个单词的长度
#include <string>
#include <iostream>
using namespace std;
int main() {
string a;
while (cin >> a)
;
cout << a.length() << endl;
} 最近做的, 模拟内存分配, 别看写得长, 其实没任何算法在里面.
mem = { 0 => 100 } # 下标 => 正数=可用空间, 负数=正在占用
free = -> i { # 查询 i 位置可用空间
j = mem.keys.select { |j| j + mem[j] >= i && j <= i }.min
return 0 if j.nil?
return j + mem[j] - i
}
req = -> n { # 申请大小为 n 的内存
return if n.zero?
i = (0..99).find { |i| free[i] >= n } # 暴力找到一个可用位置, 可以优化
return if i.nil?
m = mem[i]
mem[i] = -n
mem[i + n] = m - n if m > n
return i
}
rar = -> { # 整理连续空内存
100.times { |i| # 暴力, 可以优化成自动跳过内存区间.
next if not mem.key? i or mem[i] < 0
loop {
j = i + mem[i]
break if not mem.key? j or mem[j] < 0
mem[i] += mem[j]
mem.delete j
}
}
}
rel = -> i { # 释放 i 位置的空间, 题目保证 i 是 mem 的下标
return if not mem.key? i or mem[i] > 0
mem[i] = -mem[i]
rar.call
return true
}
while n = gets
n.to_i.times {
a, b = gets.split('=')
b = b.to_i
if a == 'REQUEST'
if k = req[b]
p k
else
puts 'error'
end
else
if not rel[b]
puts 'error'
end
end
}
end 以上.
京公网安备 11010502036488号