C. Jon Snow and his Favourite Number_UMR小豪的博客-程序员宅基地

技术标签: CF  codeforces  思维  

C. Jon Snow and his Favourite Number
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jon Snow now has to fight with White Walkers. He has n rangers, each of which has his own strength. Also Jon Snow has his favourite number x. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to improve. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number x, he might get soldiers of high strength. So, he decided to do the following operation k times:

  1. Arrange all the rangers in a straight line in the order of increasing strengths.
  2. Take the bitwise XOR (is written as ) of the strength of each alternate ranger with x and update it's strength.
Suppose, Jon has  5 rangers with strengths  [9, 7, 11, 15, 5] and he performs the operation  1 time with  x = 2. He first arranges them in the order of their strengths,  [5, 7, 9, 11, 15]. Then he does the following:
  1. The strength of first ranger is updated to , i.e. 7.
  2. The strength of second ranger remains the same, i.e. 7.
  3. The strength of third ranger is updated to , i.e. 11.
  4. The strength of fourth ranger remains the same, i.e. 11.
  5. The strength of fifth ranger is updated to , i.e. 13.
The new strengths of the  5 rangers are  [7, 7, 11, 11, 13]

Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations k times. He wants your help for this task. Can you help him?

Input

First line consists of three integers nkx (1 ≤ n ≤ 1050 ≤ k ≤ 1050 ≤ x ≤ 103) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.

Second line consists of n integers representing the strengths of the rangers a1, a2, ..., an (0 ≤ ai ≤ 103).

Output

Output two integers, the maximum and the minimum strength of the rangers after performing the operation k times.

Examples
input
5 1 2
9 7 11 15 5
output
13 7
input
2 100000 569
605 986
output
986 605
思路:一开始试了一下按照当前每个位置的数不在改变的时候作为结束点。然后剩下的对2取模,来求答案,TLE在了14组。

那样的话可能就是存在循环节了,反正这么大的数据不可能是暴力跑完的。

这样也不难搞。

把每次变化的都存起来。然后得到一个新的状态的时候,先去跟之前存起来的那些状态比较,如果发现又相同的状态,那么就表示找到了循环节了。

之后求出来循环节的长度,然后取模,得到最后的答案。

#include <bits/stdc++.h>

using namespace std;
const int MAXN=1e5+7;
int n,k,x;
int cnt;
struct node//用来存储已经出现过的状态
{
    int num[MAXN];
    int MAX;
    int MIN;
    node()
    {
        MAX=0;
        MIN=1e9;
    }
    bool operator ==(const node &a)const
    {
        for(int i=0; i<n; ++i)
        {
            if(a.num[i]!=num[i])return 0;
        }
        return 1;
    }
}p;
vector<node>q;
int check()
{
    for(int i=0; i<cnt; ++i)
    {
        if(q[i]==p)return i;
    }
    return -1;
}
int main()
{
    int i;
xx:
    while(~scanf("%d%d%d",&n,&k,&x))
    {
        q.clear();
        p.MAX=0;
        p.MIN=1e9;
        for(i=0; i<n; ++i)
        {
            scanf("%d",&p.num[i]);
            p.MAX=max(p.MAX,p.num[i]);
            p.MIN=min(p.MIN,p.num[i]);
        }
        sort(p.num,p.num+n);
        q.push_back(p);
        cnt=0;
        int pos;
        while(cnt<k)
        {
            cnt++;
            p.MAX=0;
            p.MIN=1e9;
            for(i=0; i<n; i+=2)
            {
                p.num[i]^=x;
            }
            for(i=0; i<n; ++i)
            {
                p.MAX=max(p.MAX,p.num[i]);
                p.MIN=min(p.MIN,p.num[i]);
            }
            sort(p.num,p.num+n);
            pos=check();
            if(pos!=-1)//找到循环节了
            {
                int t=cnt-pos;//循环节长度
                k=(k-pos)%t+pos;//取模之后的答案的下标
                printf("%d %d\n",q[k].MAX,q[k].MIN);
                goto xx;//找到了就直接重新读取下一组
            }
            q.push_back(p);
        }
        printf("%d %d\n",p.MAX,p.MIN);//表示没有找到循环节
    }
    return 0;
}





版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33362864/article/details/56294666

智能推荐

关于微信小程序倒计时组件安卓正常运行,ios异常问题_qq_41395531的博客-程序员宅基地

小程序倒计时组件安卓正常运行,ios异常问题后端返回的时间 格式为 yyyy-mm-dd hh:mm:ss我们代码里面自定义的倒计时组件需要的是时间戳,所以如果你是用的Date.parse(yyyy-mm-dd hh:mm:ss)原因就可以确定了话不多说上代码 let startTime1 = res.timeLimitEnd let dateTmp1 = startTime1.replace(/-/g, '/') let aaa1 =Date.pars

spring5整理:(九)事务_fenfeng2012的博客-程序员宅基地

目录一、何为数据库事务二、数据库并发问题三、事务的隔离级别四、事务类型五、Spring事务管理六、使用XML配置JDBC事务 七、tx:method标签设置​八、配置一个CRUD通用的事务配置九、使用注解配置JDBC事务一、何为数据库事务事务是一系列操作组成的工作单元,该单元内的操作是不可分割的,即要么所有操作都做,要么所有操作都不做事务必需满足AC...

oracle 10 ora01033,在Oracle10g下成功解决ORA-01033错误_weixin_39880328的博客-程序员宅基地

在Oracle10g下成功解决ORA-01033错误ERROR:ORA-01033: ORACLE initialization or shutdown in progres环境:操作系统:Windows server 2000 SP4数据库:Oracle10g(10.2.0.1)实例名:ORCL数据库服务名:dbserver解决方法:SQL*Plus: Release 10.2.0.1.0 - ...

java 统一校验规则_JAVA实现社会统一信用代码校验的方法_赵阿Q的博客-程序员宅基地

JAVA实现社会统一信用代码校验的方法发布于 2020-5-21|复制链接摘记: 网上找了几个,写的都不太适合,有的写出来了,也没有给出参考的算法链接。这样就导致了如果产生错误我们无法排查(不懂原理怎么排查对吧)。如果在使用过程中有疑虑,请参考: ..网上找了几个,写的都不太适合,有的写出来了,也没有给出参考的算法链接。这样就导致了如果产生错误我们无法排查(不懂原理怎么排查对吧)。如果在使用过程中...

一种分布式集群扩展模块:Epuck2 测距板Range and bearing_kay880的博客-程序员宅基地_epuck2

测距板改进了现有的相对定位/通信软件库(libIrcom),该库是为e-Puck机器人开发的,基于其车载红外传感器。e-RandB是与Robolabo、Iridia和RBZ机器人设计公司合作开发的。该板允许定位代理在本地通信,同时获得发射器的射程和方位,而无需任何集中控制或任何外部参考。因此,该板允许机器人拥有一个具体的、分散的和可扩展的通信系统。该系统依靠频率调制的红外通信,由两个相互连接的模块组成,用于数据和功率测量。该板可通过Uart或I2C总线与e-puck通信。它允许用户根据其他扩展模块已经

cli dll打包 vue_vue-cli3 DllPlugin 提取公用库的方法_幻想青年卢六六的博客-程序员宅基地

vue 开发过程中,保存一次就会编译一次,如果能够减少编译的时间,哪怕是一丁点,也能节省不少时间。开发过程中个人编写的源文件才会频繁变动,而一些库文件我们一般是不会去改动的。如果能把这些库文件提取出来,就能减少打包体积,加快编译速度。本文主要讲述在 vue-cli3 中利用 dllplugin 来进行预编译。1、安装相关插件yarn add [email protected]^3.2.3 add-asset...

随便推点

FCN源码解读之infer.py_伍颜的博客-程序员宅基地

infer.py是FCN中用于测试的python文件,每次可以单独测试一张图片在训练好的模型下的分割效果(直观上的以图片形式展示的分割效果)。其源码如下:import numpy as npfrom PIL import Image import caffeimport vis # the demo imag...

错误运行‘Tomcat 9.0.35‘: 地址 localhost:1099 已在使用_m0_55734518的博客-程序员宅基地_localhost1099正在使用

“Error running ‘Tomcat 9.0’: Address localhost:1099 is already in use”报错问题问题描述:idea运行项目时,左下方出现红色小方块提示问题“Error running ‘Tomcat 9.0’: Address localhost:1099 is already in use”。这是因为端口被占用了。解决问题:按win+R打开控制台输入cmd.确定后输入:netstat -aon|findstr 1099 命令查看什么

Unity即将内置骨骼动画插件Anima2D_weixin_33928137的博客-程序员宅基地

Unity一直在寻找新的方法来帮助开发者,并为他们提供最好的工具。在此我们向大家宣布,Unity将内置流行的骨骼动画插件Anima2D,从2017年1月开始免费供所有Unity开发者使用! 同时也欢迎插件作者Sergi Valls与这个强大的插件一起,加入我们专业的2D团队。我们致力于让游戏开发大众化,Anima2D将是Unity为专注于2D内容...

python简单使用protobuf,以及一个demo例子_胜天半子_王二_王半仙的博客-程序员宅基地_protobuf python

python使用protobuf1、下载protoc, 在网页的最下面,下载protoc-3.12.4-win64.zip解压即可githubProtocol Buffers v3.12.42、写.proto文件写法参见Language Guide (proto3)3、编译protoc,意思是用protoc编译,--python_out=./ 意思是编译好的文件输出到当前目录,当然想写到哪写到哪,your_message.proto, 意思是你的源文件(当前目录下的)protoc --py

linux系统下搭建svn服务器_黑崎一护父卍的博客-程序员宅基地

svn作为一种常用的版本控制工具,相信很多人都用过或曾经使用过,下面记录的是我在centos虚拟机上搭建svn的过程.原作者博文地址: https://www.cnblogs.com/-mrl/p/8980244.html前期准备:至少一台搭载centos系统的虚拟机,用来作为svn的服务器. 客户端可以使用windows来充当,如果有资源可以使用虚拟机,联系一下使用svn命令...

Lua repeat...until 循环_冷月醉雪的博客-程序员宅基地

    Lua 编程语言中 repeat...until 循环语句不同于 for 和 while循环,for 和 while 循环的条件语句在当前循环执行开始时判断,而 repeat...until 循环的条件语句在当前循环结束后判断。语法    Lua 编程语言中 repeat...until 循环语法格式:repeat statementsuntil( condition...

推荐文章

热门文章

相关标签