2017-10-28-afternoon-清北模拟赛

T1 水题(water)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK出了道水题。

这个水题是这样的：有两副牌，每副牌都有n张。

对于第一副牌的每张牌长和宽分别是xi和yi。对于第二副牌的每张牌长和宽分别是aj和bj。第一副牌的第i张牌能覆盖第二副牌的第j张牌当且仅当xi>=aj并且yi>=bj。（注意牌不能翻转）当然一张牌只能去覆盖最多一张牌，而不能覆盖好多张。

LYK想让两副牌的各n张一一对应叠起来。它想知道第二副牌最多有几张能被第一副牌所覆盖。

输入格式(water.in)

    第一行一个数n。

    接下来n行，每行两个数xi,yi。

    接下来n行，每行两个数aj,bj。

输出格式(water.out)

输出一个数表示答案。

输入样例

3

2 3

5 7

6 8

4 1

2 5

3 4

输出样例

2

数据范围

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

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

对于100%的数据1<=n<=100000，1<=xi,yi,aj,bj<=10^9。

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 inline void read(int &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 const int N(100005);
11 int n,ans;
12 struct Node {
13     int x,y;
14     bool operator < (const Node&z)const
15     {
16         if(x==z.x) return y<z.y;
17         return x<z.x;
18     }
19 }a[N],b[N];
20 const int M(1005);
21 int vis[M][M],sumvis;
22 int link[M][M],mat[M];
23 
24 bool find(int u)
25 {
26     for(int v=1; v<=n; ++v)
27       if(link[u][v]&&vis[u][v]!=sumvis)
28       {
29           vis[u][v]=sumvis;
30           if(!mat[v]||find(mat[v]))
31           {
32               mat[v]=u;
33               return 1;
34         }
35       }
36     return 0;
37 }
38 
39 inline void violence()
40 {
41     for(int i=1; i<=n; ++i)
42       for(int j=1; j<=n; ++j)
43           link[i][j]=(a[i].x>=b[j].x&&a[i].y>=b[j].y);
44     for(int i=1; i<=n; ++i)
45     {
46         sumvis++;
47         if(find(i)) ans++;
48     }
49     printf("%d
",ans);
50 }
51 
52 int Presist()
53 {
54 //    freopen("1.txt","r",stdin);
55     freopen("water.in","r",stdin);
56     freopen("water.out","w",stdout);
57     read(n);
58     for(int i=1; i<=n; ++i)
59         read(a[i].x),read(a[i].y);
60     for(int i=1; i<=n; ++i)
61         read(b[i].x),read(b[i].y);
62     if(n<=1000) violence();
63     return 0;
64 }
65 
66 int Aptal=Presist();
67 int main(int argc,char**argv){;}
匈牙利，60分

 因为可能存在 xi,yi=1,,,xj==1,yj，的情况，这种情况下，无法确定怎样覆盖更优，

所以可以以xi从小到大排序，在满足xi的情况下，将B组的y放到某数据结构中，再找满足A组的y的最大的y

需要有插入，删除不超过y的最大数的数据结构，数组80，muliset/平衡树/权值线段树

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <set>
 4 
 5 inline void read(int &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 const int N(100005);
12 
13 std:: multiset<int>set_;
14 
15 struct Card {
16     int x,y;
17     bool operator < (const Card&c)const
18     {
19         return x<c.x;
20     }
21 }a[N],b[N];
22 
23 int Presist()
24 {
25     freopen("water.in","r",stdin);
26     freopen("water.out","w",stdout);
27     int n,ans=0; read(n);
28     for(int i=1; i<=n; ++i)
29         read(a[i].x),read(a[i].y);
30     for(int i=1; i<=n; ++i)
31         read(b[i].x),read(b[i].y);
32     std:: sort(a+1,a+n+1);
33     std:: sort(b+1,b+n+1);
34     for(int i=1,j=1; i<=n; ++i)
35     {
36         for(; a[i].x>=b[j].x&&j<=n; )
37             set_.insert(b[j].y),++j;
38         if(set_.empty()) continue;
39         std:: multiset<int>:: iterator it=set_.upper_bound(a[i].y);
40         if(it==set_.begin()) continue;
41         else ans++,set_.erase(--it);
42     }
43     printf("%d
",ans);
44     return 0;
45 }
46 
47 int Aptal=Presist();
48 int main(int argc,char**argv){;}
AC

T2 梦境(dream)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK做了一个梦。

这个梦是这样的，LYK是一个财主，有一个仆人在为LYK打工。

不幸的是，又到了月末，到了给仆人发工资的时间。但这个仆人很奇怪，它可能想要至少x块钱，并且当LYK凑不出恰好x块钱时，它不会找零钱给LYK。

LYK知道这个x一定是1~n之间的正整数。当然抠门的LYK只想付给它的仆人恰好x块钱。但LYK只有若干的金币，每个金币都价值一定数量的钱（注意任意两枚金币所代表的钱一定是不同的，且这个钱的个数一定是正整数）。LYK想带最少的金币，使得对于任意x，都能恰好拼出这么多钱。并且LYK想知道有多少携带金币的方案总数。

具体可以看样例。

输入格式(dream.in)

    第一行一个数n，如题意所示。

输出格式(dream.out)

输出两个数，第一个数表示LYK至少携带的金币个数，第二数表示方案总数。

输入样例

6

输出样例

3 2

样例解释

LYK需要至少带3枚金币，有两种方案，分别是{1,2,3}，{1,2,4}来恰好得到任意的1~n之间的x。

输入样例2

10

输出样例2

4 8

数据范围

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

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

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

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 #define min(a,b) (a<b?a:b)
 5 
 6 inline void read(int &x)
 7 {
 8     x=0; register char ch=getchar();
 9     for(; ch>'9'||ch<'0'; ) ch=getchar();
10     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
11 }
12 const int N(1005);
13 int n,ans,count;
14 bool vis[N];
15 int a[N];
16 
17 void DFS(int num,int cnt,int sum)
18 {
19     if(sum>=n) { ans++; return ; }
20     if(cnt>count) { return ; }
21     for(int i=num+1; i<=min(a[cnt+1],sum+1); ++i)
22     {
23         if(vis[i]) continue; vis[i]=1;
24         DFS(i,cnt+1,sum+i); vis[i]=0;
25     }
26 }
27 
28 int Presist()
29 {
30 //    freopen("1.txt","r",stdin);
31     freopen("dream.in","r",stdin);
32     freopen("dream.out","w",stdout);
33     read(n);
34     for(int sum=0; sum<n; ++sum)
35         a[++count]=sum+1,sum<<=1;
36     DFS(0,0,0);
37     printf("%d %d
",count,ans);
38     return 0;
39 }
40 
41 int Aptal=Presist();
42 int main(int argc,char**argv){;}
爆搜30

方案总数：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]) 枚举下一枚金币是啥。

 1 #include <cstdio>
 2 
 3 #define min(a,b) (a<b?a:b)
 4 
 5 inline void read(int &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 int n,cnt,ans,f[11][1005][1005];
12 
13 int Presist()
14 {
15     freopen("dream.in","r",stdin);
16     freopen("dream.out","w",stdout);
17     
18     read(n);
19     for(; (1<<cnt)<=n; ) cnt++;
20     f[1][1][1]=1;
21     for(int i=1; i<cnt; ++i)
22       for(int j=1; j<=n; ++j)
23         for(int k=1; k<=n; ++k)
24         {
25             if(!f[i][j][k]) continue;
26             for(int p=k+1; p<=j+1; ++p)
27                 f[i+1][min(j+p,n)][p]+=f[i][j][k];
28         }
29     for(int i=1; i<=n; ++i) ans+=f[cnt][n][i];
30     printf("%d %d
",cnt,ans);
31     return 0;
32 }
33 
34 int Aptal=Presist();
35 int main(int argc,char**argv){;}
AC

T3 动态规划(dp)

Time Limit:1000ms   Memory Limit:128MB

题目描述

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并不会做，丢给了你。

输入格式(dp.in)

    第一行两个数n,k。

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

输出格式(dp.out)

一个数表示答案。

输入样例

10 2

1 2 1 2 1 2 1 2 1 2

输出样例

8

数据范围

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

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

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

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

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

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

这个k是从大到小进行枚举，每次枚举时更新这个sum 20*n^2  60分

 1 #include <cstring>
 2 #include <cstdio>
 3 
 4 #define min(a,b) (a<b?a:b)
 5 #define LL long long
 6 
 7 inline void read(int &x)
 8 {
 9     x=0; register char ch=getchar();
10     for(; ch>'9'||ch<'0'; ) ch=getchar();
11     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
12 }
13 const int N(100005);
14 int a[N],cnt[N],L,R;
15 int sum[1005][1005];
16 LL f[1005][1005];
17 
18 int Presist()
19 {
20     freopen("dp.in","r",stdin);
21     freopen("dp.out","w",stdout);
22     
23     int n,k; read(n),read(k);
24     for(int i=1; i<=n; ++i) read(a[i]);
25     for(int i=1; i<=n; ++i)
26     {
27         ++cnt[a[i]];
28         for(int j=i+1; j<=n; ++j)
29              sum[i][j]=sum[i][j-1]+cnt[a[j]],++cnt[a[j]];
30         memset(cnt,0,sizeof(cnt));
31     }
32     for(int i=1; i<=n; ++i)
33       for(int j=1; j<=k; ++k)
34         f[i][j]=0x7fffffff;
35     for(int i=1; i<=n; ++i)
36     {
37         f[i][1]=sum[1][i];
38         for(int j=2; j<=min(i,k); ++j)
39           for(int t=0; t<i; ++t)
40             f[i][j]=min(f[i][j],f[t][j-1]+sum[t+1][i]);
41     }
42     printf("%d
",f[n][k]);
43     return 0;
44 }
45 
46 int Aptal=Presist();
47 int main(int argc,char**argv){;}
View Code

固定j，随着i的增大，k不会减少

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

 1 #include <cstring>
 2 #include <cstdio>
 3 
 4 #define LL long long
 5 
 6 inline void read(int &x)
 7 {
 8     x=0; register char ch=getchar();
 9     for(; ch>'9'||ch<'0'; ) ch=getchar();
10     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
11 }
12 const int N(100005);
13 int a[N],cnt[N],L,R;
14 LL f[N],g[N],sum;
15 
16 inline void move(int l,int r)
17 {
18     for(; L>l; ) sum+=cnt[a[--L]]++;
19     for(; L<l; ) sum-=--cnt[a[L++]];
20     for(; R>r; ) sum-=--cnt[a[R--]];
21     for(; R<r; ) sum+=cnt[a[++R]]++;
22 }
23 
24 void work(int u,int v,int l,int r)
25 {
26     if(l>r) return ;
27     int mid=l+r>>1,pos;
28     LL minn=0x7fffffff;
29     for(int i=u; i<mid&&i<=v; ++i)
30     {
31         move(i+1,mid);
32         if(sum+f[i]<minn)
33           minn=sum+f[i],pos=i;
34     }
35     g[mid]=minn;
36     work(u,pos,l,mid-1);
37     work(pos,v,mid+1,r);
38 }
39 
40 int Presist()
41 {
42     freopen("dp.in","r",stdin);
43     freopen("dp.out","w",stdout);
44     
45     int n,k; read(n),read(k);
46     for(int i=1; i<=n; ++i) read(a[i]);
47     for(int i=1; i<=n; ++i) f[i]=0x7fffffff;
48     for(; k--; )
49     {
50         memset(cnt,0,sizeof(cnt));
51         L=1,R=0,sum=0,work(0,n-1,1,n);
52         for(int i=1; i<=n; ++i) f[i]=g[i],g[i]=0;
53     }
54     printf("%lld
",f[n]);
55     return 0;
56 }
57 
58 int Aptal=Presist();
59 int main(int argc,char**argv){;}
AC
——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Shy-key/p/7748160.html