poj 1455 Crazy tea party

  这道题第一眼看去很难,其实不然,短短几行代码就搞定了。
  说一下大概思路,如果是排成一排的n个人,如 1 2 3 4 5 6 7 8 我们要变成 8 7 6 5 4 3 2 1 需要交换 28次,找规律的话就是 n*(n-1)/2,但这道题是一个圈,要让他们顺序变反的话不一定1要在8的位置上去,4 3 2 1 8 7 6 5 这样也是反的,我们只要把n个人分成两部分,然后按拍成一条线的方法来出来两部分就OK了。

Continue reading

hdoj 4768 Flyer

题目意思很容易理解,学校有n个社团,每个社团只给编号从a到b 的发传单,而且只给隔了c的人发,问最后谁收到的传单是单数,输出他的编号和收到的传单数量。

昨天做这题的时候看见很多人过了,感觉不会很难,但是打死都想不出来,看了别人的思路,一下子就想通了。这里我简要说一下,用二分,我们可以很容易求出一段区间里的总的传单数,因为保证最多有一个是单数,我们就看单数在哪边。

下面是java代码,刚开始学java,代码不是很简洁。

import java.util.Scanner;

public class Main {
    static long[] a = new long[20005];
    static long[] b = new long[20005];
    static long[] c = new long[20005];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            int n = cin.nextInt();
            for (int i = 1; i <= n; i++) {
                a[i] = cin.nextLong();
                b[i] = cin.nextLong();
                c[i] = cin.nextLong();
            }
            long r = Integer.MAX_VALUE, l = 0;
            while (l < r) {
                long mid = (l+r)>>1;
                long sum = 0;
                for (int i = 1; i <= n; i++) {
                    long minnum;
                    if (mid <= b[i])
                        minnum = mid;
                    else 
                        minnum = b[i];
                    if (minnum >= a[i]) {
                        sum += (minnum - a[i])/c[i] + 1;
                    }
                }
                if (sum%2 == 1)
                    r = mid;
                else l = mid+1;
            }
            if (l == Integer.MAX_VALUE) {
                System.out.println("DC Qiang is unhappy.");
                continue;
            }
            long ans = 0;
            for (int i = 1; i <= n; i++) {
                if (l >= a[i] && l <= b[i]) {
                    if ((l - a[i]) % c[i] == 0)
                        ans += 1;
                }
            }
            System.out.println(l + " " + ans);
        }
        cin.close();
    }
}

light oj 1258 – Making Huge Palindromes(KMP)


题目链接

题意:

     给你一个字符串,在字符串尾部加上一些字符,使这个字符串变成一个回文串(正反读都一样的字符串),求该回文串的最小长度。

思路:

     在light oj里这个题目是属于KMP分类的,但乍看好像不是kmp,因为只有一个字符串。要想的到一个回文串,把该字符串翻转接到原串后面必然是一个回文串,但并不一定是最短的。我们必须考虑怎么把两个串尽量融合在一起,这就要看翻转串的前段与原串的后段有多少是匹配的了,这里就用到了KMP算法。

代码:

//2013-05-13-20.01
#include <stdio.h>
#include <string.h>
const int maxn = 1000005;
char a[maxn];
char b[maxn];
int f[maxn];


void getfail()
{
    int l = strlen(b);
    f[0] = 0;
    f[1] = 0;
    for (int i = 1; i < l; i++)
    {
        int j = f[i];
        while (j && b[i] != b[j])
            j = f[j];
        if (b[i] == b[j])
            f[i+1] = j+1;
        else
            f[i+1] = 0;
    }
}


int getans()
{
    int la = strlen(a);
    int lb = strlen(b);
    getfail();
    int j = 0;
    for (int i = 0; i < la; i++)
    {
        while (j && a[i] != b[j])
            j = f[j];
        if (b[j] == a[i])
            j++;
    }
    return la + lb - j;
}


int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        scanf("%s", a);
        int l = strlen(a);
        for (int j = 0; j < l; j++)
        {
            b[l-j-1] = a[j];
        }
        b[l] = '\0';
        printf("Case %d: %d\n", i, getans());
    }
    return 0;
}


poj 2362 hdoj 1518 Square(搜索)


题目链接


大致题意:


给定一堆不定长度的小棒子,问他们能否构成一个正方形。


 


解题思路:


POJ1011的热身题,DFS+剪枝


 


本题大致做法就是对所有小棒子长度求和sum,sum就是正方形的周长,sum/4就是边长side。


问题就转变为:这堆小棒子能否刚好组合成为4根长度均为side的大棒子


 


不难了解,小棒子的长度越长,其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少,这就是灵活性的体现。


由此,我们首先要对这堆小棒子降序排序,从最长的棒子开始进行DFS


 


剪枝,有3处可剪:


1、  要组合为正方形,必须满足sum%4==0;


2、  所有小棒子中最长的一根,必须满足Max_length <= side,这是因为小棒子不能折断;


3、  当满足条件1、2时,只需要能组合3条边,就能确定这堆棒子可以组合为正方形。


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

bool vis[21];
int stick[21];
int n;
int side;

bool cmp(int a, int b)
{
    return a > b;
}

bool dfs(int num, int len, int s)//s为搜索起点
{
    if (num == 4)
        return true;
    for (int i = s; i < n; i++)
    {
        if (vis[i])
            continue;
        vis[i] = true;
        if (len+stick[i] < side)
        {
            if (dfs(num, len+stick[i], i))
            //这里解释游戏为什么有搜索起点这一变量,只有这用到了,如果len+stick[i] > side了
            //因为是非升序,len+stick[i-1] > side必然成立,从0开始就是浪费时间
                return true;
            /*开始这里我直接 return dfs(num, len+stick[i], i);貌似这样也可以,
            但的的确确是错的,直接返回会导致我们少判很多种情况*/
        }
        else if (len+stick[i] == side)
        {
            if (dfs(num+1, 0, 0))
                return true;
            //这里同上
        }
        vis[i] = false;
    }
    return  false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &stick[i]);
            sum += stick[i];
        }
        side = sum/4;
        sort(stick, stick+n, cmp);
        if (sum % 4 || side < stick[0])
        //这里也可以去掉一些情况
        {
            puts("no");
            continue;
        }
        memset(vis, false, sizeof(vis));
        if (dfs(1, 0, 0))
            puts("yes");
        else
            puts("no");
    }
    return 0;
}


hdoj 1028/poj 2704 Pascal’s Travels(记忆化搜索||dp)


题目链接

题意

       有个小球,只能向右边或下边滚动,而且它下一步滚动的步数是它在当前点上的数字,如果是0表示进入一个死胡同。求它从左上角到右下角到路径数目。

注意, 题目给了提示了,要用64位的整数。

记忆化搜索方法

#include <stdio.h>
#include <string.h>
#define ll __int64
int n;
ll vis[36][36];
char board[36][36];

ll dfs(int x,int y)
{
    if(x==n-1&&y==n-1)
        return 1;
    if(board[x][y]=='0')
        return 0;
    if(vis[x][y])
        return vis[x][y];
    if(x+board[x][y]-'0'<n)
        vis[x][y]+=dfs(x+board[x][y]-'0',y);
    if(y+board[x][y]-'0'<n)
        vis[x][y]+=dfs(x,y+board[x][y]-'0');
    return vis[x][y];
}

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        if(n == -1)
            break;
        for (int i = 0; i < n; i++)
            scanf("%s",board[i]);
        memset(vis, 0, sizeof(vis));
        printf("%I64d\n", dfs(0,0));
    }
    return 0;
}


dp方法

#include <stdio.h>
#include <string.h>
#define ll __int64

ll vis[50][50];
char board[50][50];

int main()
{
    int i,j,n;
    while (scanf("%d",&n)!=EOF)
    {
        if(n == -1)
            break;
        for (i = 0; i < n; i++)
            scanf("%s",board[i]);
        memset(vis, 0, sizeof(vis));
        vis[0][0] = 1;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if(board[i][j] == '0')
                    continue;
                vis[i+board[i][j]-'0'][j] += vis[i][j];
                vis[i][j+board[i][j]-'0'] += vis[i][j];
            }
        }
        printf("%I64d\n", vis[n-1][n-1]);
    }
    return 0;
}


hdoj 1907


题目链接

这是一道博弈的题,准确说是尼姆博弈,只要判断各项的异或值即可。

代码

#include <stdio.h>
const int maxn = 5000;

int x[maxn];

int main()
{
    int t, n, tmp;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d",&x[i]);
            if (x[i] == 1)
                cnt++;
        }
        if (cnt == n)
        {
            if (cnt % 2)
                puts("Brother");
            else
                puts("John");
            continue;
        }
        tmp = x[1];
        for (int i = 2; i <= n;i++)
        {
            tmp ^= x[i];
        }
        if (n == 1)
        {
            puts("John");
            continue;
        }
        if (tmp)
            puts("John");
        else
            puts("Brother");
    }
    return 0;
}


hdoj 1520 Anniversary party(树形dp)


题目链接

   按照等级我们可以建一颗树,如图

      我们可以把一个节点当做一个人,每个节点都有一个权重。按照题目意思,如果我们取了某个节点,那么他的父节点和子节点都是不能取的。按要求选取节点,使得选取节点的权重和最大。

     DP,no表示不选择i点时,i点及其子树能选出的最多人数,is表示选择i点时,i点及其子树的权值和最大。

状态转移方程:

—对于叶子节点 dp[k].no = 0, dp[k].no = a[k].v

—对于非叶子节点i,

—dp[i].no = ∑max(dp[j][0], dp[j][1]) (j是i的儿子)

—dp[i].is = v + ∑dp[j].no (j是i的儿子) 

代码:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

struct node
{
    int v;
    int is, no;
    vector<int> son;
}a[6010];

bool f[6010];

void dp(int x)
{
    int t;
    for (unsigned int i = 0; i < a[x].son.size(); i++)
    {
        t = a[x].son[i];
        dp(t);
        a[x].is += a[t].no;
        a[x].no += max(a[t].no, a[t].is);
    }
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i].v);
            a[i].son.clear();
            a[i].is = a[i].v;
            a[i].no = 0;
        }
        int son, fa;
        memset(f, 0, sizeof(f));
        while (scanf("%d %d",&son, &fa) && son+fa)
        {
            a[fa].son.push_back(son);
            f[son] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            if (f[i] == false)
            {
                dp(i);
                printf("%d\n",max(a[i].is, a[i].no));
                break;
            }
        }
    }
    return 0;
}


poj 并查集小结



并查集小结


并查集大体分为三个:普通的并查集,带种类的并查集,扩展的并查集(主要是必须指定合并时的父子关系,或者统计一些数据,比如此集合内的元素数目。)



POJ-1182


经典的种类并查集


POJ-1308


用并查集来判断一棵树。。注意空树也是树,死人也是人。


POJ-1611


裸地水并查集


POJ-1703


种类并查集


POJ-1988


看上去似乎和种类并查集无关,但其实仔细想想,就是种类并查集。。。

只不过是种类数目无穷大,通过合并,可以确定两个物品之间的种类差(即高度差)


POJ-2236


裸地并查集,小加一点计算几何


POJ-2492


裸地种类并查集


POJ-2524


又是裸地并查集


POJ-1456


常规思想是贪心+堆优化,用并查集确实很奇妙。。。下面的文章中有详细介绍。


POJ-1733


种类并查集,先要离散化一下,不影响结果。。。


HDU-3038


上一道题的扩展,也是种类并查集,种类无穷大。。。。


POJ-1417


种类并查集,然后需要背包原理来判断是否能唯一确定“好人”那一堆


POJ-2912


baidu的题,AC了,不过有点乱,有时间【【【再看看】】】


ZOJ-3261   NUAA-1087


逆向使用并查集就可以了。。。


POJ-1861 
POJ-2560


Kruskal并查集



 


light oj 1231-1232 – 1233- Coin Change 背包


题目链接

In a strange shop there are n types of coins of value A1, A2 … AnC1, C2, … Cn denote
the number of coins of value A1, A2 … An respectively. You have to find the number of ways you can make K using the coins.

For example, suppose there are three coins 1, 2, 5 and we can use coin 1 at most 3 times, coin 2 at most 2 times and coin 5 at most 1 time. Then if K = 5 the possible ways are:

1112

122

5  ………………………………

暂时到半懂不懂也没办法讲明白,就不误人子弟了,直接贴代码了。

#include <stdio.h>
#include <string.h>
const int mod = 100000007;
int dp[1005];
int coin[55];
int cnt[55];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &coin[i]);
        }
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &cnt[j]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = k; j >= 0; j--)
            {
                for (int l = 1; l <= cnt[i]; l++)
                {
                    if (j - l*coin[i] >= 0)
                    dp[j] += dp[j-coin[i]*l];
                }
            }
            for (int j = 0; j <= k; j++)
                dp[j] %= mod;
        }
        printf("Case %d: %d\n", tc, dp[k]);
    }
    return 0;
}


如果说把第一题看做01背包的话,这一题就是完全背包了 

#include <stdio.h>
#include <string.h>
const int mod = 100000007;
int dp[10050];
int coin[105];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &coin[i]);
        }

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = coin[i]; j <= k; j++)
            {
                dp[j] += dp[j-coin[i]];
                dp[j] %= mod;
            }
        }
        printf("Case %d: %d\n", tc, dp[k]);
    }
    return 0;
}

第三题又是完全背包

#include <stdio.h>
#include <string.h>

int dp[100005];
int coin[101];
int cnt[101];
int used[1000101];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    for (int ca = 1; ca <= t; ca++)
    {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &coin[i]);
        }
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &cnt[j]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            memset(used, 0, sizeof(used));
            for (int j = coin[i]; j <= k; j++)
            {
                if (!dp[j] && dp[j-coin[i]] && used[j-coin[i]] < cnt[i])
                {
                    ans++;
                    used[j]=used[j-coin[i]]+1;
                    dp[j] = 1;
                }
            }
        }
        printf("Case %d: %d\n", ca, ans);
    }
    return 0;
}


poj dp 合集



1015 Jury Compromise

1029 False coin

1036 Gangsters

1037 A decorative fence

1038 Bugs Integrated, Inc.

1042 Gone Fishing

1050 To the Max                                                                                        解题报告

1062 昂贵的聘礼

1074 Parallel Expectations

1080 Human Gene Functions

1088 滑雪                                                                                                   解题报告

1093 Formatting Text

1112 Team Them Up!

1141 Brackets Sequence

1143 Number Game

1157 LITTLE SHOP OF FLOWERS

1159 Palindrome

1160 Post Office

1163 The Triangle

1170 Shopping Offers

1178 Camelot

1179 Polygon

1180 Batch Scheduling

1185 炮兵阵地                                                                                          
解题报告

1187 陨石的秘密

1189 钉子和小球

1191 棋盘分割

1192 最优连通子集

1208 The Blocks Problem

1239 Increasing Sequences

1240 Pre-Post-erous!

1276 Cash Machine

1293 Duty Free Shop

1322 Chocolate

1323 Game Prediction

1338 Ugly Numbers

1390 Blocks

1414 Life Line

1432 Decoding Morse Sequences

1456 Supermarket

1458 Common Subsequence

1475 Pushing Boxes

1485 Fast Food

1505 Copying Books

1513 Scheduling Lectures

1579 Function Run Fun

1609 Tiling Up Blocks

1631 Bridging signals

1633 Gladiators

1635 Subway tree systems

1636 Prison rearrangement

1644 To Bet or Not To Bet

1649 Market Place

1651 Multiplication Puzzle

1655 Balancing Act

1661 Help Jimmy

1664 放苹果                                                                                             解题报告

1671 Rhyme Schemes

1682 Clans on the Three Gorges

1690 (Your)((Term)((Project)))

1691 Painting A Board

1692 Crossed Matchings

1695 Magazine Delivery

1699 Best Sequence

1704 Georgia and Bob

1707 Sum of powers

1712 Flying Stars

1714 The Cave

1717 Dominoes

1718 River Crossing

1722 SUBTRACT

1726 Tango Tango Insurrection

1732 Phone numbers

1733 Parity game

1737 Connected Graph

1740 A New Stone Game

1742 Coins

1745 Divisibility

1770 Special Experiment

1771 Elevator Stopping Plan

1776 Task Sequences

1821 Fence

1837 Balance

1848 Tree

1850 Code

1853 Cat

1874 Trade on Verweggistan

1887 Testing the CATCHER

1889 Package Pricing

1920 Towers of Hanoi

1926 Pollution

1934 Trip

1936 All in All

1937 Balanced Food

1946 Cow Cycling

1947 Rebuilding Roads

1949 Chores

1952 BUY LOW, BUY LOWER

1953 World Cup Noise

1958 Strange Towers of Hanoi

1959 Darts

1962 Corporative Network

1964 City Game

1975 Median Weight Bead

1989 The Cow Lineup

2018 Best Cow Fences

2019 Cornfields

2029 Get Many Persimmon Trees

2033 Alphacode

2039 To and Fro

2047 Concert Hall Scheduling

2063 Investment

2081 Recaman’s Sequence

2082 Terrible Sets

2084 Game of Connections

2127 Greatest Common Increasing Subsequence

2138 Travel Games

2151 Check the difficulty of problems

2152 Fire

2161 Chandelier

2176 Folding

2178 Heroes Of Might And Magic

2181 Jumping Cows

2184 Cow Exhibition

2192 Zipper

2193 Lenny’s Lucky Lotto Lists

2228 Naptime

2231 Moo Volume

2250 Compromise

2279 Mr. Young’s Picture Permutations

2287 Tian Ji — The Horse Racing

2288 Islands and Bridges

2292 Optimal Keypad

2329 Nearest number – 2

2336 Ferry Loading II

2342 Anniversary party

2346 Lucky tickets

2353 Ministry

2355 Railway tickets

2356 Find a multiple

2374 Fence Obstacle Course

2378 Tree Cutting

2384 Harder Sokoban Problem

2385 Apple Catching

2386 Lake Counting

2392 Space Elevator

2397 Spiderman

2411 Mondriaan’s Dream

2414 Phylogenetic Trees Inherited

2424 Flo’s Restaurant

2430 Lazy Cows

2479 Maximum sum                                                                                      解题报告


2533 Longest Ordered Subsequence

2915 Zuma

3017 Cut the Sequence

3028 Shoot-out

3124 The Bookcase

3176 Cow Bowling

3133 Manhattan Wiring

3345 Bribing FIPA

3356 AGTC

3375 Network Connection

3420 Quad Tiling

归并树&划分树详解


先放一张图片

对4 5 2 8 7 6 1 3 分别建划分树和归并树

划分树如下图

红色的点是此节点中被划分到左子树的点。

      我们一般用一个结构体数组来保存每个节点,和线段树不同的是,线段树每个节点值保存一段的起始位置和结束位置,而在划分树和递归树中,每个节点的每个元素都是要保存的。为了直观些,我们可以定义一个结构体数组,一个结构体中保存的是一层的元素和到某个节点进入左子树的元素的个数,不同于线段树,我们不能保存一个节点的起始结尾位置,因为随层数的增加,虽然每个结构体保存的元素数目是一定的,但随层数的增加,元素早已被划分到不同的子树中了,而且这数目是指数增加的。

      那我们如何确定一个子树的边界? 在划分树中,我们都是采用递归的方式进行访问的,如果一个节点的边界是(l,r),假设mid = (l+r )/2,那么他的左右子树的边界恰好是(l,mid)和(mid+1, r),然后在进行下一层的递归。

const int maxn = 100000 + 10;
typedef struct node
{
    int num[maxn];
    int cnt[maxn];
}tree[20];

      至于这里为什么将tree大小定义20!和线段树一样,划分树都是完全完全二叉树,叶子节点的深度相差不会超过1,而且所有非叶子节点都有左右子树。关于划分树的题目,我们遇到的数据量一般都是10^5,也就是说如果把这些数建成树的话深度不会超过20。

     我们看图片会发现划分树有以下几个特点。

     1,树的根节点是原来的数组,没有做任何处理。

     2,和快排有些类似,每个节点的子节点(如果有)中,左节点的所有元素都有小于右节点的所有元素,前提是原数组中无重复的数,关于存在重复的元素的情况,我们会详细讨论。

     3,如果我们从左到有取出所有叶子节点,每个叶子节点的元素(肯定只有一个元素),这些元素必然是有序的。

我们以poj 2104   k-th number 为例,详细说一下划分树的建造和查询。

//poj 2104
//2013-04-15-19.47
#include <stdio.h>
#include <algorithm>
const int maxn = 100005;
using namespace std;

int sor[maxn];
struct node
{
    int num[maxn];
    int cnt[maxn];
}tree[20];

      接下来是建树的函数,建树之前,将数组放树的第一层,当做根节点,然后将原数组进行排序(至于升降视情况而定,但在整个程序中要统一)放在另外一个数组中,我这里放在sor中。我们先讨论集合中没有重复元素的情况,先找出mid(当前节点的中间位置),然后从左到右遍历所有元素,如果小于等于sor[mid] 放入左子树,否则放入右子树,然后递归创建左右子树。

      如果其中包含相同元素,而且恰好sor[mid] 左右都有与他相同的元素,这样我们就不能仅仅依靠比较大小来决定该数的去向了。当然,小于sor[mid]的必然去左子树,这是毋庸置疑的,但对于相同的元素,我们有个巧妙的处理方法,先计算在有序数组中sor[mid]左边有多少个和sor[mid]的元素,比如说有x个,然后在建树过程中将出现的前x+1个和sor[mid]相等的放入左子树,其他如右子树即可,然后递归建立左右子树。

     另外还有非常重要的一部分,不是还有一个cnt[]数组吗,这个数组是划分树的核心部分,它的作用是记录这个节点到第i个元素有多少被划分到了左子树,看代码很容易理解。

建树代码如下

void buildtree(int l, int r, int d)
{
    if (l == r)
    {
        return;
    }
    int mid = (l+r)>>1;
    int oplift = l, opright = mid+1;   //对左右子树的操作位置的初始化
    int same_as_mid = 0;
    /*用来计算在mid左边有多少个和sor[mid]相同的数(包括mid),这些都要放到左子树*/
    for (int i = mid; i > 0; i--)
    {
        if (sor[i] == sor[mid])
            same_as_mid++;
        else
            break;
    }
    int cnt_lift = 0;
    for (int i = l; i <= r; i++)
    {
        if (tree[d].num[i] < sor[mid])
        {
            tree[d+1].num[oplift++] = tree[d].num[i];
            cnt_lift++;
            tree[d].cnt[i] = cnt_lift;
        }
        else if(tree[d].num[i] == sor[mid] && same_as_mid)
        {
            tree[d+1].num[oplift++] = tree[d].num[i];
            cnt_lift++;
            tree[d].cnt[i] = cnt_lift;
            same_as_mid--;
        }
        else
        {
            tree[d].cnt[i] = cnt_lift;
            tree[d+1].num[opright++] = tree[d].num[i];
        }
    }
    buildtree(l, mid, d+1);
    buildtree(mid+1, r, d+1);
}

     关于询问操作,假如我们询问从区间[ql,qr]中第k大的数(看清具体要求,有些是第k小数),然后我们通过cnt数组,确定[ql,qr]有多少个点进入了左子树,然后判断第k数在左还是右子树,然后递归查询。

     肯定有m = cnt[qr] – cnt[ql-1]个数进入了左子树,如果ql是节点的左边界的话就有cnt[qr]个数进入左子树了,这里要额外注意。如果m <= k,,进入左子树查询第k数,否则进入右子树查询k-m数,我们还要确定在子树中查询的边界, 只是一个比较难理解的地方。

int query(int l, int r, int d, int ql, int qr, int k)
//6个参数,分别是当前节点的左右边界、深度、询问的左右边界及k值
{
    if (l == r)
        return tree[d].num[l];
    int mid = (l+r)>>1;
    int sum_in_lift, lift;
    if (ql == l)
    {
        sum_in_lift = tree[d].cnt[qr];
        lift = 0;
    }
    else
    {
        sum_in_lift = tree[d].cnt[qr] - tree[d].cnt[ql-1];
        // 区间进入左子树的总和
        lift = tree[d].cnt[ql-1];
    }
    if (sum_in_lift >= k)
    //证明要找的点在左子树
    {
        int new_ql = l+lift;
        int new_qr = l+lift+sum_in_lift-1;
        return query(l, mid, d+1, new_ql, new_qr, k);
        /*这里有必要解释一下,我们要确定下一步询问的位置,如果在ql的左边有i个进入左子树,
        那么ql到qr中第一个进入左子树的必定在l+i的位置*/
    }
    else
    {
        int a = ql - l - lift;
        int b = qr - ql + 1 - sum_in_lift;
        int new_ql = mid + a + 1;
        int new_qr = mid + a + b;
        return query(mid+1, r, d+1, new_ql, new_qr, k - sum_in_lift);
    }
}

POJ 2104完整代码如下(有错误,望大神指出)

#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 100005;
struct node
{
    int num[maxn];
    int cnt[maxn];
}tree[22];
int n, m;
int sor[maxn];

void build(int l, int r, int d)
{
    if (l == r)
        return tree[d].num[l];
    int mid = (l+r)>>1;
    int lift = l;
    int right = mid+1;
    int cnt = 0;
    for (int i = l; i <= r; i++)
    {
        if (tree[d].num[i] <= sor[mid])
        {
            cnt++;
            tree[d+1].num[lift++] = tree[d].num[i];
        }
        else
        {
            tree[d+1].num[right++] = tree[d].num[i];
        }
        tree[d].cnt[i] = cnt;
    }
    build(l, mid, d+1);
    build(mid+1, r, d+1);
}

int query(int l, int r, int ql, int qr,int x, int d)
{
    if (l == r)
        return l;
    int lift = 0;
    int right = 0;
    int suminlift = 0;
    int mid = (l+r)>>1;
    if (ql == l)
    {
        lift = 0;
        right = 0;
        suminlift = tree[d].cnt[qr];
    }
    else
    {
        lift = tree[d].cnt[ql-1];
        right = ql-1 - l + 1 - lift;
        suminlift = tree[d].cnt[qr] - lift;
    }
    int suminright = qr - ql + 1 - suminlift;
    if (suminlift >= x)
    {
        int newql = l + lift;
        int newqr = l + tree[d].cnt[qr] - 1;
        return query(l, mid, newql, newqr, x, d+1);
    }
    else
    {
        int newql = mid+1 + right;
        int newqr = mid+1 + right + suminright - 1;
        return query(mid+1, r, newql, newqr, x - suminlift, d+1);
    }
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &sor[i]);
            tree[0].num[i] = sor[i];
        }
        int l, r, x;
        sort(sor+1, sor+n+1);
        build(1, n, 0);
//        for (int i = 1; i <= n; i++)
//            printf("%d ", sor[i]);
//        puts("");
//        for (int i = 0; i < 6; i++)
//        {
//            for (int j = 1; j <= n; j++)
//                printf("%d ", tree[i].num[j]);
//            puts("");
//        }
        while (m--)
        {
            scanf("%d %d %d", &l, &r, &x);
            printf("%d\n", query(1, n, l, r, x, 0));
        }
    }
    return 0;
}


归并树,

如图


Light oj 1080 – Binary Simulation(树状数组区间更新点查询)


题目链接

题意:

    有一字符串只包含0和1,然后又m组操作,I L R是将从L到R的字符进行翻转操作0变为1、1变为0,Q x表示询问第x的字符。

思路:

    我们只需要计算对询问的字符进行了多少次翻转,如果是偶数次,该字符变,否则翻转。对于区间的更新,我们可以使用线段树,不过对于这个题,因为只是对点的查询,而且每个节点的初始值都相同,为0,因此我们可以直接使用树状数组。下面是一个很巧妙的做法,而且很容易理解。

用了树状数组的区间更新 单点查找(一般为单点更新 区间查找)

例如 区间(2,4)加1

则Updata(2,1)   Updata(4+1,-1)

实现了更新(2,4)的值而不改变其他值

求Sum时即可得到某一点的值

//LA 1080 - Binary Simulation
//2013-04-12-18.52
#include <stdio.h>
#include <string.h>

const int maxn = 100010;
char str[maxn];
int n;
int sum[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void change(int x, int v)
{
    while (x <= n)
    {
        sum[x] += v;
        x += lowbit(x);
    }
}

int get(int x)
{
    int s = 0;
    while (x)
    {
        s += sum[x];
        x -= lowbit(x);
    }
    return s;
}

void update(int l, int r)
{
    change(l, 1);
    change(r+1, -1);
}

int main()
{
    int t, m;
    scanf("%d",&t);
    for(int i = 1; i <= t; i++)
    {
        memset(sum, 0, sizeof(sum));
        scanf("%s",&str[1]);
        scanf("%d",&m);
        n =strlen(&str[1]);
        char op;
        int l, r;
        printf("Case %d:\n",i);
        while (m--)
        {
            getchar();
            scanf("%c",&op);
            if (op == 'I')
            {
                scanf("%d %d",&l, &r);
                update(l, r);
            }
            else
            {
                scanf("%d",&l);
                if (get(l)%2 == 1)
                {
                    if (str[l] == '1')
                        puts("0");
                    else
                        puts("1");
                }
                else
                    printf("%c\n",str[l]);
            }

        }
    }
    return 0;
}


这题也可以用线段树来做,个人感觉没有必要,有兴趣的读者可以试试。


poj 2352 Stars 树状数组


题目链接

Description

Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given
star. Astronomers want to know the distribution of the levels of the stars.………………

树状数组,简单题,我刚刚开始学的时候就a了,不多说什么了,直接贴代码。

#include<stdio.h>
#include<string.h>

int a[32002];
int level[15002];

int lowbit(int x)
{
	return x&(-x);
}

void insert(int x)
{
	while(x<32002)
	{
		a[x]++;
		x += lowbit(x);
	}
}

int sum(int x)
{
	int s=0;
	while(x)
	{
		s += a[x];
		x -= lowbit(x);
	}
	return s;
}

int main()
{
	int n, i, x, y;
	scanf("%d",&n);
	memset(a,0,sizeof(level));
	memset(level,0,sizeof(level));
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&x,&y);
		x++;
		level[sum(x)]++;
		insert(x);
	}
	for(i= 0; i < n; i++)
		printf("%d\n",level[i]);
	return 0;
}


poj 2182 Lost Cows(树状数组)


题目链接


Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood ‘watering hole’ and drank a few too many beers before dinner. When it was time to line up for
their evening meal, they did not line up in the required ascending numerical order of their brands.


Regrettably, FJ does not have a way to sort them. Furthermore, he’s not very good at observing problems. Instead of writing down each cow’s brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow
in line that do, in fact, have smaller brands than that cow.


Given this data, tell FJ the exact ordering of the cows. ……………………


题意:

          FJ有n头牛,现在它们排成一排,每一头牛都有一个不同的编号(1-n),现在知道从第二头牛开始每头牛左边比自己编号小的牛的数目,让你确定每头牛的编号。

思路:

        我用一个树状数组来表示第i头牛的左边有多少比自己标号小的,树状数组必须初始化,每个节点必须加1。每次我们可以知道最后一头牛的编号x,然后然后更新x以后的区间使其都减1(这里也可以使用线段树,不过感觉比较麻烦,因为树状数组的特性,只需要更新x就好了),然后求倒数第二头的编号,我们只需要找到一个x,使得sum(x) 为该牛左边小于其编号牛的数量,使用二分查找可以提高查找速率,然后是倒数第三头的………………………………

        因为是倒着来的,为了熟悉stl,我使用了其封装的stack 栈。

     下面是解题代码:

#include <stdio.h>
#include <string.h>
#include <stack>
#define maxn 8005

using namespace std;

int a[maxn];
int ans[maxn];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void add(int x, int v)
{
    while (x <= n)
    {
        a[x] += v;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int s = 0;
    while (x > 0)
    {
        s += a[x];
        x -= lowbit(x);
    }
    return s;
}

int binarysearch(int l, int r, int x)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    if (x <= sum(mid))
        return binarysearch(l, mid, x);
    else
        return binarysearch(mid+1, r, x);
}
/*二分查找也可以写成非递归的形式,避免了函数的调用和栈的开销,节约时间空间,
但递归的形式容易理解,也不易出错,各有优劣,这就看你如何取舍了*/

stack <int> s;
int main()
{
    int t;
    while (scanf("%d",&n) != EOF)
    {
        memset(a, 0, sizeof(a));
        //因为每次使用s后s必定为空,就不用初始化了
        
        int i;
        for (i = 1; i < n; i++)
        {
            add(i+1,1);
            scanf("%d",&t);
            s.push(t);
        }
        while (i > 1)
        {
            int x = binarysearch(1, n, s.top());
            ans[i--] = x;
            add(x, -1);
            s.pop();
        }
        ans[1] = binarysearch(1, n, 0); 
        //while循环只循环n-1次(如果循环n次栈会出错),所以要加这行
        
        for (i = 1; i <= n; i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}


线段树的方法我就暂时不写了,有感兴趣的可以上网搜一下其他人的代码,都比我写的好啊!!


POJ 1195 Mobile phones (二维树状树组)


       由于英语极差,看了半天也没看懂题目,最后参考了其他人的题解才搞懂题目,我就直接把题意贴过来了 

     

题意:这道题目只是题意自己就去理解了半天,大概题意如下:给出i一个n*n的矩阵,初始化为均为0,还有关于这个矩阵的几种操作,操作如下:命令1:(X Y A)对位于坐标(X Y)的值加A;命令2:(L B R T)求出位于L<=x<=R,B<=y<=T的值的和;命令3:退出不做任何操作。

 

思路分析如下:二维树状数组,典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和,注意一下就可以了:sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);

      这是我做的第一道二维树状树组的题目,感觉和一维的差不多,下面是题解。

 

//poj 1195
#include <stdio.h>
#include <string.h>
const int maxn = 1030;

int n, a[maxn][maxn];

int lowbit(int x)
{
    return x & (-x);
}

void update(int i, int j, int v)
{
    int t;
     while(i <= n)
     {
         t = j;                        //不能改变j的值,因为每次循环都要用到
         while (t <= n)
         {
             a[i][t] += v;
             t += lowbit(t);
         }
         i += lowbit(i);
     }
}

int getsum(int i, int j)
{
    int sum = 0, t;
    while (i > 0)
    {
        t = j;                          //不能改变j的值,因为每次循环都要用到
        while (t > 0)
        {
            sum += a[i][t];
            t -= lowbit(t);
        }
        i -= lowbit(i);
    }
    return sum;
}

int main()
{
    int op, x, y, v, xx, yy;
    while (scanf("%d%d",&op,&n) != EOF)
    {
        memset(a, 0, sizeof(a));
        while (scanf("%d",&op) && op != 3)
        {
            if (op == 1)
            {
                scanf("%d%d%d",&x, &y, &v);
                x++; y++;                         //树状数组坐标是从1开始的,以此要加1
                update(x, y, v);
            }
            else
            {
                scanf("%d%d%d%d", &x, &y, &xx, &yy);
                x ++, y ++, xx ++, yy ++;
                int ans = getsum(xx, yy) - getsum(x-1, yy) - getsum(xx, y-1) + getsum(x-1, y-1);
                // 每次getsum(i, j); 得到的结果是(i,j)前面所有数的和 
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}


 

  


POJ数据结构专辑(含部分题解)


1195 Mobile phones 树状数组                                                 
 
题解

1455 Crazy tea party                                                              
   题解

1521 Entropy huffman                                                               题解

1703 Find them, Catch them 并查集

1785 Binary Search Heap Construction

1794 Castle Walls 逆序对

1961 Period KMP重复因子                                                        题解

1984* Navigation Nightmare 并查集+坐标平移

1986* Distance Queries LCA

1988* Cube Stacking 并查集应用

1990* MooFest 线段树

2010* Moo University – Financial Aid 最大堆-最小堆

2182 Lost Cows 线段树                                                              题解

2183 Bovine Math Geniuses hash

2188 Cow Laundry 逆序对

2227 The Wedding Juicer 堆+floodfill

2236 Wireless Network 并查集

2266* Quadtree 递归构造四叉树

2269* Friends 表达式

2270 Quadtree II or: Florida Jones strikes back 将2266反之

2299 Ultra-QuickSort 归并排序

2352 Stars 树状数组                                                                   题解

2395 Out of Hay 并查集

2482 Stars in Your Window 静态2叉树

2513 Colored Sticks 并查集

2524 Ubiquitous Religions 并查集

2528 Mayor’s posters 线段树

2567 Code the Tree

2750* Potted Flower 线段树

2777 Count Color 线段树

2796 Feel Good RMQ

2823 Sliding Window 堆或双端队列

2828 Buy Tickets 线段树

2886* Who Gets the Most Candies? 线段树

2892* Tunnel Warfare 树状数组

3214* Heap 后序遍历,每个节点减去相应sub保证属性,然后对遍历结果求最长不下降序列

3253 Fence Repair huffman

3263 Tallest Cow 线段树

3274* Gold Balanced Lineup hash

3277 City Horizon 线段树

3320 Jessica’s Reading Problem 队列操作或最小堆

3321* Apple Tree 树状数组

3332 Parsing Real Numbers DFA

3344 Chessboard Dance 队列模拟

3349 Snowflake Snow Snowflakes hash(or 暴力)

3437 Tree Grafting dfs树构造

3461 Oulipo KMP

3468 A Simple Problem with Integers 线段树区间更新,懒操作          
题解

3631 Cuckoo Hashing 并查集

3667 Hotel 线段树

3690 Constellations trie匹配

3695 Rectangles 矩阵切割

 


hdoj 1166 敌兵布阵


    暴力超时,这道题可以用线段树做,因为更新的是单个节点,我们也可以用数组数组来做,我将两种方法的代码都给出

    数组数组最适宜的用途就是区间求和和点的更新,但树状数组并不适用于区间的更新问题,也不是做不到,比较麻烦且难理解,有兴趣的可以看看这个http://blog.csdn.net/xindoo/article/details/8748410

//树状数组
#include<stdio.h>

int n,ans[50005],f[50005];

int lowbit(int n)
{
    return n&(-n);
}

void add(int i,int v)
{
    while(i <= n)
    {
        ans[i] += v;
        i += lowbit(i);
    }
}

int query(int n)
{
    int s = 0;
    while(n)
    {
        s += ans[n];
        n -= lowbit(n);
    }
    return s;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int j = 1;j <= t; j++)
    {
        scanf("%d",&n);
        for(int l = 1; l <= n;l++)
        {
            scanf("%d",&f[l]);
            f[l] += f[l-1];
        }
        for(int l = 1; l <= n; l++)
            ans[l] = f[l]-f[l-lowbit(l)];
        printf("Case %d:\n",j);
        while(1)
        {
            char s[20];
            int a,b;
            scanf("%s",s);
            if (s[0] == 'E') break;
            scanf("%d%d",&a,&b);
            if (s[0] == 'A') add(a,b);
            if (s[0] == 'S') add(a,-b);
            if (s[0] == 'Q') printf("%d\n",query(b)-query(a-1));
        }
    }
    return 0;
}

//线段树解法
#include <stdio.h>
#include <string.h>
#define maxn 50005

struct node
{
    int l, r, m;
    int sum;
}tree[maxn<<2];

int a[maxn];

void build(int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    int m = (l+r)>>1;
    tree[o].m = m;
    if (l == r)
    {
        tree[o].sum = a[l];
        return;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;
 }

void update(int l, int v, int o)
{
    tree[o].sum += v;
    if (tree[o].l == l && tree[o].r == l)
        return;
    if (l <= tree[o].m)
        update(l, v, o<<1);
    else
        update(l, v, (o<<1)+1);
}

int query(int l, int r, int o)
{
    if (tree[o].l == r && tree[o].r == r)
        return tree[o].sum;
    if (tree[o].m >= r)
        return query(l, r, o<<1);
    else if (tree[o].m <l)
        return query(l, r, (o<<1)+1);
    else
        return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
}

int main()
{
    int t, n;
    scanf("%d",&t);
    for (int j = 1; j <= t; j++)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        build(1, n, 1);
        printf("Case %d:\n",j);
        while(1)
        {
            char s[20];
            int l, r;
            scanf("%s",s);
            if (s[0] == 'E')
                break;
            scanf("%d%d",&l,&r);
            if (s[0] == 'A')
                update(l, r, 1);
            else if (s[0] == 'S')
                update(l, -r, 1);
            if (s[0] == 'Q')
                printf("%d\n",query(l, r, 1));
        }
    }
    return 0;
}


poj 3468 A Simple Problem with Integers线段树区间修改


传送门 

题目意思很简单,有N个数,Q个操作,  Q l  r 表示查询从l到r 的和,C  l  r  v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!

解题方法我在代码注释中写的很详细了

#include <stdio.h>
const int maxn = 100005;                      
typedef __int64 ll;                           //Hint  The sums may exceed the range of 32-bit integers.
int a[maxn];

struct node                                   //比较复杂的线段树都需要保存一个节点的多个信息,虽然
{                                             //可以使用多个数组来存储,但我个人不推荐这种做法
    int l, r, m;
    ll sum, mark;
}tree[maxn<<2];                               // << 这里使用位运算,位运算的效率要比* /运算的效率高
                                              //推荐大家在乘除2或2的某次方的时候使用位运算,
                        
void build(int l, int r, int o)               //建树比较好理解,确定每个节点的各项,然后递归创建左右子树
{
    tree[o].l = l;
    tree[o].r = r;
    int m = (l+r)>>1;
    tree[o].m = m;
    tree[o].mark = 0;                         //mark的值一定要初始化为0,很重要
    if (l == r)                               //递归边界
    {
        tree[o].sum = a[l];
        return;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;  //这里tree[(o<<1)+1] (o<<1) 我打了括号,以为位运算的优先级比+低
 }                                                      //不注意很容易出问题的

 void update(int l, int r, int v, int o)
 {
     if (tree[o].l == l && tree[o].r == r)
     {
        tree[o].mark += v;                              //在每次更新某段的时候我们还要我们标记这一段被加了v
        return;
     }
     tree[o].sum += (ll)(r-l+1)*v;
     if (tree[o].m >= r)                                //递归更新,无外乎三种情况    
        update(l, r, v, o<<1);
     else if (l > tree[o].m)
        update(l, r, v, (o<<1)+1);
     else
     {
         update(l, tree[o].m, v, o<<1);
         update(tree[o].m+1, r, v, (o<<1)+1);
     }
 }

ll query(int l, int r, int o)                                         
 {
     if (tree[o].l == l && tree[o].r == r)                           //我们也使用递归的方式查询,这是递归边界
        return tree[o].sum + tree[o].mark*(r-l+1);
     if (tree[o].mark != 0)
     {
         tree[o<<1].mark += tree[o].mark;                            //在查询的时候我将节点的mark值传递给子节点
         tree[(o<<1)+1].mark += tree[o].mark;
         tree[o].sum += (ll)(tree[o].r -tree[o].l +1)*tree[o].mark;  //并更新sum的值
         tree[o].mark = 0;
     }
     if (tree[o].m >= r)                                             //查询的三种情况
        return query(l, r, o<<1);
     else if (tree[o].m <l)
        return query(l, r, (o<<1)+1);
     else
        return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
 }

int main()
{
    int n, q;
    while (scanf("%d%d",&n,&q) != EOF)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        build(1, n, 1);
        char com;
        int l, r, v;
        while (q--)
        {
            getchar();
            scanf("%c",&com);
            if (com == 'Q')
            {
                scanf("%d%d",&l, &r);
                printf("%I64d\n",query(l,r,1));
            }
            else
            {
                scanf("%d%d%d",&l ,&r ,&v);
                update(l, r, v, 1);
            }
        }
    }
    return 0;
}