Xunyoyo

[USACO09MAR] Cow Frisbee Team S题目描述老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。 每只奶牛的能力为整数，第 $i$ 头奶牛的能力为$R_i$ 。飞盘队的队员数量不能少于 $1$、大于$N$。一支队伍的总能力就是所有队员能力的总和。 约翰比较迷信，他的幸运数字是 $F$ ，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他 算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。 输入格式第一行：两个用空格分开的整数：$N$ 和 $F$。 第二行到 $N+1$ 行：第 $i+1$ 行有一个整数$R_i$ ，表示第 $i$ 头奶牛的能力。 输出格式第一行：单个整数，表示方案数对 $10^8$ 取模的值。 样例 #1样例输入 #1123454 5 1 2 8 2 样例输出 #113 提示数据范围与约定 对于 $100\%$ 的数据，$1 \le N \le 2000$，$1 \le F \le 1000$ ，$1 \le R_i \le 10^5$ 。 题解题目解析我做这道 ...

魔术棋子题目描述在一个M*N的魔术棋盘中，每个格子中均有一个整数，当棋子走进这个格子中，则此棋子上的数会被乘以此格子中的数。一个棋子从左上角走到右下角，只能向右或向下行动，请问此棋子走到右下角后，模（mod）K可以为几？ 如以下2*3棋盘： 123 4 45 6 6 棋子初始数为1，开始从左上角进入棋盘，走到右下角，上图中，最后棋子上的数可能为288,432或540。所以当K = 5时，可求得最后的结果为：0,2,3。 输入格式第一行为三个数，分别为M,N,K (1 ≤ M,N,K ≤ 100)以下M行，每行N个数，分别为此方阵中的数。 输出格式第一行为可能的结果个数 第二行为所有可能的结果(按升序输出) 样例 #1样例输入 #11232 3 53 4 45 6 6 样例输出 #11230 2 3 题解题目解析奇怪的背包题, 说实话这也不能算是背包题, 实际上算是一个dp题. 这道题需要对每一格都要模 $k$ , 所以每一格可以凑成的值就有 $k$ 种可能, 既然需要状态转移, 那么就需要把每一格的 $k$ 的可能都要存下来, 于是就需要开三维数组. 接着考虑如 ...

投资的最大效益题目背景约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。 题目描述例如：有如下两种不同的债券： 投资额 $$4000$，年利息 $$400$； 投资额 $$3000$，年利息 $$250$。 初始时，有 $$10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $$800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $$900$ 的利息，两年后，可获得 $$1800$ 的利息；而所有的资产达到 $$11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $$1050$；第三年后，总资产达到 $$12850$，可以购买三份债券 1，年利息可达到 $$1200$，第四年后，总资产可达到 $$14050$。 现给定若干种债券、最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。 输入格式第 ...

找啊找啊找GF题目背景“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。” “诶，别再见啊…” 七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。 但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。 题目描述sqybi 现在看中了 $n$ 个 MM，我们不妨把她们编号 $1$ 到 $n$。请 MM 吃饭是要花钱的，我们假设请 $i$ 号 MM 吃饭要花 $rmb[i]$ 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 $i$ 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 $rp[i]$ 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞 ...

搭配购买题目描述明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 $n$ 朵云，云朵已经被老板编号为 $1,2,3,…,n$，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。 输入格式第一行输入三个整数，$n,m,w$，表示有 $n$ 朵云，$m$ 个搭配和你现有的钱的数目。 第二行至 $n+1$ 行，每行有两个整数， $c_i,d_i$，表示第 $i$ 朵云的价钱和价值。 第 $n+2$ 至 $n+1+m$ 行 ，每行有两个整数 $u_i,v_i$。表示买第 $u_i$ 朵云就必须买第 $v_i$ 朵云,同理，如果买第 $v_i$ 朵就必须买第 $u_i$ 朵。 输出格式一行，表示可以获得的最大价值。 样例 #1样例输入 #11234567895 3 103 103 103 1 ...

精卫填海题目描述本题为改编题。 发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》 精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？ 事实上，东海未填平的区域还需要至少体积为 $v$ 的木石才可以填平，而西山上的木石还剩下 $n$ 块，每块的体积和把它衔到东海需要的体力分别为 $k$ 和 $m$。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 $c$。 输入格式输入文件的第一行是三个整数：$v,n,c$。 从第二行到第 $n+1$ 行分别为每块木石的体积和把它衔到东海需要的体力。 输出格式输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 Impossible（不带引号）。 样例 #1样例输入 #1123100 2 1050 550 5 样例输出 #110 样例 #2样例输入 #212310 2 150 510 2 样例输出 #21Impossible ...

[HAOI2012] 音量调节题目描述一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。 音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。 吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。 输入格式第一行依次为三个整数 $n$，$beginLevel$ 和 $maxLevel$。 第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$。 输出格式输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $maxLevel$，输出 -1。 样例 #1样例输入 #1123 ...

Tracking Segments题面翻译有一个长度为 $n$，初始全为 $0$ 的序列。我们定义一个区间是美丽的，当且仅当区间内 $1$ 的个数严格大于 $0$ 的个数。现给定 $m$ 个区间和 $q$ 次修改，每次修改可以将该位置上的 $0$ 变成 $1$。对于每组数据，求出最少第几次修改后，给定的 $m$ 个区间中至少一个是美丽的。数据保证每次修改各不相同。 题目描述You are given an array $ a $ consisting of $ n $ zeros. You are also given a set of $ m $ not necessarily different segments. Each segment is defined by two numbers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) and represents a subarray $ a_{l_i}, a_{l_i+1}, \dots, a_{r_i} $ of the array $ a $ . Let’s cal ...

Particles题面翻译给定一个长度为 $n$ 的数列，你需要删若干个数，使得数列只剩下一个数。 若删的数为 $a_i$，那么 $a_{i-1}$ 和 $a_{i+1}$ 将会合并（当删的数为当前第一或最后一个数时，没有数会合并）。 求最后一个数的最大值。 题目描述You have discovered $ n $ mysterious particles on a line with integer charges of $ c_1,\dots,c_n $ . You have a device that allows you to perform the following operation: Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $ x $ and $ y $ directly to the left an ...

补题 We Were Both Children题目描述Mihai and Slavic were looking at a group of $ n $ frogs, numbered from $ 1 $ to $ n $ , all initially located at point $ 0 $ . Frog $ i $ has a hop length of $ a_i $ . Each second, frog $ i $ hops $ a_i $ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate. However, the children can’t go far away from their home so they can only p ...