用自己电脑做网站服务器,免费源码下载网站,新公司 做网站 流程,北京电力交易中心谢开目录
题目#xff1a;跑步
思路#xff1a;
题目#xff1a;夏日漫步
思路#xff1a;
题目#xff1a;糖果促销
思路#xff1a;
题目#xff1a;第五维度 思路#xff1a;
题目#xff1a;公园
思路#xff1a; 新材料
思路#xff1a; 星际航行
思路…目录
题目跑步
思路
题目夏日漫步
思路
题目糖果促销
思路
题目第五维度 思路
题目公园
思路 新材料
思路 星际航行
思路
题目蛋糕划分
编辑
思路 题目跑步
小度每天早上要和小猫一起跑步。小猫的位置数值越小表示越在后面速度越小表示越慢它们都向一个方向跑。
小猫比较喜欢一起跑所以当速度更快的小猫遇见速度慢的小猫时它就会放慢速度变成一组一起跑。注意初始位置相同的小猫直接组成一组。
请问最终不再有追赶上的情况时最多一组有多少只小猫 思路
我们先来捋一下题目哈不同位置的小猫同时以不同速度开跑当后面的猫追上前的猫时它们就会以低速猫速度共速成为一组求最终一组最多的猫个数。
正着想不太好想因为变化因素较多。我们可以倒着想从最前面的猫开始推导若i-1只猫速度大于第i只猫不管i-1猫会不会被别的猫追上都不会影响i-1猫追上i猫这个结果。然后要注意一下刚开始在同一位置的猫会直接分成一组。操作 我们先对猫按位置排列同位置的猫猫速度小优先然后先把同一位置的猫速度统一一下此时同组的猫猫速度按最前面的猫速最低速猫设定速度最后从后向前遍历对i猫将i后面连续所有v大于i的猫都直接统计出来这个就是此组中最终会有的猫猫数然后从i猫跳到不满足条件猫的位置方便统计下一组的猫猫不断重复即可 #include bits/stdc.h //跑步有n只小猫出现在pi位置速度为vi向前跑不同速度小猫相遇时会共速成一组(取慢速那个),问最多一组的小猫个数
using namespace std; //贪心
const int N1e510;
struct node{int p;int v;}ar[N];
bool cmp(node x,node y){if(x.p!y.p)return x.py.p;//必须这么写可别偷懒else return x.vy.v;
}
int main(){int n;cinn;for(int i1;in;i){scanf(%d%d,ar[i].p,ar[i].v);}sort(ar1,ar1n,cmp);for(int i1;in;i){if(ar[i].par[i1].p) ar[i1].var[i].v;//同位置的猫速度给统一一下}int ans-1,cnt1,inden;//cnt来统计当前组有几只小猫while(1){if(inde-cnt0)break;//遍历结束if((ar[inde].p!ar[inde-cnt].par[inde].var[inde-cnt].v)||(ar[inde].par[inde-cnt].p))cnt;//两个情况都要统计进去两只猫位置不同但后猫更快 两只猫位置相同else indeinde-cnt,cnt1;ansmax(ans,cnt);}coutans;
} 题目夏日漫步
夏日夜晚小度看着庭院中长长的走廊萌发出想要在上面散步的欲望小度注意到月光透过树荫落在地砖上并且由于树荫的遮蔽度不通所以月光的亮度不同为了直观地看到每个格子的亮度小度用了一些自然数来表示它们的亮度。亮度越高则数字越大亮度相同的数字相同。
走廊是只有一行地砖的直走廊。上面一共有 n个格子每个格子都被小度给予了一个数字 ai 来表示它的亮度。
小度现在站在 1号格子想要去到 n号格子。小度可以正向或反向移动到相邻的格子每次需要花费 1的体力。
同时小度还有瞬移的能力其可以花费 1的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。
小度想知道到达 n号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。 思路 题意就是可以正向反向走一步也能正向瞬移到相同亮度的地方。 这个题可以按照跑图题来做每个相邻位置前后连起来然后当前位置和之前同亮度位置单向连接然后我们跑bfs按步数进行遍历就可以知道到最早哪一步时候可以走到终点 #include bits/stdc.h //夏日漫步
using namespace std;
const int N2e5;
int pos[1000000];
vectorintv[N];
queueintq;
int main(){int len,ans0,n,a;cinn;for(int i1;in;i){scanf(%d,a);if(i1n)v[i].push_back(i1),v[i1].push_back(i);//正常建边if(!pos[a])pos[a]i;else v[pos[a]].push_back(i),pos[a]i;//正向瞬移建边}q.push(1);int p,sign0;while(!q.empty()){ans;//按层bfslenq.size();while(len--){pq.front();q.pop();for(int i0;iv[p].size();i){if(v[p][i]n){sign1;break;}else if(pv[p][i])q.push(v[p][i]);}if(sign)break;}if(sign)break;}coutans;
} 题目糖果促销
小度最喜欢吃糖啦 这天商店糖果促销可给小度高兴坏了。
促销规则一颗糖果有一张糖纸p张糖纸可以换取一颗糖果。换出来糖果的包装纸当然也能再换糖果。
小度想吃 k颗糖果他至少需要买多少颗糖 思路 注意到“至少 ”细品就是说最后一次换糖果时恰好没有多余的糖皮即最终手里有一定且仅有一张糖皮如果手里有大于两张糖皮的话那就上次兑换就有多余的糖皮也就是多买的糖 好了我们来分析一共吃了k个糖那么有k-1个糖皮被换成了糖那么需要买的糖就是k-(k-1)/p; 最后呢这个题其实还可以二分来做 #include bits/stdc.h //糖果促销p个糖果可以换1个糖想吃k个糖至少要买多少个糖 (1t1e6, 1p1e9, 0k1e9)
using namespace std;
int t,p,k;
int main(){cint;while(t--){cinpk;if(k0) cout0\n;//注意题上的数据范围else{k-(k-1)/p;//一个式子就行coutk\n;}}
} 题目第五维度
零维是点点动成线
一维是线线动成面
二维是面面动成体
三维是体体动成史
四维是史史动????
现在人类企图理解第五维度。
而小度现在是第五维度的一位智者。一天小度发现人类的许多科学家在试图理解第五维度人类是四维生物若是他们理解了第五维度很可能也会到来第五维度的空间这显然是小度不愿意看到的毕竟哪里都有人口数量的问题….所以小度希望他们尽可能晚的理解第五维度因此小度用更高维度的视角把所有人类中在理解第五维的科学家都看到了而这些科学家的智商会不一样所以他们的理解速度 Vi 也会不一样并且他们开始理解的时间点 Si 也不一样。理解速度 Vi 描述为每过单位时间可获得 Vi 个单位理解力也就是说在 Si1 的时间点该科学家会第一次贡献 Vi 的理解力。我们定义理解力总数超过 m 时理解了第五维度。 小度因为维度更高可以使用时间悖论来给人类一次重大的打击小度可以让任意一位科学家在任意一个时间点消失所以他接下来的理解不会继续而且人类不会记得他所以他之前的贡献会消失。因为小度能力有限所以小度只能使用一次暂时悖论。
现在求在尽可能晚的情况下人类理解第五维度的最早时间点。
时间点初始为0但显然没有科学家能够在 0时刻有贡献。 思路 二分答案那么这次二分什么呢当然是时间了 我们只要遍历每个二分后的时间点就行看在有效时间内贡献最多的人消失后还能不能理解第五维度如果仍然可以理解那么我们就继续减少时间直到不能再减少时间那么答案就出来了。 那么怎么知道最终的二分结果究竟能不能使人理解理解第五维度呢我们只需要再带入一次check函数判断即可 #include bits/stdc.h//第五维度有n个科学家在不同的时间点s出现之后每天贡献v当人类贡献总和大于m时就理解了第五维度但上帝可以随机
using namespace std; //使一个人消失他的所有贡献也会消失问人类最晚多久可以理解第五维度如果不能输出-1
typedef long long ll;
ll s[100000],v[100000],n,m;
bool check(ll t){ll sum0,max_-1;for(int i1;in;i){if(ts[i])continue;//后面出现的人就跳过sum(t-s[i])*v[i];max_max(max_,(t-s[i])*v[i]);//找最大贡献的人}return sum-max_m;
}
int main(){cinnm;for(int i1;in;i){scanf(%d %d,s[i],v[i]);}ll mid,l0,r2e9;while(lr){mid(lr)1;if(check(mid)) rmid-1;else lmid1;}if(check(l))coutl;//对二分查找失败的情况进行特判else cout-1;
} 题目公园
今天是六一节小度去公园玩公园一共 N 个景点正巧看到朋友圈度度熊也在这个公园玩于是他们约定好一块去景点 N。 小度当前所在景点编号为 T从一个景点到附近的景点需要消耗的体力是 TE而度度熊所在景点编号为 F 移动消耗为 FE。 好朋友在一块赶路都会开心很多所以如果小度和度度熊一块移动(即在相同位置向相同方向移动)每一步他俩的总消耗将会减少 S。 求他俩到景点 N 时所需要的总消耗最少是多少 输入
4 4 3
1 2 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
输出
22
思路
其实注意到两个人的消耗是固定的既然不知道在哪相遇不妨把每个点都做中间相遇点试试(你看看出题人就是想让你暴力的)。
我们先对3个点找各自到其他点的最短距离假如a点是相遇点那么三个点(小度小熊终点)到此点a的最短距离×各自三个消耗(消耗怎么算就看走了多长就行因为每短的消耗是一样的)这样的话一种答案就出来了然后找出最优答案即可。
其实从这道题你发现了什么是不是找3个点的最近距离问题
#include bits/stdc.h //公园共n个景点两个人都要到n景点两人移动一个景点就各消耗e1,e2一起走消耗减少e3。求最少消耗到不了输出-1
using namespace std; //暴力枚举
typedef pairint,int pa;
const int N40005;
int dis[3][N],head[N];
int s1,s2,n,m;
long long ans1e17;
priority_queuepa,vectorpa,greaterpa Q;
struct node{int to;int next;}e[N*2];
void add(int u,int v){static int i0;i;e[i].tov;e[i].nexthead[u];head[u]i;
}
void dijkstra(int s,int dis[]){for(int i0;in;i)dis[i]40000;dis[s]0;Q.push(make_pair(0,s));while(!Q.empty()){int uQ.top().second;int dis_Q.top().first;Q.pop();if(dis_!dis[u]) continue;for(int ihead[u];i;ie[i].next){int ve[i].to;if(dis[v]dis[u]1)dis[v]dis[u]1,Q.push(make_pair(dis[v],v));}}
}
int main(){long long e1,e2,e3; //之所以ll型是因为dis是int型运算时方便给ll型ans赋值类型隐式转换cine1e2e3; //e1e2是两人的消耗e3是减少的消耗cins1s2nm;//s1s2是两个人的起点nm是景点数和边数int u,v;while(m--){scanf(%d %d,u,v);add(u,v);add(v,u); //建边}dijkstra(s1,dis[0]); //寻找3个点到其余点的最短距离dijkstra(s2,dis[1]);dijkstra(n,dis[2]);for(int i1;in;i){ //如果dis没有变说明这个点到不了标记一下if(dis[0][i]40000)dis[0][i]-1;if(dis[1][i]40000)dis[1][i]-1;if(dis[2][i]40000)dis[2][i]-1;}for(int i1;in;i){ if(dis[0][i]!-1dis[1][i]!-1dis[2][i]!-1) //3个点都要能到才算有效能连起来ansmin(ans,dis[0][i]*e1dis[1][i]*e2dis[2][i]*(e1e2-e3)); //ll*int-ll类型}if(ans1e17){cout-1;return 0;}//3个点没有一个公共交点即3个点连不起来coutans;return 0;
} 新材料 思路
直接模拟因为要考虑上次出现的位置所以使用map映射最好如果没有出现过就建立新映射如果出现过但是已经反应过就跳过如果出现过但是不足以反应就建立新映射如果能反应就反应并标记。
#include bits/stdc.h
using namespace std;
mapint,intmp;
int n,k;
int main(){scanf(%d%d,n,k);int ans0;for(int i1;in;i){int cur;scanf(%d,cur);if(!mp.count(cur))mp[cur]i;//有返回1无返回0返回-1表示已经反应过了else if(mp[cur]-1)continue;else if(i-mp[cur]k)mp[cur]i;else ans^cur,mp[cur]-1;}coutans\n;
} 星际航行 思路
我们的任务是把三维的一群点变成任意两维都相同另一维是个差为1的等差数列然后求最小代价。其实我们可以枚举下哪两维相同然后计算代价再计算剩下的一维变成等差数列的代价。
任务1把一个维度上的所有点变到同一个位置的最小代价就是把所有点都挪到中间点上你可以画图证明每两个点之间挪动的代价恰好都是两点之间的线段距离的情况下总代价最小。
如图我们只要保证更多的点分布在中间点的两边且两边的点都恰好连成线段时候代价是最小的这个偶数的点的情况奇数的点的情况会更加明显 上面的的是选10为中间点下面的是选9为中间点
任务2要把一个维度上所有点变成一个等差数列且代价最小就必须不能改变它们之间原来的顺序。如图我们假设最终的点的起点是t那么所有点最终坐标是ti 那么最终的代价是sum|xi-(ti)|最小然后我们再变形一下sum|(xi-i)-t|诶这不就是所有点xi-i到t的代价最小吗我们只需要在重复一下上面任务1的做法就行了。
那么最终做法就是先把数组排序然后找到求每个点到中间的点的距离和最终求出两个度的代价然后在求aiai-i再做一遍这样就枚举出了一种情况了然后把所有情况都枚举一下就行了。 题目蛋糕划分
小度准备切一个蛋糕。这个蛋糕的大小为 N∗N蛋糕每个部分的重量并不均匀。
小度一共可以切 K刀每一刀都是垂直或者水平的现在小度想知道在切了 K刀之后最重的一块蛋糕最轻的重量是多少。 思路
首先这个暴力dfs不行横刀14下竖刀14下共2^28*14^2会超时的 其实对最大质量的蛋糕块二分答案即可难在对答案判断
首先我们对所有的横刀状态模拟用一个数的(n-1)位的表示所有状态即可然后根据此时横刀状态对竖刀进行决策方法是 从第一列开始计算每列区间和若此时横刀区间和加上新的一列区间后值大于答案了那就要在此列左边切竖刀然后在此竖刀右面重新计算新一列区间 不断重复。其实就是每个横刀区间加上新一列区间后都不要大于答案如果大于我们就要这里要切竖刀了。最后统计竖刀和横刀数返回结果即可
另外为了加速处理还要用上二维前缀和 #include bits/stdc.h //蛋糕划分蛋糕大小N*N每个部分质量不均共切k刀(横竖均可)使最重的一块蛋糕的质量最轻是多少。
using namespace std; //2≤N≤151≤K≤2N−2 每个位置质量W小于1000 和洛谷P1182 数列分段一样思路
int n,k,fal,max_;//fal是答案出错标记方便快速结束循环
int a[20][20],sum[20][20],col[20],cnt[20],temp[20];;//col存放竖刀的位置,cnt是横切后每个区间和temp是新一列区间和
int get_sum(int x1,int y1,int x2,int y2){//求上下左右区间和return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]sum[x1-1][y1-1];
}
bool check(int m){if(mmax_)return false;//特判
//第一个循环是对每种横刀状态进行遍历每一个i都代表一种横刀状态for(int i0;i(1(n-1));i){fal0;//更新此种横刀状态为正确内部循环发现是因横刀出错时就一头冲出来memset(col,0,sizeof(col));memset(cnt,0,sizeof(cnt));memset(temp,0,sizeof(temp));vectorint v;int count0,ans0, tmpi;while(tmp){count;if(tmp1){//获取i中1的位置存入这种状态下的每个横刀位置v.push_back(count);//v用来存横刀位置若v里面为1,3,4加入n后表示横刀区间1-12-34-45-nans;}tmp/2;}if(ansk)continue;//特判v.push_back(n);int p0,top1,down;//top是该区间最上面元素位置,down是此横刀位置,p为当前的第几个横刀区间
//第二个循环是切竖刀的在每个竖位置遍历列区间一旦某个横刀区间加上这个列超过答案就说明可以切竖刀了for(int j1;jn;j){p0,top1;//每切一次竖刀就重置一次
//第三个循环是遍历横刀区间的我们要自上而下遍历每个区间for(int x:v){//用x来访问v中的所有元素取出每个横刀位置downx;int nowget_sum(top,j,down,j);//求列区间和列宽为1if(nowm){//如果仅列区间已经大于答案就说明是横刀状态失误了fal标记一下直接冲到最外面fal1; break;}
//求新的横刀区间原横刀区间加列区间cnt[p]now;//将上个区间加上这个区间if(col[j-1]){cnt[p]now;//上个位置被切过了就说明我们不应该加的}temp[p]now;//temp存每个列区间和
//判断该横刀区间决策是否切竖刀if(cnt[p]m){//该区间和大于答案说明要切竖着在j-1的位置一刀cnt再从第j列开始计算和你只有犯错的时候才知道自己犯错了col[j-1]1;//更新竖切的位置和区间和cnt[p]now;for(int ii1;iip;ii)cnt[ii]temp[ii];//之前的区间也要因此而更新了用上temp了}topdown1;//top是下个区间最上面位置}if(fal)break;}if(fal)continue;for(int j1;jn-1;j)if(col[j])ans;//col存放的竖切刀if(ansk)return true;}return false;
}
int main(){cinnk;for(int i1;in;i)//数据从11开始存后面注意这点for(int j1;jn;j){cina[i][j];max_max(max_,a[i][j]);sum[i][j]a[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1];}int l0,r2000*15*15;while(lr){int m(lr)1;if(check(m)) rm-1;//刀数太少说明应该再切小一点else lm1;}coutl\n;return 0;
}
今天的确实有点难嗯
