首页 > 其他分享 >Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)F - Dividing Game

Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)F - Dividing Game

时间:2024-08-28 20:37:38浏览次数:8  
标签:AtCoder typedef puts Dividing Contest int res

https://atcoder.jp/contests/abc368/tasks/abc368_f

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,char> pii;
const int N=2e5+10,inf=1e9;
ll n,m,k;
int b[N],sg[N],a[N];
vector<int> divi[N];//divi[i]为小于i的所有因子
void init()
{
    for(int i=1;i<N;i++)
        for(int j=2*i;j<N;j+=i)
            divi[j].push_back(i);

    sg[1]=0;
    for(int i=2;i<N;i++)
    {
        for(auto x:divi[i])
            b[sg[x]]=1;
        while(b[sg[i]]) sg[i]++;
        for(auto x:divi[i])
            b[sg[x]]=0;
    }
}
void solve()
{
    init();
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        res^=sg[a[i]];
    }
    if(res) puts("Anna");
    else puts("Bruno");
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int _=1;
    //cin>>_;
    while(_--)
    {
        solve();
    }

    return 0;
}

标签:AtCoder,typedef,puts,Dividing,Contest,int,res
From: https://www.cnblogs.com/djhjojo/p/18385507

相关文章

  • Atcoder [AGC006D] Median Pyramid Hard 题解 [ 紫 ] [ 二分 ] [ adhoc ]
    MedianPyramidHard:二分trick加上性质观察题。trick我们可以二分值域,然后把大于等于它的数标记成\(1\),其他标记为\(0\)(有些题需要标记成\(-1\)),然后根据这个来check方案是否可行,这通常通过判断某个数是否是\(1\)来实现。本质上其实就是check大于等于它的数能否成为......
  • AtCoder Beginner Contest 368
    A-Cut题意签到题思路代码#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,k;scanf("%d%d",&n,&k);vector<int>v(n);for(inti=0;i<n;i++){scanf("%d",&v[i......
  • SDKD 2024 Summer Training Contest E2补题
    SDKD2024SummerTrainingContestE2A-PaperWatering题意对x进行至多k次操作(平方或开方后向下取整),求可以得到多少不同的数。思路平方完一定不同,且平方完后一定能开方出整数,所以只用额外考虑开方后平方的情况。若开方再平方与原来不同,则答案加上当前变化数的次数,直到变......
  • AtCoder Beginner Contest 052
    A-TwoRectangles#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intA,B,C,D; cin>>A>>B>>C>>D; cout<<max(A*B,C*D); ......
  • AtCoder Beginner Contest 051
    A-Haiku直接模拟。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); strings; cin>>s; stringa,b,c; a=s.substr(0,5); b=s.substr(6,7); c=s.substr(......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)题解A~D
    A-Cut题意:将数组的后k个字符移到前面思路:可以用rotate()函数让数组中的元素滚动旋转rotate(v.begin(),v.begin()+n-k,v.end());直接输出后k个元素,再输出前n-k个元素for(inti=n-k;i<n;i++)write(v[i]);for(inti=0;i<n-k;i++)write(v[i]);B-Decrease2......
  • AtCoder ABC 368题解
    前言本题解部分思路来自于网络。A-Cut题目大意有\(n\)张卡片叠在一起,从上到下给出\(n\)卡片的编号,将\(k\)张卡片从牌堆底部放到顶部后,从上到下输出卡片的编号。解题思路按照题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;inta[105];intmai......
  • AtCoder Beginner Contest 368(ABC368)
    [ABC368F]DividingGame题意:有\(n\)堆石子,第\(i\)堆有\(a_i\)颗石子,每次可以拿走任意一堆石子数量任何数量的棋子,但是要保证拿走之后该堆的石子数量为原来的约数(不能不拿)。问是先手必胜还是后手必胜。\(n,a_i\le10^5\)。思路:发现与Nim游戏类似,且全局信息公开,状态......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)- C
    题意概述有\(N\)个数,分别为\(H_1,H_2,H_3……H_N\)。你将使用初始化为\(0\)的变量\(T\)重复以下操作,直到所有数的值都变为\(0\)或更少。将\(T\)增加\(1\)。然后,减少最前方\(H_i\)值大于等于\(1\)的值。如果\(T\)是\(3\)的倍数,\(H_i\)的值会减少\(3\);......
  • ATcoder368D题详解
    D题传送门一道很无脑的题,但考试没写出来爆搜首先看朴素算法1.从根节点开始遍历每个节点2.遇到要保存的节点就进行标记,直到所有保存节点都标记时间复杂度\(O(n)\)其实已经能过了,但我没用(doge)树链剖分(LCA)首先分析1.每一次砍掉枝叶,都是在没有要保存的节点存在子树上时2.......