sem可以为网站建设做什么,光谷网站建设哪家好,wordpress user密码,SEO案例网站建设T1 小苹果
题目描述 理论分析 对于第一问#xff0c;我们按照题意模拟每天取走的是多少个苹果即可。由于每天可以取走原来的,数据范围没次会降低到#xff0c;也就是说这样的过程的时间复杂度可以用下式表示#xff1a; 对于本题的数据范围n1e9#xff0c;这个时间复杂…T1 小苹果
题目描述 理论分析 对于第一问我们按照题意模拟每天取走的是多少个苹果即可。由于每天可以取走原来的,数据范围没次会降低到也就是说这样的过程的时间复杂度可以用下式表示 对于本题的数据范围n1e9这个时间复杂度计算后在1e5左右是可以接受的。 对于第二问首先有一个很显然的结论是第n个苹果会存在于从第一天开始的连续的若干天然后在后面的天里不再存在。因此我们可以维护一个bool类型的变量作为最后一个苹果还在不在的判别。然后在每一天的判断过程中我们通过整除关系可判别这个苹果是不是被拿走。
代码实现
#include bits/stdc.h
using namespace std;int main(){int n;cinn;int day0, last0;bool flagfalse;while(n){day;//是不是这天拿最后一个if(!flag(n-1)%30) flagtrue, lastday;//这天结束剩的苹果数nn-(n-1)/3-1;}coutday lastendl;return 0;
}T2 公路
题目描述 理论分析 贪心即可对于这个题目来说一共要走的路程是一定的所有一共加多少油也是确定的。不存在选择某种加油方案剩余油多而选择另外的方案剩余油少的问题。因此我们要做的就是让每升油的油价尽可能的低。那么问题来了我们能不能都用最低油价买油呢显然当开始的0号位置油价最低时题目中的1号这里直接对应代码的编号说明了下同我们可以办到这件事但是当1号节点油价并不是最低价的时候我们需要首先走到油价最低的站点那就至少需要在前面的节点买油。也就是说假设处的油价最低我们的问题就演变为了首先求1号点到最低花多少钱然后后半段直接用处的油价走完就行。那前半程的求解是一个数据范围比原问题更小的问题的求解。 我们当然可以像上述那样做递归的求解程序只不过这样的时间效率是不高的最差会来到只能通过一半左右的样例。实际上上述贪心的过程等价于下面的贪心我们从前往后考虑每个节点维护需求加油的数量只保证可以走到下一个节点num加完油后走到下个节点后会剩下多少油last以及历史已经过节点的最低油价mn。对于每个节点我们花费num*mn保证可以走到下一个节点。也就是说我们在拥有历史最低油价的那个点在原来的基础上多加num升油保证可以走到下一个点。
代码实现
#include bits/stdc.h
#define int long long
using namespace std;signed main(){int n, d;cinnd;int last0;vectorint v(n);vectorint a(n);for(int i0; in-1; i) cinv[i];int ans0, mn0x3f3f3f3f, num;for(int i0; in-1; i){cina[i];// 历史低价mnmin(mn, a[i]);// 至少需要多少才能走到下一个点num(v[i]-lastd-1)/d;ansansnum*mn;// 油余量够走多远lastnum*d-v[i]last;}coutansendl;return 0;
}T3 一元二次方程
题目描述 理论分析 按照题意 老老实实模拟即可。需要注意的细节稍微有点多但是细心一点也是可以一遍AC的 细节一分数输出需要保证分母不是负数。 细节二对于有两个解的情况而言题中已经提示过中的可以利用这一点简化代码的书写。 细节三根号的化简要从大到小试探因数这样更容易保证不重不漏。 细节四根号内如果是完全平方数那么最终结果将会不带有 “sqrt()” 此时答案的化简需要自己分析好。 细节五格式的答案要注意格外第一项是不是0的判断。 大概就是这些细节吧。。。时间复杂度
代码实现
#include bits/stdc.h
#define int long long
using namespace std;void print_sqrt(int s, int b, int a){int g__gcd(b, a);pairint, int p;p.firstb/g;p.seconda/g;if(p.first0) p.first*-1;if(p.second0) p.second*-1;if(p.first!1) coutp.first*;coutsqrt(s);if(p.second!1) cout/p.second;
}void print_int(int b, int a){int g__gcd(b, a);pairint, int p;p.firstb/g;p.seconda/g;if(p.second0){p.first*-1;p.second*-1;}if(p.second1) coutp.first;else coutp.first/p.second;
}void solve(){int a, b, c, g;cinabc;int deltab*b-4*a*c;if(delta0){coutNO\n;}else if(delta0){if(b0) cout0\n;else{print_int(-b, 2*a);cout\n;}}else {bool flagfalse;int num1;for(int imin(1000ll, delta-1); i0; i--){if(i*idelta){delta/(i*i);num*i;break;}else if(i*idelta delta%(i*i)0){num*i;delta/(i*i);}}if(delta1){if(a0) print_int(-b-num, 2*a);else print_int(-bnum, 2*a);cout\n;}else {if(b!0) {print_int(-b, 2*a);cout;}print_sqrt(delta, num, 2*a);cout\n;}}
}signed main(){int n, m;cinnm;while(n--){solve();}return 0;
}T4 旅游巴士
题目描述 理论分析 这是一个分层图问题即图上每个点要拆成个点。拆点的依据是原本的点 意义下的到达时间。我们使用表示到第i个点满足时间 的最短时间。初始条件为 然后跑最短路就行了。 相对难处理的点在于每条边经过的时间限制对于这一点我们可以原地等待k的倍数时间达成其实相当于出发时间晚了k的倍数时间。
代码实现
#include bits/stdc.h
#define int long long
using namespace std;int ans[20005][100];
vectorvectorpairint, int g;signed main(){int n, m, k;cinnmk;g.resize(n1);int u, v, a;while(m--){cinuva;g[u].push_back(pairint, int (v, a));}for(int i1; in; i)for(int j0; jk; j) ans[i][j]0x7f7f7f7f7f7f7f7f;queuepairint, int q;q.push(pairint, int (1, 0));ans[1][0]0;int now, pos, need;while(!q.empty()){auto tq.front();q.pop();for(int i0; ig[t.first].size(); i){nowg[t.first][i].first;pos(t.second1)%k;needans[t.first][t.second];if(needg[t.first][i].second) needneed(g[t.first][i].second-needk-1)/k*k;need;if(ans[now][pos]-1||needans[now][pos]){
// coutnow pos needendl;ans[now][pos]need;q.push(pairint, int (now, pos));}}}if(ans[n][0]0x7f7f7f7f7f7f7f7f) cout-1endl;else coutans[n][0]endl;return 0;
}
