A和I都是签到题
按位BFS K Yet Another Multiple Problem
题意：给一些可以用的数字，求最小的数，它由特定的数字组成且是n的倍数
分析：暴力枚举不可行，因为数字可能非常大。考虑到大数取模为0，BFS每一层即数位，递归输出路径。
#include <bits/stdc++.h> const int N = 1e4 + 5;
bool no[10];
std::pair<int, int> pre[N];
int dir[10];
bool vis[N];
int n, m, tot; void print(int u) {
if (u != 0) {
print (pre[u].first);
printf ("%d", pre[u].second);
}
return ;
} void BFS() {
memset (vis, false, sizeof (vis));
std::queue<int> que;
que.push (0);
while (!que.empty ()) {
int x = que.front (); que.pop ();
for (int i=0; i<tot; ++i) {
if (x == 0 && dir[i] == 0) {
continue;
}
int y = (x * 10 + dir[i]) % n;
if (y == 0) {
print (x);
printf ("%d\n", dir[i]);
return ;
}
if (vis[y]) {
continue;
}
vis[y] = true;
pre[y] = std::make_pair (x, dir[i]);
que.push (y);
}
}
puts ("-1");
return ;
} int main() {
int cas = 0;
while (scanf ("%d%d", &n, &m) == 2) {
memset (no, false, sizeof (no));
for (int i=0; i<m; ++i) {
int x; scanf ("%d", &x);
no[x] = true;
}
tot = 0;
for (int i=0; i<10; ++i) {
if (!no[i]) {
dir[tot++] = i;
}
}
printf ("Case %d: ", ++cas);
BFS ();
} return 0;
}
同类型的题目：
URAL 1495
#include <bits/stdc++.h> const int N = 1e6 + 5;
std::pair<int, int> pre[N];
bool vis[N];
int n; void print(int u) {
if (u != 0) {
print (pre[u].first);
printf ("%d", pre[u].second);
}
return ;
} void BFS() {
memset (vis, false, sizeof (vis));
std::queue<int> que;
que.push (0);
while (!que.empty ()) {
int x = que.front (); que.pop ();
for (int i=1; i<3; ++i) {
int y = (x * 10 + i) % n;
if (y == 0) {
print (x);
printf ("%d\n", i);
return ;
}
if (vis[y]) {
continue;
}
vis[y] = true;
pre[y] = std::make_pair (x, i);
que.push (y);
}
}
puts ("Impossible");
return ;
} int main() {
while (scanf ("%d", &n) == 1) {
BFS ();
} return 0;
}
HDOJ 1226
#include <bits/stdc++.h> const int N = 5e3 + 5;
std::pair<int, int> pre[N];
struct Node {
int x, len;
};
int dir[16];
bool vis[N];
int n, c, m; void print(int u) {
if (u != 0) {
print (pre[u].first);
int x = pre[u].second;
if (x < 10) {
printf ("%d", x);
} else {
printf ("%c", 'A' + x - 10);
}
}
return ;
} void BFS() {
memset (vis, false, sizeof (vis));
std::queue<Node> que;
que.push ((Node) {0, 0});
while (!que.empty ()) {
Node &u = que.front (); que.pop ();
if (u.len >= 500) {
continue;
}
for (int i=0; i<m; ++i) {
if (u.x == 0 && dir[i] == 0) {
continue;
}
int y = (u.x * c + dir[i]) % n;
if (y == 0) {
print (u.x);
int d = dir[i];
if (d < 10) {
printf ("%d\n", d);
} else {
printf ("%c\n", 'A' + d - 10);
}
return ;
}
if (vis[y]) {
continue;
}
vis[y] = true;
pre[y] = std::make_pair (u.x, dir[i]);
que.push ((Node) {y, u.len + 1});
}
}
puts ("give me the bomb please");
return ;
} int main() {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &c);
scanf ("%d", &m);
char str[3];
for (int i=0; i<m; ++i) {
scanf ("%s", str);
if (str[0] >= 'A' && str[0] <= 'F') {
dir[i] = str[0] - 'A' + 10;
} else {
dir[i] = str[0] - '0';
}
}
std::sort (dir, dir+m);
if (n == 0) {
if (dir[0] == 0) {
puts ("0");
} else {
puts ("give me the bomb please");
}
} else {
BFS ();
}
} return 0;
}
数学期望 B Candy
题意：两堆n个物品，每次拿走一个，从第一堆拿的概率p，另一堆概率1-p，问其中一堆0时，另一堆数量的期望。
分析：公式为：。p^n不好直接算，技巧：取对数后在exp阶乘回来
#include <bits/stdc++.h> //ret = sigma(exp(log(C(n+i, i) + (n+1) * log(p) + i * log(1-p))));
double run(int n, double p) {
double ret = 0, lp = log (p), lq = log (1-p), c = log (1.0);
ret = exp (c + (n+1) * lp + 0 * lq) * n;
for (int i=1; i<n; ++i) {
c = c + log (n + i) - log (i);
ret += exp (c + (n+1) * lp + i * lq) * (n - i);
}
return ret;
} int main() {
int n, cas = 0; double p;
while (scanf ("%d%lf", &n, &p) == 2) {
printf ("Case %d: ", ++cas);
if (p == 0 || p == 1) {
printf ("%.8f\n", (double) n);
} else {
printf ("%.8f\n", run (n, p) + run (n, 1.0 - p));
}
}
return 0;
}
数论 J Exam
题意：定义f(x) = 满足x%(a*b)=0的pair(a,b)的数量，求f(1)+f(2)+f(3)+...+f(n)
分析：n<=10^11普通枚举不可行。转换一下，问题变成x=a*b*c的pair(a,b,c)的数量，设a<=b<=c，则a<=,b<=
，枚举a和b，复杂度为O(
).还一个问题，题目求前缀总和，考虑pair(a,b)对1~n的贡献为n/(a*b)，相当于1~n是a*b的倍数的个数。
#include <bits/stdc++.h>
typedef long long ll;
int sqrt2(ll x) {
ll ret = (int) pow (1.0 * x, 0.5);
while (ret * ret < x) {
ret++;
}
while (ret * ret > x) {
ret--;
}
return ret;
}
int sqrt3(ll x) {
ll ret = (int) pow (1.0 * x, 1.0 / 3);
while (ret * ret * ret < x) {
ret++;
}
while (ret * ret * ret > x) {
ret--;
}
return ret;
}
ll run(ll n) {
ll sq3 = sqrt3 (n);
ll ret = sq3; //a = b = c
for (int i=1; i<=sq3; ++i) {
ll ni = n / i;
ll k = sqrt2 (ni);
ret += (ni / i - i) * 3; //a = b < c
ret += (k - i) * 3; //a < b = c
for (int j=i+1; j<=k; ++j) {
ret += (ni / j - j) * 6; //a < b < c
}
}
return ret;
}
int main() {
ll n;
int cas = 0;
while (scanf ("%I64d", &n) == 1) {
printf ("Case %d: %I64d\n", ++cas, run (n));
}
return 0;
}