(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。
#include
#include
#include
#define maxn 100010
using namespace std;
int n,ans;
struct node{
int x,y;
bool operator <(const node c)const{
if(x!=c.x)return x<c.x;
return y<c.y;
}
}a[maxn],b[maxn];
bool vis[maxn];
int qread(){
int i=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch<='9'&&ch>='0')i=i*10+ch-'0',ch=getchar();
return i;
}
int find(node now){
int pos=n+1,res=n+1;
int l=1,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(b[mid].x<=now.x)pos=mid,l=mid+1;
else r=mid-1;
}
if(pos==n+1)return pos;
for(int i=pos;i>=1;i--)
if(b[i].y<=now.y&&!vis[i]){vis[i]=1;res=i;break;}
return res;
}
int main(){
freopen("water.in","r",stdin);freopen("water.out","w",stdout);
// freopen("Cola.txt","r",stdin);
n=qread();
for(int i=1;i<=n;i++)a[i].x=qread(),a[i].y=qread();
for(int i=1;i<=n;i++)b[i].x=qread(),b[i].y=qread();
sort(a+1,a+n+1);sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
int pos=find(a[i]);
if(pos==n+1)continue;
ans++;
}
printf("%d",ans);
return 0;
}
/*
首先很容易想到贪心,但是按照长或宽来贪心贪心会遇到一种情况
A:(x[i],y[i])
B:(x[i],1),(1,y[i])
这时候我们不能确定A对应B的哪一个会更优,所以我们换一种策略
对两副牌按照x进行排序,每次遇到B类牌,将y值插入到一个multiset中,遇到A类牌(不考虑x),找到这个multisetzhongy值尽量大且不超过这张牌的y值
*/
#include
#include
#include
#include<set>
#define maxn 100010
using namespace std;
int n;
multiset<int>s;
struct node{int x,y;}a[maxn],b[maxn];
bool cmp(node x,node y){return x.x<y.x;}
int main(){
freopen("water.in","r",stdin);freopen("water.out","w",stdout);
// freopen("Cola.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)scanf("%d%d",&b[i].x,&b[i].y);
sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
int k=1,ans=0;
for(int i=1;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",ans);
return 0;
}
(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。
#include
#include
#include
#define maxn 1001
using namespace std;
int n,q[maxn],ans1=0x7fffffff,ans2;
int que[maxn],t,opv;
bool flag;
void find(int pos,int now){
if(now==opv){
flag=1;
return;
}
if(now>opv)return;
if(flag)return;
if(pos==t+1)return;
find(pos+1,now+que[pos]);
if(flag)return;
find(pos+1,now);
if(flag)return;
}
bool check(){
t=0;
for(int i=1;i<=n;i++)
if(q[i])que[++t]=i;
for(int i=1;i<=n;i++){
flag=0;opv=i;
find(1,0);
if(flag==0)return 0;
}
return 1;
}
void dfs(int pos,int cnt){
if(cnt>ans1)return;
if(pos==n+1){
if(check()){
if(cnt<ans1){
ans1=cnt;
ans2=0;
}
if(cnt==ans1)ans2++;
}
return;
}
if(pos>2)dfs(pos+1,cnt);
q[pos]=1;
dfs(pos+1,cnt+1);
q[pos]=0;
}
int main(){
// freopen("Cola.txt","r",stdin);
// freopen("T2_table.txt","w",stdout);
ans1=7;
for(n=77;n<=100;n++){
ans1++;
ans2=0;
// cin>>n;
dfs(1,0);
// printf("%d %d\n",ans1,ans2);
printf(" if(n==%d)cout<<%d<<' '<<%d;\n",n,ans1,ans2);
}
}
#include
#include
using namespace std;
int n;
int main(){
freopen("dream.in","r",stdin);freopen("dream.out","w",stdout);
scanf("%d",&n);
if(n==1)cout<<1<<' '<<1;
if(n==2)cout<<2<<' '<<1;
if(n==3)cout<<2<<' '<<1;
if(n==4)cout<<3<<' '<<2;
if(n==5)cout<<3<<' '<<2;
if(n==6)cout<<3<<' '<<2;
if(n==7)cout<<3<<' '<<1;
if(n==8)cout<<4<<' '<<8;
if(n==9)cout<<4<<' '<<8;
if(n==10)cout<<4<<' '<<8;
if(n==11)cout<<4<<' '<<7;
if(n==12)cout<<4<<' '<<6;
if(n==13)cout<<4<<' '<<4;
if(n==14)cout<<4<<' '<<2;
if(n==15)cout<<4<<' '<<1;
if(n==16)cout<<5<<' '<<59;
if(n==17)cout<<5<<' '<<58;
if(n==18)cout<<5<<' '<<56;
if(n==19)cout<<5<<' '<<53;
if(n==20)cout<<5<<' '<<49;
if(n==21)cout<<5<<' '<<44;
if(n==22)cout<<5<<' '<<38;
if(n==23)cout<<5<<' '<<32;
if(n==24)cout<<5<<' '<<26;
if(n==25)cout<<5<<' '<<20;
if(n==26)cout<<5<<' '<<14;
if(n==27)cout<<5<<' '<<10;
if(n==28)cout<<5<<' '<<6;
if(n==29)cout<<5<<' '<<4;
if(n==30)cout<<5<<' '<<2;
if(n==31)cout<<5<<' '<<1;
if(n==32)cout<<6<<' '<<724;
if(n==33)cout<<6<<' '<<701;
if(n==34)cout<<6<<' '<<674;
if(n==35)cout<<6<<' '<<644;
if(n==36)cout<<6<<' '<<611;
if(n==37)cout<<6<<' '<<576;
if(n==38)cout<<6<<' '<<538;
if(n==39)cout<<6<<' '<<500;
if(n==40)cout<<6<<' '<<459;
if(n==41)cout<<6<<' '<<419;
if(n==42)cout<<6<<' '<<378;
if(n==43)cout<<6<<' '<<339;
if(n==44)cout<<6<<' '<<299;
if(n==45)cout<<6<<' '<<264;
if(n==46)cout<<6<<' '<<228;
if(n==47)cout<<6<<' '<<197;
if(n==48)cout<<6<<' '<<166;
if(n==49)cout<<6<<' '<<140;
if(n==50)cout<<6<<' '<<114;
if(n==51)cout<<6<<' '<<94;
if(n==52)cout<<6<<' '<<74;
if(n==53)cout<<6<<' '<<60;
if(n==54)cout<<6<<' '<<46;
if(n==55)cout<<6<<' '<<36;
if(n==56)cout<<6<<' '<<26;
if(n==57)cout<<6<<' '<<20;
if(n==58)cout<<6<<' '<<14;
if(n==59)cout<<6<<' '<<10;
if(n==60)cout<<6<<' '<<6;
if(n==61)cout<<6<<' '<<4;
if(n==62)cout<<6<<' '<<2;
if(n==63)cout<<6<<' '<<1;
if(n==64)cout<<7<<' '<<14077;
if(n==65)cout<<7<<' '<<13636;
if(n==66)cout<<7<<' '<<13176;
if(n==67)cout<<7<<' '<<12714;
if(n==68)cout<<7<<' '<<12233;
if(n==69)cout<<7<<' '<<11760;
if(n==70)cout<<7<<' '<<11268;
if(n==71)cout<<7<<' '<<10787;
if(n==72)cout<<7<<' '<<10293;
if(n==73)cout<<7<<' '<<9813;
if(n==74)cout<<7<<' '<<9320;
if(n==75)cout<<7<<' '<<8849;
if(n==76)cout<<7<<' '<<8365;
if(n==77)cout<<7<<' '<<7906;
return 0;
}
/*
dp[k][i][j]选了k个硬币,最大硬币是j,硬币总合是i的方案数
这样会爆空间,所以压掉第一维
代码中的dp[i][j]是上一个状态,DP[i][j]是当前状态
由于硬币总和可能大于n,而小于n是绝对不行的,所以把大于n的情况视为等于n,最后统计答案累加dp[n][1~n]即可
*/
#include
#include
#include
#include
#include
using namespace std;
int n,sum,ans,dp[1005][1005],DP[1005][1005],i,j,k,l;
int main()
{
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
scanf("%d",&n);
sum=int(log(n)/log(2)+0.000000001)+1;
dp[1][1]=1;
for (i=1; i)
{
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
if (dp[j][k])
for (l=k+1; l<=j+1; l++)
DP[min(n,j+l)][l]+=dp[j][k];
for (j=1; j<=n; j++) for (k=1; k<=n; k++) {dp[j][k]=DP[j][k];DP[j][k]=0;}
}
for (j=1; j<=n; j++) ans+=dp[n][j];
cout<' '<<ans;
return 0;
}
#include
#include
#include
using namespace std;
int ans1,ans2,n;
void dfs(int mx,int sum,int cnt){
if(cnt==ans1){
if(sum>=n)ans2++;
return;
}
for(int i=mx+1;i<=sum+1;i++){
dfs(i,sum+i,cnt+1);
}
}
int main(){
freopen("dream.in","r",stdin);freopen("dream.out","w",stdout);
scanf("%d",&n);
ans1=int(log(n)/log(2)+0.000000001)+1;
dfs(0,0,0);
cout<' '<<ans2;
}
(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完全相同均匀分布在所有数据中。
#include
#include
#include
#define maxn 100010
using namespace std;
int n,k,a[maxn],tim[maxn],b[maxn];
long long ans=100000000000000000;
bool flag=1;
long long count(int l,int r){
long long res=0;int t=0;
// for(int i=l;i<=r;i++)
// for(int j=i+1;j<=r;j++)
// if(a[i]==a[j])res++;
for(int i=l;i<=r;i++)b[++t]=a[i];
sort(b+1,b+t+1);b[t+1]=0;
int la=1;
for(int i=2;i<=t+1;i++){
if(b[i]!=b[i-1]){
res+=1LL*(i-la)*(i-la-1)/(long long)2;
la=i;
}
}
return res;
}
void dfs(int pos,int pre,long long sum,int cut){
if(cut==k){
ans=min(ans,sum+count(pre+1,n));
return;
}
if(n-posreturn;
if(sum>=ans)return;
if(pos>n)return;
dfs(pos+1,pos,sum+count(pre+1,pos),cut+1);
dfs(pos+1,pre,sum,cut);
}
int main(){
freopen("dp.in","r",stdin);freopen("dp.out","w",stdout);
// freopen("Cola.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i!=1&&a[i]!=a[i-1])flag=0;
tim[a[i]]++;
}
int c=0,mark=n;
for(int i=1;i<=n;i++){
if(tim[i]>1)c++,mark=tim[i];
}
if(c==0){
cout<<0;return 0;
}
if(c==1){
n=mark;flag=1;
}
if(flag){
int w=n/k;
int v=n%k;
long long x=w+1;
long long Ans=v*1LL*(x-1)*(x)/(long long)2;
x--;
Ans+=1LL*(k-v)*(x-1)*(x)/(long long)2;
cout<<Ans;
return 0;
}
k--;
dfs(1,0,0,0);
cout<<ans;
}
#include
#include
#include
#define maxn 1000010
using namespace std;
int c[maxn],a[maxn];
long long tot,f[maxn],g[maxn];
int p,q,n,k;
void move(int l,int r){
while(l;
while(r>q)q++,tot+=c[a[q]],c[a[q]]++;
while(p;
while(r;
}
void work(int l,int r,int fl,int fr){
if(fl>fr)return;
int mid=(fl+fr)>>1,mi;
long long mx=1LL<<60;
for(int i=l;i<=r;i++)
if(i<mid){
move(i+1,mid);
if(f[i]+toti;
}
g[mid]=mx;
work(l,mi,fl,mid-1);
work(mi,r,mid+1,fr);
}
int main(){
freopen("dp.in","r",stdin);freopen("dp.out","w",stdout);
// freopen("Cola.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
f[0]=0;
for(int i=1;i<=n;i++)f[i]=1LL<<60;
while(k--){
p=1,q=0,tot=0;
memset(c,0,sizeof(c));
work(0,n-1,1,n);
for(int i=0;i<=n;i++)f[i]=g[i],g[i]=0;
}
cout<<f[n];
return 0;
}
预计得分80+30+50
实际得分10+30+60
T1看上去是个贪心,就用一个看起来很优的贪心策略写了一下,有一种情况没有考虑到,所以炸了
T2T3都是暴力做法,T3正解是dp,老师讲的听不懂