罗湖商城网站设计公司,泰安网站建设开发公司,优化推广的页面对于优化点击率起非常大的作用,网站 绝对路径 相对路径T1 小苹果
一、题目链接
P9748 [CSP-J 2023] 小苹果
二、题目大意
现有 n n n 个苹果从左到右排成一列#xff0c;编号为从 1 1 1 到 n n n。
每天都会从中拿走一些苹果。拿取规则是#xff0c;从左侧第 1 1 1 个苹果开始、每隔 2 2 2 个苹果拿走 1 1 1 个苹果。随…T1 小苹果
一、题目链接
P9748 [CSP-J 2023] 小苹果
二、题目大意
现有 n n n 个苹果从左到右排成一列编号为从 1 1 1 到 n n n。
每天都会从中拿走一些苹果。拿取规则是从左侧第 1 1 1 个苹果开始、每隔 2 2 2 个苹果拿走 1 1 1 个苹果。随后将剩下的苹果按原先的顺序重新排成一列。
现求多少天能拿完所有的苹果而编号为 n n n 的苹果是在第几天被拿走的
数据范围 1 ≤ n ≤ 1 0 9 1\leq n\leq10^9 1≤n≤109
三、题目分析
根据题目意思很容易想到时间复杂度为 O ( n ) O(n) O(n) 的暴力模拟方法这样就已经足够拿到 90 90 90 分了因为满分的要求是 1 0 9 10^9 109所以这大概是需要 log \log log 级的时间复杂度仔细观察之后你能发现每次会大约拿走 1 3 \frac{1}{3} 31 的苹果所以最终拿的次数是 O ( log n ) O(\log n) O(logn) 级别的所以只要我们能按轮次处理计科得到满分每一轮具体拿走的苹果数量是 ⌈ n 3 ⌉ \lceil\frac{n}{3}\rceil ⌈3n⌉因为是从第一个开始拿的注意每一轮之后 n n n 都会更新不难发现最后一个苹果只会在 n m o d 3 1 n\mod 31 nmod31 时被取走所以再判断一下即可。时间复杂度 O ( log n ) O(\log n) O(logn)
四、正解程序
#include iostream
#include cstring
#include cstdio
#include algorithm
#include cmath
#include cstdlibusing namespace std;
typedef long long ll;
int main()
{ll n;scanf(%lld,n);ll tn,ans10,ans20;while(t){ll x(t2)/3;ans1;if(ans20 t%31)ans2ans1;t-x;}printf(%lld %lld\n,ans1,ans2);return 0;
}T2 公路
一、题目链接
P9749 [CSP-J 2023] 公路
二、题目大意
现有一条公路上一共有 n n n 个站点编号为从 1 1 1 到 n n n。其中站点 i i i 与站点 i 1 i1 i1 的距离为 v i v_i vi 公里。每个站点都可以加油编号为 i i i 的站点一升油的价格为 a i a_i ai 元且每个站点只出售整数升的油。
现要从站点 1 1 1 开车到站点 n n n一开始油箱为空。油箱可以装下任意多的油且每升油可以让车前进 d d d 公里。问至少要花多少钱加油
数据范围 1 ≤ n ≤ 1 0 5 , 1 ≤ d ≤ 1 0 5 , 1 ≤ v i ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 5 1\leq n\leq 10^5,1\leq d\leq 10^5,1\leq v_i\leq10^5,1\leq a_i\leq10^5 1≤n≤105,1≤d≤105,1≤vi≤105,1≤ai≤105
三、题目分析
为了消费最小所以我们一定要尽可能加便宜的油毕竟油箱无限大所以很显然我们可以有一个贪心的思路选择一个递减的油价序列进行加油即加油跑到下一个比当前的油更便宜的地方尽可能刚好把油耗光再加油这样当然可以实现但稍微有一点点复杂我们可以做一点等价我们到一个加油站的时先不加油等到缺油的时候再从之前经过的最便宜的加油站虚空加油。如果出现更便宜的加油站我们就更新即可。以上两个思路显然是等价的。时间复杂度 O ( n ) O(n) O(n)
四、正解程序
#include iostream
#include cstdio
#include algorithm
#include cstring
#include cmath
#include cstdlibusing namespace std;
typedef long long ll;
const ll maxn100010;
ll n,d,v[maxn],a[maxn];
int main()
{scanf(%lld%lld,n,d);for(ll i1;in-1;i)scanf(%lld,v[i]);for(ll i1;in;i)scanf(%lld,a[i]);ll pricea[1],rest0,ans0;for(ll i1;in-1;i){pricemin(a[i],price);if(restv[i]){rest-v[i];continue;}ll temp(v[i]-restd-1)/d;anstemp*price;resttemp*drest-v[i];}printf(%lld\n,ans);return 0;
}T3 一元二次方程
一、题目链接
P9750 [CSP-J 2023] 一元二次方程
二、题目大意
如题所示一个字都别漏纯纯的模拟题
三、题目分析 读完题之后不难发现这就是纯纯的模拟跟着做就完了 做模拟题最关键的问题是很多时候你不知道它在说什么你大概率美学过没看过。但这不重要你只需要读完全部题目即可它一定会给足所有信息只需认真读题。 毕竟有时候还有大学知识而好多参赛者都是小学生。要有耐心和信心。 实在理解不了求根公式的话可以针对题目给你的特殊性质 C C C 来骗分代入所有 [ − 2000 , 2000 ] [−2000,2000] [−2000,2000] 的整数来判断是否有解以及求最大的解这样可以得到 50 50 50 分 你还需要枚举 Δ \Delta Δ 的平方因子来开方使得 Δ \sqrt{\Delta} Δ 变得最简这需要 O ( m ) O(m) O(m) 的思想。 但是模拟题的问题在于你很难拿到满分你有一下问题需要注意 如果出现 1 \sqrt{1} 1 请让它变成 1 1 1 如果出现乘法和除法的 1 1 1 请将它省略 a a a 可能是负数所以较大的解不一定是 − b Δ 2 a \frac{-b\sqrt{\Delta}}{2a} 2a−bΔ 而是 − b − Δ 2 a \frac{-b-\sqrt{\Delta}}{2a} 2a−b−Δ 根据题目意思你应该保证分母为正 时间复杂度 O ( T m ) O(Tm) O(Tm)
四、正解程序
#include iostream
#include cstdio
#include algorithm
#include cstring
#include cmath
#include cstdlibusing namespace std;
typedef long long ll;
ll T,m;
ll gcd(ll a,ll b)
{if(a%b0)return b;return gcd(b,a%b);
}
int main()
{scanf(%lld%lld,T,m);while(T--){ll a,b,c;scanf(%lld%lld%lld,a,b,c);ll detb*b-4*a*c;if(det0){printf(NO\n);continue;}ll q1-b,q21,q32*a;for(ll i2;i*idet;i)while(det%(i*i)0)q2*i,det/i*i;if(q30)q3-q3,q1-q1;if(det1)det0,q1q2;ll gcd1gcd(abs(q1),q3);ll gcd2gcd(q2,q3);if(det0){if(q1%q30)printf(%lld,q1/q3);elseprintf(%lld/%lld,q1/gcd1,q3/gcd1);}else{if(q1!0){if(q1%q30)printf(%lld,q1/q3);elseprintf(%lld/%lld,q1/gcd1,q3/gcd1);printf();}if(q2/gcd2!1)printf(%lld*,q2/gcd2);printf(sqrt(%lld),det);if(q3/gcd2!1)printf(/%lld,q3/gcd2);}printf(\n);}return 0;
}T4 旅游巴士
一、题目链接
P9751 [CSP-J 2023] 旅游巴士
二、题目大意
有一张图图上有 n n n 个点 m m m 条边。 1 1 1 号点为起点 n n n 号点为终点。每个点有一个时刻 a i a_i ai要求不能早于这个时刻通过此点且不允许在同种任何地方停留。
现要从起点一直走到终点要求到达终点的时刻一定是 k k k 的非负整数倍。问最早到终点的时刻是多少如果不存在这样的方案输出 − 1 -1 −1。
数据范围 2 ≤ n ≤ 1 0 4 , 1 ≤ m ≤ 2 × 1 0 4 , 1 ≤ k ≤ 100 , 1 ≤ u i , v i ≤ n , 0 ≤ a i ≤ 1 0 6 2\leq n\leq10^4,1\leq m\leq2\times10^4,1\leq k\leq100,1\leq u_i,v_i\leq n,0\leq a_i\leq10^6 2≤n≤104,1≤m≤2×104,1≤k≤100,1≤ui,vi≤n,0≤ai≤106
三、题目分析
完成题目一开始应该去尝试简化题目将其转化为熟悉且简单的模型。如果不考虑 a i a_i ai 和 k k k 的非负整数倍那么这将是一个很简单的单源最短路题目根据题目给的特殊数据提示我们先考虑 a i 0 a_i0 ai0 的情况对于到达某一个点的两个时刻 x , k x ( x k ) x,kx(xk) x,kx(xk) 来说 k x kx kx 一定不如 x x x 。也就是说对于 m o d k \mod k modk 同余的时刻来说只需要保留其最短时刻即可。所以我们可以用一个数组 d i , j d_{i,j} di,j 来表示到第 i i i 个点时刻 m o d k j \mod kj modkj 的最短时间运行一遍 B F S BFS BFS 最后输出 d n , 0 d_{n,0} dn,0 即可。这样就能拿到 35 35 35 分了。那么 a i ≠ 0 a_i\neq0 ai0 会造成什么影响呢其实我们完全可以推迟 k k k 的非负整数被的出发时间来满足这个要求。比如当前的边需要的时间是 w w w 大于目前时间 t i m tim tim 那么就需要让出发时间延后 ⌈ w − t i m k ⌉ ⋅ k \lceil\frac{w-tim}{k}\rceil\cdot k ⌈kw−tim⌉⋅k 单位时间。但是这样一来延后出发时间之后不一定是最短的路径了可能有其他的最短路径那么就不能使用 B F S BFS BFS 每个点只更新一次的方式了。因为每个点需要多次更新可以想到使用 d i j k s t r a dijkstra dijkstra 算法来解决这个最短路问题因为时间复杂度的关系我们这里需要使用堆优化利用 set 或者 priority_queue。时间复杂度 O ( n k log n k ) O(nk\log {nk}) O(nklognk)
四、正解程序
#include iostream
#include cstdio
#include algorithm
#include cstring
#include cmath
#include cstdlib
#include queueusing namespace std;
typedef long long ll;
const ll maxn20010;
struct node
{ll v,w;ll next;
}e[2*maxn];
ll p[maxn],t0;ll d[maxn][110];
bool vis[maxn][110];void insert(ll u,ll v,ll w)
{e[t].vv;e[t].ww;e[t].nextp[u];p[u]t;
}
struct New
{ll id,mod,len;bool operator(const New x) const{return lenx.len;}
};
int main()
{memset(p,-1,sizeof(p));memset(d,0x3f,sizeof(d));ll n,m,k;scanf(%lld%lld%lld,n,m,k);for(ll i1;im;i){ll u,v,w;scanf(%lld%lld%lld,u,v,w);insert(u,v,w);}priority_queueNew q;d[1][0]0;q.push({1,0,d[1][0]});while(!q.empty()){ll uq.top().id,modq.top().mod;q.pop();if(vis[u][mod])continue;vis[u][mod]true;for(ll ip[u];i!-1;ie[i].next){ll ve[i].v,we[i].w;ll timd[u][mod],now(mod1)%k;if(timw)tim(w-timk-1)/k*k;if(d[v][now]tim1){d[v][now]tim1;q.push({v,now,d[v][now]});}}}if(d[n][0]1e18)d[n][0]-1;printf(%lld\n,d[n][0]);return 0;
}
