久久久无码精品亚洲日韩蜜臀浪潮,久久久久久精品久久久久,亚洲嫩草影院久久精品

Topcoder SRM550 div1 500

Drolca — Wed, 22 Aug 2012 02:05:00 GMT

Sierpinski三角�?br />

杨辉三角,二项式系数奇偶性的判定 C(k,n)| k&n==k , 或者比较n�Q�与{k�Q�，�Q�n-k�Q�！}�?的个�?/strong>

Drolca 2012-08-22 10:05 发表评论

poj 3691 AC自动�?DP

Drolca — Fri, 13 Apr 2012 11:28:00 GMT
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include #include using namespace std;const int...  阅读全文

Drolca 2012-04-13 19:28 发表评论

Drolca — Fri, 13 Apr 2012 07:17:00 GMT

#include <iostream>
using namespace std;

const int MAXN=50*10005;
const int MAXL=1005;
const int K=26;

struct Node
{
    Node *next[K], *fail;
    int flag, id;
    void Init(int index)
    {
        id=index;
        flag=0;
        fail=NULL;
        for(int i=0; i<K; i++)next[i]=NULL;
    }
}* Q[MAXN/2], *root, T[MAXN];// Q for queue, root&T for tree;

int index=0;
Node * newNode()
{
    T[index].Init(index);
    return &T[index++];
}

int tokind(char k){return k-'a';}

void insert(char *str)
{
    if(root==NULL)
        root=newNode();

    Node *now=root;
    for(int i=0; str[i]; i++)
    {
        int kind=tokind(str[i]);
        if(now->next[kind]==NULL)
            now->next[kind]=newNode();
        now=now->next[kind];
    }
    now->flag++;
}

void buildAC()
{
    int head=0, tail=0;
    root->fail=NULL;

    Q[tail++]=root;
    while(head<tail)
    {
        Node *now=Q[head++];
        for(int i=0; i<K; i++)
        {
            if(now->next[i]!=NULL)
            {
                if(now==root)now->next[i]->fail=root;
                else
                {
                    Node *p=now->fail;
                    while(p->next[i]==NULL&&p!=root)p=p->fail;
                    p=p->next[i];
                    now->next[i]->fail=(p==NULL)?root:p;
                }
                Q[tail++]=now->next[i];
            }
        }
    }
}

int query(char *str)
{
    int res=0;
    Node *p=root;
    for(int i=0; str[i]; i++)
    {
        int kind=tokind(str[i]);
        while(p->next[kind]==NULL&&p!=root)p=p->fail;
        p=p->next[kind];
        p=(p==NULL)?root:p;
        Node *now=p;
        while(now!=root&&now->flag!=-1)
        {
            res+=now->flag;
            now->flag=-1;
            now=now->fail;
        }
    }
    return res;
}

int main()
{
    //freopen ("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        root=NULL;
        scanf("%d",&n);getchar();
        while(n--)
        {
            char str[55];
            scanf("%s",str);
            insert(str);
        }
        buildAC();
        char ch[1000005];
        scanf("%s",ch);
        printf("%d\n",query(ch));
    }
    return 0;
}

Drolca 2012-04-13 15:17 发表评论

Topcoder SRM 538 1050P

Drolca — Mon, 09 Apr 2012 09:30:00 GMT

1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6#define madd(a,b) a=(a+b)%MOD
7
8const int MOD=1000000007;
9const int MAXC=55, MAXH=75, MAXW=10, MAXB=15;
10long g[MAXC], Comb[MAXC][MAXC];
11int dp[MAXW][MAXB][MAXC][MAXH][MAXW][2];
12
13class SkewedPerspective
14{
15
16public:
17    int countThem(vector <int> cubes, int B, int w)
18    {
19        int n=cubes.size(), total=0;
20        int i, j, k;
21        for(i=0; i<n; i++) total+=cubes[i];
22
23        for(i=0; i<=total; i++)
24            for(j=0; j<=i; j++)
25                Comb[i][j]=(j?(Comb[i-1][j]+Comb[i-1][j-1])%MOD:1);
26        g[0]=1;
27        for(i=0; i<n; i++)
28            for(j=total; j; j--)
29                for(k=1; k<=j && k<=cubes[i]; k++)
30                    g[j]=(g[j]+g[j-k]*Comb[j][k])%MOD;
31
32        long ans=0;
33        dp[1][0][0][0][0][0]=1;
34        for(int tower=1; tower<=w; tower++)for(int black=0; black<=B; black++)
35        for(int color=0; color<=total; color++)for(int need=0; need<=total+black*2; need++)
36        for(int needOdd=0; needOdd<=tower; needOdd++)for(int lastBlack=0; lastBlack<2; lastBlack++)
37        {
38            int x=dp[tower][black][color][need][needOdd][lastBlack];
39            if(!x)continue;
40            //get result
41            if(black+color>0 && (B-black)*2+total-color>=need && total-color>=needOdd)
42                ans=(ans+g[color]*x)%MOD;
43            //put colored
44            madd(dp[tower][black][color+1][need][needOdd][0], x);
45            if(lastBlack) continue;
46            //put black
47            int layer=black*2+color-(tower-1);
48            for(int blackSize=1; blackSize+black*2<=B*2; blackSize++)
49                if(blackSize%2==0)
50                    madd(dp[tower][black+blackSize/2][color][need][needOdd][1], x);
51                else
52                {
53                    if(!layer && blackSize==1) continue;  //"b1bbbb"
54                    int needNow=(layer?layer-1:layer+1);
55                    if(need+needNow<=total+B*2)
56                        madd(dp[tower+1][black+(blackSize+1)/2][color][need+needNow][needOdd+needNow%2][1], x);
57                }
58
59        }
60        return int(ans);
61    }
62};
63
64int main()
65{
66    SkewedPerspective a;
67    int cubes[]={1, 1, 0};
68    vector<int> t(cubes, cubes+3);
69
70    cout<<a.countThem(t, 1, 2)<<endl;
71    return 0;
72}
73

Drolca 2012-04-09 17:30 发表评论

Drolca — Sat, 21 May 2011 13:36:00 GMT

转蝲自：(x��)http://www.iteye.com/topic/398782
很久很久以前�Q�有一��h�Q�他们决定用8个可以开合的晶体��来�l�合成不同的状态，以表�C�Z��界上的万物。他们看�?个开关状态是好的�Q�于是他们把�q�称�?字节"�?/span>

再后来，他们又做了一些可以处理这些字节的机器�Q�机器开动了�Q�可以用字节来组合出很多状态，状态开始变来变厅R��他们看到这��h��好的�Q�于是它们就�q�机器称�?计算�?�?/span>

开始计��机只在��国用。八位的字节一共可以组合出256(2�?�ơ方)�U�不同的状态�?/span>

他们把其中的�~�号�?开始的32�U�状态分别规定了�Ҏ(gu��)��的用途，一但终端、打印机遇上�U�定好的�q�些字节被传�q�来�Ӟ��p��做一些约定的动作。遇�?0x10, �l�端��换行，遇上0x07, �l�端��向��Z��嘟嘟叫，例好遇上0x1b, 打印机就打印反白的字�Q�或者终端就用彩色显�C�字母。他们看到这样很好，于是��把�q�些0x20以下的字节状态称�?控制�?�?nbsp;

他们又把所有的�I�格、标点符受��数字、大��写字母分别用连�l�的字节状态表�C�，一直编��C��W?27��P��q�样计算机就可以用不同字节来存储��p��的文字了。大家看到这��P��都感觉很好，于是大家都把�q�个�Ҏ(gu��)��叫做 ANSI �?Ascii"�~�码�Q�American Standard Code for Information Interchange�Q�美国信息互换标准代码）。当时世界上所有的计算机都用同��L(f��ng)��ASCII�Ҏ(gu��)��来保存英文文字�?/span>

后来�Q�就像徏造巴比��u塔一��P��世界各地的都开始��用计��机�Q�但是很多国家用的不是英文，他们的字母里有许多是ASCII里没有的�Q��ؓ(f��)了可以在计算��Z��存他们的文字�Q�他们决定采�?27号之后的�I�Z��来表�C��些新的字母、符��P��q�加入了很多画表格时需要用下到的横�Uѝ��竖�Uѝ��交叉等形状�Q�一直把序号�~�到了最后一个状�?55。从128�?55�q�一��늚�字符集被�U?扩展字符�?。从此之后，贪婪的�h�c�d��没有新的状态可以用了，��帝国主义可能没有想到还有第三世界国家的��Z��也希望可以用到计��机吧！

�{�中国�h们得到计��机�Ӟ��已经没有可以利用的字节状态来表示汉字�Q�况且有6000多个常用汉字需要保存呢。但是这难不倒智慧的中国人民�Q�我们不客气地把那些127号之后的奇异�W�号们直接取消掉, 规定�Q�一个小�?27的字�W�的意义与原来相同，但两个大�?27的字�W�连在一��h��Q�就表示一个汉字，前面的一个字节（他称之�ؓ(f��)高字节）�?xA1用到0xF7�Q�后面一个字节（低字节）�?xA1�?xFE�Q�这��h��们就可以�l�合出大�U?000多个��体汉字了。在�q�些�~�码里，我们�q�把数学�W�号、罗马希腊的字母、日文的假名们都�~�进��M��Q�连�?ASCII 里本来就有的数字、标炏V��字母都�l�统重新�~�了两个字节长的�~�码�Q�这��是常说�?全角"字符�Q�而原来在127号以下的那些��叫"半角"字符了�?nbsp;

中国人民看到�q�样很不错，于是��把�q�种汉字�Ҏ(gu��)��叫做 "GB2312"。GB2312 是对 ASCII 的中文扩展�?/span>

但是中国的汉字太多了�Q�我们很快就��发现有许多人的人名没有办法在这里打出来�Q�特别是某些很会(x��)�ȝ��别�h的国安��g�h。于是我们不得不�l�箋�?GB2312 没有用到的码位找出来老实不客气地用上�?/span>

后来�q�是不够用，于是�q�脆不再要求低字节一定是127号之后的内码�Q�只要第一个字节是大于127��固定表�C��是一个汉字的开始，不管后面跟的是不是扩展字�W�集里的内容。结果扩展之后的�~�码�Ҏ(gu��)��被称�?GBK 标准�Q�GBK 包括�?GB2312 的所有内容，同时又增加了�q?0000个新的汉字（包括�J�体字）和符受��?nbsp;

后来��数民族也要用电(sh��)脑了�Q�于是我们再扩展�Q�又加了几千个新的少数民族的字，GBK 扩成�?GB18030。从此之后，中华民族的文化就可以在计��机时代中传承了�?/span>

中国的程序员们看到这一�p�d��汉字�~�码的标准是好的�Q�于是通称他们叫做 "DBCS"�Q�Double Byte Charecter Set 双字节字�W�集�Q�。在DBCS�p�d��标准里，最大的特点是两字节长的汉字字符和一字节长的英文字符�q�存于同一套编码方案里�Q�因此他们写的程序�ؓ(f��)了支持中文处理，必须要注意字串里的每一个字节的��|��如果�q�个值是大于127的，那么��p��Z��个双字节字符集里的字�W�出��C��。那时候凡是受�q�加持，�?x��)编�E�的计算机僧侣们都要每天念下面这个咒语数��N��Q?nbsp;

"一个汉字算两个英文字符�Q�一个汉字算两个英文字符......"

因�ؓ(f��)当时各个国家都像中国�q�样搞出一套自��q��~�码标准�Q�结果互�怹�间谁也不懂谁的编码，谁也不支持别人的�~�码�Q�连大陆和台湾这样只盔R��?50��里�Q��用着同一�U�语�a�的兄弟地区，也分别采用了不同�?DBCS �~�码�Ҏ(gu��)��。当时的中国人想让电(sh��)脑显�C�汉字，��必��装上一�?汉字�pȝ��"�Q�专门用来处理汉字的昄��、输入的问题�Q�但是那个台湄��愚昧��徏人士写的��命�E�序��必��d��装另一套支�?BIG5 �~�码的什�?倚天汉字�pȝ��"才可以用�Q�装错了字符�pȝ��Q�显�C�就�?x��)�ؕ了套�Q�这怎么办？而且世界民族之林中还有那些一时用不上�?sh��)脑的穷苦�h民，他们的文字又怎么办？

真是计算机的巴比伦塔命题啊！

正在�q�时�Q�大天��加百列及(qi��ng)时出��C��Q�一个叫 ISO �Q�国际标谁化�l�织�Q�的国际�l�织军_��着手解册��个问题。他们采用的�Ҏ(gu��)��很简单：(x��)废了所有的地区性编码方案，重新搞一个包括了地球上所有文化、所有字母和�W�号的编码！他们打算叫它"Universal Multiple-Octet Coded Character Set"�Q�简�U?UCS, 俗称 "UNICODE"�?/span>

UNICODE 开始制订时�Q�计��机的存储器定w��极大地发展了�Q�空间再也不成�ؓ(f��)问题了。于�?ISO ��q��接规定必��ȝ��两个字节�Q�也��是16位来�l�一表示所有的字符�Q�对于ascii里的那些"半角"字符�Q�UNICODE 包持其原�~�码不变�Q�只是将光��度由原来�?位扩展�ؓ(f��)16位，而其他文化和语言的字�W�则全部重新�l�一�~�码。由�?半角"英文�W�号只需要用��C��8位，所以其�?位永�q�是0�Q�因此这�U�大气的�Ҏ(gu��)��在保存英文文本时�?x��)多��费一倍的�I�间�?nbsp;

�q�时候，从旧�C�会(x��)里走�q�来的程序员开始发��C��个奇怪的现象�Q�他们的strlen函数靠不住了�Q�一个汉字不再是相当于两个字�W�了�Q�而是一个！是的�Q�从 UNICODE 开始，无论是半角的英文字母�Q�还是全角的汉字�Q�它们都是统一�?一个字�W?�Q�同�Ӟ��也都是统一�?两个字节"�Q�请注意"字符"�?字节"两个术语的不同，"字节"是一�?位的物理存贮单元�Q��?字符"则是一个文化相关的�W�号。在UNICODE 中，一个字�W�就是两个字节。一个汉字算两个英文字符的时代已�l�快�q�去了�?/span>

从前多种字符集存在时�Q�那些做多语�a�软�g的公叔R��上过很大�ȝ��Q�他们�ؓ(f��)了在不同的国安��售同一套��Y�Ӟ��׃��得不在区域化软�g时也加持那个双字节字�W�集咒语�Q�不仅要处处��心不要搞错�Q�还要把软�g中的文字在不同的字符集中转来转去。UNICODE 对于他们来说是一个很好的一揽子解决�Ҏ(gu��)��Q�于是从 Windows NT 开始，MS ��机把它们的操作�pȝ��改了一遍，把所有的核心代码都改成了�?UNICODE 方式工作的版本，从这时开始，W(xu��)INDOWS �pȝ��l�于无需要加装各�U�本土语�a��pȝ��Q�就可以昄��全世界上所有文化的字符了�?nbsp;

但是�Q�UNICODE 在制订时没有考虑与�Q何一�U�现有的�~�码�Ҏ(gu��)��保持兼容�Q�这使得 GBK 与UNICODE 在汉字的内码�~�排上完全是不一��L(f��ng)��Q�没有一�U�简单的��术�Ҏ(gu��)��可以把文本内容从UNICODE�~�码和另一�U�编码进行�{换，�q�种转换必须通过查表来进行�?/span>

如前所�q�ͼ�UNICODE 是用两个字节来表�C�Zؓ(f��)一个字�W�，他��d��可以�l�合�?5535不同的字�W�，�q�大概已�l�可以覆盖世界上所有文化的�W�号。如果还不够也没有关�p�，ISO已经准备了UCS-4�Ҏ(gu��)��Q�说��单了��是四个字节来表�C�Z��个字�W�，�q�样我们��可以组合出21亿个不同的字�W�出来（最高位有其他用途）�Q�这大概可以用到银河联邦成立那一天吧�Q?nbsp;

UNICODE 来到�Ӟ��一起到来的�q�有计算机网�l�的兴�v�Q�UNICODE 如何在网�l�上传输也是一个必��考虑的问题，于是面向传输的众�?UTF�Q�UCS Transfer Format�Q�标准出��C��Q�顾名思义�Q�UTF8��是每次8个位传输数据�Q�而UTF16��是每次16个位�Q�只不过��Z��传输时的可靠性，从UNICODE到UTF时�ƈ不是直接的对应，而是要过一些算法和规则来�{换�?/span>

受到�q�网�l�编�E�加持的计算机僧侣们都知道，在网�l�里传递信息时有一个很重要的问题，��是对于数据高低位的解读方式�Q�一些计��机是采用低位先发送的�Ҏ(gu��)��Q�例如我们PC机采用的 INTEL 架构�Q�而另一些是采用高位先发送的方式�Q�在�|�络中交换数据时�Q��ؓ(f��)了核对双方对于高低位的认识是否是一致的�Q�采用了一�U�很��便的�Ҏ(gu��)��Q�就是在文本��的开始时向对方发送一个标志符。如果之后的文本是高位在位，那就发�?FEFF"�Q�反之，则发�?FFFE"。不信你可以用二�q�制方式打开一个UTF-X格式的文�Ӟ��看看开头两个字节是不是�q�两个字节？

讲到�q�里�Q�我们再��Z��说说一个很著名的奇怪现象：(x��)当你�?windows 的记事本里新��Z��个文�Ӟ��输入"联�?两个字之后，保存�Q�关闭，然后再次打开�Q�你�?x��)发现这两个字已�l�消�׃��Q�代之的是几个�ؕ码！呵呵�Q�有��q�就是联通之所以拼不过�U�d��的原因�?/span>

其实�q�是因�ؓ(f��)GB2312�~�码与UTF8�~�码产生了编码冲撞的原因�?/span>

从网上引来一�D�从UNICODE到UTF8的�{换规则：(x��)

Unicode

UTF-8
0000 - 007F

0xxxxxxx

0080 - 07FF

110xxxxx 10xxxxxx

0800 - FFFF

1110xxxx 10xxxxxx 10xxxxxx

例如"�?字的Unicode�~�码�?C49�?C49�?800-FFFF之间�Q�所以要�?字节模板�Q?110xxxx 10xxxxxx 10xxxxxx。将6C49写成二进制是�Q?110 1100 0100 1001�Q�将�q�个比特��按三字节模板的分段�Ҏ(gu��)��分�ؓ(f��)0110 110001 001001�Q�依�ơ代替模板中的x�Q�得刎ͼ�(x��)1110-0110 10-110001 10-001001�Q�即E6 B1 89�Q�这��是其UTF8的编码�?nbsp;

而当你新��Z��个文本文件时�Q�记事本的编码默认是ANSI, 如果你在ANSI的编码输入汉字，那么他实际就是GB�p�d��的编码方式，在这�U�编码下�Q?联�?的内码是�Q?/span>

c1 1100 0001

aa 1010 1010

cd 1100 1101

a8 1010 1000

注意��C��吗？�W�一二个字节、第三四个字节的起始部分的都�?110"�?10"�Q�正好与UTF8规则里的两字节模板是一致的�Q�于是再�ơ打开��C��本时�Q�记事本��p��认�ؓ(f��)�q�是一个UTF8�~�码的文�Ӟ��让我们把�W�一个字节的110和第二个字节�?0��L��Q�我们就得到�?00001 101010"�Q�再把各位对齐，补上前导�?�Q�就得到�?0000 0000 0110 1010"�Q�不好意思，�q�是UNICODE�?06A�Q�也��是��写的字�?j"�Q�而之后的两字节用UTF8解码之后�?368�Q�这个字�W�什么也不是。这��是只有"联�?两个字的文�g没有办法在记事本里正常显�C�的原因�?nbsp;

而如果你�?联�?之后多输入几个字�Q�其他的字的�~�码不见得又恰好�?10�?0开始的字节�Q�这样再�ơ打开�Ӟ��C��本就不会(x��)坚持�q�是一个utf8�~�码的文�Ӟ��而会(x��)用ANSI的方式解��M��Q�这时�ؕ码又不出��C��?/span>

Drolca 2011-05-21 21:36 发表评论

hdu 2102

Drolca — Fri, 01 Jan 2010 14:21:00 GMT

#include <iostream>
using namespace std;
const int M=10;
char map[2][M][M];
bool vis[2][M][M];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

struct point
{
    int layer;
    int x,y;
    int time;
}Q[200];

bool BFS(int m,int n,int t)
{
    point now,next;
    now.layer=now.x=now.y=now.time=0;
    int Front=0;
    int Near=1;
    Q[Front]=now;
    vis[now.layer][now.x][now.y]=true;
    while(Front<Near)
    {
        now=Q[Front++];
        if(map[now.layer][now.x][now.y]=='P')
        {
            if(now.time<=t)
                return true;
            return false;
        }
        if(map[now.layer][now.x][now.y]=='#')
            now.layer=!now.layer;

        if(map[now.layer][now.x][now.y]=='P')
        {
            if(now.time<=t)
                return true;
            return false;
        }
        if(map[now.layer][now.x][now.y]=='*'||map[now.layer][now.x][now.y]=='#')
            continue;
        int k;
        for(k=0;k<4;k++)
        {
            next.layer=now.layer;
            next.time=now.time+1;
            next.x=now.x+dx[k];
            next.y=now.y+dy[k];
            if(!vis[next.layer][next.x][next.y]&&next.x>=0&&next.x<m&&next.y>=0&&next.y<n)
            {
                Q[Near++]=next;
                vis[next.layer][next.x][next.y]=true;
            }
        }

    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int m,n,t;
        scanf("%d%d%d",&m,&n,&t);
        int i,j,k;
        for(k=0;k<2;k++)
        {
            for(i=0;i<m;i++)
            {
                char s[M];
                scanf("%s",&s);
                for(j=0;j<n;j++)
                {
                    map[k][i][j]=s[j];
                    vis[k][i][j]=false;
                }
            }
        }
        if(BFS(m,n,t))
            printf("YES\n");
        else
            printf("NO\n");
    }
    system("pause");
    return 0;
}

Drolca 2010-01-01 22:21 发表评论

9*9数独游戏

Drolca — Fri, 01 Jan 2010 13:19:00 GMT

#include <iostream>
using namespace std;
const int M=10;
bool userow[M][M],usecol[M][M],useblock[M][M];
int map[M][M];

struct node{
    int x,y;
    int num;
}sudu[M*M];

int find(int x,int y)
{
    int row=x/3;
    int col=y/3;
    return 3*row+col;
}

bool dfs(int n,int cnt)
{
    if(n==cnt)return 1;
    int i;
    for(i=1;i<M;i++)
    {
        if(!userow[sudu[n].x][i]&&!usecol[sudu[n].y][i]&&!useblock[find(sudu[n].x,sudu[n].y)][i])
        {
            userow[sudu[n].x][i]=true;
            usecol[sudu[n].y][i]=true;
            useblock[find(sudu[n].x,sudu[n].y)][i]=true;
            sudu[n].num=i;
            if(dfs(n+1,cnt))
                return 1;
            userow[sudu[n].x][i]=false;
            usecol[sudu[n].y][i]=false;
            useblock[find(sudu[n].x,sudu[n].y)][i]=false;
            sudu[n].num=0;

        }
    }
    return 0;

}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(userow,false,sizeof(userow));
        memset(usecol,false,sizeof(usecol));
        memset(useblock,false,sizeof(useblock));

        int i,j;
        int cnt=0;
        for(i=0;i<M-1;i++)
        {
            char mess[M];
            scanf("%s",&mess);
            for(j=0;j<M-1;j++)
            {
                map[i][j]=mess[j]-'0';
                if(map[i][j])
                {
                    userow[i][map[i][j]]=true;
                    usecol[j][map[i][j]]=true;
                    useblock[find(i,j)][map[i][j]]=true;
                }
                else
                {
                    sudu[cnt].x=i;
                    sudu[cnt].y=j;
                    sudu[cnt].num=0;
                    cnt++;
                }

            }

        }

        dfs(0,cnt);

        for(i=0;i<cnt;i++)
            map[sudu[i].x][sudu[i].y]=sudu[i].num;

        for(i=0;i<M-1;i++){
            for(j=0;j<M-1;j++)
                printf("%d",map[i][j]);
            printf("\n");
        }
    }

    return 0;
}

Drolca 2010-01-01 21:19 发表评论

Drolca — Sat, 21 Nov 2009 13:08:00 GMT
     摘要: #include using namespace std;const int maxn=200;const int INF=1000000;int g[maxn][maxn];int f[maxn][maxn];int r[maxn][maxn];in...  阅读全文

Drolca 2009-11-21 21:08 发表评论

pku 3744 Scout YYF I

Drolca — Mon, 05 Oct 2009 10:48:00 GMT

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=12;
int n;
double p;
struct matrix
{
    double m[2][2];
};
int mine[maxn];
matrix operator*(const matrix&a,const matrix&b)
{
    matrix tmp;
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            tmp.m[i][j]=0;
            for(k=0;k<2;k++)
                tmp.m[i][j]+=a.m[i][k]*b.m[k][j];
        }
    return tmp;
}

matrix power(int k)
{
    matrix tmp,res;
    matrix A;
    A.m[0][0]=p,A.m[0][1]=1-p,A.m[1][0]=1,A.m[1][1]=0;
    matrix B;
    B.m[0][0]=1,B.m[0][1]=0,B.m[1][0]=0,B.m[1][1]=1;
    if(k==0)
        return B;
    if(k==1)
        return A;
    else
    {
        tmp=power(k/2);
        res=tmp*tmp;
        if(k%2==1)
            res=res*A;
        return res;
    }
}

void slove(int n,double p)
{
    double a=1,b=0;
    int i;
    for(i=0;i<n;i++)
        scanf("%d",&mine[i]);
    sort(mine,mine+n);

    double f2=1.0,f1=0.0;
    int now=1;
    for(i=0;i<n;i++)
    {
        if((mine[i]-1)-now>=0)
        {
            matrix tmp=power(mine[i]-1-now);
            f2=(tmp.m[0][0]*f2+tmp.m[0][1]*f1)*(1-p);
            f1=0;
            now=mine[i]+1;
        }
        else
        {
            printf("%.7lf\n",0.0);
            return;
        }
    }
    printf("%.7lf\n",f2);
}

int main()
{
    while(scanf("%d %lf",&n,&p)!=EOF)
        slove(n,p);
    return 0;
}

Drolca 2009-10-05 18:48 发表评论

hdu 2292 Minimum Heap

Drolca — Mon, 05 Oct 2009 03:19:00 GMT

#include <iostream>
using namespace std;

const int maxn=1005;
__int64 n,m;
__int64 F[maxn];
int c[maxn][maxn];

int cal(int n)
{
    int t = 1;
    while (t <= n) t = t * 2 + 1;
    t = (t - 1) / 2;
    t = (t - 1) / 2;
    int sum = n - 1 - t;
    if (sum > 2 * t + 1) {
        sum = 2 * t + 1;
    }
    return sum;
}

void calc_c() {
    for (int i = 0; i < maxn; i++)
    {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
        }
    }
}

__int64 slove(int n)
{
    if(F[n])
        return F[n];
    if(n==0||n==1)
        return 1;
    int left=cal(n);
    int right=(n-1)-left;
    return F[n]=( (slove(left)*slove(right) )%m )*(__int64)c[n-1][left]%m;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(F,0,sizeof(F));
        scanf("%I64d%I64d",&n,&m);
        calc_c();
        __int64 ans=slove(n);
        printf("%I64d\n",ans);
    }
    return 0;
}

Drolca 2009-10-05 11:19 发表评论