首页 > 其他分享 >YL 模拟赛总结 9

YL 模拟赛总结 9

时间:2024-03-02 17:23:20浏览次数:28  
标签:总结 YL vis int sum 100031 模拟 节点 dp

Problem


T1

我们考虑一种贪心策略:对于价格前 \(n-1\) 小的咖啡,我们求出一种最优方案使得按照此方案买完咖啡后钱数 \(\ge 20\) 且最接近 \(20\)。

至于如何求出最优方案,进行一遍 01 背包即可。

#include<bits/stdc++.h>
using namespace std;

int n,k;
int a[1031],dp[1031];

int main(){
    //freopen("overdraft.in","r",stdin);
    //freopen("overdraft.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(k<=20){ cout<<k; return 0; }
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
        for(int j=k-20;j>=a[i];j--)
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    cout<<k-dp[k-20]-a[n];
    return 0;
}

T2

显然,题目要求的即为树的重心到每个店的距离之和。

考虑树形 dp。

令 \(s_x\) 为节点 \(x\) 的“向下”的子树大小,则有:

\[s_x=\sum_{i \in S} s_i \]

(其中 \(S\) 为节点 \(x\) 的子节点的集合)

再令 \(f_x\) 为节点 \(x\) “向上”的字数大小,则有:

\[f_x=\max_{i \in \{V-s_x-1\}} s_i \]

(其中 \(V\) 为所有节点的全集)

根据 \(f_x\) 的计算式,我们知道 \(f_x\) 是包含了 \(s_x\) 的。

因此对于所有节点,取 \(f\) 值最大的即为树的重心。

剩下的求距离仅需再次 dfs 一遍即可解决。

#include<bits/stdc++.h>
using namespace std;

int n,ans,C;
int g[100031],f[100031];
bool vis[100031];
vector<int> G[100031];

void dfs(int x){
	vis[x]=1;
	for(auto i:G[x]){
		if(!vis[i]){
			dfs(i);
			g[x]+=g[i]+1,f[x]=max(f[x],g[i]+1);
		}
	}
	f[x]=max(f[x],n-g[x]-1);
	vis[x]=0;
}

int main(){
	cin>>n;
	for(int i=1,a,b;i<n;i++){
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	dfs(1);
	f[0]=1e9+31;
	for(int i=1;i<=n;i++)
		if(f[C]>f[i]) C=i;
	//cout<<C<<' ';

	memset(g,0,sizeof(g));
	dfs(C);
	for(int i=1;i<=n;i++) ans+=g[i];
	cout<<ans;
	return 0;
}

T3

考虑贪心地使用 \(k\) 张优惠券。

具体而言,维护三个优先队列,分别表示原价、优惠价、和差价。

然后模拟买咖啡的过程。若当前的最小优惠价 \(+\) 最小差价 \(<\) 最小原价,则使用一张优惠券。

否则,说明当前使用优惠券不比买原价更优,直接买原价即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,k,ans;
int p[20031],c[20031];
struct node{
    int val,id;
    friend bool operator < (node a,node b){
        return a.val>b.val;
    }
};
bool vis[20031];
priority_queue<node> a,b;
priority_queue<int,vector<int>,greater<int> > d;

signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>p[i]>>c[i],a.push({p[i],i}),b.push({c[i],i});
    for(int i=1;i<=k;i++) d.push(0);
    while(m>0&&ans<n){
        while(vis[a.top().id]) a.pop(); while(vis[b.top().id]) b.pop();
        if(d.top()+b.top().val<a.top().val){
            node t=b.top(); int x=t.val+d.top(); 
            if(m<x) break; m-=x,d.pop(),d.push(p[t.id]-c[t.id]),vis[t.id]=1; 
        }
        else{ node t=a.top(); int x=t.val; if(m<x) break; m-=x,vis[t.id]=1; } ans++;
    }
    cout<<ans;
    return 0;
}

T4

考虑进行线性 dp 求解。

我们令 \(dp_{i,j}\) 表示选择 \(i\) 个物品,总重量为 \(j\) 时的方案总数。

转移方程即为

\[dp_{i,j}=\sum^{k=1}_{j \div 2 \le k \le j,k \neq y} dp_{i-1,j-k} \]

这样直接计算,时间复杂度为 \(O(n^2)\) 无法接受。

考虑进行前缀和优化。

维护一个前缀和数组 \(sum_{i,j}\),首先 \(dp_{i,j}\) 至少是 \(sum_{i-1,j \div 2}\)。

然后分类讨论即可:

  • 若 \(j>n\),则为了保持决策区间长度为 \(n+1\)(包括当前的),则 \(dp_{i,j}\) 需要减去 \(sum_{i-1,j-n-1}\)。

  • 若 \(j \div 2 \le y \le j\),则 \(j-y \sim j\) 这个决策区间应该被去除,即 \(dp_{i,j}\) 需要减去 \(dp_{i-1,j-y}\)。

#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353;
int n,x,y,ans;
int dp[31][100031],sum[31][100031];

int main(){
    cin>>n>>x>>y;
    dp[0][0]=1;
    for(int i=0;i<=x;i++) sum[0][i]=1;
    for(int i=1;i<=20;i++){
        for(int j=1;j<=x;j++){
            dp[i][j]=sum[i-1][j/2];
            if(j>n) dp[i][j]=(dp[i][j]-sum[i-1][j-n-1]+MOD)%MOD;
            if(j-j/2<=y&&y<=j) dp[i][j]=(dp[i][j]-dp[i-1][j-y]+MOD)%MOD;
            sum[i][j]=(sum[i][j-1]+dp[i][j])%MOD; 
        }
    }
    for(int i=0;i<=20;i++) ans=(ans+dp[i][x])%MOD;
    cout<<ans;
    return 0;
}

标签:总结,YL,vis,int,sum,100031,模拟,节点,dp
From: https://www.cnblogs.com/XOF-0-0/p/18048926

相关文章

  • YL 模拟赛总结 6
    ProblemT1为了方便处理,我们令男生为\(1\),女生为\(-1\)。求一遍前缀和\(sum\),若存在两个下标\(l,r\)使得\(sum_l=sum_r\),则说明区间\([l+1,r]\)的和为\(0\),即男女人数相等。在这样的区间中取长度最大的即可。需要特殊处理\(sum_0\)。#include<bits/stdc++.h>#defi......
  • YL 模拟赛总结 7
    ProblemT1预处理出前\(10^4\)个格子需要填什么数,然后输出即可。具体地,我们记录\(e\)为当前层数,\(o\)为上一层的最后一个的位置,\(last\)为上一个填的格子的位置。我们知道,一个格子要么在一层的起点,要么在一层的中间,要么在一层的末尾。枚举\(1\sim5\)分别对这三种情......
  • 点分治杂题总结
    前言由于已经点明是点分治,所以我们在文章中约定,题解只叙述:求经过当前递归到的\(x\)对于答案的贡献,用以减少文章冗余程度。如有错误,欢迎指出。\(\texttt{1.[BJOI2017]树的难题}\)其实还是比较简单一题,做多了自然就会。首先我们先\(\texttt{dfs}\),在\(x\)的子树上处理一......
  • YL 模拟赛总结 11
    ProblemT1略。T2略。T3结论题。令所有牛的最终饥饿值为\(x\),则分别对于每一头牛进行考虑:对于第一头牛,它需要的最少玉米袋数为\(h_1-x\);对于第二头牛,它单独需要的最少玉米袋数为\(h_2-x\),而第一头牛已经用了\(h_1-x\)袋玉米,因此它需要的最少玉米袋数为\(h_2-x-......
  • 3.2每日总结
    石家庄铁道大学2024年春季  2022级课堂测试试卷—数据同步练习课程名称:大数据库技术与应用 任课教师:王建民  考试时间:120分钟  一、    数据结构分析:(1)京津冀三省的2015年度的科技成果数据原始表,为Access数据库,; (2)要求将三省的科技成果数据汇总到同一表中(要......
  • Living-Dream 周考总结 第3期
    Link,第四场没打。T1\(100\),没挂分。\(\operatorname{lcm}(x,y)=\dfrac{x}{\gcd(x,y)}\timesy\)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as0......
  • Living-Dream 周考总结 第4期
    Link。T1\(100\),没挂分。依题计算即可。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); ios::sync_with_stdio(0); ......
  • Living-Dream 周考总结 第1期
    Link。T1依题计算即可,\(O(1)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ ios::sync_with_stdio(0); doublen;cin>>n,n=ceil(n/5.0); cout<<setprecision(2)<<fixed; if(n<=100)cout<<0.58......
  • Living-Dream 周考总结 第2期
    Link,第二场没打。T1\(100\),没挂分。依题计算即可,\(O(1)\)。#include<bits/stdc++.h>usingnamespacestd;doublen,a,b;intmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); cin>>n>&......
  • 解决Puppeteersharp 被检测到的方法, 顺带学习了js如何实现 模拟点击拖动事件
    varlaunchOptions=newLaunchOptions{Headless=false,DefaultViewport=null,IgnoreHTTPSErrors=true,ExecutablePath=path+"\\.local-chromium\\chrome-win\\chr......