关键词:
A. Poker (Hdu ????)
题目大意
给定n个币,每次投至少m个,当投(x)个时,给回(lfloor x imes (1 - p \%) floor)。问你最多能投多少次。
解题思路
很显然每次投(m)元是最优的,因为但凡投(m+1)元,给回的钱数不可能会增加二,要不不变要不减少。
每次投减少(m - lfloor m imes (1 - p \%) floor)个币,先算出可以减少多少次,记为(cnt)次,剩余(a)个币。
因为是给(m)个币返回(lfloor m imes (1 - p \%) floor)个,我们要倒推回去(k)次,找到那一点,恰好满足(a + k imes (m - lfloor m imes (1 - p \%) floor) geq m)
即(k geq dfracm - a(m - lfloor m imes (1 - p \%) floor))
最终答案就是(cnt - k)。
(代码是考虑小于号的情况)
神奇的代码
#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, p;
cin >> n >> m >> p;
if (n < m)
cout << 0 << endl;
continue;
int qwq = m - m * (100 - p) / 100;
int cnt = n / qwq;
n %= qwq;
cnt -= (m - n) / qwq;
if ((m - n) % qwq == 0)
++cnt;
cout << cnt << endl;
return 0;
B. Distance (Hdu ????)
题目大意
告诉你(n)个人距离你的距离,问这(n)个人俩俩距离和最小值是是多少。
解题思路
很容易发现距离和最小就是这(n)个人位于同一条直线且位于你的同一边,计算俩相邻人之间的距离对答案的贡献即可。
神奇的代码
#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 kase;
cin >> kase;
for (int ii = 1; ii <= kase; ii++)
int n;
cin >> n;
vector<LL> qwq(n);
for (int i = 0; i < n; ++i)
cin >> qwq[i];
sort(qwq.begin(), qwq.end());
LL ans = 0;
for (int i = 0; i < n - 1; ++i)
ans += (qwq[i + 1] - qwq[i]) * (LL)(i + 1) * (LL)(n - i - 1);
cout << ans << endl;
return 0;
C. Covid (Hdu ????)
题目大意
(n)个人,告诉你每个人每刻的位置。如果有人和感染病毒的人在某一刻在同一位置,那么那人也被感染。初始只有1号人感染了,问最终感染人的编号。
解题思路
模拟时间流逝暴力搞就好了。
神奇的代码
#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 main(void)
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
int n;
cin >> n;
int tot = 0;
vector<queue<pair<int, int>>> people(n);
for (int len, t, p, i = 0; i < n; ++i)
cin >> len;
for (int j = 1; j <= len; ++j)
cin >> t >> p;
people[i].push(make_pair(t, p));
tot = max(t, tot);
vector<bool> sign(n, 0);
sign[0] = true;
int pos[12] = 0;
for (int i = 1; i <= tot; ++i)
for (int j = 0; j < n; ++j)
if (sign[j] && (!people[j].empty()) && people[j].front().first == i)
pos[people[j].front().second] = i;
for (int j = 0; j < n; ++j)
if ((!people[j].empty()) && people[j].front().first == i)
if (pos[people[j].front().second] == i)
sign[j] = true;
people[j].pop();
printf("1");
for (int i = 2; i <= n; ++i)
if (sign[i - 1])
printf(" %d", i);
puts("");
return 0;
D. Car (Hdu ????)
题目大意
周一到周五限制车尾号0-9,一周一个车位号只能限一次。告诉你车牌号,问如何限号,才能使得每天未被限制的车的数量的最小值最大。输出这个最值。
解题思路
枚举每个车位号应该在哪一天限制,爆搜就好了。也就(10^5)种情况
神奇的代码
#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);
void DFS(int tot, int cnt[], int sum[], int &ans, int n)
if (tot == 10)
int qwq = 1e9;
for (int i = 0; i < 5; ++i)
qwq = min(qwq, sum[i]);
ans = min(ans, n - qwq);
return;
for (int i = 0; i < 5; ++i)
sum[i] += cnt[tot];
DFS(tot + 1, cnt, sum, ans, n);
sum[i] -= cnt[tot];
int main(void)
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
int n;
read(n);
int cnt[10] = 0;
for (int x, i = 1; i <= n; ++i)
read(x);
cnt[x % 10]++;
int ans = 1e9 + 7;
int sum[5] = 0;
DFS(0, cnt, sum, ans, n);
write(ans, ‘
‘);
return 0;
E. Drink (Hdu ????)
题目大意
有(n)个人,告诉你他们对于可乐、雪碧、芬达的喜好程度的排序。现在你有可乐、雪碧、芬达(a,b,c(a+b+c=n))瓶,问如何分配,使得他们的快乐值最大。若一个人喝到第一喜欢的,有3快乐值;第二喜欢的,有2快乐值;第三喜欢的,有1快乐值。
解题思路
就一道费用流裸题。
由于喜好程度的排序只有六种情况,把人数压成这六个点。
源点连三种饮料,容量为它们的瓶数,费用0。饮料连接六种情况,容量无穷,费用为相应的快乐值。六种情况连接汇点,容量为该情况的人数,费用为0。
由于是最大快乐值,把费用取相反数跑一遍最小费用最大流后取相反数即可。
神奇的代码
#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);
#define MIN(a, b) (((a) < (b) ? (a) : (b)))
#define MAX(a, b) (((a) > (b) ? (a) : (b)))
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define M 30
#define N 12
const int INF = 23333333;
int head[N], nxt[M * 2], to[M * 2], flow[M * 2], cost[M * 2], pre[N], dis[N], team[N * 5], val[N], fr[M * 2];
int num, u, v, w, st, en;
bool vis[N];
LL ans;
void add(int u, int v, int f, int w)
num++;
nxt[num] = head[u];
to[num] = v;
fr[num] = u;
flow[num] = f;
cost[num] = w;
head[u] = num;
num++;
nxt[num] = head[v];
to[num] = u;
fr[num] = v;
flow[num] = 0;
cost[num] = -w;
head[v] = num;
inline bool SPFA()
int l = 0, r = 1;
team[1] = st;
fo(i, st, en)
dis[i] = INF;
pre[i] = 0;
vis[i] = false;
dis[st] = 0;
vis[st] = 1;
while (l < r)
u = team[++l];
for (int i = head[u]; i; i = nxt[i])
v = to[i];
if (flow[i] && dis[v] > dis[u] + cost[i])
dis[v] = dis[u] + cost[i];
pre[v] = i;
if (!vis[v])
team[++r] = v;
vis[v] = 1;
vis[u] = 0;
if (pre[en])
return true;
else
return false;
inline void DFS()
int qwq = INF;
for (int i = pre[en]; i; i = pre[fr[i]])
qwq = MIN(qwq, flow[i]);
ans += (LL)qwq * (LL)dis[en];
for (int i = pre[en]; i; i = pre[fr[i]])
flow[i] -= qwq;
flow[i ^ 1] += qwq;
int main(void)
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
num = 1;
ans = 0;
int n, a, b, c;
read(n);
read(a);
read(b);
read(c);
st = 0;
en = 10;
char qwq[4];
int cnt[6] = 0;
for (int i = 1; i <= n; ++i)
scanf("%s", qwq);
if (strcmp(qwq, "012") == 0)
cnt[0]++;
if (strcmp(qwq, "021") == 0)
cnt[1]++;
if (strcmp(qwq, "102") == 0)
cnt[2]++;
if (strcmp(qwq, "120") == 0)
cnt[3]++;
if (strcmp(qwq, "201") == 0)
cnt[4]++;
if (strcmp(qwq, "210") == 0)
cnt[5]++;
add(st, 1, a, 0);
add(st, 2, b, 0);
add(st, 3, c, 0);
add(1, 4, INF, -3);
add(1, 5, INF, -3);
add(1, 6, INF, -2);
add(1, 7, INF, -1);
add(1, 8, INF, -2);
add(1, 9, INF, -1);
add(2, 4, INF, -2);
add(2, 5, INF, -1);
add(2, 6, INF, -3);
add(2, 7, INF, -3);
add(2, 8, INF, -1);
add(2, 9, INF, -2);
add(3, 4, INF, -1);
add(3, 5, INF, -2);
add(3, 6, INF, -1);
add(3, 7, INF, -2);
add(3, 8, INF, -3);
add(3, 9, INF, -3);
add(4, en, cnt[0], 0);
add(5, en, cnt[1], 0);
add(6, en, cnt[2], 0);
add(7, en, cnt[3], 0);
add(8, en, cnt[4], 0);
add(9, en, cnt[5], 0);
while (SPFA())
DFS();
write(-ans, ‘
‘);
for (int i = st; i <= en; ++i)
head[i] = 0;
return 0;
F. Cloth (Hdu ????)
题目大意
晒衣服,U字型,告诉你竖着的长度和横着的长度的衣杆,衣服挂在上面,要求任意两件的距离不小于(x),问最大晒多少件。
解题思路
qwq
神奇的代码
qwq
G. Solo (Hdu ????)
题目大意
有(n)题,已知自己和对手完成每道题的时间,且对手从第1题开始写。问如何安排顺序,使得获得的分数最大。
每一道题第一个选手AC即得一分。若同时完成则我得一分。
我完成了可以选择任意时刻交,对手完成立刻交。
若有一题有人完成了,另一人会立刻放弃该题。
解题思路
一开始考虑的是设(dp[i][j])表示前(i)题比对手超前(j)分钟时获得的最大分数,由于分钟数达(10^9)爆空间,所以考虑数据范围不那么大的状态。
设(dp[i][j])表示前(i)题,得分为(j)时的最大超前对手时间。
然后考虑能否完成第(i)题以及是否写第(i)题转移即可。
(dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]-(a[i+1]-b[i+1])) if dp[i][j]-(a[i+1]-b[i+1])geq 0)
(dp[i+1][j] = max(dp[i+1][j],dp[i][j] + b[i+1]))
初始化(dp[0][0]=0),其余为(-1)。
答案就是(dp[n][i] eq -1)中(i)的最大值。
神奇的代码
#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 int N = 2e3 + 8;
LL dp[N][N];
LL a[N], b[N];
int main(void)
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
int n;
read(n);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dp[i][j] = -1;
for (int i = 1; i <= n; ++i)
read(a[i]);
for (int i = 1; i <= n; ++i)
read(b[i]);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j)
if (dp[i - 1][j] != -1)
if (dp[i - 1][j] + b[i] >= a[i])
dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j] - (a[i] - b[i]));
dp[i][j] = max(dp[i][j], dp[i - 1][j] + b[i]);
int ans = 0;
for (int i = 0; i <= n; ++i)
if (dp[n][i] != -1)
ans = i;
write(ans, ‘
‘);
return 0;
H. Hanoi (Hdu ????)
题目大意
qwq
解题思路
qwq
神奇的代码
qwq
2021年百度之星·程序设计大赛-初赛二1005水题(贪心结论)(代码片段)
problemsolution开始还以为是CF987E,但是奇偶性并不一样,,结果是个贪心乱搞。。样例都没过交了能过,醉了。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;intmain() ios::sync_with_stdio(0),ci 查看详情
2021年百度之星·程序设计大赛-初赛二1002随机题意(区间贪心)(代码片段)
problem随机题意Accepts:1411Submissions:3641TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给一个整数数组a_1,a_2,\\cdots,a_na1,a2,⋯,an和kk,你想要找到一个最大的值xx,使 查看详情
2021年百度之星·程序设计大赛-初赛二1001签到(找规律,快速幂)(代码片段)
problem签到Accepts:6141Submissions:13643TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给a,ba,b,每次a,ba,b会变为a+b,a-ba+b,a−b,问kk次之后变成了哪两个数 查看详情
2018“百度之星”程序设计大赛-初赛(b)(代码片段)
degree Accepts:1581 Submissions:3494 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:131072/131072K(Java/Others)ProblemDescription度度熊最近似乎在研究图论。给定一个有 NN 个 查看详情
2018“百度之星”程序设计大赛-初赛(b)(代码片段)
rank264,三题水过~hdu6380_degree#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=200005;intin[maxn];intn,m,k;intmain()intt;scanf("%d",&t);while(t--)memset(in,0,sizeof(in) 查看详情
2021年百度之星·程序设计大赛-初赛二1003魔怔(并查集,联通性,欧拉回路)(代码片段)
problemsolution发现除了起点和终点,剩下所有点周围的边都会被恰经过偶数次,所以这些点初始连向了偶数条白边。考虑由白边连接形成的图,每个连通块中度数为奇数的点一定为偶数个。所以起点所在连通块最多有两... 查看详情
2018“百度之星”程序设计大赛-初赛(a)(代码片段)
度度熊拼三角 Accepts:2536 Submissions:4433 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)ProblemDescription度度熊有 NN 根木棒,每根木棒的长度为a_ia? 查看详情
2018“百度之星”程序设计大赛-初赛(a)(代码片段)
第二题还算手稳+手快?最后勉强挤进前五百(期间看着自己从两百多掉到494名)1001 度度熊拼三角 (hdoj6374)链接:http://acm.hdu.edu.cn/showproblem.php?pid=6374签到题 题意:给n根木棒求可以拼出的周长最长的三角形可以... 查看详情
2018“百度之星”程序设计大赛-初赛(a)度度熊学队列listrope(代码片段)
c++list使用1#include<cstdio>2#include<cstdlib>3#include<cmath>4#include<cstring>5#include<time.h>6#include<string>7#include<set>8#include<map>9#include< 查看详情
2022百度之星程序设计大赛-初赛-第二场1001和(代码片段)
problemsolution题意:给出长为n的序列,q次询问区间是否存在<=k个数之和>=x。n,q<1e5,k<10.思路:因为要和>=x,所以让和尽可能大,即判断区间中最大的k个数之和是否大于x即可。即区间最... 查看详情
2017"百度之星"程序设计大赛-初赛(a)
2017"百度之星"程序设计大赛-初赛(A)hdu6108 求出n-1的因子个数即可#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#definerep(i,a,b)for(inti=a;i<=b;++i)#de 查看详情
hdu5253连接的管道(kruskal)(百度之星程序设计大赛-初赛)
连接的管道TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1323 AcceptedSubmission(s):519ProblemDescription老Jack有一片农田 查看详情
2017"百度之星"程序设计大赛-初赛(b)小小粉丝度度熊
ProblemDescription度度熊喜欢着喵哈哈村的大明星——星星小姐。为什么度度熊会喜欢星星小姐呢?首先星星小姐笑起来非常动人,其次星星小姐唱歌也非常好听。但这都不是最重要的,最重要的是,星星小姐拍的一手好代码!于是... 查看详情
[singularity]百度之星程序设计大赛初赛1001小c的倍数问题
小C的倍数问题 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识,我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之,如果一个数每一位加起来是3的... 查看详情
2017"百度之星"程序设计大赛-初赛(a)01,05,06
小C的倍数问题 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识,我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之,如果一个数每一... 查看详情
hdu6114chess组合数(2017"百度之星"程序设计大赛-初赛(b))
ChessTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):513 AcceptedSubmission(s):319ProblemDescription車是中国象棋中的一种棋 查看详情
2017"百度之星"程序设计大赛-初赛(a)
小C的倍数问题ProblemDescription根据小学数学的知识,我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之,如果一个数每一位加起来是3的倍数,则这个数肯定是3的倍数。现在给定进制P,求有多少个B满足P... 查看详情
hdu6109数据分割并查集(2017"百度之星"程序设计大赛-初赛(a))
数据分割TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1119 AcceptedSubmission(s):268ProblemDescriptio 查看详情