T1:小苹果(apple)。考察简单数学运算(取余)。近些年所谓的签到题,也并不完全是送分题了,需要同学们从题干的描述中找到规律,成为了找规律题。找出规律后,代码实现很短。这道题题目大意:有n个苹果,从第1个苹果开始,每隔2个拿走1个;第一遍拿完之后再把剩下苹果再按这个规则重新拿,直到所有苹果拿完为止。乍一看这个题目很像约瑟夫环问题,如果按照上述步骤模拟拿苹果的过程,可以得90分,最后一个n为10e9的用例过不了。所以还是要找规律,我们发现每次拿走的苹果数约为当前所剩苹果的1/3,那什么时候会拿走编号为n的苹果呢?用手简单演算一下会发现,当所剩苹果数为3的倍数多1的时候,就会把编号为n的最后那个苹果给取走。难度系数为入门,代码如下:
#include <bits/stdc++.h> using namespace std; int ans1, ans2; int main() { int n; cin>>n; while(n > 0) { ans1++; if(n%3 == 1 && !ans2) { ans2 = ans1; } n -= ceil(n/3.0); } cout<<ans1<<" "<<ans2<<endl; return 0; }
T2:公路(road)。这是一道结合了贪心思想和模拟的一道题,题目大意:有n个加油站编号为1-n,给出每个加油站的油价,以及每两个加油站之间的距离,和每升油可以行驶的距离,起始时油箱为空,问从1号加油站行驶到n号加油站,最少需要花费多少钱。简单模拟一下加油的过程,第1站肯定要加油,否则动都动不了。至于加多少,最少要保证能行驶到第2站。如果第2站的油价比第1站高,那在第2站加油不如在第1站多加一点保证能行驶到第3站;如果第2站的油价比第1站低,那第1站的油只需要保证行驶到第2站,后面需要的油在第2站加最优。把上述过程一般化,可以具体化为:从第1站开始,每次行驶到油价比上一站更低的站点时,累加从上一次加油的站点行驶到该站点的距离来计算在上一站需要加多少油,从而在新站点换成价格更低的油。再加上一些细节的处理,如浮点数的精度问题,难度系数为普及-,代码如下:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 1e5+5; ll v[MAX], a[MAX]; ll ans = 0; int main() { int n, d; cin>>n>>d; for(int i = 1; i < n; ++i) cin>>v[i]; for(int i = 1; i <= n; ++i) cin>>a[i]; int last = 1; ll road = 0; double oil = 0.0; for(int i = 1; i <= n; ++i) { if(a[i] < a[last] || i == n) { if(oil*d < road) { // 浮点数处理可能会带来精度误差 // 油箱中剩余油也可以转化为剩余可以行驶的距离 ans += ceil((road - oil*d)/d) * a[last]; oil += ceil((road - oil*d)/d) - road*1.0/d; } else { oil -= road*1.0/d; } road = 0; last = i; } road += v[i]; } cout<<ans<<endl; return 0; }
T3:一元二次方程(uqe)。这是一道数学题,要求严格按照数学上的要求(该约分约分,该化简化简),用字符串的形式输出一元二次方程较大的那个解。题面很长,对于小学生不太友好。虽然放在T3这个位置,思维难度并不大,但要注意的细节很多。因为没有实时评测结果,想要拿到满分也并不那么容易,难度系数普及/提高-,下面直接给出代码:
#include <bits/stdc++.h> using namespace std; int square(int num) { for(int i = sqrt(num); i >= 1; --i) { if(num%i == 0) { if(num/i%i == 0) return i; } } } void p(int x, int y) { if(0 == x) { cout<<0; } else { int X = abs(x); int Y = abs(y); int gcd = __gcd(X, Y); if(x*y > 0) { if(Y/gcd == 1) cout<<X/gcd; else cout<<X/gcd<<"/"<<Y/gcd; } else { if(Y/gcd == 1) cout<<-X/gcd; else cout<<-X/gcd<<"/"<<Y/gcd; } } } int main() { int T, M; cin>>T>>M; while(T--) { int a, b, c; cin>>a>>b>>c; if(b*b < 4*a*c) { cout<<"NO"<<endl; } else if(b*b == 4*a*c) { p(-b, 2*a); cout<<endl; } else { int delta = b*b - 4*a*c; int q = square(delta); if(q*q == delta) { if(a > 0) p(-b+q, 2*a); else p(-b-q, 2*a); cout<<endl; } else { if(b != 0) { p(-b, 2*a); cout<<"+"; } int A = abs(a); int gcd = __gcd(2*A, q); if(2*A/gcd == 1 && q/gcd == 1) { cout<<"sqrt("<<delta/q/q<<")"<<endl; } else if(2*A/gcd == 1) { cout<<q/gcd<<"*sqrt("<<delta/q/q<<")"<<endl; } else if(q/gcd == 1) { cout<<"sqrt("<<delta/q/q<<")/"<<2*A/gcd<<endl; } else { cout<<q/gcd<<"*sqrt("<<delta/q/q<<")/"<<2*A/gcd<<endl; } } } } return 0; }
#include <bits/stdc++.h> using namespace std; const int MAX = 1e4+5; typedef pair<int, int> pair_t; vector<pair_t> g[MAX]; int n, m, k; bool isok; int vis[MAX][105]; int ans = 1e9; int main() { cin>>n>>m>>k; for(int i = 0; i < m; ++i) { int u, v, a; cin>>u>>v>>a; g[u].push_back(make_pair(v, a)); } memset(vis, 0x3f, sizeof(vis)); queue<pair_t> que; que.push(make_pair(1, 0)); while(!que.empty()) { int u = que.front().first; int t = que.front().second; que.pop(); if(u == n && t%k == 0) { isok = true; if(t < ans) ans = t; } for(int i = 0; i < g[u].size(); ++i) { int v = g[u][i].first; int a = g[u][i].second; int add = 0; if(a > t) { add = ceil((a-t)*1.0/k)*k; } if(t+add+1 < vis[v][(t+add+1)%k]) { vis[v][(t+add+1)%k] = t+add+1; que.push(make_pair(v, t+add+1)); } } } if(!isok) cout<<-1<<endl; else cout<<ans<<endl; return 0; }