暴力咯

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//常量区
const int maxn = 1e6 + 5;
int arr[maxn];
//函数区

//main函数
int main(){
    int s, e, p, maxd = 0, mind = 1e8;
    while(scanf("%d%d%d", &s, &e, &p) == 3){
        for(int i = s; i <= e; i++) arr[i] = p;
        maxd = max(maxd, e);
        mind = min(mind, s);
    }
    int left = mind, i = mind + 1;
    for(i; i <= maxd; i++){
        if(arr[i] != arr[i-1]){
            printf("[%d, %d, %d],", left, i-1, arr[i-1]);
            while(!arr[i]) i++;
            left = i;
        }     
    }
    printf("[%d, %d, %d]\n", left, i-1, arr[i-1]);
    return 0;
}

#include<stdio.h>
int book[1000000];
int main(){
	int x,y,v,i,pre,Max=0;
	//freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&x,&y,&v)!=EOF){
		for(i=x;i<=y;i++) book[i]=v;
		if(Max<y) Max=y;
	}
	for(i=0;!book[i];i++);
	pre=i;
	for(i++;i<=Max;i++)
		if(book[i]!=book[i-1]){
			printf("[%d, %d, %d],",pre,i-1,book[i-1]);
            while(!book[i]) i++;
            pre=i;
		}
	printf("[%d, %d, %d]",pre,i-1,book[i-1]);
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNextInt()) {
			int[] price = new int[10001];
			
			int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
			while (cin.hasNextInt()) {
				int b = cin.nextInt(), e = cin.nextInt(), p = cin.nextInt();
				for (int i = b; i <= e; ++i) {
					price[i] = p;
				}
				if (b < min) {
					min = b;
				}
				if (e > max) {
					max = e;
				}
			}
			
			System.out.print("[" + min + ", ");
			for (int i = min + 1, pre = price[min]; i < max; ++i) {
				int cur = price[i];
                                //比较前一点个当前点的价格，如果不一样，说明这是一个划分点
				if (cur != pre) {
                                        //前一个点不为0，说明前一个点是一个右闭区间
					if (pre != 0) {
						System.out.print(i - 1 + ", " + pre + "],");
					}
                                        //当前点不为0，说明当前点是一个左闭区间
					if (cur != 0) {
						System.out.print("[" + i + ", ");
					}
				}
				pre = cur;
			}
			System.out.println(max + ", " + price[max] + "]");
		}
	}
}

//这道题目可以定义一个结构体用于存储每个分段的起始时间，截止时间，价格，然后对所
//有相邻且价格一致的区间进行merge，这也是题目本身想要考察的。但是这样的做法不适
//合考试时候时间有限的情况下，虽然单纯的merge并不复杂，但是注意题目中提到了酒店
//的价格可能不一致，如果不一致，按后面的价格为准，如果后面记录的价格和前面的记录
//不一样，这就可能导致原来的一个区间段更新价格后分裂成为两个或者三个，略显复杂。
//所以可以直接用一个数组存储每天的价格，这样做的好处就是即使前后数据不一致，后面
//的会直接覆盖前面的完成价格更新，缺点就是需要一个数组来记录每天的价格，空间复杂
//度较高，对于这个实际问题而言，不会出现特别多的天数，所以不必考虑大数问题，当然
//也所幸内存够用。特别需要注意输出格式要满足题目要求。
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int i = 0;
	int start, end, price;
	while (cin >> start >> end >> price){
		vector<int> prices(10000);
		for (i = start; i <= end; i++)
			prices[i] = price;
		int min = start;
		int max = end;
		while (cin >> start >> end >> price){
			if (start < min)
				min = start;
			if (end > max)
				max = end;
			for (i = start; i <= end; i++)
				prices[i] = price;
		}

		cout << "[" << min << ", ";
        for (i = min + 1; i <= max; i++){
            if (prices[i] != prices[i - 1]){
                if (prices[i - 1] != 0)
                    cout << i - 1 << ", " << prices[i - 1] << "]";
                if (i < max && prices[i] != 0)
                    cout << "," << "[" << i << ", ";
            }
        }
        cout << max << ", " << prices[max] << "]" << endl;
	}
	return 0;
} 

线段树问题

#include <iostream>
#include <vector>

using namespace std;

struct segNode{
    int height, start, end;
    segNode* left, * right;
    segNode(int start, int end, int height):start(start), end(end), height(height){}
};

void insert(segNode* root, int start, int end, int height){
    if(!root) return;
    if(end < root->start || start > root->end) return;
    if(root->left){
        insert(root->left, start, end, height);
        insert(root->right, start, end, height);
        return ;
    }
    if(start <= root->start && end >= root->end)
        root->height = height;
    else if(start > root->start){
        root->left = new segNode(root->start, start - 1, root->height);
        root->right = new segNode(start, root->end, root->height);
        insert(root->right, start, end, height);
    }else{
        root->left = new segNode(root->start, end, height);
        root->right = new segNode(end + 1, root->end, root->height);
    }
}

void print_segNode(segNode* root, vector<vector<int>>& result, int& lst){
    if(!root) return;
    if(root->left){
        print_segNode(root->left, result, lst);
        print_segNode(root->right, result, lst);
        return;
    }
    if(root->height == 0)
        lst = -1;
    else if(root->height == lst)
        result.back()[1] = root->end;
    else {
        result.emplace_back(vector<int>{root->start, root->end, root->height});
        lst = root->height;
    }

}

int main(){
    vector<vector<int>> result;
    int start, end, height;
    segNode* root = new segNode(0, INT32_MAX, 0);
    while(cin >> start >> end >> height)
        insert(root, start, end, height);
    int lst = -1;
    print_segNode(root, result, lst);
    for(int i=0; i<result.size(); i++) {
        if(i != 0)
            cout << ",";
        cout << "["  << result[i][0] << ", " << result[i][1] << ", " << result[i][2] << "]";
    }
    return 0;
}

//题意其实是：每次给出L, R, Color表示把[L, R]这个区间涂成Color这个颜色，
//后来的涂色会覆盖之前的颜色。最后按顺序输出所有区间的颜色。
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
map<pii, int> mp; //用map维护区间[pii.first, pii.second]及其对应颜色int
typedef map<pii, int>::iterator MIT;

int main(){
    int a, b, c;
    while( 3 == scanf("%d%d%d", &a, &b, &c) ){
        
        if(!mp.empty()){ //插入区间[a, b]之前先处理已存在的区间
            MIT it = mp.lower_bound(pii(a, INT_MIN)); 
            if(it != mp.begin()) --it; //找到第一个可能和[a,b]相交的区间
            while(it != mp.end()){ //向后枚举所有相交的区间，注意这里每个区间只会插入删除一次，不影响复杂度
                if(it->first.first < a ){
                    if( it->first.second >= a ){
                        if(it->first.second <= b) { //左边部分相交的区间，修改它的右端点为a - 1
                            *const_cast<int*>(&(it->first.second)) = a - 1;
                            ++it;
                        }
                        else{	//区间[a,b]被完全包含
                            int tmp = it->first.second;
                            *const_cast<int*>(&(it->first.second)) = a - 1;
                            mp.insert(make_pair(pii(b + 1, tmp), it->second));
                            break;
                        }
                    }
                    else{ //在[a,b]左边（不相交）的区间
                        ++it;
                    }
                }
                else if(a <= it->first.first && it->first.first <= b){
                    if(it->first.second <= b) mp.erase(it++);	//被[a,b]完全包含的区间，直接删除
                    else{
                        *const_cast<int*>(&(it->first.first)) = b + 1;	 //右边部分相交的区间，修改它的左端点为b + 1
                        break;	//这是最后一个可能相交的区间，跳出
                    }
                }
                else break;	//右端点大于b的，都不可能相交
            }
        }
        //插入[a,b]
        mp.insert(make_pair(pii(a, b), c));
    }
    //合并相邻区间输出
    const char* s = "";
    int L , R, C, flag = 0;
    for(MIT it = mp.begin(); it != mp.end(); ++it){
        if(flag && R + 1 == it->first.first && C == it->second){
            R = it->first.second;
        }
        else{
            if(flag)  {
                printf("%s[%d, %d, %d]", s, L, R, C);
                s = ",";
            }
            L = it->first.first;
            R = it->first.second;
            C = it->second;
            flag = 1;
        }
    }
    if(flag) printf("%s[%d, %d, %d]", s, L, R, C);
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<int[]> list = new ArrayList<>( ), list1 = new ArrayList<>();
        while(in.hasNextLine()){
            String temp = in.nextLine() ;
            if(temp.equals(""))break ;
            int[] a = {Integer.parseInt(temp.split(" ")[0]), Integer.parseInt(temp.split(" ")[1]), Integer.parseInt(temp.split(" ")[2])} ;
            list.add(a) ;
        }
        
        int[] a = getarray(list) ;
//        System.out.print(Arrays.toString(a));
        int temp = -1 , j = 0;
        for( int i = 0; i< a.length; i++){
            if(a[i] != 0) {
                if (a[i] != temp) {
                    int m1 = i + 1;
                    list1.add(new int[]{m1, m1, a[i]});
                    j++;
                    temp = a[i];
                } else {
                    int m = list1.get(j - 1)[0], n = i + 1;
                    list1.set(j - 1, new int[]{m, n, a[i]});
                }
            }
        }
        for(int i = 0; i< list1.size()-1; i++) System.out.print(Arrays.toString(list1.get(i))+",");
        System.out.print(Arrays.toString(list1.get(list1.size()-1)));
    }
    private static int[] getarray(List<int[]> list) {
        int[] a = new int[1000000] ;
        for (int i = 0; i< list.size(); i++) {
            for(int j = list.get(i)[0]-1; j< list.get(i)[1]; j++)
                a[j] = list.get(i)[2] ;
        }
        return a ;
    }
}

	

这题我的思路很简单，没用到多么高深的算法，直接来暴力破解法。

运行时间：160ms
占用内存：15996k

代价就是比较大的空间复杂度，因为我这里创建了一个15000大小的数组用来保存15000天每一天的价格（之前10000）提示数组越界，说明数据量还是蛮大的。

思路就是 首先更新每一天的价格，最后一回得到一个这样的价格数组:
[0,100,100,100,110,110,200,200,0,0,...]
这个数组的索引就是价格的天数，
然后剩下的就有点像搜索重复字符串的味道了，
在数组中从index=0开始遍历，查到价格为100的索引(1,3), 查到价格为110的索引(4,5),...
然后打印之即可。
简单粗暴，但是代价就是时间跟空间复杂度比较高。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 储存每一个的价格,列表索引为天数，element为价格
        int[] prices = new int[12000];
        while (sc.hasNext()) {
            //更新价格数组
            int start = sc.nextInt();
            int end = sc.nextInt();
            int price = sc.nextInt();
            for (int i = start; i <= end; i++) {
                prices[i] = price;
            }
        }
        System.out.print(handle(prices));

    }

    public static StringBuffer handle(int[] prices) {
        StringBuffer buf = new StringBuffer();
        int size = prices.length;
        int i = 0;
        int lastDay = 0;
        while (i < size) {
            int currentPrice = prices[i];
            i++;
            while (i < size && currentPrice == prices[i]) {
                //价格跟之前一样，我们继续增加索引
                i++;
            }
            // 此时的i为新的价格的第一天;
            int current = i;
            if (prices[current - 1] != 0) {
                buf.append("[").append(lastDay).append(", ").append(current - 1).append(", ")
                        .append(prices[current - 1]).append("]").append(",");
            }
            lastDay = i;
        }
        //删除最后一个逗号
        return buf.deleteCharAt(buf.length() - 1);

    }
}

//区间树，见算法导论第14章
//用数组暴力模拟的前提是起始日期和终止日期都不会很大
//算是偷鸡的做法
//直接借用了TreeMap，其中key代表日期的起点，value存放一个数据结构（start，end，value）
//我们在向map中插入之前先查询map，把所有本次中覆盖的集合删除掉（有可能会有不完全覆盖的现象，需要处理）
//之后合并连续日期并且价格相同的情况
//以下第一行是添加的输入比如(3, 10, 100)
//第二行是集合中原有的数据比如(1,4,10),(5,6,101),(7,8,19),(9,10,100)
//比如添加 ----------------------------------
//   --------    ----------   ---------   ------
//      ^            ^            ^         ^
//    需要截断       直接删掉     直接删掉     截断
//变成
//  ---|----------------------------------|---
//再判断挨着的是否需要合并
//牛客的数据集是真的菜，模拟居然能过。。。
//另外注意TreeMap的SubMap不是一个真的map，对SubMap的修改会影响TreeMap本身
//以上 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static class Node implements Comparable<Node>{
        int low, high, val;
        public Node(int low, int high, int val) {
            this.low = low;
            this.high = high;
            this.val = val;
        } @Override public int compareTo(Node o) {
            return this.val - o.val;
        }
    }

    public static void insert(TreeMap<Integer, Node> map, Node node) {
        NavigableMap<Integer, Node> subMap = map.subMap(node.low, true, node.high, true);
        while (subMap.size() > 0) {
            Node tmp = subMap.pollFirstEntry().getValue();
            if (subMap.size() == 0 && tmp.low <= node.high && node.high < tmp.high) {
                map.put(node.high + 1, new Node(node.high + 1, tmp.high, tmp.val));
            }
        }
        //check last
        Map.Entry<Integer, Node> entry = map.floorEntry(node.low);
        if (entry != null) {
            Node last = entry.getValue();
            if (last.high > node.high) {
                map.put(node.high + 1, new Node(node.high + 1, last.high, last.val));
            }
            if (last.high >= node.low) {
                last.high = node.low - 1;
            }
            if (last.high == node.low - 1 && last.val == node.val) {
                map.remove(last.low);
                node.low = last.low;
            }
        }
        //check next
        entry = map.ceilingEntry(node.high);
        if (entry != null && entry.getValue().low == node.high + 1 && entry.getValue().val == node.val) {
            map.remove(entry.getValue().low);
            node.high = entry.getValue().high;
        }
        map.put(node.low, node);
    }


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TreeMap<Integer, Node> map = new TreeMap<>();
        String line;
        while ((line = br.readLine()) != null) {
            int[] tmp = lineToIntArray(line);
            insert(map, new Node(tmp[0], tmp[1], tmp[2]));
        }
        StringBuffer sb = new StringBuffer();
        int i = 0;
        for (Map.Entry<Integer, Node> entry: map.entrySet()) {
            Node tmp = entry.getValue();
            sb.append("[");
            sb.append(tmp.low);
            sb.append(", ");
            sb.append(tmp.high);
            sb.append(", ");
            sb.append(tmp.val);
            sb.append("]");
            if (++i != map.size())
                sb.append(",");
        }
        System.out.println(sb);
    }

    public static int[] lineToIntArray(String line) {
        String[] arr = line.trim().split(" ");
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++)
            ans[i] = Integer.parseInt(arr[i]);
        return ans;
    }
}

#include <iostream>

using namespace std;
 
int main()
{     int x,y,v,a[100010],Max=0;     while(cin>>x>>y>>v)     {         for(int i=x;i<=y;i++)             a[i] = v;         if(Max < y)             Max = y;     }     int i=0;     while(!a[i])         i++;     int p = i;     for(i++;i<=Max;i++)     {         if(a[i] != a[i-1])         {             printf("[%d, %d, %d],", p, i-1, a[i-1]);             while(!a[i])                 i++;             p = i;         }     }     printf("[%d, %d, %d]", p, i-1, a[i-1]);          return 0;
}

暴力肝就行了

#include <stdio.h>

#define MAXN 10010

int l,r,cost;
int ans[MAXN];

int main()
{
	int i=0,flag=0,left=0;
	while(scanf("%d%d",&l,&r)!=EOF)
		for(scanf("%d",&cost);l<=r;ans[l++]=cost)	;
	for(;i<MAXN;i++)
		if(!ans[i])
		{
			if(left^i)
			{
				if(flag)
					putchar(',');
				else
					flag = 1;
				printf("[%d, %d, %d]",left,i-1,ans[left]);
			}
			left = i + 1;
		}
		else if(ans[i]^ans[left])
		{
			if(flag)
				putchar(',');
			else
				flag = 1;
			printf("[%d, %d, %d]",left,i-1,ans[left]);
			left = i;
		}
	return 0;
}

#include <iostream>
#include <map>
#include <math.h>
using namespace std;


int main(){
    map<int,int> jb;
    int max1=0,min1=50000;
    int a=0,b=0,c=0;
    while(cin>>a>>b>>c){
        max1=max(max1,b);
        min1=min(min1,a);
        for(int x=a;x<=b;x++){
            jb[x]=c;
        }
    }
    for(int x=min1;x<max1;x++){
        if(jb[x]==0){
            continue;
        }
        int b=x,e=x,shu=jb[x];
        while(jb[e]==shu){e++;}
        if(x!=min1){cout<<",";}
        x=e-1;
        cout<<"["<<b<<", "<<e-1<<", "<<shu<<"]";
    }
    return 0;
}

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

map<pair<int, int>, int> M;
vector<pair<pair<int, int>, int> > Res;
int main()
{
    int l, r, p;
    while (cin >> l >> r >> p)
    {
        while (true)
        {
            auto iter = M.lower_bound(make_pair(l, -1));
            // Left End
            if (iter != M.begin())
            {
                auto piter = iter;
                piter --;
                if (piter->first.second >= l)
                {
                    int ll = piter->first.first;
                    int rr = piter->first.second;
                    int pp = piter->second;
                    M.erase(piter);

                    // [ll, ..., l, ..., rr]
                    M[make_pair(ll, l - 1)] = pp;
                    // [ll, ..., l, ..., r, ..., rr]
                    if (rr > r) M[make_pair(r + 1, rr)] = pp;
                    continue;
                }
            }
            // Right End
            if (iter == M.end()) break;
            if (iter->first.first > r) break;
            // [l, ..., ll, ..., rr, ..., r]
            if (iter->first.second <= r) M.erase(iter);
            else
            {
                int ll = iter->first.first;
                int rr = iter->first.second;
                int pp = iter->second;
                M.erase(iter);
                // [l, ..., ll, ..., r, ..., rr]
                M[make_pair(r + 1, rr)] = pp;
            }
        }
        M[make_pair(l, r)] = p;
    }
    // Output
    for (auto i = M.begin(); i != M.end(); i ++)
    {
        if (!Res.size()) Res.push_back(*i);
        else {
            if (Res[Res.size() - 1].second == i->second && Res[Res.size() - 1].first.second + 1 >= i->first.first)
                Res[Res.size() - 1].first.second = i->first.second;
            else Res.push_back(*i);
        }
    }
    cout << '[' << Res[0].first.first << ", " << Res[0].first.second << ", " << Res[0].second << ']';
    for (int i = 1; i < Res.size(); i ++)
    {
        cout << ",[" << Res[i].first.first << ", " << Res[i].first.second << ", " << Res[i].second << ']';
    }
    return 0;
}