首页 > 其他分享 >AtCoder Beginner Contest 326 F

AtCoder Beginner Contest 326 F

时间:2023-10-31 23:55:05浏览次数:47  
标签:ansx AtCoder Beginner int LL back else 326 push

F - Robot Rotation
一句话不开LL,见祖宗
感谢大佬,和洛谷上的题解

上面已经将的很清楚了,但是如果你跟我一样一开始看不懂他们的代码,那么这篇可能为你解惑

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define int LL//LL!
map<LL,LL> ma;
int n,x,y ;
vector<int> a,b;
LL ansx=-1,ansy=-1;

void solve(){
    ma.clear();
    int len=a.size();
    int llen=len/2;
    LL sum=0;
    for(auto v:a) sum-=v;//为了放便反向的减法,先全部减一遍,要加的时候加上双倍的就行了
    //这里是选法,二进制状态压缩,1表示选正,0表示选负,i一开始为0,表示什么都不选(全为负),然后一位一位加上去,到最后二进制全为1表示全选正
    for(int i=0;i<(1<<llen);i++){
        LL res=0;
        //双向搜索
        for(int j=0;j<llen;j++){//二进制里为1就选正
            if(i>>j&1) res+=2*a[j];//因为之前减过,所以要加上双倍才可以
        }
        ma[res]=i;//选法i(注意是i的二进制,也就是选法)
    }
    for(int i=0;i<(1<<(len-llen));i++){
        LL res=0;
        for(int j=0;j<len-llen;j++)
            if(i>>j&1) res+=2*a[j+llen];
        if(ma.count(x-(sum+res))) {//x=sum+res1+res2=>x-sum-res2
            ansx=(i<<llen)+ma[x-sum-res];//合并在一起(二进制)
            return;
        }
    }

}
signed main(){//LL!
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        if(i&1) b.push_back(v);//记录对y轴的改变
        else a.push_back(v);//x轴
    }
    solve();
    swap(a,b),swap(ansx,ansy),swap(x,y);//换一下,可以重复利用函数
    solve();
    swap(ansx,ansy);//转换回来
    if(ansx==-1||ansy==-1) {//无解
        cout<<"No";
        return 0;
    }
    cout<<"Yes\n";
    int to=1;//一开始朝x轴正方向
    vector<char> c;
	//当然也可以不用这么麻烦
    for(int i=1;i<=n;i++){
        if(i&1){//y轴,to肯定在x轴朝右(1)或者左(3)
            int now=ansy&1;ansy>>=1;
            if(now==0){//负向
                if(to==1){
                    c.push_back('R');
                }else{
                    c.push_back('L');
                }
                to=4;//更新to的朝向
            }
            else{//正向
                if(to==1){//x轴正向
                    c.push_back('L');
                }else{
                    c.push_back('R');
                }
                to=2;
            }
        }
        else{//x轴
            int now=ansx&1;ansx>>=1;//取出该位置的值,1为取正方向,0为负方向
            if(now==0){
                if(to==2){
                    c.push_back('L');//逆时针转到负向
                }
                else{
                    c.push_back('R');
                }
                to=3;
            }
            else{//正向
                if(to==2){
                    c.push_back('R');//顺时针旋到正向
                }
                else{
                    c.push_back('L');
                }
                to=1;
            }
        }
    }
    for(auto v:c) cout<<v;
    return 0;
}

标签:ansx,AtCoder,Beginner,int,LL,back,else,326,push
From: https://www.cnblogs.com/bu-fan/p/17802068.html

相关文章

  • AtCoder Beginner Contest(abc) 312
    B-TaKCode难度:⭐题目大意题目定义一种矩阵X:该矩阵的是一个长度为9的由黑白色块组成正方形矩阵;该矩阵的左上角和右下角都是一个3*3的黑色矩阵(总共18个),这两个黑色矩阵外面(边缘不算)包围一圈白色色块(总共14个);现在一个n*m的黑白矩阵,问这个大矩阵中有多少......
  • 《AT_abc326_g Unlock Achievement》解题报告
    考场上压根没想到网络流,感觉这题是做过的网络流里算质量比较高的了。首先我们肯定是想直接贪心,但是发现怎么贪心都没办法,而且数据范围非常小,一般数据范围非常小,且贪心不了但又只能贪心的题就用网络流实现。考虑如何建模,首先我们发现权值有正有负,考虑最大权闭合子图,正权值连汇点,......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上,即使在\(N=5\)的情况下,也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题,就感觉是搜索,这很显然。但是我们会发现,最最最native的搜索,是\(4^{5\times5}=2^{50}\)的。感觉不大可过,但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目(然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数,则结束。定义这若干次掷骰子的总的结果为,每次......
  • AT_abc326_f Robot Rotation 题解
    AT_abc326_fRobotRotation题解经典问题,以前遇到过一个类似的问题:[ABC082D]FTRobot。建议对比着看一看这两道题,是两种不同的思路。(那一道题不用输出方案,因此可以用bitset优化;而此题需要输出方案,因此需要双向搜索。思路注意到每次只能「左转」和「左转」。所以,偶数次走......
  • AtCoder Beginner Contest(abc) 311
    B-VacationTogether难度:⭐题目大意给定n个人的工作计划,'o'表示这天休息,'x'表示工作;请找出一段最长的所有人都休息的连续休息的天数;解题思路数据不大,暴力即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio......
  • AtCoder Beginner Contest 321(ABC321)
    A.321-likeChecker直接模拟。CodeB.Cutoff直接暴力枚举\([0\sim100]\),每次把第\(n\)个数当作当前枚举的\(i\),然后看看条件是否满足。CodeC.321-likeSearcherDescription给你一个\(K\),求出\([1\simK]\)区间内有多少个321-likeNumber。321-likeNumber的......
  • Atcoder Beginner Contest 326 (ABC326)
    不知道为什么拖到现在,我是摆怪。A.2UP3DOWN模拟,略。B.326-likeNumbers模拟,略。C.Peak双指针板子。D.ABCPuzzle基础dfs。但是赛时不知道为什么觉得状态数不会很少,于是写了一个巨大复杂的状压。这里粗略算算有效状态数:仅考虑每行的限制,有\(\binom{3}{5}=10\)种选......
  • 题解 ABC326G【Unlock Achievement】
    题解ABC326G【UnlockAchievement】problem有\(n\)项属性,第\(j\)个属性的等级\(l_j\)初始为\(1\),每提升一级花费\(c_j\)的钱。又有\(m\)项成就,第\(i\)项成就要求对于所有\(1\leqj\leqn\),都要\(l_j\geqL_{i,j}\),如果满足所有要求,获得\(a_i\)的钱。求你最多......
  • 2023-2024-1 20231326 《计算机基础与程序设计》第五周周总结
    2023-2024-120231326《计算机基础与程序设计》第五周周总结目录2023-2024-120231326《计算机基础与程序设计》第五周周总结作业信息作业信息这个作业属于哪个课程2022-2023-1-计算机基础与程序设计这个作业的要求2022-2023-1计算机基础与程序设计第五周作业这......