【hdu 1698 Just a Hook（被搞死）】

Just a Hook

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8814 Accepted Submission(s): 4291

Problem Description

In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.

Now Pudge wants to do some operations on the hook.

Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks.
The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows:

For each cupreous stick, the value is 1.
For each silver stick, the value is 2.
For each golden stick, the value is 3.

Pudge wants to know the total value of the hook after performing the operations.
You may consider the original hook is made up of cupreous sticks.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations.
Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind.

Output

For each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example.

Sample Input

1 10 2 1 5 2 5 9 3

Sample Output

Case 1: The total value of the hook is 24.

Source

2008 “Sunline Cup” National Invitational Contest

Recommend

wangye

暂时到图片。。还没有解决。。。我弱爆了。。呜呜呜。。悲了个剧。。。

===========================================================================================

悲了个剧。。。超时一次。。。

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

/***************************************************/
class Node
{
public:
    int l;
    int r;
    int value;
    int id;
};

#define MAXN 100010

Node _map_[MAXN*4];
int n;

/***************************************************/
void debugShowMap()
{
    for (int i = 0; i < n * 3; i++)
    {
        printf("%d ", _map_[i].value);
    }
    printf("\n");
}

void make_map(int start, int end, int id)
{
    _map_[id].id = id;
    _map_[id].l  = start;
    _map_[id].r  = end;
    if (start == end)
    {
        _map_[id].value = 1;
    }
    else
    {
        int mid = (start + end) / 2;
        make_map(start,   mid, id * 2);
        make_map(mid + 1, end, id * 2 + 1);
        _map_[id].value = _map_[id*2].value + _map_[id*2+1].value;
    }
}

void cover_hook(const int start, const int end, const int id, const int value)
{
    if (start == end && start == _map_[id].r && start == _map_[id].l)
    {
        _map_[id].value = value;
    }
    else
    {
        int mid;
        mid = (_map_[id].l + _map_[id].r) / 2;
        if (mid >= end)
        {
            cover_hook(start, end, id * 2,     value);
        }
        else if (mid + 1 <= start)
        {
            cover_hook(start, end, id * 2 + 1, value);
        }
        else
        {
            cover_hook(start,   mid, id * 2,     value);
            cover_hook(mid + 1, end, id * 2 + 1, value);
        }
        _map_[id].value = _map_[id*2].value + _map_[id*2+1].value;
    }
    //_map_[id].value = _map_[id*2].value + _map_[id*2+1].value;
}

/***************************************************/
int main()
{
    //freopen("in.dat", "r", stdin);
    int t;
    scanf("%d", &t);
    int case_count;
    for (case_count = 1; case_count <= t; case_count++)
    {
        scanf("%d", &n);
        make_map(1, n, 1);
        int _time;
        scanf("%d", &_time);
        //debugShowMap();
        while (_time--)
        {
            int start, end, value;
            scanf("%d%d%d", &start, &end, &value);
            cover_hook(start, end, 1, value);
            //debugShowMap();
        }
        printf("Case %d: The total value of the hook is %d.\n", case_count, _map_[1].value);
    }
    return 0;
}

// end
// ism

再来。。。。。一定AC。。。Fight！！！

==============================================================================================

终于AC了。。

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<string.h>
  4 using namespace std;
  5 
  6 void debug()
  7 {
  8     printf("--debug msg--\n");
  9 }
 10 
 11 struct Hook
 12 {
 13     int iLeft;
 14     int iRight;
 15     int iCount;
 16 };
 17 
 18 Hook iMap[300100];
 19 int n;
 20 
 21 void iInit(int x, int y, int iID)
 22 {
 23     if (iMap[iID].iLeft == 0 && iMap[iID].iRight == 0)
 24     {
 25         iMap[iID].iLeft  = x;
 26         iMap[iID].iRight = y;
 27         iMap[iID].iCount = 1;
 28     }
 29 
 30     if (x == y)
 31     {
 32         return;
 33     }
 34     int iMid = (x + y) / 2;
 35     iInit(x,      iMid, iID * 2);
 36     iInit(iMid+1, y,    iID * 2 + 1);
 37 }
 38 
 39 void iInsert(int x, int y, int iID, int key)
 40 {
 41     if (iMap[iID].iCount == key)
 42     {
 43         return ;
 44     }
 45     if (iMap[iID].iLeft == x && iMap[iID].iRight == y)
 46     {
 47         iMap[iID].iCount = key;
 48         return ;
 49     }
 50     if (iMap[iID].iCount != -1)
 51     {
 52         iMap[iID*2].iCount = iMap[iID*2+1].iCount = iMap[iID].iCount;
 53         iMap[iID].iCount   = -1;
 54     }
 55     int iMid = (iMap[iID].iLeft + iMap[iID].iRight) / 2;
 56     if (y <= iMid)
 57     {
 58         iInsert(x, y, iID*2, key);
 59     }
 60     else
 61     {
 62         if (x > iMid)
 63         {
 64             iInsert(x, y, iID * 2 + 1, key);
 65         }
 66         else
 67         {
 68             iInsert(x,      iMid, iID * 2,     key);
 69             iInsert(iMid+1, y,    iID * 2 + 1, key);
 70         }
 71     }
 72 }
 73 
 74 int iSearch(int i)
 75 {
 76     if (iMap[i].iCount != -1)
 77     {
 78         return (iMap[i].iRight - iMap[i].iLeft + 1) * (iMap[i].iCount);
 79     }
 80     else
 81     {
 82         return iSearch(i*2) + iSearch(i*2+1);
 83     }
 84 }
 85 int main()
 86 {
 87     //freopen("in.dat", "r", stdin);
 88     int t;
 89     scanf("%d",&t);
 90     int tt=1;
 91     while(t--)
 92     {
 93         scanf("%d",&n);
 94         iInit(1,n,1);
 95         int m;
 96         scanf("%d",&m);
 97         for(int i=0;i<m;i++)
 98         {
 99             int x,y,key;
100             scanf("%d%d%d",&x,&y,&key);
101             iInsert(x,y,1,key);
102         }
103         printf("Case %d: The total value of the hook is %d.\n",tt,iSearch(1));
104         tt++;
105         memset(iMap,0,sizeof(iMap));
106     }
107     return 0;
108 }

======================================================================================================================================

终于明白这题到底应该怎么搞了。。原来的想法都是错的。这回应该是对的了。。。

罪过罪过。。学习速度还是慢了啊。。

加油。。fight。。

  1 // Project name : 1007 ( Just a Hook ) 
  2 // File name    : main.cpp
  3 // Author       : iCoding
  4 // E-mail       : honi.linux@gmail.com
  5 // Date & Time  : Tue Aug  7 13:53:26 2012
  6 
  7 
  8 #include <iostream>
  9 #include <stdio.h>
 10 #include <string>
 11 #include <cmath>
 12 #include <algorithm>
 13 using namespace std;
 14 
 15 class Node
 16 {
 17 public:
 18     int iLeft;
 19     int iRight;
 20     int iValue;
 21 };
 22 
 23 #ifndef  MAXN
 24 #define MAXN 100000
 25 #endif
 26 
 27 Node iMap[MAXN*4];
 28 
 29 int n;
 30 
 31 
 32 /***************************************************************************************/
 33 void iCreateMap(int iStart, int iEnd, int iID)
 34 {
 35     iMap[iID].iLeft  = iStart;
 36     iMap[iID].iRight = iEnd;
 37     if (iStart == iEnd)
 38     {
 39         //scanf("%d", iMap[iID].iValue);
 40         iMap[iID].iValue = 1;
 41     }
 42     else
 43     {
 44         int iMid;
 45         iMid = (iStart + iEnd) / 2;
 46         iCreateMap(iStart,   iMid, iID * 2);
 47         iCreateMap(iMid + 1, iEnd, iID * 2 + 1);
 48         iMap[iID].iValue = 1;
 49     }
 50 }
 51 
 52 void iChangeHook(int iStart, int iEnd, int iID, int iValue)
 53 {
 54     if (iMap[iID].iLeft == iStart && iMap[iID].iRight == iEnd)
 55     {
 56         iMap[iID].iValue = iValue;
 57     }
 58     else
 59     {
 60         int iMid = (iMap[iID].iLeft + iMap[iID].iRight) / 2;
 61         if (iMap[iID].iValue >= 0)
 62         {
 63             iMap[iID*2]  .iValue = iMap[iID].iValue;
 64             iMap[iID*2+1].iValue = iMap[iID].iValue;
 65         }
 66         if (iMid >= iEnd)
 67         {
 68             iChangeHook(iStart, iEnd, iID * 2,     iValue);
 69         }
 70         else if (iMid + 1 <= iStart)
 71         {
 72             iChangeHook(iStart, iEnd, iID * 2 + 1, iValue);
 73         }
 74         else
 75         {
 76             iChangeHook(iStart,   iMid, iID * 2,     iValue);
 77             iChangeHook(iMid + 1, iEnd, iID * 2 + 1, iValue);
 78         }
 79         iMap[iID].iValue = -1;
 80     }
 81 }
 82 
 83 int iGetHookSum(int iStart, int iEnd, int iID)
 84 {
 85     int iAnswer = 0;
 86     int iMid = (iMap[iID].iLeft + iMap[iID].iRight) / 2;
 87     if (iMap[iID].iValue >= 0)
 88     {
 89         iAnswer = iMap[iID].iValue * (iEnd - iStart + 1);
 90     }
 91     else
 92     {
 93         iAnswer = iGetHookSum(iStart, iMid, iID * 2) + iGetHookSum(iMid + 1, iEnd, iID * 2 + 1);
 94     }
 95     return iAnswer;
 96 }
 97 
 98 /***************************************************************************************/
 99 int main()
100 {
101     int iT;
102     scanf("%d", &iT);
103     int iCaseCount;
104     for (iCaseCount = 1; iCaseCount <= iT; iCaseCount++)
105     {
106         scanf("%d", &n);
107         iCreateMap(1, n, 1);
108         int m;
109         scanf("%d", &m);
110         for (int i = 0; i < m; i++)
111         {
112             int iStart, iEnd, iValue;
113             scanf("%d%d%d", &iStart, &iEnd, &iValue);
114             iChangeHook(iStart, iEnd, 1, iValue);
115         }
116         printf("Case %d: The total value of the hook is %d.\n", iCaseCount, iGetHookSum(1, n, 1));
117     }
118     return 0;
119 }
120 
121 // end 
122 // Code by Sublime text 2
123 // iCoding@CodeLab