打卡：AcWing学习记录2.0

（ps.学习打卡记录）

1 . 翻硬币

附代码

#include 
using namespace std;
void turn(string &s, int i){if (s[i] == '*')s[i] = 'o';elses[i] = '*';
}
int main(){string s, t;cin >> s >> t;int ans = 0;for (int i = 0; i < s.size() - 1; ++i){if (s[i] != t[i]){turn(s, i);turn(s, i + 1);ans++;}}cout<<ans<<endl;return 0;
}

2 . 飞行员兄弟

附代码

#include 
using namespace std;
char s[5][5], backup[5][5];
void turn(int i, int j) {for(int k=0;k<4;++k){if(backup[i][k]=='+') backup[i][k]='-';else backup[i][k]='+';}for(int k=0;k<4;++k){if(backup[k][j]=='+') backup[k][j]='-';else backup[k][j]='+';}if(backup[i][j]=='+') backup[i][j]='-';else backup[i][j]='+';
}
int main() {for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; j++) {cin >> s[i][j];}}int ans = 6666666;vector<pair<int, int>> final;for (int op = 0; op < (1 << 16); op++) {int cur = 0;vector<pair<int, int>> sat;memcpy(backup, s, sizeof(s));for (int i = 0; i < 16; ++i) {if (op >> i & 1) {turn(i / 4, i % 4);cur++;sat.emplace_back(i / 4, i % 4);}}bool flage = true;for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; j++) {if (backup[i][j]=='+')flage = false;}}if (flage) {if (cur < ans) {ans = cur;final = sat;}}}cout<<ans<<endl;for(auto k:final){cout<<k.first+1<<' '<<k.second+1<<endl;}return 0;
}

3 . 数的范围

#include 
using namespace std;
int main() {int n, p;cin >> n >> p;vector<int> a(n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);}sort(a.begin(), a.end());while (p--) {int x;cin >> x;int l = 0, r = n - 1;while (l < r) {int mid = (l + r) / 2;if (a[mid] >= x) r = mid;else l = mid + 1;}if (a[l] == x) {r = n - 1;int pos = l;while (l < r) {int mid = (l + r + 1) / 2;if (a[mid] > x) r = mid - 1;else l = mid;}cout << pos << ' ' << r << endl;} elsecout << -1 << ' ' << -1 << endl;}return 0;
}

4 . 数的三次方根

#include 
using namespace std;
int main() {double x;cin >> x;double l = 0, r = x;if (l > r) swap(l, r);while (fabs(r - l) > 1e-7) {double mid = (l + r) / 2;if (mid * mid * mid < x) l = mid;else r = mid;}cout << setiosflags(ios::fixed) << setprecision(6) << r << endl;return 0;
}

5 . 机器人跳跃问题

#include 
using namespace std;
int n = 0;
vector<int> a(n);
bool check(long long x) {for (int i = 0; i < n; ++i) {if (x >= a[i + 1]) x += (x - a[i + 1]);else x -= (a[i + 1] - x);if (x < 0) return false;else if (x > 1e5) return true;}return true;
}
int main() {cin >> n;a.resize(n + 1);for (int i = 1; i <= n; ++i)cin >> a[i];long long l = 0, r = 1e5;while (l < r) {long long m = (l + r) / 2;if (check(m)) r = m;else l = m + 1;}cout << l << endl;return 0;
}

今天洛谷多校训练赛开了，下午输出了三道题（思路），代码队友打的。

（ps.由于题目是团队内部共享，所以不能放题目链接）

1 . Goldbach’s conjecture

题意：弱哥德巴赫猜想，给定一个偶数 $n$ ，一定可以分解成两个质数的和。输出任意一组解即可。当时我们直接跑暴力，枚举其中一个数就过了。结果 $std$ 就是这么做的，复杂度最大 O ( x log ⁡ x ) O(\sqrt x\log x) O(x ​logx) ，随机数据下 x \sqrt x x ​ 几乎达不到，等后面证明过程看懂了，我会再更新的。

2 . Everybody deserves a long long name

题意：模拟一串变换规则。正解是用 $parser$ 来解释成编程语言的，我们纯手打，幸亏没 $WA$ ，不然调试会自闭的。

3 . Billionaire

题意：第一天给你 $1$ 元，第二天给你 $2$ 元，第三天给你 $3$ 元 $\dots \dots$ ，给了初始金额和领钱的日期，求成为十亿富翁的日期。看完题后想直接暴力模拟，然后测试数据居然有 $1e5$ 组，只能进行优化，我们优化了查找第几天达成十亿富翁，日期向后累加也是以年为单位推进，提前打好闰年表，优化到了 $O(\log n)$ 级别。$std$ 用了 $Zeller$ 公式将年份的每天对应一个整型标志，然后计算。

4 . Final Spark

题意：激光宽度 $W$ 米，目标视为半径为 $R$ 米的圆，只能直线移动 $S$ 米，问能打中目标的概率。本来看完题觉得是个平面解析问题，很轻松就可以 $A$ 掉，然而在决定最大覆盖面积的时候选了穿过圆心（直觉失误。。。），结果一直被样例卡住。正解是以激光的一边与圆相切，然后去算覆盖面积。

剩下的题基本都是思路还没到位，思路不完善，没理解题意，看了题解后再补吧。

ps.补两位大佬的 $github$ id
fstqwq

ftiasch

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！