wordpress 网站为什么打不开,杭州抖音代运营,建一个私人彩票网站,贵州网站开发哪家好目录 1. 第一题2. 第二题3. 第三题 ⏰ 时间#xff1a;2024/08/17 #x1f504; 输入输出#xff1a;ACM格式 ⏳ 时长#xff1a;2h 本试卷还有选择题部分#xff0c;但这部分比较简单就不再展示。
1. 第一题
村子里有一些桩子#xff0c;从左到右高度依次为 1 , 1 2… 目录 1. 第一题2. 第二题3. 第三题 ⏰ 时间2024/08/17 输入输出ACM格式 ⏳ 时长2h 本试卷还有选择题部分但这部分比较简单就不再展示。
1. 第一题
村子里有一些桩子从左到右高度依次为 1 , 1 2 , 1 2 3 , . . . 1,12,123,... 1,12,123,...每两颗桩子之间的间隔为 1 1 1。现在下了一场大雪但是不知道雪下了多厚现在给你两个数字这是雪后某相邻两个桩子在雪面上的高度请你通过这两个数字计算雪的厚度。
输入描述
在一行中输入两个正整数 a , b a, b a,b 1 ≤ a b ≤ 5 ⋅ 1 0 5 1\leq ab\leq5\cdot10^5 1≤ab≤5⋅105。
输出描述
在一行中输出一个整数代表雪的厚度。我们可以证明答案一定存在。
题解
只需注意到 a k − a k − 1 k a_k-a_{k-1}k ak−ak−1k于是可以用 b − a b-a b−a 定位到右边柱子的下标计算它的高度即可。
#include bits/stdc.husing namespace std;
using i64 long long;int main() {i64 a ,b;cin a b;i64 k b - a;i64 old_h k * (k 1) / 2;cout old_h - b endl;return 0;
}2. 第二题
牛牛有一种锯齿状的积木这种积木比较长但是每个单位长度的高度是相等的高度为 1 1 1 或者 2 2 2。 现在牛牛拿出了两块长度分别为 n n n 和 m m m 的积木她现在想把这两块积木拼接在一起即使中间有空隙也没有关系。但是拼接后的积木的高度要不超过 3 3 3请你帮助牛牛计算在满足这个前提下拼接后的积木的长度最短可以是多少。 例如有两块形状如下的积木: 输入描述
第一行给出两个正整数 n , m n,m n,m代表第一块和第二块积木的长度。 第二行给出 n n n 个数字代表第一块积木每个单位的高度。 第三行给出 m m m 个数字代表第二块积木每个单位的高度 1 ≤ n , m ≤ 1000 1\leq n,m \leq 1000 1≤n,m≤1000。
输出描述
在一行中输出一个正整数代表拼接后积木的最短长度
题解
本题直接模拟即可。
说白了就是给定 a a a 和 b b b 两个数组初始时先让 a a a 和 b b b 的左端对齐。
先让 a a a 在 b b b 上向右滑动计算两者重叠部分的按位元素和只要重叠部分中有一个位置出现了 3 3 3 的情况说明当前拼接是无效的继续右移。我们自然是希望 a a a 右移的距离尽可能地小。再让 b b b 在 a a a 上向右滑动同样是找到正确的拼接位置并使得 b b b 右移的距离尽可能小。还要考虑一种特殊情况就是无法上下拼接此时需要将 a a a 和 b b b 直接横向连接长度为 m n mn mn。
#include bits/stdc.husing namespace std;int min_len(const string a, const string b) {int n a.length(), m b.length();// a在b上滑动for (int i 0; i m; i) {bool valid true;for (int j i; j i n j m; j) {if (a[j - i] - 0 b[j] - 0 3) {valid false;break;}}if (valid)return max(m, i n);}return m n;
}int main() {int n, m;cin n m;string a, b;cin a b;cout min(min_len(a, b), min_len(b, a)) endl;return 0;
}3. 第三题
牛牛也是要回家过年的呢。 牛牛所在的国家有 n n n 座城市 m m m 条有向道路第 i i i 条道路由城市 u i u_i ui 通往城市 v i v_i vi通行费为 w i w_i wi。 作为一头豪气的牛希望他回家的花费是一个特殊的数字(例如666元)。具体的说牛牛希望从城市 1 1 1 移动到城市 n n n并恰好花费 a a a 元。 请你告诉牛牛他有多少种回家的方案?
输入描述
第一行三个整数 n , m , a ( 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 , 1 ≤ a ≤ 1000 ) n,m,a\,(1\leq n\leq 100,1\leq m\leq 1000,1\leq a\leq1000) n,m,a(1≤n≤100,1≤m≤1000,1≤a≤1000)含义如题面所示。 接下来 m m m 行第 i i i 行三个整数 u i , v i , w i ( 1 ≤ u i , v i ≤ n , 1 ≤ w i ≤ a ) u_i,v_i,w_i\,(1\leq u_i,v_i\leq n,1\leq w_i\leq a) ui,vi,wi(1≤ui,vi≤n,1≤wi≤a)描述了一条道路。
输出描述
如果牛牛回家的方案数大于等于 20220201 20220201 20220201 种请你在第一行输出 All roads lead to Home!然后在第二行输出回家的方案数对 20220201 20220201 20220201 取模的结果。 否则只需要输出一行一个整数表示牛牛回家的方案数。
题解
本题使用动态规划求解。
设 d p [ i ] [ j ] dp[i][j] dp[i][j] 为从城市 1 1 1 到城市 i i i花费恰好为 j j j 的方案数。由于从 1 1 1 到 1 1 1 花费为 0 0 0也算是一种方案因此 d p [ 1 ] [ 0 ] 1 dp[1][0]1 dp[1][0]1其他地方为 0 0 0。
假设 u → w v u\overset{w}{\to} v u→wv且在城市 u u u 的时候已经花费了 j j j那么有如下的转移方程 d p [ v ] [ j w ] d p [ u ] [ j ] d p [ v ] [ j w ] dp[v][j w]dp[u][j]dp[v][j w] dp[v][jw]dp[u][j]dp[v][jw]
注意在计算 v v v 的时候我们必须要保证 u u u 已经计算完毕因此要按照拓扑序进行计算。
#include bits/stdc.husing namespace std;const int MOD 20220201;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, a;cin n m a;vectorvectorpairint, int graph(n 1);vectorint in(n 1, 0);for (int i 0; i m; i) {int u, v, w;cin u v w;graph[u].emplace_back(v, w);in[v];}vectorvectorint dp(n 1, vectorint(a 1, 0));vectorbool st(n 1, 0);dp[1][0] 1;queueint q;for (int i 1; i n; i) {if (!in[i]) q.push(i);}while (!q.empty()) {auto u q.front();q.pop();for (auto [v, w]: graph[u]) {if (!--in[v]) q.push(v);for (int j 0; j w a; j) {if (dp[v][j w] dp[u][j] MOD || st[u]) {st[v] true;}dp[v][j w] (dp[v][j w] dp[u][j]) % MOD;}}}if (st[n]) cout All roads lead to Home! endl;cout dp[n][a] endl;return 0;
}
文章转载自： http://www.morning.yxlpj.cn.gov.cn.yxlpj.cn http://www.morning.wclxm.cn.gov.cn.wclxm.cn http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.fwblh.cn.gov.cn.fwblh.cn http://www.morning.wlxfj.cn.gov.cn.wlxfj.cn http://www.morning.qhtlq.cn.gov.cn.qhtlq.cn http://www.morning.nslwj.cn.gov.cn.nslwj.cn http://www.morning.lmxzw.cn.gov.cn.lmxzw.cn http://www.morning.zlnyk.cn.gov.cn.zlnyk.cn http://www.morning.uqrphxm.cn.gov.cn.uqrphxm.cn http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.qdxtj.cn.gov.cn.qdxtj.cn http://www.morning.fyxr.cn.gov.cn.fyxr.cn http://www.morning.pxlsh.cn.gov.cn.pxlsh.cn http://www.morning.qxwwg.cn.gov.cn.qxwwg.cn http://www.morning.bqdgr.cn.gov.cn.bqdgr.cn http://www.morning.qgtbx.cn.gov.cn.qgtbx.cn http://www.morning.wpspf.cn.gov.cn.wpspf.cn http://www.morning.pmptm.cn.gov.cn.pmptm.cn http://www.morning.pinngee.com.gov.cn.pinngee.com http://www.morning.dighk.com.gov.cn.dighk.com http://www.morning.qctsd.cn.gov.cn.qctsd.cn http://www.morning.xrwtk.cn.gov.cn.xrwtk.cn http://www.morning.glbnc.cn.gov.cn.glbnc.cn http://www.morning.gxfzrb.com.gov.cn.gxfzrb.com http://www.morning.ygrdb.cn.gov.cn.ygrdb.cn http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.qbrdg.cn.gov.cn.qbrdg.cn http://www.morning.yhyqg.cn.gov.cn.yhyqg.cn http://www.morning.bqpg.cn.gov.cn.bqpg.cn http://www.morning.nhlyl.cn.gov.cn.nhlyl.cn http://www.morning.nbiotank.com.gov.cn.nbiotank.com http://www.morning.xpzrx.cn.gov.cn.xpzrx.cn http://www.morning.xnqwk.cn.gov.cn.xnqwk.cn http://www.morning.hfxks.cn.gov.cn.hfxks.cn http://www.morning.kyfrl.cn.gov.cn.kyfrl.cn http://www.morning.ltqtp.cn.gov.cn.ltqtp.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.kxrld.cn.gov.cn.kxrld.cn http://www.morning.ggjlm.cn.gov.cn.ggjlm.cn http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.grzpc.cn.gov.cn.grzpc.cn http://www.morning.hrtwt.cn.gov.cn.hrtwt.cn http://www.morning.jwtjf.cn.gov.cn.jwtjf.cn http://www.morning.bhwll.cn.gov.cn.bhwll.cn http://www.morning.wnnts.cn.gov.cn.wnnts.cn http://www.morning.rhlhk.cn.gov.cn.rhlhk.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.rfycj.cn.gov.cn.rfycj.cn http://www.morning.cptzd.cn.gov.cn.cptzd.cn http://www.morning.pxmyw.cn.gov.cn.pxmyw.cn http://www.morning.sxwfx.cn.gov.cn.sxwfx.cn http://www.morning.bhpsz.cn.gov.cn.bhpsz.cn http://www.morning.hjjfp.cn.gov.cn.hjjfp.cn http://www.morning.ddqdl.cn.gov.cn.ddqdl.cn http://www.morning.wfmqc.cn.gov.cn.wfmqc.cn http://www.morning.llxns.cn.gov.cn.llxns.cn http://www.morning.rcrfz.cn.gov.cn.rcrfz.cn http://www.morning.lhzqn.cn.gov.cn.lhzqn.cn http://www.morning.sfdky.cn.gov.cn.sfdky.cn http://www.morning.heleyo.com.gov.cn.heleyo.com http://www.morning.smj79.cn.gov.cn.smj79.cn http://www.morning.zbkdm.cn.gov.cn.zbkdm.cn http://www.morning.prjty.cn.gov.cn.prjty.cn http://www.morning.mhnd.cn.gov.cn.mhnd.cn http://www.morning.szoptic.com.gov.cn.szoptic.com http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.yfffg.cn.gov.cn.yfffg.cn http://www.morning.jcrlx.cn.gov.cn.jcrlx.cn http://www.morning.zlff.cn.gov.cn.zlff.cn http://www.morning.pyxwn.cn.gov.cn.pyxwn.cn http://www.morning.nqwz.cn.gov.cn.nqwz.cn http://www.morning.dnzyx.cn.gov.cn.dnzyx.cn http://www.morning.dnmzl.cn.gov.cn.dnmzl.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.nfnxp.cn.gov.cn.nfnxp.cn http://www.morning.dtnjr.cn.gov.cn.dtnjr.cn http://www.morning.qsbcg.cn.gov.cn.qsbcg.cn http://www.morning.cylbs.cn.gov.cn.cylbs.cn http://www.morning.gywxq.cn.gov.cn.gywxq.cn
