A. Drink (Hdu 6743)
题目大意
给定(n)种饮料，每种无限瓶，每瓶饮料有水分(x[i])，包含(y[i])卡路里。
现要求选一种饮料不断喝，求摄入至少(m)水分下，得到的卡路里最小值。
解题思路
一开始没看到只能喝一种饮料考虑DP，结果开场3分钟就破百AC怀疑人生，他们都这么快的吗？？
因为只能喝一种就枚举每一种饮料求最小值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
int ans = 1e9 + 7;
for (int x, y, i = 1; i <= n; ++i)
{
cin >> x >> y;
ans = min(ans, (int)ceil(m * 1.0 / x) * y);
}
cout << ans << endl;
}
return 0;
}
B. GPA (Hdu 6744)
题目大意
给你四门总分，告诉你每一门中，成绩对应的绩点关系，问绩点最高是多少。
解题思路
就(11^4)种情况爆搜就好了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
double ans;
double ch(int x){
if (x >= 95) return(4.3);
if (x >= 90) return(4.0);
if (x >= 85) return(3.7);
if (x >= 80) return(3.3);
if (x >= 75) return(3.0);
if (x >= 70) return(2.7);
if (x >= 67) return(2.3);
if (x >= 65) return(2.0);
if (x >= 62) return(1.7);
if (x >= 60) return(1.0);
return 0;
}
void solve(int x,int pos,double mark){
if (pos==4){
mark += ch(x);
ans = max(ans, mark);
return;
}
if (x >= 95) solve(x-95,pos+1,mark+4.3);
if (x >= 90) solve(x-90,pos+1,mark+4.0);
if (x >= 85) solve(x-85,pos+1,mark+3.7);
if (x >= 80) solve(x-80,pos+1,mark+3.3);
if (x >= 75) solve(x-75,pos+1,mark+3.0);
if (x >= 70) solve(x-70,pos+1,mark+2.7);
if (x >= 67) solve(x-67,pos+1,mark+2.3);
if (x >= 65) solve(x-65,pos+1,mark+2.0);
if (x >= 62) solve(x-62,pos+1,mark+1.7);
if (x >= 60) solve(x-60,pos+1,mark+1.0);
solve(x,pos+1,mark);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int kase; cin>>kase;
for (int ii=1,m; ii <= kase; ii++) {
cin>>m;
ans = 0;
solve(m,1,0);
cout<<fixed<<setprecision(1)<<ans<<endl;
}
return 0;
}
C. Dec (Hdu 6745)
题目大意
给定两个正整数(a,b)，每次操作可以让(a)或(b)减一，直到两个都变为一，问整个过程中，出现(a，b)互质的情况数的最大值。
解题思路
抽象成平面上的点，左下角((1,1))，初始点((a,b))，一次可以向左或向下走一格，(i,j)互质点((i,j))有一个贡献，问从((a,b))到((1,1))的所有路径中，走到有贡献点的最大值，Dp即可。预处理从(1,1)到所有点最大值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int dp[1002][1002];
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
int main(void)
{
dp[1][1] = 1;
for (int i = 1; i <= 1000; ++i)
for (int j = 1; j <= 1000; ++j)
{
if ((i == 1) && (j == 1))
continue;
if (i == 1)
dp[i][j] = dp[i][j - 1] + (__gcd(i, j) == 1);
else if (j == 1)
dp[i][j] = dp[i - 1][j] + (__gcd(i, j) == 1);
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + (__gcd(i, j) == 1);
}
int kase;
cin >> kase;
for (int a, b, ii = 1; ii <= kase; ii++)
{
read(a);
read(b);
write(dp[a][b], '
');
}
return 0;
}
D. Civilization (Hdu 6746)
题目大意
看原文吧，就是建城市得粮食得人口派人取工作继续得粮食直到人口达到9问最短的时间。
解题思路
枚举建城市地点然后优先派人口到能取得粮食最多的地方工作，模拟模拟就好了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
int dis(int i, int j, int x, int y)
{
int qwq = abs(i - x) + abs(j - y);
return (int)ceil(qwq * 1.0 / 2);
}
int a[505][505];
int n;
int dx[24] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -3, -2, -1, 1, 2, 3, -2, -1, 0, 1, 2, -1, 0, 1, 0};
int dy[24] = {3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -2, -2, -2, -3};
int up[9] = {0, 1 * 1 * 8, 2 * 2 * 8, 3 * 3 * 8, 4 * 4 * 8, 5 * 5 * 8, 6 * 6 * 8, 7 * 7 * 8, 8 * 8 * 8};
int solve(int x, int y)
{
vector<int> qwq;
for (int i = 0; i < 24; ++i)
{
if ((x + dx[i] <= 0) || (x + dx[i] > n) || (y + dy[i] <= 0) || (y + dy[i] > n))
continue;
qwq.push_back(a[x + dx[i]][y + dy[i]]);
}
sort(qwq.begin(), qwq.end(), greater<int>());
int cur = a[x][y];
int people = 1;
int ju = 0;
size_t len = 0;
int tot = 0;
int gg = 0;
while (people < 9)
{
gg = (int)ceil((up[people] - tot) * 1.0 / cur);
ju += gg;
tot += gg * cur;
people++;
if (len < qwq.size())
{
cur += qwq[len];
++len;
}
}
return ju;
}
int main(void)
{
int kase;
read(kase);
for (int x, y, ii = 1; ii <= kase; ii++)
{
read(n);
read(x);
read(y);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
read(a[i][j]);
int ans = 1e9 + 7;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
ans = min(ans, dis(i, j, x, y) + solve(i, j));
}
}
printf("%d
", ans);
}
return 0;
}
E. Rotate (Hdu 6747)
题目大意
一个圆环由外到内分成(n)层，第(i)层被分为(a[i])块，(a[i])是偶数，一半涂黑色一半涂白色，间隔涂。
现独立旋转每一层，每一层会等概率随机终止一种局面，问黑色联通块个数的期望值。
(a[i])不降。
解题思路
由于(a[i])不降，块的长度只会减小，所以第(i+1)层的黑块至多与与第(i)层的中的一个黑块会有接触，这样有接触之间的黑块连一条边，它们就构成了一个森林。
对于森林，联通块数量 = 点数 - 边数。
由期望的线性性质，E(联通块) = E(点数) - E(边数)
而(E( ext{点数}) = sumlimits_{i = 1}^{n} dfrac{a[i]}{2})
对于边数，第(i+1)层的一个黑块与第(i)层的一个黑块会有接触的概率是
[frac{ frac{2pi}{a[i+1]} + frac{2pi}{a[i]}}{2pi} = frac{1}{a[i+1]} + frac{1}{a[i]}
]
由期望定义知这也是期望边数。
再乘以它们的数量即得
[left( dfrac{1}{a[i+1]} + dfrac{1}{a[i]}
ight) dfrac{a[i]}{2} dfrac{a[i+1]}{2} = dfrac{a[i] + a[i+1]}{4}
]
所以(E( ext{边数}) = sumlimits_{i=1}^{n-1}dfrac{a[i] + a[i+1]}{4})
把(E( ext{边数}))和(E( ext{点数}))代入化简得
(E( ext{联通块}) = dfrac{a[1] + a[n]}{4})
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mo = 1e9 + 7;
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int inv4 = 250000002;
int kase;
cin >> kase;
for (int ii = 1; ii <= kase; ii++)
{
int n;
cin >> n;
int a;
cin >> a;
if (n == 1)
{
cout << a / 2 << endl;
continue;
}
else
{
int b;
for (int i = 2; i <= n; ++i)
cin >> b;
cout << (LL)(a + b) * inv4 % mo << endl;
}
}
return 0;
}
F. Matrix (Hdu 6748)
题目大意
给定以原点作为中心的四个正方形，要求从被覆盖的整点中选出(k)个，它们的权值最小。一个点((x,y))的权值为它到原点的曼哈顿距离乘以被正方形覆盖的次数。
解题思路
qwq
神奇的代码
qwq
G. Mosquito (Hdu 6749)
题目大意
给了一个网格图，一些边缘网格（窗户）有一些蚊子，蚊子每一刻可以上下左右移动一格，不能移出网格，假设网格足够聪明，问最少过多长时间，每个网格都有至少一只蚊子。
解题思路
首先蚊子数少于网格数就直接输出 -1。
考虑逆向，即初始时刻每个位置都有一只蚊子，现在蚊子要飞回窗户，问最少过多长时间，限制就是飞回某一窗户的蚊子数不能多余该窗户原有的蚊子数。
先预处理出每个位置的蚊子飞到每一个窗户所需要的时间。
很显然时间越长，蚊子肯定能飞回窗户，方案可行对时间具有单调性。
二分时间，得到每个蚊子能飞到哪些窗户，再考虑如何分配哪些蚊子飞到哪些窗户，可以看出是带有反悔性的决策，跑一遍网络流即可判断是否可行。
但蚊子数太多，如果我们把每只蚊子与能飞到的窗户连一条边，点数和边数会巨大，我们考虑如何压点。
考虑到蚊子能飞到窗户的情况数最多只有(2^6)种，于是我们把能飞到窗户的情况相同的蚊子都压成一个点，这样点数就只有((2+6+2^6))。
具体的连边，就是源点与所有情况数连一条边，容量为该情况对应的蚊子数；每种情况与对应的窗户连一条边，容量无限；每个窗户与汇点连一条边，容量是该窗户初始有的蚊子数量。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MIN(a, b) (((a) < (b) ? (a) : (b)))
#define MAX(a, b) (((a) > (b) ? (a) : (b)))
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
#define M 100
#define N 640
const int INF = 233333333;
struct data
{
int to, nxt, flow;
} line[N * 2];
int n, m, l, r, ans, team[M * 2], dis[M * 2], head[M * 2], num, u, v, st, en, qaq;
void add(int u, int v, int w)
{
num++;
line[num].nxt = head[u];
line[num].to = v;
line[num].flow = w;
head[u] = num;
num++;
line[num].nxt = head[v];
line[num].to = u;
line[num].flow = 0;
head[v] = num;
}
bool BFS()
{
int u, v;
l = r = 0;
team[++r] = st;
memset(dis, 0, sizeof(dis));
dis[st] = 1;
while (l < r)
{
u = team[++l];
for (int i = head[u]; i; i = line[i].nxt)
{
v = line[i].to;
if (dis[v] == 0 && line[i].flow)
{
dis[v] = dis[u] + 1;
team[++r] = v;
}
}
}
if (dis[en])
return true;
else
return false;
}
int DFS(int u, int f)
{
if (u == en)
return f;
int tmp = 0;
int qwq = 0;
int v = 0;
for (int i = head[u]; i; i = line[i].nxt)
{
v = line[i].to;
if (dis[v] == dis[u] + 1 && line[i].flow)
{
qwq = DFS(v, MIN(f - tmp, line[i].flow));
line[i].flow -= qwq;
line[i ^ 1].flow += qwq;
tmp += qwq;
if (tmp == f)
return tmp;
}
}
return tmp;
}
int x[8], y[8], cnt[8];
int k;
int ddis[1001][1001][8];
int main(void)
{
int t;
read(t);
while (t--)
{
read(n);
read(m);
read(k);
long long qmq = 0;
for (int i = 1; i <= k; ++i)
{
read(x[i]);
read(y[i]);
read(cnt[i]);
qmq += (long long)cnt[i];
for (int a = 1; a <= n; ++a)
for (int b = 1; b <= m; ++b)
{
ddis[a][b][i] = abs(a - x[i]) + abs(b - y[i]);
}
}
if (qmq < (long long)n * m)
{
printf("-1
");
continue;
}
int tot = (1 << (k));
st = 0;
en = tot + k + 1;
int l = 0, r = n + m;
int cc[66] = {0};
while (l < r)
{
int mid = (l + r) >> 1;
num = 1;
for (int i = st; i <= en; ++i)
head[i] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
int sign = 0;
for (int a = 1; a <= k; ++a)
{
if (ddis[i][j][a] <= mid)
sign |= (1 << (a - 1));
}
cc[sign]++;
}
}
for (int i = 0; i < (1 << k); ++i)
{
for (int a = 1; a <= k; ++a)
if ((i >> (a - 1)) & 1)
add(i + 1, tot + a, INF);
add(st, i + 1, cc[i]);
cc[i] = 0;
}
for (int i = 1; i <= k; ++i)
add(tot + i, en, cnt[i]);
int dd = 0;
while (BFS())
dd += DFS(st, INF);
if (dd < n * m)
l = mid + 1;
else
r = mid;
}
write(r, '
');
}
return 0;
}
H. Function (Hdu 6750)
题目大意
给定(n)，计算(sumlimits_{i = 1}^{n} sumlimits_{t|i} t [gcd(t,dfrac{i}{t}) = 1])
解题思路
参考出处
化公式
从([gcd(t,dfrac{i}{t}) = 1] = epsilon(gcd(t,dfrac{i}{t})) = sumlimits_{d|gcd(t,frac{i}{t})} mu(d) 1(frac{gcd(t,frac{i}{t})}{d}) = sumlimits_{d|gcd(t,frac{i}{t})} mu(d))出发。
[egin{aligned}
sumlimits_{i = 1}^{n} sumlimits_{t|i} t [gcd(t,dfrac{i}{t}) = 1] &= sumlimits_{i = 1}^{n} sumlimits_{t|i} t sumlimits_{d|gcd(t,frac{i}{t})} mu(d) \
&= sumlimits_{i = 1}^{n} sumlimits_{t|i} t sumlimits_{d|t,d|frac{i}{t}} mu(d) \
调整顺序，枚举mu(d)考虑有多少个&= sumlimits_{d = 1}^{n} mu(d) sumlimits_{t = 1}^{lfloor frac{n}{d}
floor} td lfloor frac{n}{d^2 t}
floor \
(调整顺序，将最右边的d^2t看成关于lfloor frac{n}{d^2 t}
floor的自变量)&= sumlimits_{t = 1}^{n} lfloor frac{n}{t}
floor sumlimits_{d^2|t} mu(d) frac{t}{d} \
调整顺序&= sumlimits_{d = 1}^{sqrt{n}} mu(d) sumlimits_{t = 1}^{lfloor frac{n}{d^2}
floor} lfloor frac{n}{d^2t}
floor frac{td^2}{d} \
&= sumlimits_{d = 1}^{sqrt{n}} mu(d)d sumlimits_{t = 1}^{lfloor frac{n}{d^2}
floor} t lfloor frac{n}{d^2t}
floor \
G(x) = sumlimits_{i = 1}^{x} t lfloor frac{i}{t}
floor o &=sumlimits_{d = 1}^{sqrt{n}} mu(d)d cdot G left( lfloor frac{n}{d^2}
floor
ight)
end{aligned}
]
(G(x))可用整数分块求，求累加和也可用整数分块求。
至于复杂度为什么会有log不会qwq
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
const LL mo = 1e9 + 7;
const LL N = 1e6 + 8;
bool visit[N];
LL prim[N];
int u[N];
LL sum_mu[N];
void pre_mu()
{
sum_mu[0] = 0;
memset(visit, false, sizeof(visit));
int tot = 0;
u[1] = 1;
sum_mu[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!visit[i])
{
visit[i] = true;
prim[++tot] = i;
u[i] = -1;
}
for (int j = 1; j <= tot; j++)
{
if (prim[j] * i > N)
break;
visit[prim[j] * i] = true;
if (i % prim[j])
u[prim[j] * i] = -u[i];
else
{
u[prim[j] * i] = 0;
break;
}
}
sum_mu[i] = (sum_mu[i - 1] + (LL)u[i] * i % mo + mo) % mo;
}
}
LL inv2 = 500000004;
LL calc(LL l, LL r)
{
LL nxt = 0;
LL tmp = 0;
while (l <= r)
{
nxt = r / (r / l);
tmp = (tmp + (r / l) * ((l + nxt) % mo) % mo * ((nxt - l + 1) % mo) % mo * inv2 % mo) % mo;
l = nxt + 1;
}
return tmp;
}
int main(void)
{
pre_mu();
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
{
LL n;
LL ans = 0;
read(n);
LL up = sqrt(n);
LL l = 1;
LL nxt = 0;
while (l <= up)
{
nxt = (LL)sqrt(n / (n / (l * l)));
if (nxt > up)
nxt = up;
ans = (ans + calc(1, n / (l * l)) * ((sum_mu[nxt] - sum_mu[l - 1] + mo) % mo) % mo) % mo;
l = nxt + 1;
}
write(ans, '
');
}
return 0;
}