注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

2009-7-17的笔记  

2009-07-17 14:34:09|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Mosaicism

mos.in

mos.out

时限:3s

给定n个序列。序列i的得分是,(A, B, j, k)的数量,使得AB都在第i个序列中出现,并且Aj中但是不在k中出现,Bk中但是不在j中出现。(A, B), (j, k)都是无序二元组。求每个序列的得分。同个序列中数各不相同。AB是数。

输入格式:

第一行一个数n,然后接下来n行,每行描述一个序列。每个序列先读入序列的长度l,接下来l个数,表示这个序列。

输出格式:

一行n个数,用空格分隔,依次表示每个序列的得分。

样例输入:

4

4    1 5 2 4

3    3 6 4

3    5 2 6

3    4 3 1

样例输出:

6 3 2 1

数据范围:

100%的数据满足:n<=300,每个序列长度<=300,序列中的数<=10^5

 >=1


Permutations

perm.in

perm.out

时限:1s

排列AB的乘积C=AB定义为C[i]=A[B[i]]。给定一个排列A,求有多少排列B满足AB=BA。答案mod p

输入格式:

第一行两个数:n,pn是序列A的长度,接下来第二行n个数表示排列A

输出格式:

第一数表示答案。

样例输入:

5 100

3 4 2 5 1

样例输出:

5

数据范围:

30%的数据满足n<=10

100%的数据满足n<=100000,p<=1000000000
Infrastructure

inf.in

inf.out

时限:3s

一张n个点m个边的连通无向图,满足任何一个双连通分量的大小不超过13(不存在割点的诱导子图)。已知每个点的权值,选择权值和最小的点使得每条边两侧的点至少有一个被选择。

输入格式:

第一行两个数n,m,第二行n个整数,表示每个点的权值。再接下来m行,每行两个不同的数u,v(1<=u,v<=n),表示uv之间有一条边。任两个不同的点之间至多只有一条边。

输出格式:

一个数表示最小的权值和。

样例输入:

15 21

9 8 7 100 99 2 3 8 4 6 7 2 1 6 2

1 2

2 4

4 5

5 6

2 6

1 5

4 3

3 7

7 9

9 8

8 4

4 7

3 9

5 10

10 13

5 12

12 13

12 15

12 14

15 14

13 11

样例输出:

129

样例说明:

选择节点:1 4 6 7 9 10 12 13 15

数据范围:

对于30%的数据满足,n<=18

对于100%的数据满足n<=2008, m<=10000,权值在1~1000000内。


还以为是难题,所以统统写朴素


第一题,数学+hash或15个int的集合


第二题,数学排列组合pi(n!*x^n)


第三题,树状dp?怎么看都是超时的......


  评论这张
 
阅读(371)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017