网页设计网站怎么做特效WordPress仿wp大学模板

网页设计网站怎么做特效,WordPress仿wp大学模板,荣成做网站的公司,python网站开发用什么软件题目描述 春天到了#xff0c;我们的朋友佩皮托#xff08;Pepito\texttt{Pepito}Pepito#xff09; 坠入了爱河。但他不确定她是否也爱他#xff0c;于是他决定询问雏菊。他摘下一朵雏菊#xff0c;交替说着“她爱我”和“她不爱我”#xff0c;每说一句话就摘下一片花…题目描述春天到了我们的朋友佩皮托Pepito \texttt{Pepito}Pepito 坠入了爱河。但他不确定她是否也爱他于是他决定询问雏菊。他摘下一朵雏菊交替说着“她爱我”和“她不爱我”每说一句话就摘下一片花瓣。最后一片花瓣对应的那句话会告诉他他的爱是否得到了回应。我们想帮助佩皮托总是得到“她爱我”的答案。因此我们将通过摘掉花瓣数为偶数的雏菊上的一片花瓣确保所有雏菊的花瓣数都是奇数。我们有一片矩形的雏菊田宽度为W WW高度为H HH。田地的每个位置( w , h ) (w, h)(w,h)都有一朵雏菊其中w 1 , 2 , … , W w 1, 2, \ldots, Ww1,2,…,Wh 1 , 2 , … , H h 1, 2, \ldots, Hh1,2,…,H。我们已经耐心地数了每朵雏菊的花瓣数P [ w , h ] P[w, h]P[w,h]。从田地的左上角即位置( 1 , 1 ) (1, 1)(1,1)开始你必须经过所有花瓣数为偶数的位置。如果你的当前位置是( w , h ) (w, h)(w,h)你只能做三种移动向下( h 1 ) (h 1)(h1)、向左( w − 1 ) (w - 1)(w−1)和向右( w 1 ) (w 1)(w1)。你的任务是计算经过所有花瓣数为偶数的位置所需的最少移动次数。输入格式第一行包含一个整数表示测试用例的数量。对于每个测试用例第一行包含两个整数W WW和H HH用空格分隔。接下来是H HH行每行包含W WW个数字1 11到9 99表示对应雏菊的花瓣数。输出格式对于每个测试用例输出一个整数表示最少移动次数。样例输入5 5 3 54578 36329 75241 9 1 759456785 2 2 22 22 6 6 777777 772777 777777 777727 727777 777777 7 7 1811181 1118811 1881111 8111111 1188181 1881181 1111111样例输出11 7 3 11 24题目分析问题本质这道题可以抽象为一个网格遍历问题我们有一个H × W H \times WH×W的网格每个格子有一个数字1 11到9 99。我们需要从左上角( 1 , 1 ) (1, 1)(1,1)出发。必须访问所有数字为偶数的格子称为“目标点”。移动方式只能向下、向左或向右不能向上。需要计算最少移动步数。关键约束不能向上移动这意味着我们只能从上往下逐行遍历一旦离开某一行就无法返回。必须访问所有偶数格子这是我们的核心目标。起点固定从( 1 , 1 ) (1, 1)(1,1)开始。观察与简化由于不能向上移动我们的路径必然是单调向下的。这意味着我们只能按行顺序访问第1 11行 → 第2 22行 → … → 第H HH行。对于每一行如果有偶数格子需要访问我们必须在该行内水平移动来访问所有这些格子。对于没有偶数格子的行我们只需从上一行的某个位置垂直向下移动一行不需要水平移动。进一步分析对于一行中的多个偶数格子访问它们的最优策略是从该行的某个进入点开始。访问该行所有偶数格子。离开该行准备进入下一行。在一行内访问所有目标点的最小水平移动距离取决于进入点的列位置该行最左目标点的列位置该行最右目标点的列位置实际上对于一行有多个目标点的情况访问所有点的最小水平移动方案只有两种先到最左目标点然后一路向右访问到最右目标点。先到最右目标点然后一路向左访问到最左目标点。状态设计由于我们只关心有目标点的行需要访问的行可以忽略没有目标点的行只需在行间转移时计算垂直移动距离。定义状态d p [ i ] [ 0 ] dp[i][0]dp[i][0]访问完第i ii个目标行后停在该行最左目标点的最小步数。d p [ i ] [ 1 ] dp[i][1]dp[i][1]访问完第i ii个目标行后停在该行最右目标点的最小步数。状态转移设第i − 1 i-1i−1个目标行在第r i − 1 r_{i-1}ri−1​行最左目标点在l i − 1 l_{i-1}li−1​列最右目标点在r i − 1 r_{i-1}ri−1​列。设第i ii个目标行在第r i r_iri​行最左目标点在l i l_ili​列最右目标点在r i r_iri​列。设两行之间的行距为g a p r i − r i − 1 gap r_i - r_{i-1}gapri​−ri−1​。从d p [ i − 1 ] [ 0 ] dp[i-1][0]dp[i−1][0]停在l i − 1 l_{i-1}li−1​转移到d p [ i ] [ 0 ] dp[i][0]dp[i][0]停在l i l_ili​方案 A先到l i l_ili​然后向右访问到r i r_iri​再返回l i l_ili​。步数 d p [ i − 1 ] [ 0 ] g a p ∣ l i − 1 − l i ∣ ( r i − l i ) × 2 dp[i-1][0] gap |l_{i-1} - l_i| (r_i - l_i) \times 2dp[i−1][0]gap∣li−1​−li​∣(ri​−li​)×2方案 B先到r i r_iri​然后向左访问到l i l_ili​自然停在l i l_ili​。步数 d p [ i − 1 ] [ 0 ] g a p ∣ l i − 1 − r i ∣ ( r i − l i ) dp[i-1][0] gap |l_{i-1} - r_i| (r_i - l_i)dp[i−1][0]gap∣li−1​−ri​∣(ri​−li​)从d p [ i − 1 ] [ 0 ] dp[i-1][0]dp[i−1][0]转移到d p [ i ] [ 1 ] dp[i][1]dp[i][1]停在r i r_iri​方案 C先到l i l_ili​然后向右访问到r i r_iri​自然停在r i r_iri​。步数 d p [ i − 1 ] [ 0 ] g a p ∣ l i − 1 − l i ∣ ( r i − l i ) dp[i-1][0] gap |l_{i-1} - l_i| (r_i - l_i)dp[i−1][0]gap∣li−1​−li​∣(ri​−li​)方案 D先到r i r_iri​然后向左访问到l i l_ili​再返回r i r_iri​。步数 d p [ i − 1 ] [ 0 ] g a p ∣ l i − 1 − r i ∣ ( r i − l i ) × 2 dp[i-1][0] gap |l_{i-1} - r_i| (r_i - l_i) \times 2dp[i−1][0]gap∣li−1​−ri​∣(ri​−li​)×2从d p [ i − 1 ] [ 1 ] dp[i-1][1]dp[i−1][1]的转移类似只需将l i − 1 l_{i-1}li−1​替换为r i − 1 r_{i-1}ri−1​。初始化对于第一个目标行假设在第f i r s t R o w firstRowfirstRow行从起点( 1 , 1 ) (1, 1)(1,1)出发需要先垂直向下移动f i r s t R o w − 1 firstRow - 1firstRow−1行。然后按照上述两种方案访问该行的所有目标点。最终答案访问完所有目标行后答案为min ⁡ ( d p [ m − 1 ] [ 0 ] , d p [ m − 1 ] [ 1 ] ) \min(dp[m-1][0], dp[m-1][1])min(dp[m−1][0],dp[m−1][1])其中m mm是目标行的数量。如果整个网格没有目标点答案为0 00。算法步骤读取输入找出所有有偶数格子的行及其列位置。如果没有目标行输出0 00。初始化第一个目标行的d p dpdp值。对于每个后续目标行计算从上一目标行转移过来的最小步数。输出最终的最小步数。时间复杂度预处理O ( H × W ) O(H \times W)O(H×W)动态规划O ( m ) O(m)O(m)其中m mm是目标行的数量m ≤ H m \leq Hm≤H总时间复杂度O ( H × W ) O(H \times W)O(H×W)在题目限制下完全可行。代码实现// An Odd Love// UVa ID: 11617// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.010s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intt;cint;while(t--){intW,H;cinWH;vectorstringgrid(H);for(inti0;iH;i)cingrid[i];// 存储有目标的行及其目标列vectorpairint,vectorinttargetRows;for(inth0;hH;h){vectorintcols;for(intw0;wW;w){if((grid[h][w]-0)%20)cols.push_back(w);}if(!cols.empty()){targetRows.push_back({h,cols});}}// 如果没有目标行答案就是0从起点开始不用移动if(targetRows.empty()){cout0endl;continue;}constintINF1e9;intmtargetRows.size();vectorvectorintdp(m,vectorint(2,INF));// 初始化第一个目标行intfirstRowtargetRows[0].first;vectorintfirstColstargetRows[0].second;intfirstLeft*min_element(firstCols.begin(),firstCols.end());intfirstRight*max_element(firstCols.begin(),firstCols.end());intfirstRowDistfirstRight-firstLeft;// 从起点(0,0)到第一个目标行// 需要先向下移动firstRow行intdownStepsfirstRow;// 从第0行到第firstRow行// 停在左端点dp[0][0]downStepsfirstLeftfirstRowDistfirstRowDist;// 下移到最左到最右回最左dp[0][0]min(dp[0][0],downStepsfirstRightfirstRowDist);// 下移到最右到最左// 停在右端点dp[0][1]downStepsfirstLeftfirstRowDist;// 下移到最左到最右dp[0][1]min(dp[0][1],downStepsfirstRightfirstRowDistfirstRowDist);// 下移到最右到最左回最右// 处理后续目标行for(inti1;im;i){intprevRowtargetRows[i-1].first;vectorintprevColstargetRows[i-1].second;intprevLeft*min_element(prevCols.begin(),prevCols.end());intprevRight*max_element(prevCols.begin(),prevCols.end());intcurrRowtargetRows[i].first;vectorintcurrColstargetRows[i].second;intcurrLeft*min_element(currCols.begin(),currCols.end());intcurrRight*max_element(currCols.begin(),currCols.end());intcurrRowDistcurrRight-currLeft;introwGapcurrRow-prevRow;// 行间距离for(intprevSide0;prevSide2;prevSide){if(dp[i-1][prevSide]INF)continue;intprevCol(prevSide0)?prevLeft:prevRight;// 从上一目标行到当前目标行// 中间需要下移rowGap行// 我们可以选择在中间行的任意列移动// 对于停在左端点// 方案1先到当前行最左访问到最右然后回到最左intcost1dp[i-1][prevSide]rowGapabs(prevCol-currLeft)currRowDistcurrRowDist;// 方案2先到当前行最右访问到最左停在最左intcost2dp[i-1][prevSide]rowGapabs(prevCol-currRight)currRowDist;dp[i][0]min(dp[i][0],min(cost1,cost2));// 对于停在右端点// 方案3先到当前行最左访问到最右停在最右intcost3dp[i-1][prevSide]rowGapabs(prevCol-currLeft)currRowDist;// 方案4先到当前行最右访问到最左然后回到最右intcost4dp[i-1][prevSide]rowGapabs(prevCol-currRight)currRowDistcurrRowDist;dp[i][1]min(dp[i][1],min(cost3,cost4));}}intansmin(dp[m-1][0],dp[m-1][1]);coutansendl;}return0;}