水题(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。

/*T1 贪心
可以对x[i]排序
每次遇到B类牌,将y值插入数据结构中查前驱,删除。
n^2数组 80分
splay或权值线段树或multiset 100*/ #include<bits/stdc++.h> #define N 100007 using namespace std;
int n;
multiset<int>s;
struct node{
int x,y;
} a[N],b[N];
int cmp(node A,node B){return A.x<B.x;} int main()
{
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 ;
}

梦境(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。

/*
可以搜索dfs(Max,sum,tot)//Max为金币最大值 sum<s^tot
s^0+2^1+....2^k
k=log n
大约是O(n)级别,复杂度n^2 */
#include<cstdio>
#include<iostream>
using namespace std;
int n,ans,sum; void dfs(int k,int d,int l,int r)
{
if(k==d)
{
sum+=min(max(r-(n-r),),r-l+);
return;
}
for(int i=l; i<=r; i++) dfs(k+,d,i+,r+i);
}
int main()
{
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
scanf("%d",&n);
for(int i=; i<=n; i<<=) ans++;
dfs(,ans,,);
printf("%d %d\n",ans,sum);
return ;
}

dfs

/*
dp
dp[i][j][k]当前i个金币,和为j,数量为k。枚举下一个金币是啥。
可以if(dp[i][j][k]) 才枚举下一个。优化了。
*/
#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 ;
}

动态规划(dp)

Time Limit:2000ms   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

60分

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

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

k可以从大到小枚举,每次更新sum

复杂度n^2*k

100分

当固定j,随着i增大,k不可能变小

因此具有决策单调性。

类似1D1D动态规划思想

考虑60分代码

cin>>n>>m;

for (i=1; i<=n; i++) g[i]=sum(1,i);

for (j=1; j<=m; j++)

{

for (i=1; i<=n; i++) {f[i]=g[i]; g[i]=1000000000;}

for (i=1; i<=n; i++) //求g[1]~g[n]

for (k=i-1; k>=0; k--) //g[1]~g[n]有可能能从f[0]~f[n-1]转移而来

g[i]=min(g[i],f[k]+sum(k+1,i));

}

cout<<g[n];

for (i=1; i<=n; i++) //求g[1]~g[n]

for (k=i-1; k>=0; k--) //g[1]~g[n]有可能能从f[0]~f[n-1]转移而来

g[i]=min(g[i],f[k]+sum(k+1,i));

void work(int l,int r,int fl,int fr) //要求g[fl]~g[fr],可以用f[l]~f[r]进行转移

{

if (fl>fr) return;

int mid=(fl+fr)>>1,mi;

LL mx=1LL<<60;

for (int i=l;i<=r;i++) // 求g[mid]

if (i<mid)

{

move(i+1,mid); //求sum(i+1,mid) -> tot;

if (f[i]+tot<mx) mx=f[i]+tot,mi=i;

}

//mi 表示最优解的位置,mx 最优解是多少

g[mid]=mx;

work(l,mi,fl,mid-1);

work(mi,r,mid+1,fr);

}

work(0,n-1,1,n)  // 求g[1]~g[n]  可以用f[0]~f[n-1]转移

c[i] i这个数字在当前区间出现了几次

#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
typedef long long LL;
int c[N],a[N];
LL f[N],g[N];
int p,q,n,k;
LL tot;
void move(int l,int r) // [p,q]之前的区间
{
while (l<p) p--,tot+=c[a[p]],c[a[p]]++;
while (r>q) q++,tot+=c[a[q]],c[a[q]]++;
while (p<l) c[a[p]]--,tot-=c[a[p]],p++;
while (r<q) c[a[q]]--,tot-=c[a[q]],q--;
}
void work(int l,int r,int fl,int fr)
//需要求dp[fl] ~ dp[fr] 最优解一定从l~r中的某一个转移过来
{
if (fl>fr) return;
int mid=(fl+fr)>>,mi;
LL mx=1LL<<;
for (int i=l;i<=r;i++)
if (i<mid)
{
move(i+,mid); -> tot=sum(i+,mid);
if (f[i]+tot<mx) mx=f[i]+tot,mi=i;
}
g[mid]=mx;
work(l,mi,fl,mid-);
work(mi,r,mid+,fr);
}
int main()
{
freopen("dp.in","r",stdin);
freopen("dp.out","w",stdout);
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
f[]=;
for (int i=;i<=n;i++) f[i]=1LL<<;
while (k--)
{
p=,q=,tot=;
for (int i=;i<=n;i++) c[i]=;
work(,n-,,n);
for (int i=;i<=n;i++) f[i]=g[i],g[i]=;
}
cout<<f[n];
return ;
}
05-13 22:13