预计分数：0+30+30=60

实际分数：0+30+40=70

T1水题(water)

贪心，按长度排序，

对于第一幅牌里面的，在第二个里面，找一个长度小于，高度最接近的牌

进行覆盖。

考场上的我离正解只差一个小于号之遥。。。。。。。

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <iostream>

 #include <set>

 using namespace std;

 int n;

 multiset <int> s;

 struct node {int x,y;} a[],b[];

 int cmp(node i,node j) {return i.x<j.x;}

 int main()

 {

     freopen("water.in","r",stdin);

     freopen("water.out","w",stdout);

     int T;

     T=;

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);

         for(int i=;i<n;i++) scanf("%d%d",&b[i].x,&b[i].y);

         sort(a,a+n,cmp);

         sort(b,b+n,cmp);

         s.clear();

         int k=,ans=;

         for(int i=;i<n;i++)

         {

             while(a[i].x>=b[k].x&&k<n)

             {

                  s.insert(b[k].y);

                  k++;

             }

             if(s.empty())continue;

             multiset<int>::iterator it=s.upper_bound(a[i].y);

             if (it==s.begin()) continue; it--;

             ans++; s.erase(it);

         }

         printf("%d\n",ans);

     }

     return ;

 }

T2下午梦境(dream)

不会做，手玩30分

正解

dp||爆搜

1 2 4 8 ...
1 3 7 15 31 ...
int(log(n)/log(2))+1

方案总数：dp，搜索

2^0+2^1+...+2^k = O(n)
k=log(n)
dfs(Max,Sum,S) // Max金币最大值，Sum所有金币的和，S金币的数量

dp[i][j][k] 当前有i个金币，金币和是j，最大的金币k。

if (dp[i][j][k]) 枚举下一枚金币是啥。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int MAXN=1e6;

 inline int read()

 {

     char c=getchar();int flag=,x=;

     while(c<''||c>'')    {if(c=='-')    flag=-;c=getchar();}

     while(c>=''&&c<='')     x=x*+c-,c=getchar();return x*flag;

 }

 int n;

 int main()

 {

     //freopen("dream.in","r",stdin);

     //freopen("dream.out","w",stdout);

     n=read();

     if(n==)    printf("0 1");

     if(n==)    printf("1 1");

     if(n==)    printf("2 1");

     if(n==)    printf("2 1");

     if(n==)    printf("3 1");

     if(n==)    printf("3 2");

     if(n==)    printf("3 2");

     if(n==)    printf("3 1");

     if(n==)    printf("4 8");

     if(n==)    printf("4 8");

     if(n==)    printf("4 8");

     if(n>)    printf("5 6");

     return ;

 }

 #include <cmath>

 #include <cstdio>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int n,sum,ans,dp[][],DP[][],i,j,k,l;

 int main()

 {

     freopen("dream.in","r",stdin);

     freopen("dream.out","w",stdout);

     scanf("%d",&n);

     sum=int(log(n)/log()+0.000000001)+;

     dp[][]=;

     for (i=; i<sum; i++)

     {

         for (j=; j<=n; j++)

           for (k=; k<=n; k++)

             if (dp[j][k])

               for (l=k+; l<=j+; l++)

                 DP[min(n,j+l)][l]+=dp[j][k];

         for (j=; j<=n; j++) for (k=; k<=n; k++) {dp[j][k]=DP[j][k];DP[j][k]=;}

     }

     for (j=; j<=n; j++) ans+=dp[n][j];

     cout<<sum<<' '<<ans;

     return ;

 }

标程

T3动态规划(dp)

题目描述

LYK在学习dp，有一天它看到了一道关于dp的题目。

这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想让最终这n个数的价值和尽可能少。

例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。

LYK并不会做，丢给了你。

输入输出格式

输入格式：

第一行两个数n,k。

接下来一行n个数ai表示这n个数。

输出格式：

一个数表示答案。

输入输出样例

输入样例#1：复制

10 2

1 2 1 2 1 2 1 2 1 2

输出样例#1：复制

说明

对于30%的数据n<=10。

对于60%的数据n<=1000。

对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。

其中有30%的数据满足ai完全相同均匀分布在所有数据中。

考场上我想出60分的dp了

但是我感觉不对，直觉告诉我一定不对，。

但实际上是对的mmp。。。。。

打了30分暴力走人，，

正解：

dp[i][j] 1~i 切了j刀，的最优解

dp[i][j]=min{dp[k][j-1]+sum(k+1,i)}

可以证明这个转移方程具有单调性

20*n^2的简单dp -> 在固定j的情况下随着i的增大，k不降 -> 分治求dp值

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define N 1000011

 #define min(x, y) ((x) < (y) ? (x) : (y))

 #define max(x, y) ((x) > (y) ? (x) : (y))

 using namespace std;

 int n, q, ans;

 int f[N];

 struct node

 {

     int x, y, z;

 }p[N], t[N];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline bool cmp(node x, node y)

 {

     return x.z > y.z;

 }

 inline int find(int x)

 {

     return x == f[x] ? x : f[x] = find(f[x]);

 }

 inline bool check(int k)

 {

     int i, j, x, y, lmin, lmax, rmin, rmax;

     for(i = ; i <= n + ; i++) f[i] = i;

     for(i = ; i <= k; i++) t[i] = p[i];

     std::sort(t + , t + k + , cmp);

     lmin = lmax = t[].x;

     rmin = rmax = t[].y;

     for(i = ; i <= k; i++)

     {

         if(t[i].z < t[i - ].z)

         {

             if(find(lmax) > rmin) return ;

             for(j = find(lmin); j <= rmax; j++)

                 f[find(j)] = find(rmax + );

             lmin = lmax = t[i].x;

             rmin = rmax = t[i].y;

         }

         else

         {

             lmin = min(lmin, t[i].x);

             lmax = max(lmax, t[i].x);

             rmin = min(rmin, t[i].y);

             rmax = max(rmax, t[i].y);

             if(lmax > rmin) return ;

         }

     }

 //    cout<<find(1)<<endl;

     if(find(lmax) > rmin) return ;

     return ;

 }

 int main()

 {

     freopen("number.in","r",stdin);

     freopen("number.out","w",stdout);

     int i, x, y, mid;

     n = read();

     q = read();

     for(i = ; i <= q; i++)

         p[i].x = read(), p[i].y = read(), p[i].z = read();

     x = , y = q;

     //cout<<check(2)<<endl;

     //return 0;

     ans = q + ;

     while(x <= y)

     {

         mid = (x + y) >> ;

         if(check(mid)) ans = mid, y = mid - ;

         else x = mid + ;

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

Day1下午解题报告