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即可。

推荐阅读

char
李逍遥寻找仙药的迷阵之旅

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

蜡笔小新 2023-12-12 13:59:33
char
关于数论的开发笔记

本文由编程笔记#小编整理，主要介绍了关于数论相关的知识，包括数论的算法和百度百科的链接。文章还介绍了欧几里得算法、辗转相除法、gcd、lcm和扩展欧几里得算法的使用方法。此外，文章还提到了数论在求解不定方程、模线性方程和乘法逆元方面的应用。摘要长度：184字。 ... [详细]

蜡笔小新 2023-12-11 17:31:53
io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

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

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

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

蜡笔小新 2023-12-14 11:49:51
char
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
char
二叉树层序创建问题的解决方法

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

蜡笔小新 2023-12-13 18:20:50
require
CF：3D City Model（小思维）问题解析和代码实现

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

蜡笔小新 2023-12-13 14:17:11
char
C++字符字符串处理及字符集编码方案

本文介绍了C++中字符字符串处理的问题，并详细解释了字符集编码方案，包括UNICODE、Windows apps采用的UTF-16编码、ASCII、SBCS和DBCS编码方案。同时说明了ANSI C标准和Windows中的字符/字符串数据类型实现。文章还提到了在编译时需要定义UNICODE宏以支持unicode编码，否则将使用windows code page编译。最后，给出了相关的头文件和数据类型定义。 ... [详细]

蜡笔小新 2023-12-13 04:59:58
char
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18
io
hdu 5439（找规律）的数列求和问题

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

蜡笔小新 2023-12-12 14:05:58
char
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
io
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
format
java boolean 大小_java boolean 大小

先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ... [详细]

蜡笔小新 2023-12-12 13:36:56
io
Android工程师面试准备及设计模式使用场景

本文介绍了Android工程师面试准备的经验，包括面试流程和重点准备内容。同时，还介绍了建造者模式的使用场景，以及在Android开发中的具体应用。 ... [详细]

蜡笔小新 2023-12-11 18:25:26
object
微软的STL容器类实现是否线程安全？

本文讨论了微软的STL容器类是否线程安全。根据MSDN的回答，STL容器类包括vector、deque、list、queue、stack、priority_queue、valarray、map、hash_map、multimap、hash_multimap、set、hash_set、multiset、hash_multiset、basic_string和bitset。对于单个对象来说，多个线程同时读取是安全的。但如果一个线程正在写入一个对象，那么所有的读写操作都需要进行同步。 ... [详细]

蜡笔小新 2023-12-11 11:53:23

Tags | 热门标签

RankList | 热门文章