编程之美2015初赛第二场AB

作者:网络    软件教程库   2020-05-19

题目1 : 扑克牌

时间限制:2000ms
单点时限:1000ms
内存限制:256mb
描述
一副不含王的扑克牌由52张牌组成,由红桃、黑桃、梅花、方块4组牌组成,每组13张不同的面值。现在给定52张牌中的若干张,请计算将它们排成一列,相邻的牌面值不同的方案数。

牌的表示方法为xy,其中x为面值,为2、3、4、5、6、7、8、9、t、j、q、k、a中的一个。y为花色,为s、h、d、c中的一个。如2s、2h、td等。

输入
第一行为一个整数t,为数据组数。

之后每组数据占一行。这一行首先包含一个整数n,表示给定的牌的张数,接下来n个由空格分隔的字符串,每个字符串长度为2,表示一张牌。每组数据中的扑克牌各不相同。

输出
对于每组数据输出一行,形如”case #x: y”。x为数据组数,从1开始。y为可能的方案数,由于答案可能很大,请输出模264之后的值。

数据范围
1 ≤ t ≤ 20000

小数据

1 ≤ n ≤ 5

大数据

1 ≤ n ≤ 52

样例输入
5
1 tc
2 tc ts
5 2c ad ac jc jh
4 ac kc qc jc
6 ac ad as jc jd kd
样例输出
case #1: 1
case #2: 0
case #3: 48
case #4: 24
case #5: 120

dp。

(以为是排列组合,想了很久无果)
其实和【bzoj 1079】完全一样。

如果dp的状态是每个面值剩余几张的话复杂度是o(413),但如果变成剩余几张的有几种面值的话就是o(134)了,因为剩余数量相同的面值是等价的。

f[a][b][c][d][last]表示剩余1张的有a种面值,剩余2张的有b种面值…上一次选的是剩余last张的一种面值。

转移就是在选择剩余last1张的面值中选择方案少一种,其他任意,详见代码。

#include cstdio
#include algorithm
#include cstring
#include cstdlib
#include queue
#include map
#include vector
#include iostream
#include set
#define ull unsigned long long
using namespace std;
ull f[14][14][14][14][5];
char s[10];
int t,n,c[14],sum[10];
ull dfs(int a,int b,int c,int d,int last)
{
    if (f[a][b][c][d][last]) return f[a][b][c][d][last];
    ull tmp=0;
    if (a) tmp+=dfs(a-1,b,c,d,1)*(a-(last==2));
    if (b) tmp+=dfs(a+1,b-1,c,d,2)*(b-(last==3));
    if (c) tmp+=dfs(a,b+1,c-1,d,3)*(c-(last==4));
    if (d) tmp+=dfs(a,b,c+1,d-1,4)*d;
    f[a][b][c][d][last]=tmp;
    return tmp;
}
int main()
{
    cint;
    for (int t=1;t=t;t++)
    {
        printf("case #%d: ",t);
        scanf("%d",n);
        for (int i=1;i=13;i++)
            c[i]=0;
        for (int i=1;i=n;i++)
        {
            scanf("%s",s);
            if (s[0]-‘0‘=2s[0]-‘0‘=9)
                c[s[0]-‘0‘]++;
            if (s[0]==‘a‘) c[1]++; 
            if (s[0]==‘t‘) c[10]++;
            if (s[0]==‘j‘) c[11]++;
            if (s[0]==‘q‘) c[12]++;
            if (s[0]==‘k‘) c[13]++;
        }
        for (int i=1;i=10;i++)
            sum[i]=0;
        for (int i=1;i=13;i++)
            sum[c[i]]++;
        for (int i=1;i=4;i++)
            f[0][0][0][0][i]=1;
        ull ans=dfs(sum[1],sum[2],sum[3],sum[4],0);
        for (int i=1;i=13;i++)
            if (c[i]1)
            {
                for (int j=2;j=c[i];j++)
                    ans*=j;
            }
        printf("%llu\n",ans);
    }
    return 0;
}

题目2 : 攻城略地

时间限制:2000ms
单点时限:1000ms
内存限制:256mb
描述
a、b两国间发生战争了,b国要在最短时间内对a国发动攻击。已知a国共有n个城市(城市编号1, 2, …, n),城市间有一些道路相连。每座城市的防御力为w,直接攻下该城的代价是w。若该城市的相邻城市(有道路连接)中有一个已被占领,则攻下该城市的代价为0。

除了占领城市,b国还要摧毁a国的交通系统,因而他们需要破坏至少k条道路。由于道路损毁,攻下所有城市的代价相应会增加。假设b国可以任意选择要摧毁的道路,那么攻下所有城市的最小代价是多少?

输入
第一行一个整数t,表示数据组数,以下是t组数据。

每组数据第一行包含3个整数n, m, k。

第二行是n个整数,分别表示占领城市1, 2, …, n的代价w。

接下来m行每行两个数i, j,表示城市i与城市j间有一条道路。

输出
对于每组数据输出一行,格式为”case #x: y”。x表示数据编号(从1开始),y为答案。

数据范围
1 ≤ t ≤ 30

k ≤ m

0 ≤ w ≤ 108

小数据

1 ≤ n ≤ 1000

0 ≤ m ≤ 5000

大数据

1 ≤ n ≤ 106

0 ≤ m ≤ 106

样例输入
2
4 4 2
6 5 3 4
1 2
1 3
2 3
2 4
4 4 4
6 5 3 4
1 2
1 3
2 3
2 4
样例输出
case #1: 7
case #2: 18

贪心。

在每一个连通块都选择权值最小的来占领,一定最优。

也就是说权值较大的最好不要从连通块中分离出去。

法一:
首先把ans设为权值总和,按照权值降序排列,让大的使用一条边加入连通块中,ans减去大的权值,直到把mk条边全部用完。
(注意连通块内的最小的点得权值不能去掉)

法二:
可以把每个连通块中除了树上的边都删去,看是否删够了k条边,如果不够的话就把连通块中除最小权值点外的点排序,去掉并让答案加上这个权值(因为他独立出来了);
直到删够了k条边。

编程之美2015初赛第二场ab

原文地址:http://blog.csdn.net/regina8023/article/details/45437419

以上就是由(软件教程库https://www.itjcku.com/9999/1091490.html)本站为大家整理

阅读全部内容


Tags:编程初赛预赛第二

返回首页



推荐内容

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...

用USB安装linux

手边没有光驱,安装ubuntu可以用 linuxlive usb creator 2.9.3,在百度网盘里有的。http ...

一个复杂子查询SQL优化

select * from test.vmark vk where id in (select v.id ...

Java多线程中常见的几个问题

我们都知道,在java中要想实现多线程,有两种手段,一种是继续thread类,另外一种是实现runable接口。  1. ...

OracleDataIntegrator12c-CreatingaCollocatedAgent

http://www.oracle.com/webfolder/technetwork/tutorials/obe/fm ...

CompilingGCC5onOSX

compiling gcc 5 on os x */--> pre.src {backgro ...

查看Linux上MySQL版本信息

如果mysql是用rpm或者yum安装的,可用 #rpm -qa|grep mysql查看. 如: [[email#16 ...

《赢在测试2-中国软件测试专家访谈录》读书笔记

《赢在测试2-中国软件测试专家访谈录》读书笔记 2015-04-30 测试人物经历与观点 1.董杰 百度测试架构师 董杰 ...

Objective-C的KVC和KVO

字面意思分别是: kvc是指key value coding,键值编码。 kvo是指key value observin ...

20150502调试分析之使用gdb远程调试ARM开发板

20150502 调试分析之 使用gdb远程调试arm开发板 2015-05-02 lover雪儿 今天我们要学习 ...

限制Apache日志access.log文件大小

可以在apache的httpd.conf配置文件中配置apache自带的程序rotatelogs的功能。 rotate ...

UVa11561-GettingGold

题目:给你一个二维的地图,里面有陷阱‘t‘,金子‘g‘以及墙壁‘#‘,和普通的道路‘.‘,现在已知一个人在起点‘p‘; ...

configure:error:cannotcomputesuffixofobjectfiles:cannotcompile

centos 6.5下安装gcc-4.8.4 make的时候提示以下错误: configure: error: can ...

我读的第一本书《梦断代码》

一切都是兴趣所在,兴趣才是发展的动力,虽然我们在这个开发过程中不可否认的会遇到挫折、瓶颈,但我认为,地狱与天堂共存 ...

iOS中定时器NSTimer的使用

ios中定时器nstimer的使用 1、初始化 + (nstimer *)timerwithtimeinterval:( ...

数组遍历二叉

//任务二叉树遍历 void cmission::initmission(dword base) { cha ...

Oracle基础<1>--数据库设计

一:为什么需要使用数据库设计   数据库设计可以使数据库通过健壮的数据库结构 高效并且健康 的进行工作。 二.数据库设计 ...

LinuxShell之七函数应用

函数是什么?函数是一些命令的集合,使用一个名称做代表,称为函数名称。函数名称的命名规则和变量相同。一旦函数定义好了,执行 ...

SkillButton技能冷却

#pragmaonce #include"cocos2d.h" using_ns_cc; classskillbutto ...

sles11启用Xmanager

一:开启xmanager要满足一下2个条件:1.安装了gnome桌面环境,并且默认启动级别为52.ip地址为固定ip地址 ...

linux软件管理之rpm、yum

应用程序: 程序:architecturec语言:源代码——》(编译)二进制格式脚本:解释器(二进制程序)源代码——》编 ...

MyEclipse2014下搭建Android开发环境

1、下载android-sdk_r24.1.2-windows.zip,将其解压到一个文件夹中,例如:d:\progra ...

LinuxShell之八转向的用法

一、文件代码“转向”的意思是说:原本应由标准输入(如键盘)读取数据的,改由其它文件读取;原本应把结果显示在标准输出(如屏 ...

Java中有关null的9件事

java中有关 null 的9件事 对于java程序员来说,null是令人头痛的东西。时常会受到空指针异常(np ...

LDAP账号同步和Windows域集成验证

#65279;#65279; paradise.ezla.com.tw/files/article/html/32/32 ...

在同一个sql语句中如何写不同条件的count数量(转)

select sum(case when (t.条件字段=‘00‘) then 1 else 0 ...

详解MessageBox(),MsgBox函数的正确使用

//或者使用chr(13),chr(10)效果一样 msgbox aamp;chr(13)amp;bamp;chr( ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com