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

推荐阅读

io
Linux 环境下多线程编程实战案例分析

在 Linux 环境下，多线程编程是实现高效并发处理的重要技术。本文通过具体的实战案例，详细分析了多线程编程的关键技术和常见问题。文章首先介绍了多线程的基本概念和创建方法，然后通过实例代码展示了如何使用 pthreads 库进行线程同步和通信。此外，还探讨了多线程程序中的性能优化技巧和调试方法，为开发者提供了宝贵的实践经验。 ... [详细]

蜡笔小新 2024-11-08 13:02:21
io
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
io
寒假作业解析：第三周 2月12日第7题

尽快完成之前的练习任务！每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析：通过对比不同路线的等待时间，可以找到最优解。此问题可以通过动态规划或贪心算法来解决，具体取决于路线的复杂性和约束条件。 ... [详细]

蜡笔小新 2024-11-06 14:33:36
io
使用JavaScript生成Java兼容的UUID代码实现与优化技巧

本文介绍了UUID（通用唯一标识符）的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符，广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID，并提供了多种优化方法，以提高生成效率和兼容性。 ... [详细]

蜡笔小新 2024-11-05 18:19:54
char
探究 Lua 在 .NET 生态系统中的应用与挑战：鲜为人知的研究领域

在当前的软件开发领域，Lua 作为一种轻量级脚本语言，在 .NET 生态系统中的应用逐渐受到关注。本文探讨了 Lua 在 .NET 环境下的集成方法及其面临的挑战，包括性能优化、互操作性和生态支持等方面。尽管存在一定的技术障碍，但通过不断的学习和实践，开发者能够克服这些困难，拓展 Lua 在 .NET 中的应用场景。 ... [详细]

蜡笔小新 2024-11-08 14:47:43
io
手指触控|Android电容屏幕驱动调试指南

手指触控|Android电容屏幕驱动调试指南 ... [详细]

蜡笔小新 2024-11-07 01:42:20
io
利用GLSL在iOS上实现YV12到RGB的转换，并附带展示结果图像

本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式，并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例，读者可以轻松掌握这一过程，适用于需要进行视频处理的应用开发。 ... [详细]

蜡笔小新 2024-11-06 19:18:22
char
如何构建和优化微信公众平台账号

本文探讨了如何有效地构建和优化微信公众平台账号，涵盖了用户信息管理、内容创作与发布、互动策略及数据分析等方面。通过合理设置用户信息字段，如用户名、昵称、密码、真实姓名和性别等，确保账号的安全性和用户体验。同时，文章还介绍了如何利用微信公众平台的各项功能，提升用户参与度和品牌影响力。 ... [详细]

蜡笔小新 2024-11-06 18:47:33
io
2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南

2012年9月12日，优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分，有一道题目涉及中国人的血型分布情况，具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中，至少有一人为B型血的概率不低于90%，则需要选取的最少人数是多少？该问题不仅考察了概率统计的基本知识，还要求考生具备一定的逻辑推理能力。 ... [详细]

蜡笔小新 2024-11-06 15:25:14
io
蓝桥杯算法实战：节点选取策略优化分析

本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果，提出了基于贪心算法和动态规划的综合优化方案，旨在提高算法效率和准确性。实验结果表明，该优化策略在处理大规模数据集时表现出色，显著提升了算法性能。 ... [详细]

蜡笔小新 2024-11-06 12:51:58
char
常见字符串哈希函数的综合分析与应用

本文对常见的字符串哈希函数进行了全面分析，涵盖了BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash等多种算法。这些哈希函数在不同的应用场景中表现出各异的性能特点，通过对比其算法原理、计算效率和碰撞概率，为实际应用提供了有价值的参考。 ... [详细]

蜡笔小新 2024-11-06 11:58:06
io
设计实战 | 10个Kotlin项目深度解析：首页模块开发详解

设计实战 | 10个Kotlin项目深度解析：首页模块开发详解 ... [详细]

蜡笔小新 2024-11-05 14:40:47
io
2016-2017 ACM-ICPC东北欧区域赛（NEERC 16）Gym101190E：离线查询与排序优化策略

题目链接：http://codeforces.com/gym/101190/attachments题意：在一个共享三轮车站点，某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说，需要设计一种算法，在满足所有用户需求的同时，最小化总等待时间和资源浪费。通过合理的数据结构和算法优化，可以显著提高系统的整体性能和用户体验。 ... [详细]

蜡笔小新 2024-11-05 11:36:52
io
深度优先搜索解题报告：NOJ1102 黑白图像问题分析与实现

针对NOJ1102黑白图像问题，本文采用深度优先搜索算法进行详细分析与实现。该问题要求在给定的时间限制（普通Java为1000-3000毫秒）和内存限制（65536KByte）内，处理一个n×n的黑白图像。通过对图像的逐像素遍历，利用深度优先搜索算法有效地识别并标记相连的黑色区域，从而实现图像的高效处理。实验结果显示，该方法在多种测试用例中均能稳定达到预期效果，具有较高的准确性和效率。 ... [详细]

蜡笔小新 2024-11-04 16:22:16
list
CAS 机制下的无锁队列设计与实现

CAS 机制下的无锁队列设计与实现 ... [详细]

蜡笔小新 2024-11-04 15:38:05

Tags | 热门标签

RankList | 热门文章