CCPC2015部分题解

作者： | 来源：互联网 | 2023-10-11 10:53

【ASecreteMasterPlan】http:acm.uestc.edu.cn#problemshow1215【题意】水题，题意就是给了两个2*2的矩形

【A Secrete Master Plan】http://acm.uestc.edu.cn/#/problem/show/1215

【题意】水题&＃xff0c;题意就是给了两个2*2的矩形&＃xff0c;判断通过旋转是否这两个矩形是否相同。

【解题方法】水题。模拟一下&＃xff0c;

【AC 代码】

#include using namespace std; typedef long long LL;int main(){int T;scanf("%d",&T);int cas &＃61; 1;while(T--){printf("Case #%d: ",cas&＃43;&＃43;);int a[5],b[5];for(int i &＃61; 0;i <4;i&＃43;&＃43;)scanf("%d",&a[i]);swap(a[2],a[3]);for(int i &＃61; 0;i <4;i&＃43;&＃43;)scanf("%d",&b[i]);swap(b[2],b[3]);bool flag &＃61; false;for(int i &＃61; 0;i <4;i&＃43;&＃43;){if(b[i] &＃61;&＃61; a[0]){bool lead &＃61; false;for(int j &＃61; 0;j <4;j&＃43;&＃43;){if(b[(i&＃43;j)%4] !&＃61; a[j])lead &＃61; true;}if(!lead){flag &＃61; true;break;}}}if(flag) puts("POSSIBLE");else puts("IMPOSSIBLE");} }

【
C - The Battle of Chibi】
http://acm.uestc.edu.cn/#/problem/show/1217

【题意】在一个长度为n序列选出m个数&＃xff0c;使得这m个数单调递增。

【解题方法】很容易推出dp方程dp[i][j] &＃61; dp[i][j] &＃43; dp[k][j-1],a[k]

【AC 代码】

// //Created by just_sort 2016/9/22 19:47 //Copyright (c) 2016 just_sort.All Rights Reserved //#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int maxn &＃61; 1010; const int mod &＃61; 1e9&＃43;7; int a[maxn],b[maxn],dp[maxn][maxn]; int n,m; void add(int &x,int y){x &＃61; (x&＃43;y)%mod; } int getsum(int x,int y){int ans &＃61; 0;while(x>0){add(ans,dp[x][y]);x-&＃61;x&-x;}return ans; } void update(int x,int y,int d){while(x<&＃61;n){add(dp[x][y],d);x&＃43;&＃61;x&-x;} } int main() {int T,cas&＃61;1;scanf("%d",&T);while(T--){memset(dp,0,sizeof(dp));scanf("%d%d",&n,&m);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){scanf("%d",&a[i]);b[i]&＃61;a[i];}sort(b&＃43;1,b&＃43;n&＃43;1);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){a[i] &＃61; lower_bound(b&＃43;1,b&＃43;n&＃43;1,a[i])-b;}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){for(int j&＃61;1; j<&＃61;min(m,i&＃43;1); j&＃43;&＃43;){if(j&＃61;&＃61;1) update(a[i],1,1);else{int temp &＃61; getsum(a[i]-1,j-1);update(a[i],j,temp);}}}int ans &＃61; getsum(n,m);printf("Case #%d: %d\n",cas&＃43;&＃43;,ans);}return 0; }

【
D - Pick The Sticks】
http://acm.uestc.edu.cn/#/problem/show/1218

【题意】要从n根棍子里面选出若干根&＃xff0c;放到一个长度为L的水管里面(暂且这么叫了&＃xff09;&＃xff0c;要求一根水管的重心必须在水管里面。

【解题方法】如果不考虑在外面的水管的话&＃xff0c;我们很容易想到这是个裸地背包问题&＃xff0c;有了可以放在管子里&＃xff0c;我们也可以稍微改变一下得到变形的背包dp。dp[3][i],分别表示没有&＃xff0c;有一根&＃xff0c;有两根完全放在里面的就行啦。然后套路转移就可以了。

【Trick】特判1&＃xff0c;还有为了不出现小数&＃xff0c;造成错误&＃xff0c;在前面先*2。

【AC 代码】

// //Created by just_sort 2016/9/22 19:02 //Copyright (c) 2016 just_sort.All Rights Reserved //#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int maxn &＃61; 4010; LL dp[3][maxn]; int a[maxn]; LL b[maxn]; int n,L; int main() {int T,cas&＃61;1;scanf("%d",&T);while(T--){scanf("%d%d",&n,&L);LL ans &＃61; 0;L*&＃61;2;for(int i&＃61;0; i&＃61;a[i]/2; j--){dp[1][j] &＃61; max(dp[1][j],dp[0][j-a[i]/2]&＃43;b[i]);dp[2][j] &＃61; max(dp[2][j],dp[1][j-a[i]/2]&＃43;b[i]);if(j>&＃61;a[i]){dp[0][j] &＃61; max(dp[0][j],dp[0][j-a[i]]&＃43;b[i]);dp[1][j] &＃61; max(dp[1][j],dp[1][j-a[i]]&＃43;b[i]);dp[2][j] &＃61; max(dp[2][j],dp[2][j-a[i]]&＃43;b[i]);}}}ans &＃61; max(ans,dp[2][L]);printf("Case #%d: %lld\n",cas&＃43;&＃43;,ans);}return 0; }

【G - Ancient Go】http://acm.uestc.edu.cn/#/problem/show/1221

【题意】围棋&＃xff0c;判断X棋是否能走一步吃掉某些o棋。满足条件为X棋包含的棋子里面没有.

【解题方法】暴力每一个.棋&＃xff0c;把它变成X&＃xff0c;然后从4个方向深度搜索&＃xff0c;判断一下可行性。

【AC 代码】

// //Created by just_sort 2016/9/22 20:11 //Copyright (c) 2016 just_sort.All Rights Reserved //#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; int dir[4][2]&＃61;{{0,1},{0,-1},{1,0},{-1,0}}; char s[20][20]; bool vis[20][20]; bool ok; bool check(int x,int y) {if(x>&＃61;1&&x<&＃61;9&&y>&＃61;1&&y<&＃61;9) return true;return false; } void dfs(int x,int y) {if(s[x][y]&＃61;&＃61;&＃39;.&＃39;){ok&＃61;1;return ;}if(s[x][y]&＃61;&＃61;&＃39;x&＃39;) return ;for(int i&＃61;0; i<4; i&＃43;&＃43;){int tx &＃61; x&＃43;dir[i][0];int ty &＃61; y&＃43;dir[i][1];if(check(tx,ty) && !vis[tx][ty]){vis[tx][ty]&＃61;1;dfs(tx,ty);}} } int main() {int t,cas&＃61;1;scanf("%d",&t);while(t--){memset(vis,false,sizeof(vis));for(int i&＃61;1; i<&＃61;9; i&＃43;&＃43;){scanf("%s",s[i]&＃43;1);}bool flag&＃61;0;for(int i&＃61;1; i<&＃61;9; i&＃43;&＃43;){for(int j&＃61;1; j<&＃61;9; j&＃43;&＃43;){if(s[i][j]&＃61;&＃61;&＃39;.&＃39;){s[i][j]&＃61;&＃39;x&＃39;;for(int k&＃61;0; k<4; k&＃43;&＃43;){int tx &＃61; i&＃43;dir[k][0];int ty &＃61; j&＃43;dir[k][1];if(check(tx,ty)&&s[tx][ty]&＃61;&＃61;&＃39;o&＃39;){memset(vis,false,sizeof(vis));vis[tx][ty]&＃61;1;ok&＃61;0;dfs(tx,ty);if(ok&＃61;&＃61;0) flag&＃61;1;}}s[i][j]&＃61;&＃39;.&＃39;;}if(flag) break;}if(flag) break;}if(flag){printf("Case #%d: Can kill in one move!!!\n",cas&＃43;&＃43;);}else{printf("Case #%d: Can not kill in one move!!!\n",cas&＃43;&＃43;);}}return 0; }

【
H - Sudoku】
http://acm.uestc.edu.cn/#/problem/show/1222

【题意】就是求解一个4*4的数独问题。

【解题方法1】搜索

【解题方法2】套DLX模板&＃xff0c;我个智障。

【AC 代码】

// //Created by just_sort 2016/9/21 13:02 //Copyright (c) 2016 just_sort.All Rights Reserved //#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int maxnode &＃61; 100010*2; const int maxm &＃61; 1010; const int maxn &＃61; 1010*4; struct DLX{int n,m,size;int U[maxnode],D[maxnode],L[maxnode],R[maxnode],Row[maxnode],Col[maxnode];//U D R L用来记录某个标号的节点的上下左右节点的编号//Row Col用来记录某个标号的节点在矩阵中的行号和列号int H[maxn],S[maxm];//H是行头,S用来保存某一列中1的数量int ansd,ans[maxn];void init(int _n,int _m){n&＃61;_n,m&＃61;_m;//初始化列头for(int i&＃61;0; i<&＃61;m; i&＃43;&＃43;){S[i]&＃61;0;U[i]&＃61;D[i]&＃61;i;L[i]&＃61;i-1,R[i]&＃61;i&＃43;1;}R[m]&＃61;0,L[0]&＃61;m;size&＃61;m;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) H[i]&＃61;-1;}void Link(int r,int c){&＃43;&＃43;S[Col[&＃43;&＃43;size]&＃61;c];Row[size]&＃61;r;D[size]&＃61;D[c];U[D[c]]&＃61;size;U[size]&＃61;c;D[c]&＃61;size;if(H[r]<0){H[r]&＃61;L[size]&＃61;R[size]&＃61;size;}else{R[size]&＃61;R[H[r]];L[R[H[r]]]&＃61;size;L[size]&＃61;H[r];R[H[r]]&＃61;size;}}//对某一列进行删除&＃xff0c;并删除列中为1的行void remove(int c){L[R[c]]&＃61;L[c];R[L[c]]&＃61;R[c];for(int i&＃61;D[c]; i!&＃61;c; i&＃61;D[i])for(int j&＃61;R[i]; j!&＃61;i; j&＃61;R[j]){U[D[j]]&＃61;U[j];D[U[j]]&＃61;D[j];--S[Col[j]];}}//反着恢复状态void resume(int c){for(int i&＃61;U[c]; i!&＃61;c; i&＃61;U[i])for(int j&＃61;L[i]; j!&＃61;i; j&＃61;L[j]){U[D[j]]&＃61;D[U[j]]&＃61;j;&＃43;&＃43;S[Col[j]];}L[R[c]]&＃61;R[L[c]]&＃61;c;}//d为递归深度bool dance(int d){if(R[0]&＃61;&＃61;0){ansd&＃61;d;return true;}int c&＃61;R[0];//一个优化找到列中包含1最多的列因为这样有助于减少递归深度&＃xff08;很显然1多了删掉的行也多矩阵缩小得就快&＃xff09;for(int i&＃61;R[0]; i!&＃61;0; i&＃61;R[i]){if(S[i]}dlx; char s[100]; char temp[10]; int main() {int T,cas&＃61;1;scanf("%d",&T);while(T--){memset(s,0,sizeof(s));int cnt&＃61;0;for(int i&＃61;0; i<4; i&＃43;&＃43;){scanf("%s",temp);for(int j&＃61;0; j<(int)strlen(temp); j&＃43;&＃43;){s[cnt&＃43;&＃43;]&＃61;temp[j];}}s[cnt]&＃61;&＃39;\0&＃39;;dlx.init(16*9,16*4);for(int i&＃61;0; i<4; i&＃43;&＃43;){for(int j&＃61;0; j<4; j&＃43;&＃43;){int x &＃61; i,y &＃61; j,z &＃61; x/2*2&＃43;y/2;int w &＃61; i*4&＃43;j;if(s[w]&＃61;&＃61;&＃39;*&＃39;){for(int k&＃61;1; k<&＃61;4; k&＃43;&＃43;){dlx.Link(w*4&＃43;k,w&＃43;1);dlx.Link(w*4&＃43;k,16&＃43;x*4&＃43;k);dlx.Link(w*4&＃43;k,32&＃43;y*4&＃43;k);dlx.Link(w*4&＃43;k,48&＃43;z*4&＃43;k);}}else{int t&＃61;s[w]-&＃39;0&＃39;;dlx.Link(w*4&＃43;t,w&＃43;1);dlx.Link(w*4&＃43;t,16&＃43;x*4&＃43;t);dlx.Link(w*4&＃43;t,32&＃43;y*4&＃43;t);dlx.Link(w*4&＃43;t,48&＃43;z*4&＃43;t);}}}dlx.dance(0);for(int i&＃61;0; i}

【
L - Huatuo&＃39;s Medicine】
http://acm.uestc.edu.cn/#/problem/show/1226

【题意】水题&＃xff0c;输出2*n-1即可。

推荐阅读

main
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
ip
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
main
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
jsp
知识图谱——机器大脑中的知识库

本文介绍了知识图谱在机器大脑中的应用，以及搜索引擎在知识图谱方面的发展。以谷歌知识图谱为例，说明了知识图谱的智能化特点。通过搜索引擎用户可以获取更加智能化的答案，如搜索关键词"Marie Curie"，会得到居里夫人的详细信息以及与之相关的历史人物。知识图谱的出现引起了搜索引擎行业的变革，不仅美国的微软必应，中国的百度、搜狗等搜索引擎公司也纷纷推出了自己的知识图谱。 ... [详细]

蜡笔小新 2023-12-14 10:06:19
tree
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
ip
VB.NET在线急等问题解决方法，如何统计数据库字段下的数据并显示在文本框里？

本文介绍了一个在线急等问题解决方法，即如何统计数据库中某个字段下的所有数据，并将结果显示在文本框里。作者提到了自己是一个菜鸟，希望能够得到帮助。作者使用的是ACCESS数据库，并且给出了一个例子，希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句，得到的结果是650，但不知道如何得到560。希望能够得到解决方案。 ... [详细]

蜡笔小新 2023-12-13 15:15:30
main
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
main
Ubuntu安装常用软件详细步骤

目录1.GoogleChrome浏览器2.搜狗拼音输入法3.Pycharm4.Clion5.其他软件1.GoogleChrome浏览器通过直接下载安装GoogleChro ... [详细]

蜡笔小新 2023-12-12 21:26:41
main
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
main
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
bit
Which is more efficient: char str[] or char *str?

This article discusses the efficiency of using char str[] and char *str and whether there is any reason to prefer one over the other. It explains the difference between the two and provides an example to illustrate their usage. ... [详细]

蜡笔小新 2023-12-12 10:13:35
bit
微软头条实习生分享深度学习自学指南

本文介绍了一位微软头条实习生自学深度学习的经验分享，包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性，并提供了一些建议。 ... [详细]

蜡笔小新 2023-12-14 20:58:32
jsp
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
main
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
bit
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27

Tags | 热门标签

RankList | 热门文章