爱飞鱼的blog

...

牛客周赛 Round 51 D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcd Solution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质gcd(a,b)=gcd(a−b,b)gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(a−b,b)，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。 1234567891011void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } ...

牛客周赛 Round 51 D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcd Solution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质gcd(a,b)=gcd(a−b,b)gcd(a,b)=gcd(a-b,b)gcd(a,b)=gcd(a−b,b)，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。 1234567891011void solve(){ string s; cin>>s; cin>>n; ll res=0; for(auto x:s){ res=res*10+x-'0'; res%=n; } ...

...

牛客周赛round56 C.给定一个c，要求在给定范围内构造a,b满足a⊕b=ca\oplus b=ca⊕b=c.要求值域在1-1e9 Sol:本题的范围比较宽松，只需要构造1，c^1.注意到1e9情况有些特殊，我们特判即可。 思考：如果范围限定到[l,r][l,r][l,r]如何寻找b和c，考虑从二进制位考虑？ 123456789101112131415void solve() { cin >> n; if (n == 1) cout << 2 << " " << 3 << endl; else if (n == 1e9) { for (int i = 30; i >= 0; i--) { if ((n >> i) & 1) { int tmp = 1 << i; cout <<...

AtCoder Beginner Contest 367 待补：ABC 367 G 题解 - spdarkle - 博客园 (cnblogs.com) D.一个湖周围有 NNN 个休息区。 这些休息区按顺时针顺序编号为 111 、 222 、......、 NNN 。 从休息区 iii 顺时针走到休息区 i+1i+1i+1 需要 AiA_iAi​ 步。(其中休息区 N+1N+1N+1 指的是休息区 111 ）。 从休息区 sss 顺时针走到休息区 ttt （ s≠ts \neq ts=t ）所需的最小步数是 MMM 的倍数。 求 (s,t)(s,t)(s,t) 的可能对数。 Sol:注意只能顺时针，所以固定起点的时候，到达任何一个点的路程都是确定的。考虑破环成链，维护%mod意义下的前缀和一个map桶，像滑动窗口维护这个map。但要注意边界，因aia_{i}ai​表示的是一条边。 12345678910111213141516171819202122232425262728293031void solve() { cin >> n >>...

Codeforces Round 294 (Div. 2) C题：有n个老师，m个学生，a方案是1老师和2学生，b方案是2老师和1学生，求最多可以成功达成多少套方案？ Sol：wa了一发贪心，样例怎么全过了？从纯数学的角度去看，就是线性规划，只不过由于参数不确定需要分类讨论，我们只需要设x套a，y套b，求x+y的最大值（在两个总人数的约束条件下。 1234567void solve(){ cin>>n>>m; if(m<n)swap(n,m); if(m>2*n)cout<<n<<endl; else cout<<(n+m)/3<<endl; //cout<<ad+tmp<<endl;} 考虑到数据范围很小，官方正解是直接暴力枚举 12345678910111213141516171819202122int main() {#ifndef ONLINE_JUDGE freopen("in",...

Codeforces Round 790 (Div. 4) D:题意：给定一个国际象棋棋盘，每个点都有权值，求在哪放置象，能使得象能攻击到的位置和最大。 Solution：由于数据范围很小，我们考虑最简单的暴力实现。对于每一个点，我们向四个攻击方向去走直到到达边界，定义方向数组即可。 123456789101112131415161718192021222324252627int dx[5]={1,1,-1,-1};int dy[5]={-1,1,1,-1};void solve(){ cin>>n>>m; vector<vector<int>>v(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>v[i][j]; } } int ans=0; for(int...

总结：既然不会用python就不要比赛的时候再去查再想着用，chatgpt的思路和题意理解也就看个乐子 https://codeforces.com/contest/1850 1.B题wa了一发，对于vector熟练度不够，导致忘记对于每次一个测试点结束以后，vector没有clear 2.D题:初看想复杂了，发现删除的题目数有单调性，就以为是二分。多看几个样例才发现是一个基于贪心但需要用排序加双指针实现的简单题 3.E题本质上是求解一个一元二次方程的整数解，由于数据量过大，如果普通二分longlong也不够，所以根据题目答案范围做了特判，超过1e18直接结束本轮，更新右端点。 考虑写一个解一元二次方程的模板函数，最好精度比较高 一道题题面如下，时间限制1s,每个测试点有t组样例 (1≤t≤100)，然后n的范围是2e5,假设数据很强，我的算法 时间复杂度n*根号n，根据计算已经1e9所以肯定过不了 还有一个问题就是，如何理解下面这句话？ 保证对于所有的测试用例，n 的总和不超过...

...