网站建设可自学吗,网站网站如何做的充值,网络交友的网站建设,深圳公司注册登记中心目录
B - Leftover Recipes
C - We Got Everything Covered!
D - A Balanced Problemset?
E - Lame King
F - Grid Ice Floor
B - Leftover Recipes
问题描述
你的冰箱里有N种食材。我们将它们称为食材1、……和食材N。你有Qi克的食材i。
你可以制作两种菜肴。制…目录
B - Leftover Recipes
C - We Got Everything Covered!
D - A Balanced Problemset?
E - Lame King
F - Grid Ice Floor
B - Leftover Recipes
问题描述
你的冰箱里有N种食材。我们将它们称为食材1、……和食材N。你有Qi克的食材i。
你可以制作两种菜肴。制作一份A菜你需要每种食材i(1≤i≤N)克。制作一份B菜你需要每种食材i克。你只能制作整数份的每种菜肴。
只使用冰箱里的食材你能制作的菜肴总份数最多是多少
约束条件
1≤N≤101≤Qi≤10^60≤Ai≤10^6存在i使得Ai≥1。0≤Bi≤10^6存在i使得Bi≥1。所有输入值均为整数。
输入
输入以以下格式从标准输入给出
N
Q1 Q2 …… QN
A1 A2 …… AN
B1 B2 …… BN输出
假设你能制作最多S份菜肴请输出整数S。
示例1
InputOutput 2
800 300
100 100
200 105这个冰箱里有800克的食材1和300克的食材2。
你可以用100克的食材1和100克的食材2制作一份A菜用200克的食材1和10克的食材2制作一份B菜。
要制作两份A菜和三份B菜你需要100×2200×3800克的食材11和100×210×3230克的食材2都不超过冰箱里的数量。这样你总共可以制作五份菜肴但无法制作六份所以答案是5。
示例2
InputOutput 2
800 300
100 0
0 1038你可以用800克的食材1制作8份A菜用300克的食材2制作30份B菜总共38份。
示例3
InputOutput 2
800 300
801 300
800 3010你无法制作任何菜肴。
示例4
InputcopyOutputcopy 10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0222222最开始认为是深度搜索但不确定有几种食材觉得不行后面又以为背包问题但考虑因素太多了感觉也不行后面才发现直接暴力枚举就行了。
思路
先计算出全部制作A菜最多可以制作多少份然后减少制作一份1A菜后能制作多少份B菜每次更新最大值。
AC代码
#includestdio.h
int a[11], b[11], c[11], d[11], e[11];
int main()
{int n, i, sum 1e9, j;scanf(%d, n);for (i 1; i n; i)scanf(%d, a[i]);for (i 1; i n; i)scanf(%d, b[i]);for (i 1; i n; i)scanf(%d, c[i]);for (i 1; i n; i)//计算全部制作A菜可以制作多少份存在sum上{if (b[i] ! 0){if (sum a[i] / b[i])sum a[i] / b[i];}}for (i 1; i n; i)//全部制作A菜后还剩下的材料存在d数组里面d[i] a[i] - (b[i] * sum);int u sum;for (i 0; i u; i)//每次减少制作i份A菜{for (j 1; j n; j)//复制d数组到e数组e[j] d[j];for (j 1; j n; j)//加上恢复的材料e[j] i * b[j];int p 1e9;for (j 1; j n; j)//全部制作B菜能制作多少份{if (c[j] ! 0){if (p e[j] / c[j])p e[j] / c[j];}}if (sum u - i p)//更新最大值sum u - i p;}printf(%d\n, sum);//打印结果return 0;
}C - We Got Everything Covered!
给定两个正整数 n 和 k。
你的任务是找到一个字符串 s使得使用前 k 个小写英文字母可以形成的长度为 n 的所有可能字符串都是 s 的子序列。
如果有多个答案输出长度最小的。如果仍然有多个答案你可以输出任意一个。
注意 如果一个字符串 a 是另一个字符串 b 的子序列那么可以通过从 b 中删除一些可能为零字符而不改变剩余字符的顺序来得到 a。
输入
输入的第一行包含一个整数 t (1≤t≤676)表示测试用例的数量。
每个测试用例包括一行输入包含两个整数 n (1≤n≤26) 和 k (1≤k≤26)。
输出
对于每个测试用例输出一行包含一个字符串 s满足上述条件。如果有多个答案输出长度最小的。如果仍然有多个答案你可以输出任意一个。
示例 1
InputOutput 4
1 2
2 1
2 2
2 3ab
aa
baab
abcbac注意
对于第一个测试用例可以使用前 2 个小写英文字母形成的长度为 1 的两个字符串都作为 s 的子序列如下所示
a:abb:ab
对于第二个测试用例可以使用前一个小写英文字母形成的长度为 2 的一个字符串作为 s 的子序列如下所示
aa:aa
对于第三个测试用例可以使用前 2 个小写英文字母形成的长度为 2 的 4 个字符串都作为 s 的子序列如下所示
aa:baabab:baabba:baabbb:baab
对于第四个测试用例可以使用前 3 个小写英文字母形成的长度为 2 的 9 个字符串都作为 s 的子序列如下所示
aa:abcbacab:abcbacac:abcbacba:abcbacbb:abcbacbc:abcbacca:abcbaccb:abcbaccc:abcbac
这题看了半天不知道题目讲什么意思看懂题目之后才发现题目不难也没有考察什么算法
题目意思大概就是输入k代表1~k个小写字母a~ak)可以重复使用1~k中的字母组成一个字符串s输入的n表示从1~k个字符抽取n个字符组合字符串h要使从s串中间删除某些元素使得s串能变成所有的h串的组合然后让我们找到长度最短的s串显然串的长度就是n*k1~k个字符出现的数量相同。
AC代码
#includestdio.h
int main()
{int k, n, t, i, j;char a a;scanf(%d, t);while(t--)//t个测试数据{scanf(%d %d, n, k);for (i 1; i n; i)//重复n次{if(i%21)//奇数正序输出1~k字符{for (j 1; j k; j)printf(%c, a - 1 j);}else//偶数反序输出k~1字符{for (j k; j 1; j--)printf(%c, a - 1 j);}}printf(\n);}return 0;
} D - A Balanced Problemset?
ay成功创建了一个难度为x的问题并决定将其设为Codeforces Round #921的第二个问题。
但Yash担心这个问题会使比赛失衡协调员会拒绝它。因此他决定将它分解成一个包含n个子问题的问题集使得所有子问题的难度都是正整数并且它们的总和等于x。
协调员Aleksey将问题集的平衡定义为问题集中所有子问题的难度的最大公约数。
如果他选择子问题的难度最优地找出Yash可以实现的问题集的最大平衡。
输入
输入的第一行包含一个整数t1≤t≤10^3表示测试用例的数量。
每个测试用例包含一行输入包含两个整数x1≤x≤10^8和n1≤n≤x。
输出
对于每个测试用例输出一行包含一个整数表示Yash可以实现的问题集的最大平衡。
示例 1
InputOutput 3
10 3
5 5
420 692
1
6注意
对于第一个测试用例一种可能的方法是将难度为10的问题分解成难度分别为4、2和4的三个问题得到的平衡等于2。
对于第二个测试用例将难度为5的问题分解成包含5个问题的问题集每个问题的难度为1得到的平衡等于1。
思路 最开始我的思路是判断x能否直接整除n如果能平衡就是x/n,如果不能就暴力凑例如10不能整除3,最开始拆成p3 3q4前面两个3分别减一减少的凑到4变成226直到q%p0然而数据较大一旦x为素数最差情况就是O(t*x)显然不行。
看了题解思路直接暴力枚举x的因子更新最大值这样的话时间复杂度为O(t*logx)xi*j,必须保证i和j中有一个大于等于n且i这样的话可以叠加凑成n个比如x12,n6这种情况必须保证有一个因子大于等于6
AC代码
#includestdio.h
int main()
{int t, n, x, sum, i, j;scanf(%d, t);while (t--){sum -1e9;scanf(%d %d, x, n);for (i 1; i * i x; i)//枚举x的所有因子{if (x % i)continue;if (i n)sum sum (x / i) ? sum : (x / i);//sum取sum和(x/i)中较大值else if (x / i n)sum sum i ? sum : i;//sum取sum和i中较大值}printf(%d\n, sum);}return 0;
} E - Lame King
给定一个大小为201×201的棋盘即有201行和201列。棋盘的行从下到上编号为−100到100。棋盘的列从左到右编号为−100到100。记号(r,c)表示位于第r行和第c列的格子。
在位置(0,0)有一个国王棋子它想尽快到达位置(a,b)。在这个问题中我们的国王很笨。每秒钟国王只能进行以下五种移动之一。
跳过。国王的位置保持不变。向上移动。如果国王当前的位置是(r,c)它将移动到位置(r1,c)。向下移动。位置从(r,c)变为(r−1,c)。向右移动。位置从(r,c)变为(r,c1)。向左移动。位置从(r,c)变为(r,c−1)。
国王不允许进行使其超出棋盘范围的移动。国王之所以笨是因为他不允许连续两秒钟进行相同的移动。例如如果国王向右移动下一秒他只能跳过、向上、向下或向左移动。
国王需要多少秒钟才能到达位置(a,b)
输入
输入的第一行包含一个整数t1≤t≤10^4——测试用例的数量。接下来t行每行包含一个测试用例的描述。
每个测试用例由两个整数a和b−100≤a,b≤100组成表示国王想要到达的格子的位置。保证a≠0或b≠0。
输出
输出t个整数。第i个整数应该等于国王在第i个测试用例中到达目标位置所需的最少秒数。国王始终从位置(0,0)开始。
示例 1
输入输出 5
-4 1
4 4
0 -6
-5 -4
7 -87
8
11
9
15注意
第一个示例的一种可能解决方案是向下移动向右移动向下移动向右移动向下移动向左移动向下移动。
第二个示例的一种可能解决方案是交替进行向右移动和向上移动每种移动各进行4次。
第三个示例的一种可能解决方案是从向左移动和跳过移动开始交替进行以向左移动开始。因此向左移动将使用66次跳过将使用5次。
思路
本题为思维题例如如果目标在右上角尽量是右上右上或上右上右这样走这样可以减少停顿时间直到走到的点只在目标点的左方或下方才需要考虑停顿的时间所以答案有两种可能
1.向右走的距离和向上走的距离小于等于1答案为abs(x)abs(y)
2向右走的距离和向上走的距离大于1答案为abs(x)abs(y)abs(abs(x)-abs(y))-1
一开始又往搜索方面想真是越学越傻了
AC代码
#includestdio.h
#includemath.h
int main()
{int t, x, y, sum;scanf(%d, t);while (t--){scanf(%d %d, x, y);x abs(x); y abs(y);sum x y;if (abs(x - y) 1)sum abs(x - y) - 1;printf(%d\n, sum);}return 0;
} F - Grid Ice Floor
题目描述
有一个N×M网格和一个站在上面的玩家。 让 (i,j) 表示该网格中第 i 行从顶部开始数的方块和第 j 列从左边开始数的方块。 该网格的每个方块都是冰或石头用 N 长度为 M 的字符串表示如下
如果 Si 的第 j 个字符是 .则方块 (i,j) 是冰;如果 Si 的第 j 个字符是 #则方块 (i,j) 是石头。
此网格的外围第 1 行、第 N 行、第 11 列、第 M 列中的所有方块是石头。
最初玩家站在冰块 (2,2) 上。 玩家可以进行以下移动零次或多次。
首先指定移动方向上、下、左或右。然后沿着该方向移动直到玩家碰到石头。具体来说继续执行以下操作: 如果移动方向上的下一个方块是冰块则去到该方块并继续移动如果移动方向上的下一个方块是石头则留在当前方块并停止移动。
找出玩家可以触及经过或停留在的冰块数量。
约束条件
3≤N,M≤200Si 是长度为 M 的字符串由 # 和 . 组成。如果 i1、iN、j1 或 jM则方块 (i,j) 是石头。方块 (2,2) 是冰。
输入
输入以以下格式从标准输入给出
N M
S1
S2
⋮⋮
sN输出
以整数形式输出答案。
示例 1
InputOutput 6 6
######
#....#
#.#..#
#..#.#
#....#
######12例如玩家可以通过以下移动停留在 (5,5) 上
(2,2)→(5,2)→(5,5)。
玩家可以通过以下移动经过 (2,4)
(2,2)→(2,5)在过程中经过 (2,4)。
玩家无法经过或停留在 (3,4) 上。
示例 2
InputOutput 21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################215 思路
最开始我思路是bfs列举4个方向每个方向一直走到底第一次到这个点将这个点入队遇到冰块sum显然这样会出现很多重复的后来想到可以用一个二维数组标记到的每一个冰块为1这样就可以起到去重的作用,最后再统计总和
#includestdio.h
char a[210][210];
int n, m, book[210][210], ss[210][210];//book标记遇到的点ss标记遇到的冰块
struct nb{int x;int y;
}link[100010];//列队
int hard 1, tail 2, sum 0;
int main()
{int i, j;scanf(%d %d, n, m);for (i 0; i n; i)scanf(%s, a[i]);//起始点入队并标记link[1].x 1; link[1].y 1;book[1][1] 1; ss[1][1] 1;while (hard tail){for (i 1; i 4; i)//4个方向{int tx link[hard].x;int ty link[hard].y;if (i 1)while (a[tx][ty 1] .)//右{ty;ss[tx][ty] 1;}if (i 2)while (a[tx][ty - 1] .)//左{ty--;ss[tx][ty] 1;}if (i 3)while (a[tx 1][ty] .)//下{tx;ss[tx][ty] 1;}if (i 4)while (a[tx - 1][ty] .)//上{tx--;ss[tx][ty] 1;}if (book[tx][ty] 0)//如果第一次到这个点将这个点入队{book[tx][ty] 1;link[tail].x tx; link[tail].y ty;tail;}}hard;}for (i 1; i n - 1; i)//统计遇到的数量for (j 1; j m - 1; j)if (ss[i][j] 1)sum;printf(%d, sum);return 0;
}把补题写完发现题目本身不难除了最后一题考察了搜索前面的题目基本都是一些模拟题和思维题然而在测试的时候只写出来一题还得多练个人感觉自己做题太慢了测试的时候又太急了不认真读题目感觉这题自己不会写直接看下一题了其实慢下来都可以写出来的除了第4题写补题当时确实没想到看了题解还有就是一定要思路清晰再写写到一半发现思路不对又浪费时间
