当前位置: 首页 > news >正文

福州市 2025 国庆集训 Day2 前三题题解

福州市 2025 国庆集训 Day2 前三题题解

T1

U614648 strip

首先不难想到,将最长的两个放在两端,并且最长的将非插头那端突出去是最合算的。

然后我们来看看中间的 \(s-2\) 个位置与 \(n-2\) 个插座的分配。

需要遵循的原则:

  • 插最多

  • 空间利用率要高

此时假设我们已经知道了最多插 \(x\) 个。那么绝对是用最短的 \(x\) 个插座。贪心一下。

那么插最多就是我们要求的,所以我们来看看如何使空间利用率最高。

因为每个插座的长度均为 \(3\),所以如果插座 \(A\) 的长度模 \(3\)\(1\),插座 \(B\) 的长度模 \(3\)\(2\),那么它俩余下的部分就可以刚好无缝衔接地占用一个插座的位置。两个余 \(1\) 的也同理。

所以我们可以二分答案 \(x\)。对于二分出来的 \(x\),计算是否可以塞下。不行则更新右端点,可以则更新左端点。

所以时间复杂度就是 \(O(Tn\log n)\)

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ljl;
int n,a[N],T;
ljl s;
bool check(int x)
{int cnt[3];ljl ts=0ll;memset(cnt,0,sizeof(cnt));for(int i=1;i<=x;++i)ts=ts+a[i]/3,++cnt[a[i]%3];if(cnt[2]>=cnt[1])ts=ts+cnt[1],cnt[2]-=cnt[1],ts+=cnt[2];else//cnt[1]>cnt[2]ts=ts+cnt[2],cnt[1]-=cnt[2],ts=ts+(cnt[1]+1)/2;return ts<=s;
}
void tpoint()
{int l=0,r=n,mid;while(l<r){
//		cout<<l<<' '<<r<<'\n';mid=(l+r+1)/2;if(check(mid))l=mid;else r=mid-1;}cout<<l+2<<'\n';return;
}
void Main()
{cin>>n>>s;for(int i=1;i<=n;++i)cin>>a[i];if(n==1||s==1){cout<<1<<'\n';return;}sort(a+1,a+n+1);s-=2;n-=2;
//	for(int i=1;i<=n;++i)cout<<a[i]<<' ';
//	cout<<'\n';tpoint();return;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;while(T--)Main();return 0;
}

T2

U614650 expr

恶心大模拟。为什么我的思路有点儿与众不同啊……

注意到每个运算在外边都会配上一对括号。所以用个栈,像括号序列匹配那样。

然后我们就开个 map,将每个下标映射两个值。一个是运算后的值。另一个是这个运算的右括号的下标。这样就可以直接访问该运算后边的那个运算符(如果有的话)。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,ans;
stack<int> st; 
string s;
map<int,pair<int,int> > num;
int getnum(int a,int b,char opt)
{
//	cout<<a<<' '<<b<<' '<<opt<<'\n';if(opt=='!')return !a;if(opt=='&')return a&b;if(opt=='|')return a|b;if(opt=='^')return a^b;if(opt=='-')return (a&&!b?0:1);return -1;
}
void solve(int l,int r)
{
//	cout<<l<<' '<<r<<'\n';if(s[l+1]=='!'){num[l].first=!(num[l+2].first);num[l].second=r;return;}if(s[num[l+1].second+1]=='-')//((0->1)->1){num[l].first=getnum(num[l+1].first,num[num[l+1].second+3].first,'-');num[l].second=r;return;}int a=num[l+1].first,b=num[num[l+1].second+2].first;num[l].first=getnum(a,b,s[num[l+1].second+1]);num[l].second=r;return;
}
void Main()
{cin>>s;n=(int)s.size();num.clear();s=" "+s;ans=0;while(!st.empty())st.pop();for(int i=1;i<=n;++i){if(s[i]=='(')st.push(i);if(s[i]==')'){solve(st.top(),i);st.pop();}if(s[i]>='0'&&s[i]<='9'){num[i].first=s[i]-'0';num[i].second=i;}}if(s[1]>='0'&&s[1]<='9')ans=s[1]-'0';else ans=num[1].first;cout<<ans<<'\n';return;
}
int main(){
//	freopen("expr3.in","r",stdin);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;while(T--)Main();return 0;
}

T3

U614651 course

推式子题。可惜我太菜了推出不来 /ll。

我们假设 \(\frac{\sum^k_{j=1}c_{i_j}}{\sum_{j=1}^k t_{i_j}}\ge x\)

那么有:

\[\sum ^k_{j=1} c_{i_j}\ge x\cdot \sum^k_{j=1}t_{i_j}\\ \sum ^k_{j=1} c_{i_j}-x\cdot \sum^k_{j=1}t_{i_j}\ge 0\\ \sum^k_{j=1}({c_{i,j}-x\cdot t_{i_j}})\ge 0 \]

所以我们可以定义新的权值 \(a_i=c_i-x\cdot t_i\),若 \(\sum^k_{j=1}a_j\ge 0\) 则合法。

想要 \(\sum^k_{j=1}a_j\ge 0\),显然是选择最大的 \(k\)\(a\),所以可以排个序。

所以只要二分 \(x\),判断是否合法即可。注意精度。

这里为什么不是小等于,而是大等于呢?

因为如果是小等于,则你随便给它一个大点的值(比如说 \(1\),其实也是不可能达到的上限)就能合法。

时间复杂度:\(O(n\log^2 n)\)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=1e5+5;
int n,k;
db c[N],t[N],a[N];
bool cmp(db a,db b){return a>b;}
bool check(db x)
{for(int i=1;i<=n;++i)a[i]=c[i]-x*t[i];sort(a+1,a+n+1,cmp);db ans=0.0;for(int i=1;i<=k;++i)ans+=a[i];return ans>=0;
}
int main(){ios::sync_with_stdio(0);cin>>n>>k;for(int i=1;i<=n;++i)cin>>c[i];for(int i=1;i<=n;++i)cin>>t[i];db l=0.0,r=1.0,mid;while(l<r&&r-l>0.0001){
//		cout<<l<<' '<<r<<' '<<mid<<'\n';mid=(l+r)/2.0;if(check(mid))l=mid;else r=mid;}cout<<fixed<<setprecision(3)<<l<<'\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=23122

相关文章:

  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树
  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐
  • 2025 年砝码厂家 TOP 企业品牌推荐排行榜,不锈钢,标准,校准,天平,无磁,锁型,蓬莱,铸铁,定制,单双钩砝码公司推荐!
  • Java 在Word 文档中添加批注:高效文档协作的利器 - 指南
  • 2025雨棚生产厂家 TOP 企业品牌推荐排行榜,西安,陕西,西北推拉雨棚,推拉,移动,活动,户外,电动伸缩雨棚推荐这十家公司!
  • 关于整除分块
  • 2025 年木工机械设备厂家 TOP 企业品牌推荐排行榜,深度剖析木工机械设备推荐这十家公司!
  • Python语言自动玩游戏的消消乐游戏程序代码3QZQ
  • Python语言自动玩游戏的数字拼图游戏程序代码ZXQMQZQ
  • 如何找出集合的两个子集使得和相等?
  • Python语言自动玩游戏的俄罗斯方块游戏程序代码QZQ
  • Spring AI(七)Spring AI 的RAG搭建集合火山向量模型+阿里云Tair(企业版)
  • Python语言自动玩游戏的数字拼图游戏程序代码QZQ
  • 赛前训练4 字符串哈希
  • 英语
  • 处处吻
  • ThreadLocal原理与使用详解
  • WinCC监控框架实战解析:打通物联网网关的关键步骤
  • 2025国庆Day1
  • 2025 年包装印刷厂家 TOP 企业品牌推荐排行榜,西安,陕西,咸阳包装印刷,礼盒,定制,设计,优质,品质,环保,生产包装印刷公司推荐!