Kiki & Little Kiki 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1894 Accepted Submission(s): 979
Problem Description
There are n lights in a circle numbered from 1 to n. The left of light 1 is light n, and the left of light k (1< k<= n) is the light k-1.At time of 0, some of them turn on, and others turn off.
Change the state of light i (if it's on, turn off it; if it is not on, turn on it) at t+1 second (t >= 0), if the left of light i is on !!! Given the initiation state, please find all lights’ state after M second. (2<= n <= 100, 1<= M<= 10^8)
Change the state of light i (if it's on, turn off it; if it is not on, turn on it) at t+1 second (t >= 0), if the left of light i is on !!! Given the initiation state, please find all lights’ state after M second. (2<= n <= 100, 1<= M<= 10^8)
Input
The input contains one or more data sets. The first line of each data set is an integer m indicate the time, the second line will be a string T, only contains '0' and '1' , and its length n will not exceed 100. It means all lights in the circle from 1 to n.
If the ith character of T is '1', it means the light i is on, otherwise the light is off.
If the ith character of T is '1', it means the light i is on, otherwise the light is off.
Output
For each data set, output all lights' state at m seconds in one line. It only contains character '0' and '1.
Sample Input
1
0101111
10
100000001
Sample Output
1111000
001000010
题意:
给出 m (1 ~ 10 ^ 8),代表有 m 秒钟,后给出 n(1 ~ 100) 个灯的开关状态(环)。每一秒钟如果该灯的左边灯是 1 的话,则改变自身灯的状态,输出当过了 m 秒后灯的状态。
思路:
矩阵快速幂。设 a,b,c 三盏灯:
ai+1 = (ci + ai)% 2;
bi+1 = (ai + bi)% 2;
ci+1 = (bi + ci)% 2;所以可以得到矩阵:
vector 中的 size 函数导致了 TLE, 每次循环求长度浪费了不少的时间,在已知的长度下就可以不用求了。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vec; typedef vector<vec> mat; int len; mat mul (mat a, mat b) { mat c(len, vec(len)); for (int i = 0; i < len; ++i) { for (int j = 0; j < len; ++j) { for (int k = 0; k < len; ++k) { c[i][j] = (a[i][k] * b[k][j] + c[i][j]) % 2; } } } return c; } mat pow (mat a, int n) { mat b(len, vec(len)); for (int i = 0; i < len; ++i) { b[i][i] = 1; } while (n > 0) { if (n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { int n; char str[105]; while (~scanf("%d%s", &n, str)) { len = strlen(str); mat a(len, vec(len)); for (int i = 0; i < len; ++i) { if (!i) a[i][i] = a[i][len - 1] = 1; else a[i][i] = a[i][i - 1] = 1; } a = pow(a, n); for (int i = 0; i < len; ++i) { int res = 0; for (int j = 0; j < len; ++j) { res ^= (a[i][j] & (str[j] - '0')); } printf("%d", res); } printf("\n"); } return 0; }
相关推荐
迪杰斯特拉算法总结与代码描述 Problem Description One day , Kiki wants to visit one of her ... To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.
克隆 Kiki 存储库 git 克隆 (或 'git clone git://github.com/GeneAssembly/kiki.git' 用于只读访问) 确保安装了 CMake 构建和测试 cd 琪琪目录光盘仓.. 使气./ki -i ../test/short.fa -o 测试cat test.contig*...
KIKI专业视频编辑器应用程序是非常快速和有用的应用程序与Android的无限功能11支持,它有很多功能,如,视频编辑器,照片到GIF,视频到照片,快动作,慢动作,视频静音像许多功能和易于使用.而在这个应用程序有订阅...
kiki第02课 唐太宗与贞观之治.ppt
《Kiki儿童保护系统》是一款专为4-12岁少年儿童使用的强大安全保护系统,旨在为我们祖国未来的小花朵保驾护航,让他们在健康的互联网中翱翔。 《Kiki儿童保护系统》具有如下特点:界面直观简单易用;极具人性化...
kiki修改版qq魔法表情(200个表情),内有详细说明。
scratch3源码微型地下城-完整的游戏Kiki'sMicroDungeon-FullGame本资源系百度网盘分享地址
kiki是一个实验性社交网络。 奇奇与其他社交网络有何不同? 主要区别在于社交网络始终存在于您的计算机上。 这意味着kiki将脱机工作,并且没有人会跟踪您。 在kiki中,您是云的一部分。 当您使用kiki向朋友发布...
avr-net-io kikiv1.2 android网络远程开发
龟龟利用链式语法包装turtle库,使之更符合自然语言和思维,提高turtle库的表达能力。从schemdraw的链式语法,加工的函数中得到了启发。
kiki nanobot是3D益智游戏。 它基本上是游戏推箱子和库拉世界的混合体。
kiki_portfolio
kiki-web--demo产业新尖兵<<<<<<< HEAD jkl 掌握添加开发分支 在主分支文本上添加 123大师
kiki-s-Delivery-Service-Portfolio
Kikiuce 1.4 for XP
kikiUCE内存修改器 欢迎大家下载
kiki7000.github.io 我的网站 执照 MIT License Copyright (c) 2021 kiki7000 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation ...
,橙色图标的那种,和一台电脑绑定的,打开后要求输入密码,我已经有了密码,400分请高手帮忙破解成正常视频,谢谢!
如何编制软件测试用例[2]软件测试[Kiki]对测试用例划分等级有很多感触:许多时候当开发部门应客户需要或发现严重bug而快速发布一个新版本时,要求在限定的时间内快速测试以确保系统基本功能正常时,有些测试人员不知...