【dp】UvaLive 6201 6204 6205 6208

news/2025/1/16 2:04:14/

6201  Wedding of Sultan

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4212

本题只要想到用Stack做的话，会很简单。如果当前的节点已经入过栈了，则pop出来同时给栈顶元素的值加1，否则放入栈中。

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
stack<char> ST;
int main() {int n;char str[1009];bool mark[1009];int num[1009];scanf("%d",&n);for(int t=1; t<=n; t++) {memset(str,0,sizeof(str));memset(mark,false,sizeof(mark));memset(num,0,sizeof(num));scanf("%s",str);int len=strlen(str);while(!ST.empty()){ST.pop();}for(int i=0;i<len;i++){if(mark[str[i]]==false){ST.push(str[i]);mark[str[i]]=true;}else{char ch=ST.top();ST.pop();if(!ST.empty()){ch=ST.top();num[ch]++;}}}char tmp=str[0];sort(str,str+len);memset(mark,false,sizeof(mark));printf("Case %d\n",t);for(int i=0;i<len;i++){if(mark[str[i]]==false){if(tmp==str[i])printf("%c = %d\n",str[i],num[str[i]]);elseprintf("%c = %d\n",str[i],num[str[i]]+1);mark[str[i]]=true;}}}return 0;
}
//AEFFGGEHMMHJBCCDDBJA


开始这么写的，反正WA，不知道为啥

 

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main() {int n;char str[1009],num[100],loc[100],ans[100];bool mark[100],vis[100];scanf("%d",&n);for(int t=1; t<=n; t++) {memset(str,0,sizeof(str));scanf("%s",str);int len=strlen(str);memset(num,0,sizeof(num));memset(mark,false,sizeof(mark));memset(ans,0,sizeof(ans));for(int i=0; i<len; i++) {if(mark[str[i]-'A']==true) continue;for(int j=i+1; j<len; j++) {if(str[i]==str[j]) {loc[str[i]-'A']=j;mark[str[i]-'A']=true;break;}}}for(int i=0; i<len; i++) {memset(mark,false,sizeof(mark));for(int j=i+1; j<loc[str[i]-'A']; j++) {if(mark[str[j]-'A']==false) {num[str[i]-'A']++;mark[str[j]-'A']=true;}}}//for(int i=0;i<len;i++) printf("%d ",num[str[i]-'A']);memset(mark,false,sizeof(mark));memset(vis,false,sizeof(vis));for(int i=0; i<len; i++) {if(vis[str[i]-'A']==true) continue;int tmp=0x7f7f7f;for(int j=0; j<len; j++) {if(vis[str[j]-'A']==false&&tmp>num[str[j]-'A']) {tmp=num[str[j]-'A'];}}for(int j=0; j<len; j++) {if(num[str[j]-'A']==tmp&&vis[str[j]-'A']==false) {vis[str[j]-'A']=true;ans[str[j]-'A']=num[str[j]-'A'];for(int m=j+1; m<loc[str[j]-'A']; m++) {if(mark[str[m]-'A']==false) {mark[str[m]-'A']=true;ans[str[j]-'A']-=num[str[m]-'A'];}}}}}printf("Case %d\n",t);memset(mark,false,sizeof(mark));char flag=str[0];sort(str,str+len);for(int i=0; i<len; i++) {if(mark[str[i]-'A']==false) {if(flag==str[i])printf("%c = %d\n",str[i],ans[str[i]-'A']);elseprintf("%c = %d\n",str[i],ans[str[i]-'A']+1);mark[str[i]-'A']=true;}}}return 0;
}
//AEFFGGEHMMHJBCCDDBJA

6204 Poker End Games
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4215

 

题意：

每次a,b的输赢概率均为1/2，求a赢的概率和场数比赛的期望。

题解：

由于赢的概率误差不超过1e-5那么，最多只需要做33次，就可以了不再做了,以为(1/2)^33<1e-5;

 

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double ansE=0,ans=0;
void dfs(int a,int b,int k){int tmp=a>b?b:a;if(k>33) return;if(a==0){ansE+=k*pow(0.5,k);return;}if(b==0){ansE+=k*pow(0.5,k);ans+=pow(0.5,k);return;}dfs(a-tmp,b+tmp,k+1);dfs(a+tmp,b-tmp,k+1);
}
int main(){int n,a,b;while(~scanf("%d",&n)){for(int t=1;t<=n;t++){scanf("%d %d",&a,&b);ansE=0;ans=0;dfs(a,b,0);printf("Case %d: %.6lf %.6lf\n",t,ansE,ans);}}
return 0;
}

 

6205 - Overlapping Characters

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4216

 

本题纯暴力：

 

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
char str[100][100][100];
int num[100][100];
int mark[100];
int main(){int n,q;while(~scanf("%d %d",&n,&q)){memset(num,0,sizeof(num));char a[100];memset(a,0,sizeof(a));scanf("%s",a);for(int i=0;i<n;i++){for(int j=0;j<17;j++){scanf("%s",str[i][j]);}}char pat[100];for(int t=1;t<=q;t++){memset(pat,0,sizeof(pat));memset(num,0,sizeof(num));scanf("%s",pat);int len=strlen(pat);for(int i=0;i<len;i++){int j=0;for(;a[j];j++){if(a[j]==pat[i]){mark[i]=j;break;}}for(int k=0;k<16;k++){for(int m=0;m<43;m++){if(str[j][k][m]=='*'){num[k][m]++;}}}}printf("Query %d: ",t);for(int i=0;i<len;i++){bool flag=false;for(int k=0;k<16;k++){for(int m=0;m<43;m++){if(num[k][m]==1&&str[mark[i]][k][m]=='*'){//&&str[mark[i]][k][m]=='*'printf("Y");flag=true;break;}}if(flag==true) break;}if(flag==false) printf("N");}puts("");}}
return 0;
}
/*
3 2
ABC
...............***.........................
..............*****........................
.............*******.......................
............*********......................
...........***********.....................
..........*************....................
.........*******.*******...................
........*******...*******..................
.......*******.....*******.................
......*********************................
.....***********************...............
....*************************..............
...*******.............*******.............
..*******...............*******............
.*******.................*******...........
*******...................*******..........
...........................................
*****************..........................
******************.........................
*******************........................
********.....*******.......................
..******.....*******.......................
..******.....*******.......................
..*****************........................
..****************.........................
..*****************........................
..******.....*******.......................
..******.....*******.......................
..******.....*******.......................
********************.......................
*******************........................
******************.........................
*****************..........................
...........................................
........*************......................
.....****************......................
...******************......................
..*******************......................
.*******.......******......................
*******....................................
*******....................................
*******....................................
*******....................................
*******....................................
*******....................................
.*******.......******......................
..*******************......................
...******************......................
.....****************......................
........*************......................
...........................................
ABC
AB*/

 

 

 

6208 - Learning Vector

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4219

 

典型的0、1背包：

 

//Time:732ms
//Length:1095B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 55
struct _node
{int x,y;bool operator <(const _node &b) const{if(y*b.x!=b.y*x)    return  y*b.x>b.y*x;return x>b.x;}
}no[MAXN];
int dp[MAXN*MAXN][MAXN];
int main()
{//freopen("/home/moor/Code/input","r",stdin);int ncase,n,k,ans;scanf("%d",&ncase);for(int hh=1;hh<=ncase;++hh){scanf("%d%d",&n,&k);memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;for(int i=0;i<n;++i)    scanf("%d%d",&no[i].x,&no[i].y);sort(no,no+n);ans=0;for(int i=0;i<n;++i)for(int j=MAXN*MAXN-1;j>=0;--j)for(int l=k-1;l>=0;--l)if(dp[j][l]>=0){int tmp=(no[i].y+2*j)*no[i].x+dp[j][l];dp[j+no[i].y][l+1]=max(dp[j+no[i].y][l+1],tmp);}for(int i=MAXN*MAXN-1;i>=0;--i) ans=max(ans,dp[i][k]);printf("Case %d: %d\n",hh,ans);}return 0;
}

 

 

 

 

 

 


http://www.ppmy.cn/news/350206.html

相关文章

Echarts实现系统监控

Echarts实现系统监控

效果图 页面代码 <!DOCTYPE html> <html style"height: 100%"><head> <meta charset"utf-8"> <title>Echarts</title> <script type"text/javascript"src"http://echarts.baidu.com/gallery/vendo…
阅读更多...
Lambda表达式使用详细讲解

Lambda表达式使用详细讲解

目录 1.新思想 1.1函数式编程思想 1.2.函数式接口 2.通往lambda之路 2.1.什么是lambda表示式&#xff1f; 2.2. lambda表示式有哪些特点&#xff1f; 2.3.lambda表示式使用场景 2.4.lambda表示式语法 2.5.Lambda简化写法 2.6.Lambda表达式结构 3.Stream流 3.1概述 …
阅读更多...
UVALive 6208

UVALive 6208

离散DP 由于状态转移需要记录三维&#xff0c;第三维是之前的高度&#xff0c;而这个变量取值只有离散的几个&#xff0c;故用map来存。 不过一开始一直T啊&#xff0c;最后加些剪枝终于过了。。。 #include <iostream> #include <cstdio> #include <string&g…
阅读更多...
[LeetCode周赛复盘] 第 89 场双周赛20221015

[LeetCode周赛复盘] 第 89 场双周赛20221015

[LeetCode周赛复盘] 第 89 场双周赛20221015 一、本周周赛总结二、 [Easy] 6208. 有效时间的数目1. 题目描述2. 思路分析3. 代码实现 三、[Medium] 6209. 二的幂数组中查询范围内的乘积1. 题目描述2. 思路分析3. 代码实现 四、[Medium] 6210. 最小化数组中的最大值1. 题目描述…
阅读更多...
致编辑,将语雀文档迁移到csdn

致编辑,将语雀文档迁移到csdn

用户每天文章发布数限制&#xff1a; 博客专家&#xff1a;50篇 企业博客&#xff1a;30篇 VIP&#xff1a;20篇 普通&#xff1a;10篇 ** 原本打算在语雀发文章 但是现在要vip&#xff0c;文章才能公布到互联网 无奈只能再次迁移到csdn 但是csdn每天发文数量限制为10篇 ** …
阅读更多...
linux gcc strip命令简介

linux gcc strip命令简介

阅读目录 strip简介strip示例strip命令用法程序开发是否要strip静态库如何strip参考资料 strip简介 strip经常用来去除目标文件中的一些符号表、调试符号表信息&#xff0c;以减小静态库、动态库和程序的大小。 strip支持的选项可通过如下命令查看&#xff1a; strip --help…
阅读更多...
HDFS实验二：部署HDFS/学习搭建HDFS

HDFS实验二：部署HDFS/学习搭建HDFS

一、HDFS实验&#xff1a;部署HDFS指导 2.1 实验目的 1&#xff0e; 理解HDFS存在的原因&#xff1b; 2&#xff0e; 理解HDFS体系架构&#xff1b; 3&#xff0e; 理解master/slave架构&#xff1b; 4&#xff0e; 理解为何配置文件里只需指定主服务、无需指定从服务&…
阅读更多...
论文浅尝 | ERNIE-ViL：从场景图中获取结构化知识来学习视觉语言联合表示

论文浅尝 | ERNIE-ViL：从场景图中获取结构化知识来学习视觉语言联合表示

笔记整理&#xff1a;朱珈徵&#xff0c;天津大学硕士 链接&#xff1a;https://www.aaai.org/AAAI21Papers/AAAI-6208.YuFei.pdf 动机 现有的视觉语言预训练方法试图通过在大的图像文本数据集上的视觉基础任务来学习联合表示&#xff0c;包括基于随机掩码子词的掩码语言建模、…
阅读更多...
最新文章

Copyright @ 2022~2023