A 大佬的生日大礼包
https://ac.nowcoder.com/acm/contest/53548/A
思路：
根据题意 发现答案呈单调性 即最多可以发放k份物品 则一定可以发放（0,k）件物品，则可以使用二分 来归并到 答案。那么我们只需要一个 check（p） 函数判断 答案p 是否可行即可。发现 三个礼包都减去一个u盘和一个鼠标，则 豪华礼包剩一个键盘，幸运礼包剩一个 鼠标，普通礼包剩一个u盘，满足 区分性。因为 希望相邻的参赛选手拿到的礼包类型都不同，则易证明 每种礼包类型不能超过 P/2。每种礼包最多能为答案贡献为 min(该礼包个数，P/2）;
代码文章来源地址https://www.toymoban.com/news/detail-407171.html
bool check(ll a,ll b,ll c,ll k){
a=a-k;b=b-k;
if(a<0||b<0)return false;
ll cnt=0;
ll kk=(k+1)/2;
cnt=cnt+min(a,kk);
cnt+=min(b,kk);
cnt+=min(c,kk);
if(cnt>=k)return true;
else return false;
}
B 圣诞节糖果
https://ac.nowcoder.com/acm/contest/53548/B
思路：
根据题意 我们只需要选择两堆糖果，然后 可以获得两堆糖果总数对p取模的余数的个数。暴力做法 就是两个for 循环即可，但 因为 n的数据范围是（2,1e5） 所以会超时，但是我们可以发现我们将n堆糖果对p取余 之后排序，就可以 发现 当遍历到第i堆糖果的时候，因为 都需要对p取余，所以我们可以发现，当两堆糖果 个数总和大于P的时候 一定是小于等于a[i]的，所以我们对我们贡献最大的就是两堆之和小于等于P的，并且需要满足尽可能大，满足单调性，即存在 一个a[j])为答案时，必然是存在所有a[k]+a[i]<=P k属于(i+1,j-1）都是小于等于P的，且必然存在 所以a[s]+a[i]>P s属于（j+1,n）。
代码
for(int i=1;i<=n;i++){
ll l=i+1,r=n;
while(l<r){
ll mid=(l+r+1)>>1;
if(a[i]+a[mid]<p)l=mid;
else r=mid-1;
}
if(i<r)maxx=max(maxx,(a[i]+a[r])%p);
}
C 最优乘车
https://ac.nowcoder.com/acm/contest/53548/C
思路：
就是一个简单的最短路问题，难点在与 建图方式，因为我们需要求从饭店到S公园的过程中换车的次数最少，类似求闭包，我们可以将所有公交路线上的车能互相到达的车站都连一条边，等同于 保证在同一条公交路线最多只走一次，所以 最终的最短路距离减-1 就是换乘次数。
int main(){
int m,n;cin>>m>>n;
vector<vector<int>>v(n+10);
string s;getline(cin,s);
for(int i=0;i<m;i++){
getline(cin,s);int sum=0;
for(int j=0;j<s.size();j++){
if(s[j]==' ') v[i].push_back(sum),sum=0;
else sum=sum*10+s[j]-'0';
}
v[i].push_back(sum);
}
for(int i=0;i<m;i++){
for(int j=0;j<v[i].size();j++){
for(int k=j+1;k<v[i].size();k++){
f[v[i][j]][v[i][k]]=1;
}
}
}
memset(dist,0x3f,sizeof(dist));
queue<int>q;q.push(1);dist[1]=0;
while(q.size()){
int k=q.front();q.pop();
for(int i=1;i<=n;i++){
if(f[k][i]&&dist[i]>dist[k]+1){
dist[i]=dist[k]+1;q.push(i);
}
}
}
if(dist[n]==0x3f3f3f3f)cout<<"NO"<<endl;
else cout<<max(dist[n]-1,0)<<endl;
return 0;
}
D 小H和游戏
https://ac.nowcoder.com/acm/contest/53548/D
思路：
阅读题意 发现每次轰炸都会波及到与该城市距离不超过2的城市。 可以对每个点 维护三个信息，该点被轰炸的次数，该点儿子被轰炸的次数，该点孙子被轰炸的次数。然后 就可以类比到 题目要求 每次 该城市被轰炸，会影响到的点为，该点的儿子 该点的孙子，该点的父亲，该点父亲的儿子，该点父亲的父亲。 记录答案为 该点被轰炸的次数+该点父亲的儿子被轰炸的次数+该点父亲的父亲的孙子被轰炸的次数。 所以我们只需要预处理一下找到每个人 的父亲是谁就行，做一遍dfs 即可。
代码
void dfs(ll u,ll fa){
f[u]=fa;
for(int i=h[u];i!=-1;i=ne[i]){
ll j=e[i];
if(j==fa)continue;
dfs(j,u);
}
}
int main(){
memset(h,-1,sizeof(h));
ll n,q;cin>>n>>q;
for(int i=1;i<n;i++){
ll x,y;cin>>x>>y;
add(x,y),add(y,x);
}
dfs(1,0);
while(q--){
ll k;cin>>k;
// 轰炸该点设计的范围
// 该点儿子
d[k][1] ++;
// 该点孙子
d[k][2] ++;
//该点父亲
d[f[k]][0] ++,
// 该点父亲的儿子
d[f[k]][1] ++;//x的父亲被波及，x父亲的儿子被波及(包括x)
//该点父亲的父亲
d[f[f[k]]][0] ++; //x的父亲的父亲被波及
// 记录答案 设计到 该点被轰炸的次数+该点父亲的儿子被轰炸的次数+该点父亲的父亲的孙子被轰炸的次数
cout << d[k][0] + d[f[k]][1] + d[f[f[k]]][2] << endl;
}
return 0;
}
E 小H的询问
https://ac.nowcoder.com/acm/contest/53548/E
思路：
题目范围为1e5,正解为线段树 时间复杂度O(nlongn)//不会请自学后再来看题解
思路：
#include<iostream>
using namespace std;
const int N=4e6;
typedef long long ll;
const ll inf=1e15;
struct node
{
int l,r;
ll v1,v2; //用来判断是否为有效区间
ll lmax,rmax,tmax,sum; //lmax为从左端点开始连续的最大值，rmax从右端点开始的连续的最大值,tmax整个区间的最大值,sum为区间的和
int flag;
}tr[N];
ll g[N];
int n,m;
void pushup(node&u,node&l,node&r)//用子节点的信息更新父节点的信息
{
u.flag=0;
u.tmax=max(l.tmax,r.tmax);
u.sum=l.sum+r.sum;
u.v1=l.v1,u.v2=r.v2;
u.lmax=l.lmax,u.rmax=r.rmax;
u.tmax=max(l.tmax,r.tmax);
if(l.v2^r.v1)
{
u.tmax=max(u.tmax,l.rmax+r.lmax);
if(l.flag) u.lmax=max(u.lmax,l.sum+r.lmax);
if(r.flag) u.rmax=max(u.rmax,r.sum+l.rmax);
if(l.flag&&r.flag)
{
u.flag=1;
u.sum=l.sum+r.sum;
}
}
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,(g[l]%2==0?0:1),(g[l]%2==0?0:1),g[l],g[l],g[l],g[l],1};
else
{
tr[u]={l,r,(g[l]%2==0?0:1),(g[r]%2==0?0:1),0,0,0,0,0};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int c)
{
if(tr[u].l==l&&tr[u].r==l)
{
tr[u].v1=tr[u].v2=(c%2==0?0:1);
tr[u].tmax=tr[u].lmax=tr[u].rmax=tr[u].sum=c;
tr[u].flag=1;
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(mid>=l) modify(u<<1,l,c);
else modify(u<<1|1,l,c);
pushup(u);
}
}
node query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
return tr[u];
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(mid>=r) return query(u<<1,l,r);
else if(mid<l) return query(u<<1|1,l,r);
else
{
node res;
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
pushup(res,left,right);
return res;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&g[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d",&a);
if(a==1)
{
scanf("%d%d",&b,&c);
modify(1,b,c);
}
else
{
scanf("%d%d",&b,&c);
printf("%lld\n",query(1,b,c).tmax);
}
}
return 0;
}
F : 大水题
https://ac.nowcoder.com/acm/contest/53548/F
思路：
此题可以用容斥定理来解决
没见过的请上网自学一下容斥定理,这里不过多讲解
解法 1
signed main()
{
int n;
while(cin >> n)
{
int res = 0; //统计 2 和 5 11 13 的倍数
//减去 2， 5， 11， 13 的倍数
res += n / 2;
res += n / 5;
res += n / 11;
res += n / 13;
//举例 10和他的倍数，因为也是 2的倍数 也是 5的倍数会多被加
//同理 每对数字都要把多的减去
res -= n / 10;
res -= n / 22;
res -= n / 26;
res -= n / 55;
res -= n / 65;
res -= n / 143;
//同上减去的时候 2 和 5 和 11 的倍数多被减去了 要加上
res += n / 110;
res += n / 130;
res += n / 286;
res += n / 715;
//最后多加了再减去
res -= n / 1430;
cout << n - res << endl;
}
return 0;
}
解法 2:
二进制来枚举所有情况
代码
int main()
{
while(cin>>n)
{
sum=n;
ll cnt,res,flag;
for(int i=1;i<1<<4;i++)//枚举所有的情况
{
cnt=0;
res=1;
flag=0;
for(int j=0;j<4;j++)
{
if(i>>j&1)
{
cnt++;
if(res*s[j]>n)
{
flag=1;
break;
}
res*=s[j];
}
}
if(!flag)
{
if(cnt%2) sum-=n/res;
//容斥定理 减去奇数加上偶数（例如把2,5,11,13的倍数减掉把2和5，2和11，2和13,3和11,3和13,11和13的加上........）
else sum+=n/res;
}
}
cout<<sum<<endl;
}
return 0;
}
G 被3整除的子序列
https://ac.nowcoder.com/acm/contest/53548/G
思路：
给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除（子序列可以不连续，但是选的数要按照给出数的顺序）
答案对1e9+7取模
有多种解法，这里讲解一种dp的思路
f[i][j][k]//表示从前i个数中选,选了j个数,他们组成的数字取模3的余数为k
代码
int main()
{
string a;
cin>>a;
f[0][0][0]=1;//初始化
for(int i=1;i<=a.size();i++)//表示的第一维前i个数
{
for(int j=0;j<=i;j++)//表示的第二维选了j个数，这里j应该小于等于i（直接写成a.size()应该也可以）
{
for(int k=0;k<3;k++)
{
int d=(int)a[i-1]-'0';//我这里i的下标是从1开始,而字符串的下标是从0开始，所以要减一
int p=k*10+d;
p%=3; //表示选完第i个数之后取模的结果，用于下面的转移
f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;//这个地方表示第i个数不选，那么就等于前i-1个数中选j的方案数
f[i][j][p]=(f[i][j][p]+f[i-1][j-1][k])%mod;//表示选了第i个数，则应该从i-1，j-1状态转移
}
}
}
ll sum=0;
for(int i=1;i<=a.size();i++)
{
sum=(sum+f[a.size()][i][0])%mod;
}
cout<<sum;
return 0;
}
H：最大m个子段和
https://ac.nowcoder.com/acm/contest/53548/H
思路：
动态规划（dp）解法
dp[i][j][k]表示将前i个数分成j组，并且第i个数选或不选的最大值，这里k的取值为0/1 0表示不选,1表示选
代码
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&g[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=-inf；//因为要求最大值先初始化为负无穷
f[0][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=min(m,i);j++)
{
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);//表示第i个数不选，则从i-1转移过来
if(j>0)
{
//第i个数选有两种选发，一种是将第i个数放到之前的连续区间中
f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+g[i]);
//第2种是将第i个数自己新开一个区间
f[i][j][1]=max(f[i][j][1],max(f[i-1][j-1][0],f[i-1][j-1][1])+g[i]);
}
}
}
printf("%lld",max(f[n][m][0],f[n][m][1]));
return 0;
}
I 春游
https://ac.nowcoder.com/acm/contest/53548/I
思路：
思路：
首先计算两种船每个人的花费。然后尽可能的用单人花费最小的那种情况。然后剩余的再做分类考虑。
假设
1.两人船单人花费 < 三人船
优先考虑两人船。 如果 n 是偶数，那么全部 2人船。如果奇数 剩下一个人。
分成两种情况， 其一，剩下一人单独坐两种船最小的那一个。
其二，可以再拆出来一个二人船，凑一个三人船。 两种情况取min
2.三人船单人花费 < 两人船
同理优先考虑三人。
如果可以全部坐 3 人，那么全部3人，否则余下 1 人 或者 2 人。
同理，剩下的人考虑坐两种船最小的那一种。
否则 余 1：可以拆出一个三人船，凑 2个 2 人船
余2：拆除一个三人船，凑 3 个 2 人船,
3.n <= 2 的情况需要特判。
因为要保证单价是最优解，所以必须坐满， n <= 2 不满足两种船至少有一个船坐满。
代码
void solved()
{
int n, a, b;
cin >> n >> a >> b;
if(n <= 2)
{
cout << min(a, b) << endl;
return;
}
int da = a / 2;
int db = b / 3;
int ans;
if(da <= db)
{
if(n % 2 == 0)
{
cout << n /2 * a << endl;
return;
}else
{
ans = n / 2 * a;
ans = min(ans + min(a, b), ans - a + b);
cout << ans << endl;
}
}else
{
if(n % 3 == 0)
{
cout << n / 3 * b << endl;
return;
}else
{
ans = n / 3 * b;
if(n % 3 == 1)
ans = min(ans + min(a, b), ans - b + 2 * a);
else if(n % 3 == 2) ans = min(ans + min(a, b), ans - b + 3 * a);
cout << ans << endl;
}
}
}
J 种树
https://ac.nowcoder.com/acm/contest/53548/J
思路：
首先可以在有树的地方，可以沿着一个方向一直种树，直到结尾。
所以如果开头和结尾至少有一颗树，那么只需要一次就可以把空地填上。
否则两边都没树，中间有树，就要花两次走一次左，走一次右边。
代码
void solved()
{
cin >> n;
string s;
cin >> s;
int ans = 0;
bool f1 = false;
for(int i = 0; i < n; i++)
{
if(s[i] == '0') f1 = true;
}
if(!f1)
{
cout << 0 << endl;
return;
}
if(s[0] == '1' || s[n - 1] == '1')
{
cout << 1 << endl;
return;
}else cout << 2 << endl;
}
K Tokitsukaze and Average of Substring
https://ac.nowcoder.com/acm/contest/53548/K
思路:
n 为 5000，满足 n ^ 2 复杂度。所以可以枚举所有 l 和 r 的情况。
通过 st 数组维护 i ~ j 中每个数字出现的个数，这样每添加一个新的 j + 1 字符，统计他前面出现过多少次即可。
对于每一个 i 都要清空之前的 st 数组。
代码
void solved()
{
cin >> n;
string s;
cin >> s;
double res = 0;
for(int i = 0; i < n; i++)
{
st[s[i] - 'a']++;
int ans = 0;
for(int j = i + 1; j < n; j++)
{
int x = s[j] - 'a';
ans += st[x];
st[x]++;
res = max(res, ans * 1.0 / (j - i + 1) * 1.0);
}
memset(st, 0, sizeof st);
}
cout << fixed << setprecision (6) << res << endl;
}
L 01串题
https://ac.nowcoder.com/acm/contest/53548/L
思路：
无数次操作之后，满足 0 和 1 是相间排列的。并且题目保证 x 是偶数。
所以 0 和 1 各自出 x 一半的个数。
然后剩下的必须全部消掉。如果说剩下奇数那么肯定会多。无法消去。
然后先构造 010101, 然后多余的偶数个 1放在左边， 0 放在右边
代码
void solved()
{
int a, b, x;
cin >> a >> b >> x;
a -= x / 2;
b -= x / 2;
if(a < 0 || b < 0 || a % 2 != 0 || b % 2 != 0)
{
cout << -1 << endl;
return;
}
string s;
for(int i = 1; i <= b; i ++) s += '1';
for(int i = 1; i <= x / 2; i++) s+= "01";
for(int i = 1; i <= a; i ++) s += '0';
cout << s;
}
M 不点两面(hard version)
https://ac.nowcoder.com/acm/contest/53548/M
思路：
用一个数组 st 维护牌河中出现的次数。
如果添加 x 一张进入牌河，看看是否使得 x + 3, x - 3 成为安全牌
同理移出一张牌，看看是否使得不是安全牌
代码
void solved()
{
int m, q;
cin >> m >> q;
int sum = 0;
for(int i = 0; i < q; i++)
{
int op, x;
cin >> op >> x;
if(op == 1)
{
if(x - 3 >= 1)
{
if(!st[x - 3]) sum++;
st[x - 3]++;
}
if(x + 3 <= m)
{
if(!st[x + 3]) sum++;
st[x + 3]++;
}
}else
{
if(x - 3 >= 1)
{
if(st[x - 3] == 1) sum--;
st[x - 3]--;
}
if(x + 3 <= m)
{
if(st[x + 3] == 1) sum--;
st[x + 3]--;
}
}
cout << sum <<endl;
}
N 惊鸿
https://ac.nowcoder.com/acm/contest/53548/N
思路：
需要知道位运算的概念。
对于 or 运算，a or b = c ， c >= a, c >= b
所有我们对于某一个数字，让他和所有的数字都 or 一遍，一定是它能够最大化的值
所以求出来所有数字的 or * 4 就是最大值
int main(){
ll t;cin>>t;
while(t--){
ll a,b,c,d;cin>>a>>b>>c>>d;
ll k=a|b|c|d;
cout<<k*4<<endl;
}
return 0;
}
O：双子爆破者
https://ac.nowcoder.com/acm/contest/53548/O
思路：
由题可知文章来源：https://www.toymoban.com/news/detail-407171.html
代码
int main(){
int t;
cin>>t;
while(t--){
double M,m,v;
cin>>M>>m>>v;
double v1=(m*v)/(M-m);
cout<<v1<<endl;
}
return 0;
}
到了这里，关于天梯赛题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
