久久久久久国产精品免费免费,国产精品亚洲综合久久,欧美日韩精品久久久久

END

CisJiong — Sat, 04 Dec 2010 12:31:00 GMT

END. IF YOU LOVE ACM,JUST DO IT WHATEVER OTHER SAY.

CisJiong 2010-12-04 20:31 发表评论

KM模板

CisJiong — Sat, 26 Jun 2010 05:39:00 GMT

摘要: KM�Q�解��x��大权匚w��问题。最��权匚w��的办法是用一个很大的�?当前�Ҏ��|��而不是直接对�Ҏ��取反(�q�样只能处理左右点相�{�的完全二分图，即K(n, n)).HDU2426 Interesting Housing Problemhttp://acm.hdu.edu.cn/showproblem.php?pid=2426�l�出n个�h对m个房间的喜欢度，求��d��Ƣ度最大的匚w��。赤裸裸KM求最大权�Q�本题无视负权�?... 阅读全文

CisJiong 2010-06-26 13:39 发表评论

FOJ1919 K-way Merging sort(java+dfs+map)

CisJiong — Thu, 03 Jun 2010 16:55:00 GMT

http://acm.fzu.edu.cn/problem.php?pid=1919
大意��是求题目所定义的K合�ƈ排序需要交换的�ơ数�?br>记忆化搜�?br>

1、n2、n≥k�Ӟ��n分成k堆，有n%k堆的f(n/k+1,k)
3、有k-n%k堆的f(n/k,k)�Q?
4、k堆合�q�时�Q�最大比较次��Cؓ�Q�每�ơ取最��值都是让k堆比较取最��，用k-1�ơ，�ȝ��?k-1)*(n-k+1)
5、最后剩下k-1堆含一个元素的堆，�?k-1)*(k-2)/2�ơ比较�?

java HashMap�?br>新徏HashMap�Q�Map map=new HashMap();
插入键��|��map.put(n,tmp)
查找键是否存在：map.containsKey(n)�Q�返回boolean型�?br>�q�回键��|��map.get(n)

Java Map接口扩展�Q?br>http://www.javaeye.com/topic/421014

CisJiong 2010-06-04 00:55 发表评论

CisJiong — Sun, 30 May 2010 14:42:00 GMT

��法��D��2.3-7�Q?br>题目��是标题�Q�要求在nlgn内完成。从csdn上找到答案：
先排序，然后比较�Q?/p>

int i=0,j=n-1;
int b=0;
while (i<j)
{
    int k=s[i]+s[j];
    if (k==x) b=1,break;
    else if (k<x) i++;
    else j--;
}
if (b) printf("Y\n");
else printf("N\n");

nlgn+n=nlgn,卛_��以在规定旉��内完成�?br>
同样道理�Q�找三个��C��和也可以在n^2旉��内完成�?br>sum=a[i]+b[i]+c[i];
�{��h找两个数其和为s=sum-a[i];
共有n个，每个查找为线性时间n�Q?br>nlgn+n^2=n^2�?

FOJ 1707 �{�式数量
http://acm.fzu.edu.cn/problem.php?pid=1707

CisJiong 2010-05-30 22:42 发表评论

FOJ1914 Funny Positive Sequence

CisJiong — Sun, 30 May 2010 02:13:00 GMT

http://acm.fzu.edu.cn/problem.php?pid=1914
题目大意:
��是�l�出一个序列，��它循环左移n�ơ可以得到n个不同的序列�Q?br>求这n个序列中能够生成题目所定义的序列个数�?br>
可以先算��Z��满��条�g的序列，相减卛_��?br>不满��的序列肯定是因为由非正数的存在�Q�所以对每个非正敎ͼ�向前搜烦�q�篏加直到和大于0�Q?br>则以�q�个区间内所有数开始的序列均不满��条�g�?br>

CisJiong 2010-05-30 10:13 发表评论

PKU1837 Balance(DP)

CisJiong — Fri, 28 May 2010 09:53:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1837
�l�出一个称所有钩子位�|�（数组pos存）�Q�一些砝码的重量�Q�数�l�w存）�Q�求全部砝码要��用�ƈ使称�q��的放法��L��?br>力矩=�?距离
用dp[i][k]表示前i�U�砝码��生力矩�ؓk的放法，考虑�W�i+1�U�砝码，有dp[i+1][k+w[i]*pos[j]]=sigma(dp[i][k])�?br>三重循环�I��D�Q�最后输出dp[n][0]卛_��?br>动态规划，真的很神奇！

CisJiong 2010-05-28 17:53 发表评论

POJ1094 Sorting It All Out(拓扑排序)

CisJiong — Sat, 22 May 2010 15:16:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
拓扑排序�Q�能��定��序的情冉|��在拓扑排序时每个时刻入度�?的顶点只有一个�?br>

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

int n,degree[30],res[30];
struct Node
{
    int pos;
    Node *next;
}node[30];

void insert(char a,char b)
{
    int aa=a-'A';
    int bb=b-'A';
    Node *p=new Node;
    p->pos=bb;
    p->next=node[aa].next;
    node[aa].next=p;
}

int top_sort()
{
    bool flag=false;
    int in[30]={0};
    int i,tmp,top,sta[100];
    for(i=0,top=0;i<n;i++)
    {
        in[i]=degree[i];
        if(in[i]==0)    sta[top++]=i;
    }
    if(top>1)    flag=true;
/*    for(i=0;i        printf("%d ",in[i]);
    puts("");*/
    for(i=0;i<n;i++)
    {
        if(top==0)    return -1;
        if(top>1)    flag=true;
        tmp=sta[--top];
        res[i]=tmp;
        Node *p=node[tmp].next;
        while(p)
        {
            if(--in[p->pos]==0)
                sta[top++]=p->pos;
            p=p->next;
        }
    }
    if(flag)    return 0;
    return 1;
}

int main()
{
    bool flag,incon;
    int i,m,num=0,tmp;
    char str[4];
    ifstream input;
    input.open("in.txt");
//    while(input>>n>>m)
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)    break;
        flag=incon=false;
        memset(degree,0,sizeof(degree));
        for(i=0;i<n;i++)
            node[i].next=NULL;
        for(i=1;i<=m;i++)
        {
            scanf("%s",str);
        //    input>>str;
            if((!flag)&&(!incon))
            {
                degree[str[2]-'A']++;
                 insert(str[0],str[2]);
                tmp=top_sort();
                if(tmp==-1)
                {
                    num=i;
                    incon=true;
                }
                else if(tmp==1)
                {
                    num=i;
                    flag=true;
                }
            }
        }
        if(flag)
        {
            printf("Sorted sequence determined after %d relations: ",num);
            for(i=0;i<n;i++)
                printf("%c",'A'+res[i]);
            puts(".");
        }
        else if(incon)    printf("Inconsistency found after %d relations.\n",num);
        else    printf("Sorted sequence cannot be determined.\n");
    }
    system("pause");
    return 0;
}

CisJiong 2010-05-22 23:16 发表评论

FOJ1084 Three powers(高精�?

CisJiong — Tue, 11 May 2010 12:53:00 GMT

http://acm.fzu.edu.cn/problem.php?pid=1084
a[n]>Sa[i](i

import java.util.*;
import java.math.BigInteger;
public class Main
{
    public static void main(String[] args)
    {
        Scanner cin=new Scanner(System.in);
        BigInteger num;
        int[] res=new int[100];
        int len;
        while(cin.hasNextBigInteger())
        {
            num=cin.nextBigInteger();
            if(num.signum()==0) break;
            num=num.subtract(BigInteger.valueOf(1));
            if(num.signum()==0)
            {
                System.out.println("{ }");
                continue;
            }
            len=0;
            while(num.bitLength()>0)
            {
                res[len++]=num.bitLength();
                num=num.clearBit(res[len-1]-1);
            }
            System.out.print("{");
            for(int i=len-1;i>0;i--)
                 System.out.print(" "+BigInteger.valueOf(3).pow(res[i]-1)+",");
            System.out.println(" "+BigInteger.valueOf(3).pow(res[0]-1)+" }");
        }
    }
}

CisJiong 2010-05-11 20:53 发表评论

FOJ1492 地震预测

CisJiong — Sat, 08 May 2010 17:07:00 GMT

http://acm.fzu.edu.cn/problem.php?pid=1492
TLE了很多，以前向别��了代码看不懂�Q�今晚重做，一�ơAC。主要思想是记录排序后盔R��的元素�ƈ及时更新�?/p>

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

struct Node
{
    int pos,val;
    bool operator<(const Node &a) const
    {
        return val<a.val;
    }
}node[100001];
int pos[100001],alloc[100001][2];//pos 原来元素�Q?-n)在排序后的位�|�，alloc排序后相��d��素在原序列的位置

inline int min(int a,int b)
{
    return a>b ? b : a;
}

int main()
{
    int i,n,res,t1,t2;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&node[i].val);
            node[i].pos=i;
        }
        sort(node+1,node+n+1);
        node[0].pos=0,node[0].val=100000000;
        node[n+1].pos=n+1,node[n+1].val=100000000;
        pos[0]=0,pos[n+1]=n+1;
        for(i=1;i<=n;i++)
        {
            pos[node[i].pos]=i;
            alloc[node[i].pos][0]=node[i-1].pos;
            alloc[node[i].pos][1]=node[i+1].pos;
        }
        res=node[pos[n]].val;
        for(i=1;i<n;i++)
        {
            t1=abs(node[pos[i]].val-node[pos[alloc[i][0]]].val);
            t2=abs(node[pos[i]].val-node[pos[alloc[i][1]]].val);
            res+=min(t1,t2);
            alloc[alloc[i][0]][1]=alloc[i][1];
            alloc[alloc[i][1]][0]=alloc[i][0];
        }
        printf("%d\n",res);
    }
    return 0;
}

CisJiong 2010-05-09 01:07 发表评论

CisJiong — Sat, 01 May 2010 13:58:00 GMT

摘要: http://acm.pku.edu.cn/JudgeOnline/problem?id=1032�l�出n�Q�把n分解��q�不相同��C��和，使之乘积最大。贪心，Discuss里面的思�\�Q�把n分解��Z��2开始的�q�箋整数�Q�如果有多，则从高位开始依�ơ加1。如26�Q�我们得�?+3+4+5+6�Q�此时还剩余6�Q?6-2-3-4-5-6�Q�，接下来从高位依次加一�Q�变�?+4+5+6+7�Q�还�?�Q��l�加�l�最大的7�Q�最后答�?.. 阅读全文

CisJiong 2010-05-01 21:58 发表评论