首页 > 其他分享 >AtCoder Beginner Contest 313

AtCoder Beginner Contest 313

时间:2024-03-04 15:12:18浏览次数:33  
标签:AtCoder Beginner Contest 313 text 异或 oplus


\[\large \text{Round 2 : AtCoder Beginner Contest 313 (VP)} \]

一言:
当我拔出第二把剑时,就是为了我所爱之人
——刀剑神域

这场比赛真的是大败而归,只 A 了 \(A,B,C,E\)。。。

虽然但是,\(F,G\) 确实不可做,但是 \(D\) 题还是有点可惜了。

\(\text{D: Odd or Even}\)

感觉考场上最有价值的就是这道题了。

首先对于 \(k=1\),我们直接特判,每次询问 \(1 \le i \le n\) 即可。

注意,以下定义均基于前 \(k+1\) 个数。

我们定义 \(a_i\) 表示第 \(i\) 个位置上最终的答案,\(b_i\) 表示除开第 \(i\) 个位置的异或和,即 \(b_i = a_1 \oplus a_2 \oplus a_3.... \oplus a_{i-1} \oplus a_{i+1} ... \oplus a_{k+1}\)。

接着我们可以考虑一种特殊情况,即 \(n=k+1\)。

显然,我们可以每次查询 \(b_i\),因为 \(k\) 是奇数,所以 \(A=a_1 \oplus a_2 \oplus a_3.... \oplus a_{k+1}=b_1 \oplus b_2 \oplus ..... \oplus b_{k+1}\)。接着根据异或的性质,有 \(a_i=A \oplus b_i\),也就求出了前 \(k+1\) 个数。

那么对于一般情况,我们就需要求出剩余的数,可以每次在查询时从输出 \([3,k+2]\) 开始,每次往后面挪一位,然后就可以根据以前的答案,异或后得到答案。

\(\text{Submission}\)

\(\text{What I learned:}\)

  • 当题目与奇偶性相关时,一定要想到异或哦。

  • 求一个序列时,可以先求出前 \(k\) 个,然后再慢慢递推下去。

标签:AtCoder,Beginner,Contest,313,text,异或,oplus
From: https://www.cnblogs.com/SFsaltyfish/p/18051853

相关文章

  • AtCoder Beginner Contest 343
    AtCoderBeginnerContest343比赛链接A-WrongAnswer思路简单的模拟,事实上我们需要注意一下当a和b都为0的情况Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ inta,b; cin>>a>>b; intans=a+b; //cout<<a+b-1<<en......
  • AtCoder Beginner Contest 343
    基本情况前四题秒了,但是都有不够优雅的地方F知道是线段树,但是写不出来,极其绝望C-343C-343(atcoder.jp)更简洁的回文判断MyCodeboolcheck_p(i64x){std::strings(std::to_string(x));intn=sz(s);for(inti=0;i<n/2;i++){if......
  • AtCoder Beginner Contest 343:起航
    AtCoderBeginnerContest343:起航2024/3/2/22:53有点儿晚了,简单总结一下。前4题都很基础,一点点小思维,其中C题边界又盲目追求刚刚好,WA了一次,总结经验,程序实际设计应该略微大于数据范围。EFG开始就做不动了,只剩了20多分钟,先通读然后看E题,E题读了半天发现大概是体积交并反......
  • AtCoder Beginner Contest 343
    B-AdjacencyMatrix难度:⭐题目大意给定一个无向图的邻接矩阵,问每个节点都和哪些节点相练;解题思路没啥好说的;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'......
  • AtCoder Beginner Contest 343(小白来了)
    A-WrongAnswer思路:给你两个数(A,B0~9)输出非A+B(0~9)解法:许多(A+B)^1等等Code:#include<iostream>usingnamespacestd;intmain(){intA,B;cin>>A>>B;cout<<!(A+B);return0;}B-AdjacencyMatrix思路......
  • AtCoder Beginner Contest 342
    B-Whichisahead?难度:⭐题目大意给定n个人的位置顺序,现有m次询问,给出a,b两个人,问谁在前面;解题思路模拟就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl......
  • AtCoder DP Contest vp 记录
    题单。A从\(i-1\)与\(i-2\)转移即可。#include<bits/stdc++.h>usingnamespacestd;intn;inth[100031];intdp[100031];intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>h[i]; memset(dp,0x3f,sizeof(dp)); dp[1]=0; for(inti=1;i<......
  • SC5312A SC5313A丨IQ解调器
    产品简介:300MHz至6GHz的直接IQ解调器更多信息请加weixin-pt890111获取 SC5312A和SC5313A是300MHz至6GHz的直接IQ解调器,将RF直接下变频为模拟同相和正交IF或IQ基带。直流耦合差分IQ对可馈送到任何双通道数字转换器进行模数转换。本地振荡器(LO)由外部源(如分别为SC5505A和SC......
  • AtCoder Regular Contest 172
    Preface开学了小溜一下之前没打的ARC,结果这场后面没有计数改成数论了又给我创飞了这场的DE都太玄学了,属于是自己想半天一点屌思路没有然后看一眼题解就顿悟的类型总结就是菜得发昏A-Chocolate挺有意思的签到题考虑从大到小依次切,对于一个原来\(H'\timesW'\)的块,为了尽量......
  • AtCoder Beginner Contest 342
    AtCoderBeginnerContest342比赛链接开学了,以后codeforces大概率只能补题了,但是atcoder还是可以做的A-Yay!思路找出只出现一次的字符就可以Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ strings; cin>>s; std::map<ch......