【LDUOJ】2020年下半年第12周训练

【LDUOJ】2020年下半年第12周训练

目录

 

A. 偷天换日

题目大意：

题目思路：

Code:

C. 数对 

题目大意：

题目思路：

D. 阶乘和

题目大意：

题目思路：

F. 蛋糕店

题目大意：

题目思路：

Code:

G. 最小生成树

H. 买汽水 

题目大意：

题目思路：

Code:

---

A. 偷天换日

题目大意：

神偷对艺术馆内的名画垂涎欲滴准备大捞一把。
艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。
警察会在n秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

第一行一个整数n(n≤600n≤600)。
第二行若干组整数，对于每组整数(t,x)(t,x)，tt表示进入这个展览厅或经过走廊要耗费tt秒的时间，若x>0x>0表示走廊通向的展览厅内有x幅画,接下来x对整数(w,c)(w,c)表示偷一幅价值为ww的画需要cc秒的时间。若x=0x=0表示走廊一分为二。(t,c≤5t,c≤5;x≤30x≤30)
输入是按深度优先给出的。房间和走廊数不超过300个。

题目思路：

主要是按照深度优先遍历给出的，那么就直接dfs中回溯一下背包dp即可

注意有一个细节(由于忽略导致卡了一晚上...)

经过走廊就会花费，进入展厅和走出展厅都需要花费

所以不要忘记没每经过一个点花费要*2

其余的按照背包即可，其实也不需要背包(二叉树枚举就行了)，只需要在叶子节点进行背包即可

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lldn",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const ll mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;
}ll n,m,p;
int ls[maxn],rs[maxn];
ll num[maxn];
ll dp[2005][2005];
ll s[2005];
int cnt = 0;
void dfs(int &rt,ll w){rt = ++cnt;read(num[rt]);///花费int c;read(c);///数量if(c == 0){dfs(ls[rt],w+num[rt]);dfs(rs[rt],w+num[rt]);for(int k=0;k<=n;k++){for(int j=0;j<=n;j++){if(j+k+2*num[rt] <= n)dp[rt][j+k+2*num[rt]] = max(dp[rt][j+k+2*num[rt]],dp[ls[rt]][j] + dp[rs[rt]][k]);}}}else{for(int i=1;i<=c;i++){int val,cost;read(val);read(cost);for(int k=n;k>=cost+2*num[rt];k--)dp[rt][k] = max(dp[rt][k-cost]+val,dp[rt][k]);}}
}
int main(){read(n);int root;dfs(root,0);ll ans = 0;printf("%lldn",dp[root][n-1]);return 0;
}

---

C. 数对 

题目大意：

定义友好数对(i,j)为，a_i与a_j 至少一个数字相同

给出n个数字，求友好数对的数量

题目思路：

数对！

---

D. 阶乘和

题目大意：

输出1! + 2! + 3! + ...n!

题目思路：

年轻人不讲武德，直接py秒掉即可

---

F. 蛋糕店

题目大意：

第一行是一个正整数nn(1≤n≤1000001≤n≤100000)，表示男女的人数。
第二行包括nn个绝对值在1500到2500的整数，每个整数的绝对值表示每个男生的身高。如果是一个正整数，表示这个男的喜欢比他高的女生，如果是负整数，就表示这个男的喜欢和比他低的女生。
第三行包括nn个整数，每个整数的绝对值表示每个女孩的身高。同理。

输出最多能匹配的数量

题目思路：

仔细分析一下就可以发现

只能正数与负数匹配，那么就存4个数组

每两个数组进行匹配一下，这时候不需要进行二分图匹配

这时候只需要贪心的去考虑一下即可

小的匹配小的就行 

为了联系一下一个高级的写法，这题就当作是练习了

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lldn",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const ll mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;
}ll n,m,p;
int a[4][maxn];
int pre[maxn];
int vis[maxn];
int Find(int x,int up){if(x>up || x ==-1) return -1;if(!vis[x]) return x;return pre[x] = Find(pre[x],up);
}
ll work(int *g,int *v){/// v1 与 v2 可以匹配v1 < v2的最大值int leng = g[0];int lenv = v[0];for(int i=1;i<=lenv;i++){vis[i] = 0;pre[i] = i+1;}sort(g+1,g+1+leng);sort(v+1,v+1+lenv);ll res = 0;for(int i=1;i<=leng;i++){int l = 1,r = lenv;int ans = -1;while(l<=r){int mid = (l+r)/2;if(v[mid]>g[i]){r = mid-1;ans = mid;}else l = mid+1;}ans = Find(ans,lenv);if(~ans) res++,vis[ans] = 1;}return res;
}
int main(){read(n);for(int i=1;i<=n;i++){ll x;read(x);if(x>0) a[0][++a[0][0]] = x;else a[1][++a[1][0]] = -x;}for(int i=1;i<=n;i++){ll x;read(x);if(x>0) a[2][++a[2][0]] = x;else a[3][++a[3][0]] = -x;}///0 与 3 匹配 满足 0 < 3///1 与 2 匹配 满足 1 > 2ll ans = work(a[0],a[3]) + work(a[2],a[1]);printf("%lldn",ans);return 0;
}

---

G. 最小生成树

题解

---

 

H. 买汽水 

题目大意：

czyz暑期集训一共N天。由于jmy和lkf玩游戏总是输，作为惩罚，他需要给oiers买汽水。
jmy最多只能给大家花M元钱。由于每天汽水的价格都不固定，现在给出每天买汽水的花销，我们可以随意选择让jmy哪些天买汽水（当然总花费不能超过M）。请问最多一共能够花掉jmy多少钱呢？
暑假最多不超过40天，jmy给大家花的钱最多有一亿。

题目思路：

折半搜索的经典题目吧.

之前做过一个原题有解释：相似例题

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lldn",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const ll mod= 1e8+7;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll a[maxn],cnt = 0;
ll ans = 0;
void dfs(int s,int e,ll w,int f){if(s == e+1){ans = max(ans,w);if(!f) a[++cnt] = w;else{int l = 1,r = cnt;while(l<=r){int mid = (l+r)/2;if(a[mid] + w <= m){l = mid+1;ans = max(ans,a[mid]+w);}else r = mid-1;}}return ;}if(w+num[s] <= m) dfs(s+1,e,w+num[s],f);dfs(s+1,e,w,f);
}
int main(){read(n);read(m);for(int i=1;i<=n;i++) read(num[i]);dfs(1,n/2,0,0);sort(a+1,a+1+cnt);dfs(n/2+1,n,0,1);printf("%lldn",ans);return 0;
}