题解：第一题：我写的指针线段树，但是被卡了， 但是数组线段树不会，因为不用建树

这道题用并查集，从后往前染色，则不能覆盖，把一段颜色放在一个并查集中，O(N)的修改，我们让这段颜色的father指向他们这段的右端点，表示我下一次染色只能从右端点右边的一个开始；

#include 
      
       const int M = 1000000 + 5;int n, k;using namespace std;int vis[M], lf[M], rg[M], c[M], fa[M];void read(int &x){    x=0;int f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}    x*=f;}int find(int a){    if(fa[a]==a) return a;    return fa[a]=find(fa[a]) ;}void uni(int a,int b){    if(find(a)!=find(b)) fa[fa[a]]=fa[b] ;}void paint(int now, int co){    vis[now] = co;    if(now != 1 && vis[now-1])uni(now-1, now);    if(now != n && vis[now+1])uni(now, now+1);}int main(){    freopen("paint.in","r",stdin);    freopen("paint.out","w",stdout);    scanf("%d%d", &n, &k);    for(int i = 1; i <= k; i++)        read(lf[i]), read(rg[i]), read(c[i]);    for(int i = 1; i <= n; i++)fa[i] = i;    for(int i = k; i >= 1; i--){        int now = lf[i];        while(now <= rg[i]){            if(!vis[now]) paint(now, c[i]);            now = find(now) + 1;        }    }    for(int i = 1; i <= n; i++)printf("%d ", vis[i]);    return 0;}
      

 

第二题：我们想的dp     dp[j][i] = max (dp[k][j] + 1) 如果i,j,k连成的线合法，我们只需要最后的两个点就好了；

但是这样是N^3的， 过不了；我们想办法省去一维: dp[i] = max (dp[j] + 1),那我们必须保证转移到j的线再加上i-j这条线合法，构建

凸壳的边满足的条件是：犄角递增； 我们N*N枚举边的犄角（cmath : atan2(vec.y, vec.x) ）排序，按这个顺序建凸壳一定合法；我们用dp[i][j]表示以j结尾的凸壳边最多有多少条边； 更新它就用max  dp[?][i] ，维护一个桶，O(1)，当再次来到i就构成了一个凸壳；

#include 
      
       const int M = 100000 + 5;using namespace std;void read(int &x){    x=0;int f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}    x*=f;}struct Point{    int x, y;}p[305];Point operator -(const Point &a, const Point &b){    return (Point){a.x - b.x, a.y - b.y};}struct Edge{ double ang; int from, to;}G[300*300];bool cmp(Edge a, Edge b){
    return a.ang < b.ang;}int dp[305][305], tong[305];int main(){ //   freopen("convex.in","r",stdin);  //  freopen("convex.out","w",stdout);    int n, tot = 0;    scanf("%d", &n);    for(int i = 1; i <= n; i++)scanf("%d%d",&p[i].x, &p[i].y);        for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)            if(i != j){                Point tmp = p[j] - p[i];                G[++tot].ang = atan2(tmp.y, tmp.x);                G[tot].from = i;                G[tot].to = j;            }    sort(G+1, G+1+tot, cmp);    int ans = 0;    if(n <= 3){        printf("%d\n", n);        return 0;    }    for(int h = 1; h <= n; h++){        memset(dp, 0, sizeof(dp));        memset(tong, 0x8f, sizeof(tong));        tong[h] = 0;        for(int i = 1; i <= tot; i++){            int from = G[i].from, to = G[i].to;            dp[from][to] = tong[from] + 1;            tong[to] = max(tong[to], dp[from][to]);            //printf("%d %d %d %d %d\n", i, dp[from][to], from, to, tong[to]);        }        ans = max(ans, tong[h]);    }    printf("%d\n",ans);}
      

 

第三题：贪心+dp

首先电视连续与不连续与他们排在任何一种种类后面没有关系， 所以我们把一个种类放在一起；对于连续与不连续的电视节目其实就是看他们分成了几段，如果分成3段，我们就会有3个b的收益，所以我们选3个最大的b, 剩下的a贪心要最大的；就可以预处理出每种颜色分成k段的最大收益；

dp[i][k]表示考虑了前i种电视分成了k段的最大收益，限制是什么，对于单个电视分的段数 <= ceil(k /2);以下是std

/* * m.cpp * *  Created on: Oct 28, 2013 *      Author: acm */#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int MAX_N = 600 + 10, INF = ~0U >> 2;struct TV { int t, a, b; int id; void read(int id) { this->id = id; cin >> t >> a >> b; } bool operator<(const TV&o) const { return b - a > o.b - o.a; }};struct TVSet { vector
             
               a; void add(TV o) { a.push_back(o); } vector
              
                maxret; int color, n; vector
               
                
                  > dp, how; void update(int i, int j, int hw, int c) {// cout << i << " " << j << " " << c << " " << dp[i][j] << endl; if (c > dp[i][j]) { dp[i][j] = c; how[i][j] = hw; } } void doit() { n = a.size(); color = a[0].t; dp.assign(n + 1, vector
                 
                  (n + 1, -INF)); how.assign(n + 1, vector
                  
                   (n + 1)); sort(a.begin(), a.end()); dp[0][0] = 0; for (int i = 0; i < n; ++i) { TV me = a[i]; for (int j = 0; j <= n; ++j) { int c = dp[i][j];// cout << i << " " << j << " " << c << endl; if (c == -INF) continue; if (j > 0) update(i + 1, j, 0, c + me.a); update(i + 1, j + 1, 1, c + me.b); update(i + 1, j, -1, c); } } maxret.assign(n + 1, 0); for (int i = 0; i <= n; ++i) { maxret[i] = dp[n][i];// cerr << maxret[i] << endl; } } vector
                   
                    
                      > chains; void buildIt(int k) { chains.clear(); int i = n, j = k; vector
                     
                      
                        > op; while (i > 0) { if (how[i][j] == -1) { --i; continue; } if (how[i][j] == 0) { op.push_back(make_pair(0, a[i - 1])); --i; continue; } if (how[i][j] == 1) { op.push_back(make_pair(1, a[i - 1])); --i, --j; continue; } } int chk = 0; for (int i = 0; i < op.size(); ++i) { pair
                       
                         t = op[op.size() - 1 - i];// cerr << t.second.id << endl; if (t.first == 0) { chains[0].push_back(t.second); chk += t.second.a; } else { chains.push_back(vector
                        
                         ()); chains.back().push_back(t.second); chk += t.second.b; } }// cout << chk << " " << maxret[k] << endl;// cout << chains.size() << " " << k << endl; } bool operator<(const TVSet&o) const { return a.size() < o.a.size(); }};TVSet set[MAX_N];int n;vector
                         
                           tvsets;vector
                          
                           
                            
                              > > dp;int main() { freopen("tv.in","r",stdin); freopen("tv.out","w",stdout); cin >> n; for (int i = 0; i < n; ++i) { TV t; t.read(i); --t.t; set[t.t].add(t); } for (int i = 0; i < n; ++i) { if (set[i].a.size()) { tvsets.push_back(set[i]); } } sort(tvsets.begin(), tvsets.end()); for (int i = 0; i < tvsets.size(); ++i) { tvsets[i].doit(); } dp.resize(tvsets.size() + 1); dp[0] = vector
                             
                              
                                >(1, vector
                               
                                (1, 0));// dp[0][0][0] = 0; int curSum = 0, curMax = 0; for (int i = 0; i < tvsets.size(); ++i) { int nextSum = curSum + tvsets[i].n; int nextMax = tvsets[i].n; if(i>0) dp[i-1].clear(); dp[i + 1] = vector
                                
                                 
                                   >(nextSum + 1, vector
                                  
                                   (nextMax + 1, -INF)); TVSet&set = tvsets[i]; for (int j = 0; j <= curSum; ++j) { for (int k = 0; k <= curMax; ++k) { int c = dp[i][j][k]; if (c == -INF) continue; for (int me = 0; me <= set.n; ++me) { int nc = c + set.maxret[me]; int nk = max(me, k); if (nc > dp[i + 1][j + me][nk]) { dp[i + 1][j + me][nk] = nc; } } } } curSum = nextSum, curMax = nextMax; } int best = 0; for (int j = 0; j <= curSum; ++j) { for (int k = 0; k <= curMax; ++k) if (k + k - 1 <= j) { if (dp[tvsets.size()][j][k] > best) { best = dp[tvsets.size()][j][k]; } } } cout << best << endl;}