前言:OTL
JZOJ 5461 购物
题目
有m块钱,k张优惠券,n个物品每个物品原价 P i P_i Pi元,优惠价 Q i Q_i Qi元,问最多可以买多少个物品(优惠券每个物品最多使用一次)
分析
k k k张优惠券能用完肯定尽量用完,所以可以想到维护一个以优惠差值的大小为顺序的堆,首先先插入优惠价最小的 k k k个商品,然后不断地把堆中的商品变成原价或把新的商品变成优惠价,其实就是运用了贪心的思想并用堆维护
代码
#include <cstdio>
#include <queue>
#include <algorithm>
#define rr register
using namespace std;
struct rec{
int p,q;
bool operator<(const rec &x)const{
return p-q<x.p-x.q;
}
}a[50001]; priority_queue<rec>Q;
int n,k,ans; long long m;
int in(){
rr int ans=0; rr char c=getchar();
while (c<48||c>57) c=getchar();
while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
return ans;
}
bool cmp(rec x,rec y){return x.q<y.q;}
int main(){
n=in(); k=in(); scanf("%lld",&m);
for (rr int i=1;i<=n;i++) a[i]=(rec){in(),in()};
sort(a+1,a+1+n,cmp); rr priority_queue<int>q;
for (rr int i=1;i<=n;i++)
if (Q.size()<k&&m>=a[i].q) m-=a[i].q,ans++,Q.push(a[i]);//k个优惠商品未插入完
else if (Q.size()==k){
rr rec x=Q.top();
if (x.p-x.q+a[i].q<a[i].p){//补差值
Q.pop(); Q.push(a[i]);
m-=a[i].q-x.q;
if (m>=x.p) m-=x.p,ans++,q.push(x.p);//新增原价商品
else if (q.size()&&q.top()>x.p){//找出一样价格低的商品替换
rr int y=q.top(); q.pop(); q.push(x.p);
m+=y-x.p;
}
}
else if (m>=a[i].p) m-=a[i].p,ans++,q.push(a[i].p);//原价商品
else if (q.size()&&q.top()>a[i].p){//找出一样价格低的商品替换
rr int y=q.top(); q.pop(); q.push(a[i].p);
m+=y-a[i].p;
}
}
return !printf("%d",ans);
}
JZOJ 5455 拆网线
题目
在一棵 n n n个节点上的树上取 k k k个节点,至少保留多少条边能使树上的连通点数不少于2且两两配对
分析
由于树上的父节点<子节点,虽然从根节点跑是行不通的,但是可以从最后一个节点与所连边进行匹配(两两配对),那么以下会分为三种情况
- 配对组数 × 2 = \times2= ×2=保留的节点数,那么配对组数即为答案
- 配对组数 × 2 < \times2< ×2<保留的节点数,那么需要新增一些边,新增的数量为(保留节点数-配对组数 × 2 \times2 ×2) ÷ 2 \div2 ÷2
- 否则需要删除一些边,删除的数量为(配对组数 × 2 \times2 ×2-保留节点数) ÷ 2 \div2 ÷2
代码
#include <cstdio>
#define rr register
int in(){
int ans=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int main(){
rr int t=in();
while (t--){
rr int n=in(),k=in(),e[n],ans=0; rr bool v[n]; v[0]=0;
for (rr int i=1;i<n;i++) e[i]=in()-1;
for (rr int i=n-1;i;i--)
if (!v[i]&&!v[e[i]]) ans++,v[e[i]]=1;//两两配对(逆向)
if (ans*2<k) ans+=k-ans*2; else if (ans*2>k) ans-=(ans*2-k)/2;//多出的或少的
if (ans) print(ans); else putchar(48); putchar(10);
}
return 0;
}
JZOJ 5459 密室
题目
在一个有向图中,每个点都能获得若干种钥匙,而若要到其它点需要特定的钥匙用来走单向边(钥匙不会消失),问最少经过多少条边从起点走向终点
分析
这些钥匙是否存在可以用二进制表示,当然,按照这样的思维,可以用 s p f a spfa spfa完成这道题,当然需要修改一些地方。
伪代码
while (q.size()){
rr int u=q.front().first,t=q.front().second; q.pop();
for (rr int i=ls[u];i;i=e[i].next)
if ((t&e[i].w)==e[i].w&&dis[e[i].y][t|a[e[i].y]]>dis[u][t]+1){//除了正常的松弛操作,还要判断是否存在
dis[e[i].y][t|a[e[i].y]]=dis[u][t]+1;
if (!v[e[i].y][t|a[e[i].y]])//多的钥匙用按位或得到
v[e[i].y][t|a[e[i].y]]=1,q.push(std::make_pair(e[i].y,t|a[e[i].y]));
}
v[u][t]=0;
}
当然讲了这么多最后判断最小值就可以了
思考:对空间的优化(我不打是因为我不会)
代码
#include <cstdio>
#include <cstring>
#include <queue>
#define rr register
struct node{int y,w,next;}e[6001]; std::queue<std::pair<int,int> >q;
int n,m,k,dis[5001][1024],ls[5001],a[5001],ans=2147483647; bool v[5001][1024];
int in(){
int ans=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
return ans;
}
int min(int a,int b){return (a<b)?a:b;}
int main(){
n=in(); m=in(); k=in();
if (n==1) return !putchar('0');//特判
for (rr int i=1;i<=n;i++)
for (rr int j=k;j>=1;j--) if (in()) a[i]|=1<<j-1;//输入点权
for (rr int i=1;i<=m;i++){
rr int x=in();
e[i]=(node){in(),0,ls[x]}; ls[x]=i; //邻接表
for (rr int j=k;j>=1;j--) if (in()) e[i].w|=1<<j-1;
}
memset(dis,127/3,sizeof(dis)); q.push(std::make_pair(1,a[1])); v[1][a[1]]=1; dis[1][a[1]]=0;
while (q.size()){
rr int u=q.front().first,t=q.front().second; q.pop();
for (rr int i=ls[u];i;i=e[i].next)
if ((t&e[i].w)==e[i].w&&dis[e[i].y][t|a[e[i].y]]>dis[u][t]+1){//松弛
dis[e[i].y][t|a[e[i].y]]=dis[u][t]+1;
if (!v[e[i].y][t|a[e[i].y]])
v[e[i].y][t|a[e[i].y]]=1,q.push(std::make_pair(e[i].y,t|a[e[i].y]));//加入队列
}
v[u][t]=0;
}
for (rr int i=0;i<1<<k;i++) ans=min(ans,dis[n][i]);//求最小值
if (ans==707406378) printf("No Solution"); else printf("%d",ans);
return 0;
}