acleast

     摘要: 题目大意：        输入给出三种操作：              1、add     x     y&n...  阅读全文

先说一下逆序数的概念：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那末它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。
如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——这是北大《高等代数》上的定义。

题意：给出一个排列，排列中的数各不相同，都是从0到n-1，要求得到的是一个最短的逆序的长度，这些子序列是转动原来的序列得到的。
一种最基本的做法：就是枚举每一个点求出这个点前面比它的数的个数，然后加起来。还好这种做法没有超时，这里有一种O（nlog(n)）的算法
就是利用点树。我在网上找过，网上关于点树的资料很少，百度百科里面有一篇。还有就是http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html
不过好像是一个人写的. @_@    ^_^
以下借用了他的实现

 

题目大意：
　　有N头牛，站在X轴上，没有共点的情况，每个牛有一个听力值V(i)，他们交流所消耗的最少volume为abs（X（i）-（X（j）））*MAX{V（i）,V（j）}
         最后再求总和。
由于数据量最大为20000,显然O(n^2)的算法会超时。先按V值进行从小到大排序可解决MAX的问题，最后就是对每头牛求V值小于他的权值了。
对于第i个牛，在0~i-1中，用两个数状数组，a表示坐标小于x[i]的个数，b表示坐标小于x[i]的牛的坐标之和，另外c表示0~i-1中所有牛的坐标之和。

 1long long solve()
 2{
 3    long long ans=0,c=dd[0].id;
 4
 5    update(a,dd[0].id,1);
 6    update(b,dd[0].id,dd[0].id);
 7    
 8    long long p,q;
 9    for(int i=1;i<n;i++){
10        p=get_sum(a,dd[i].id);
11        q=get_sum(b,dd[i].id);
12        ans+=dd[i].v*(dd[i].id*p-q+(c-q)-dd[i].id*(i-p));
13        update(a,dd[i].id,1);
14        update(b,dd[i].id,dd[i].id);
15        c+=dd[i].id;
16    }
17    return ans;
18}

     摘要: 题目大意：      有N个工件要在M个机器上加工，有一个N*M的矩阵描述其加工时间。      同一时间内每个机器只能加工一个工件，问加工完所有工件后，使得平均加工时间最小。   将工件作为二分图中X部的点，总共N个。   将每个机器拆成...  阅读全文

     摘要: 这是我有史以来写得最长的一个程序，前段时间就看了这个题，在网上搜了一下算法，当时看得还有点不太明白，大牛也都说这题代码太长不好写，开始写了一些，后面发现不会写了，就放下了。昨天又来看这个题，居然写出来了，不过还是花了我一个晚上的时间来调试，开始交一次结果就RE了，后来在网上找来了官方数据一个一个的运行才发现找圈DFS的时候陷入了死循环，加了一个标志变量，还是WA，后来反复看解思路才知道换边的时候每...  阅读全文

题目大意：从一点经过所有的边两次，且两次的方向不同，又回到起始点，典型的欧拉回路题

 1#include<iostream>
 2using namespace std;
 3#define N 10005
 4struct node{
 5    int v;
 6    bool flag;
 7    node *next;
 8};
 9
10node *dd[N];
11node set[10*N];
12int n,m;
13
14void init()
15{
16    memset(dd,0,sizeof(dd));
17    scanf("%d%d",&n,&m);
18    int u,v;
19    for(int i=1;i<=m;i++){
20        scanf("%d%d",&u,&v);
21        set[i].v=v;
22        set[i].flag=false;
23        set[i].next=dd[u];
24        dd[u]=&set[i];
25
26        set[i+m].v=u;
27        set[i+m].flag=false;
28        set[i+m].next=dd[v];
29        dd[v]=&set[i+m];
30    }
31}
32
33void dfs(int k)
34{
35    node *p=dd[k];
36    while(p){
37        if(p->flag==false){
38            p->flag=true;
39            dfs(p->v);
40        }
41        p=p->next;
42    }
43    printf("%d\n",k);
44}
45
46int main()
47{
48    init();
49    dfs(1);
50    return 0;
51}

这是一道典型的欧拉回路的题，第一次做这种题，参考了一下别人的代码，结果WA了一晚上，最后照着别人的代码一步一步的改，最后才发现有存在x==y的情况
真是杯具，浪费了一晚上的时间

题目大意：给定一个二叉树，求让它成为孩子结点值不大于父亲结点值，同时左孩子结点值小于右孩子结点值。
用广搜建立二叉树，再后序遍历，求最长不下降子序列，我做了一点变化，将左右孩子交换后先序遍历后求最长不上升子序列。
开始超时了，后来把队列用数组实现就行了，不过注意一下没有右孩子时，左孩子可以和父亲结点值相等。

     摘要: 前段时间学会了trie树之后，今天终于学习了一下AC自动机，这个还是挺难学的，现在我还是有点不太懂，参照了网上的代码才把这道题给Ａ了。让我自己背着写出来还不一定会写。这里有一篇比较好的介绍AC自动机的文章http://www.cppblog.com/mythit/archive/2009/04/21/80633.html先看一下这道题吧，大意是给我们一部字典和一个模式串，让我们求出字典中有多少个单...  阅读全文

又贡献了一版的WA和TLE一道题，本来不是很难，但是由于初始化有问题，一直RE。
先说说这道题的思路吧，两次dfs进行缩点，缩点之后再深搜一次找出最长路径与缩点之后的顶点数相比，
相等则输出Yes,否则输出No。