即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397
A Juggling Letters
题目大意
给你 $n$ 个字符串,问能不能打乱成相等的三个字符串
思路
因为可以随意打乱,所以统计每个字母个数,只要每个字母的个数模 $n$ 余 $0$ 即可
Continue reading “Codeforces Round #666 (Div. 2) 题目大意 & 解题报告”
「Jump up HIGH!!」
即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397
给你 $n$ 个字符串,问能不能打乱成相等的三个字符串
因为可以随意打乱,所以统计每个字母个数,只要每个字母的个数模 $n$ 余 $0$ 即可
Continue reading “Codeforces Round #666 (Div. 2) 题目大意 & 解题报告”
给你两个序列 $a,b$,求两个序列最短的公共子序列
对,是最短……
我吐了,这题我写了两天……
考虑到我自己写的博客还没有 AC 自动机的,我会简单写一下
有一个说烂但是很形象的说法 Trie + KMP
AC 自动机用于多模式串匹配
就是你拿一个字符串,和一堆字符串
然后 AC 自动机可以让你快速的知道这一堆字符串中,那些是你这一个字符串的子串
jt 学长说的没错,SA 果然是写一次忘一次……
于是这次重新学了一次,发现之前的 Blog 问题比较多,于是重写一次算了
实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页,不过是写给自己的罢了
因为老手机被拿来腾讯会议了,加之确实也算得上时代的眼泪了(
所以换了一台 Redmi K30 5G picasso
那么,开始迁移吧
拿老账号一下就解锁了,没有等待时间,赞美小米
到 XDA 论坛上看一眼没有什么坏处
目测这个手机没有什么好包,Lineageos 都只有一个 alpha 的非官方版,还是 3 个月前的产物了… 详情看这个帖子
不过有一个 eu 版的 miui 包,走起 在这个帖子里
事实上 CN 版的 MIUI 也不错,不过人在 CN 身不由己。我相信小米有保护用户信息的决心(至少 MIUI 12 中可见一二),但是不清楚小米能不能做到。
而且 EU 版有 Google 全家桶,so why not?
之前手滑执行了一次命令,导致 Firefox 的配置文件没了
然后操作失误,把云端备份的插件列表搞没了
万幸的是目前整理到的损失似乎只有这些,那就顺便整理一下自己的插件吧
事实上,Firefox 默认主题挺好看的
配合 Arc Theme 可以得到更好的显示效果,何乐而不为
Firefox 默认的标签页有点单调。啥都不显示没意思,显示的东西又没啥用……
所以使用 Tabliss 是一个不错的选择
当你标签页血多的时候,Firefox 会在标签栏提供一个滚动条
虽然很人性化,但是明显不够用啊
使用 OneTab 可以归档标签页。毕竟一般开那么多个标签页,真正在用的也没几个
使用 Tree Style Tab 可以给以树形结构管理标签页,改变线性的标签页整理方式
广告屏蔽,比 AdblockPlus 快多了
配合 cobaltdisco/Google-Chinese-Results-Blocklist 使用,可以在 Google 屏蔽掉大部分 SEO 站
什么时候中文互联网的 SEO 站能少一点
暴力猴,在 https://greasyfork.org/zh-CN 或者是 Github 上搞到脚本后就往这东西里面放
我使用的脚本有这些
用这个可以通过快捷键直接把选中内容送到 Google Translate 里
Aria2 Download Manager Integration
捕获下载链接,直接传给 Aria2
后台挂两个 Aria2,配合这个使用体验不错
不过,这个插件自带的 webui 不太可用,会自动覆盖设置
不过你都后台挂两个 Aria2 了,顺手搭个 httpd 挂个 Aria2 webui 应该也很简单
重写一些 http 请求为 https,防止某些网站/运营商耍流氓
Firefox Multi-Account Containers
对于国内的毒瘤,除了独立沙箱,应该没有什么防的住 ta 作恶的
这个插件提供了容器功能,你可以把你觉得不太行的网页每次用指定容器打开
终于不用隐私模式用 Baidu 了
把性能里的线程调小点
Firefox 的个性化可以避免一堆插件挤在你得地址栏上,毕竟你经常会调整设置的插件也就那么几个
这个问题实际上是没有答案的,浏览器这种东西比较偏个人。你喜欢那个,那个就是对的
不过这里还是给几个理由
Firefox 曾经是比 Chrome 资源占用少很多。
不过现在 Firefox 也用默认多线程了,这个优势虽然还有一点,但也不算多了
所以找几个这之外的理由
出于时间原因,没有能力给这几个理由找依据
如果你不相信我的话,那么关闭这个页面就好
应该是一场新手入门欢乐赛
打着也确实快乐,应该是我 CTF 比赛第一次做出 Oi 之外的题目
绝大多数知识点都在 CTF Wiki 上,剩下就是脑洞了
管他呢,mcfx txdy!
同志,用 Linux!
然后就是 nc 一把梭
$ nc 47.94.239.235 4001
welcome to Lilac@HIT
Here is kunkun's address:
flag{zonghelou_714}
放进 IDA 去,一看,就是打开 $signer/$music
,不允许你写 ../
然后 Hint 告诉你要访问 ../flag
然后就是傻逼题目了
nc 47.94.239.235 4002
input the singer's name:
..
input the song's name:
/flag
here is the lyric:
flag{w0w_you_successfully_escape_the_r3strict}
打开一看,发现 rand()
函数的种子是 time()%10
那为什么要动脑子,写个种子是 0 的情况
试一下就行了
#include <cstdio>
int num = 0;
int myRand() {
num = (num * num + 233) % 23333;
return num;
}
void mySrand(unsigned int seed) {
num = seed;
}
int playOnce() {
fflush(stdout);
int ai = myRand() % 3;
if( ai == 0)
return 1;
if( ai == 1)
return 2;
if( ai == 2)
return 0;
}
int main() {
mySrand(1);
int n = 100;
while( n -- ) {
printf( "%d\n", playOnce() );
}
}
然后直接拿输出日服务器就行了
题目给了二进制,大力 IDA
IDA 告诉我们 Hint,是根据 Target 位移出来的东西
简单的分析可以发现,基本上就是 8 位一截
然后写个程序大力草就行了
basket.cpp
:
#include <cstdio>
#include <iostream>
int n;
int read() {
int x = 0, w = 1; char ch = 0;
while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
return x * w;
}
int main() {
while(1) {
n = read();
int u1 = ( 1 << 8 ) - 1;
int tmp1 = n & u1;
n >>= 8;
int tmp2 = n & u1;
n >>= 8;
int tmp3 = n & u1;
n >>= 8;
int tmp4 = n & u1;
int res = tmp1;
res <<= 8;
res |= tmp4;
res <<= 8;
res |= tmp2;
res <<= 8;
res |= tmp3;
printf( "%d\n", res );
}
}
//-1897606077
// 00011101110010011010100010000110./basket.run 0.00s user 0.00s system 0% cpu 2.026 total
//
// Press ENTER or type command to continue
// 1133434084
// 10000111000111011010100111001000./basket.run 0.00s user 0.00s system 0% cpu 0.656 total
//
// 00011101 11001001 10101000 10000110
// 10000111 00011101 10101001 11001000
// 10001001 00011101 10101011 11000110
temp.py
:
#!/usr/bin/python
from pwn import *
sh = process( './basket.o' )
rem = remote( "47.94.239.235", "4003" )
rem.recvline()
sh.sendline( rem.recvline() )
rem.sendline( sh.readline() )
for i in range (1,90):
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
print( rem.recvline() )
sh.sendline( rem.recvline() )
rem.sendline( sh.readline() )
rem.interactive()
事后发现基本上随便乱输入就可以得到 flag
毕竟是 pwn 题
放到 IDA,读入量比字符串定义的多
直接多放点就过去了
$ nc 47.94.239.235 4004
请开始你的表演:
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
ncongrats, here is the flag
flag{stack_0verflow_is_annoying!!}
tql!!!
和上面的题目一样,都有溢出的漏洞
执行 get_flag()
函数应该会输出 Flag
那 pwntool 直接草就行了
扩展阅读: 栈溢出原理 – CTF Wiki
和上面一样,还是溢出,但是这次要带个参
然后我直接按普通堆做
全然没有注意开了 NX 保护…
后来给了个 Hint
那就是大力 ROP 搞就行了
扩展阅读: 基本 ROP – CTF Wiki
逐位 Xor 加密,直接解
代码就是对着 char 瞎jb位移
然后倒推一下,输出,没了
当时写了个 cpp 还原的,找不到了,不过本来就是签到题,不管了
代码注释里表明这是个算法
目测 TEA 及其变种
网上找个解密的,没了
IDA 后基本上可以发现这是个 RC4 加密算法
然而我赛后才发现
想个办法把里面东西倒出来
发现程序调用了 memcmp,LD_PRELOAD 可以套到目标密文
RC4 具有自反性,在把目标密文放进去,得到明文,也就是 Flag
赛后 mcfx 爷提醒是个数组,还是个巨大线性方程组
我拿 IDA 打开,然后得到了一大堆 if
包裹的条件判断
Vim 随便处理一下就可以变成 z3 的 solve 函数的参数
然后放到 z3 里跑就行了
如果直接用 .model()
输出会输出不全,手动 .model().eval()
脚本太大了,这里是链接:https://blog.woshiluo.com/wp-content/uploads/2020/05/libac_re5.zip
我怎么写的这么多行?
Vim 宏真好用
这次的 WEB 题相比较别的真的好欢乐…
curl -v
或者直接 F12 看 Header
extract
会覆盖变量,考虑覆盖 language_file
没了
签到题,payload 是 admin'#
查看页面原码,得到 login.php.bak
发现 SQL 注入可能性基本为 0
我们可以使 $dbpass
为 null
发现进来的 $password
没有验证,不传就行了
题目给了任意读,但是扬了 flag
可惜 file 被 open 了,我们可以在 procfs 里找到
但是我们并不知道 pid
所以用一个科技 /proc/self
没了
感觉这个比上一道简单
构造一下
curl http://47.93.34.105:8081/\?s\=QNKCDZO\&t\=240610708 -d 'pw=20200501", "password": "shouhukunkun'
没了
我确实菜
对着题目给的参数 base64 -d
三次,得到 flag.jpg
猜测参数就是查询套三次 base64
然后试图获取 index.php
发现替换了非字母且非.
为空
替换 config
为 !
扫描 .index.php.swp
提示看 f1lllaggg!lilac.php
然后代码审计 f1lllaggg!lilac.php
要么 extract
魔改 t,要么直接传空 t
可以过非严格判断
所以那个链接是干什么的,迷惑
这次的比赛激起了我对 Crypto 的兴趣
前五题都是工具题目,没啥说的
合理运用 CyberChef 和 Wikipedia 即可
题目说是原题,直接拖 Google
实际上是 Vigenère 密码,和醋酸的英文名几乎一样
然后找个工具爆破就没了
查看源码,发现使用 Unix 时间戳做密码
Unix 时间戳就那么多,写个爆破就行了
from Crypto.Cipher import AES
#from secret import flag
import time
from hashlib import md5
import base64
time = int(time.time())
while 1:
time = time - 1
key = md5(str(time).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = base64.b64decode( 'THM3FOB7PxOgVoI1fGsqQDJLGu41mL9nKCNeMvXzB+l8MFirir0C19YRS/ruDILq')
outData = aes.decrypt(flag)
print(outData)
跑个 30s,在输出里搜索一下 flag 就行了
基本上就是 b64 变种
映射一下就行了
#include <cstdio>
char mp[1000];
int main() {
FILE* qwq = fopen( "qwq", "r" );
FILE* cip = fopen( "cipher.txt", "r" );
char s1, s2;
while( fscanf( qwq, "%c", &s1 ) !=EOF && fscanf( cip, "%c", &s2 ) ) {
if( map[s1] != 0 )
continue;
mp[s1] = s2;
}
for( char a = 'A'; a <= 'Z'; a ++ ) {
if( mp[a] == 0 )
printf( "0" );
printf( "%c", mp[a] );
}
for( char a = 'a'; a <= 'z'; a ++ ) {
if( mp[a] == 0 )
printf( "0" );
printf( "%c", mp[a] );
}
for( char a = '0'; a <= '9'; a ++ ) {
if( mp[a] == 0 )
printf( "0" );
printf( "%c", mp[a] );
}
printf( "%c", mp['+'] );
printf( "%c", mp['/'] );
printf( "%c", mp['='] );
}
RSA 原理题
直接解就行了
n 变成三个质数相乘了,但是不影响我们解密
import binascii
import gmpy
p = 252647779892687905173761792949656998433
q = 290615416181922737045361451171930371659
r = 281613259213037257262703439109757908501
n = p * q * r
e = 0x10001
# rased = pow(flag, e, n)
rsaed = 1169612223485519024207841670191078798101684935551461601922416127588930439758194701318838707953651437973827125265577
phi = ( p - 1 ) * ( q - 1 ) * ( r - 1 )
inv = gmpy.invert( e, phi )
print(inv)
print(hex(pow( rsaed, inv, n )))
小插曲,我本来手写的 exgcd 求逆元,结果写错了,最后因为不会 py 而选择了 gmpy
题目关于劳动法和基本法的什么东西就先略过了
大家都知道是怎么回事(
然后,StegSolve
直接 Frame
逐个看就行了
题目说的是 9 位数字密码
这,不就是爆破
虽然事后发现 7zip 可以直接打开,惊了
据说是非预期的错误,笑了
题目说了 010Editor
那就没什么说的了
strings
没了
仔细看,Red plane 0 左上角一段白
就选择 Red plane 0 通道,LSB 一下,就知道 Flag 了
访问链接即可
明文破解
pkcrack -c "lilac.png" -p lilac.png -C ./zip-2.zip -P ./lilac-logo.zip -d qwq.zip
没了
binwalk 草出来里面的 png
发现 png 的 CRC 有问题
改个 Height,没了
我先建议出题人司马
直接 OD 会有一句 You see the string,but it is not so easy...but it's baby!
来嘲讽你
总之 binwalk 套出里面的 7z,解压出来是个 gif,string 里面的 Flag 是 Fake
gif 逐帧草出来两个残缺二维码,补全,扫一下,结果还是 Fake
赛后有 Hint 告诉我们
「你在第二层,你以为他在第五层,实际上他在第一层」
你妈的,直接对 EXE Resource Hacker 得到一个凯撒密码
解出来是个网址,访问是个残缺二维码
补上定位点,扫就得到 Flag
没啥说的,签到
总之是一场相当快乐的比赛
几乎除了 Web 所有东西都是现学的,这大概就是在线比赛的乐趣吧,没有所谓记忆造成的堡垒
感谢举办方,给了我学习的机会
最后,跟我一起喊,mcfx 天下第一!
在很多情况下,如果你直接带着 Linux 输入法
这样的关键字去 Google 搜索
那么你得到的通常都是 Google Pinyin,或者 Sogou Pinyin
Google Pinyin 年久失修,Sogou 的话,维护也不算多上心
如果你再认真一点,你也许可以找到 Sunpinyin 和 Libpinyin
这两个的体验已经相当不错了,但你也会发现,在准确率上,还是差了点,而且在词库大的时候,还会很卡
这个时候,你就会查到 Rime —— 中州韵输入法引擎
聪明的输入法懂我心意
这是 Rime 自己的标语
Rime 具有更强大的定制性,更优秀的词语联想,以及跨平台的支持
如果你不相信 Sogou(相信我,没几个人相信 Sogou 不会上传你的数据),那么 Rime 是目前最优秀的选择
Arch Linux
小鹤双拼用户
对于 Arch Linux,我们首先需要选择一个输入平台,我选择的是 Fcitx5
关于 Fcitx5,你可以查阅 Fcitx5 – ArchWiki
(虽然这个东西在 Waylnd 下的功能还很残缺,但是,Wayland 本身问题也不少)
关于 Rime,Arch Wiki 有 这个页面
这个页面简单的介绍了 Rime 的安装方式与使用方式,不过并没有关于 Fcitx5 的介绍
所以我来简单的记录一下
pacman -S fcitx5 fcitx5-qt fcitx5-gtk
pacman -S fcitx5-chinese-addons fcitx-rime
此时,Fcitx5 的配置文件在 ~/.config/fcitx5
下
pacman -S librime
pacman -S rime-double-pinyin #需要双拼的话,安装这个
此时,Rime 的配置文件在 ~/.local/share/fcitx5/rime
下
你可以选择使用 kcm-fcitx5
来通过 GUI 进行配置
不过本篇文章,我选择自己动手
注意:Fcitx5 在关闭的时候,会覆盖配置文件,所以请确保 Fcitx5 关闭后,再修改配置文件
$ cat ~/.config/fcitx5/profile
[Groups/0]
# Group Name
Name=Default
# Layout
Default Layout=us
# Default Input Method
DefaultIM=rime
[Groups/0/Items/0]
# Name
Name=keyboard-us
# Layout
Layout=
[Groups/0/Items/1]
# Name
Name=rime
# Layout
Layout=
[GroupOrder]
0=Default
这份配置文件给 Fcitx5 设置了两个输入法,一个是 US 键盘,一个是 Rime
然后,和其他输入平台一样,我们需要配置环境变量
cat ~/.xprofile
export GTK_IM_MODULE=fcitx5
export XMODIFIERS=@im=fcitx5
export QT_IM_MODULE=fcitx5
这个是使用 Xorg 时才有效的
关于使用 Wayland 时的环境变量设置,请查阅 Environment variables (简体中文) – Arch Wiki
然后将 Fcitx5 加入自启动后,重启即可
Github 上有许多优秀的 rime 的配置文件
通常情况下,你只需要将整个项目 clone 到本地,便可以直接使用
以及,这也是一个不错 Rime 配置 https://sh.alynx.one/posts/My-RIME/
下面,就是我的折腾环节
明月拼音不是不香
就是每次在打词库里没有的词组的时候,经常会出现一堆繁体好几页,我还找不到自己想要的
这个问题显然是简体繁体之间转换除了什么奇怪的问题,不过,这个问题显然不好解决
既然解决不了,不如搞一个基于简体的输入方案
显然,不止我一个这么想
hosxy/rime-aurora-pinyin 就是这样一种输入方案,码表全部为简体中文,并且几乎只有 「通用规范汉字表」 中的汉字
然后你兴冲冲的下载了,开始用了,发现有一个问题
这个输入方案,没有词组……
通常情况下, Sogou 词库 里能找到我们需要的词库
但是这次不一样,这个输入方案里一点词库都没有
所以即使从 Sogou 词库里鼓捣几个下来,输入体验也不是很好
这个时候,我们需要一份中文常用词汇表
我找到了这个 indiejoseph/现代汉语常用词表.txt
简单处理一下(Vim 都可以处理),就可以用做 Rime 的词库了
再来试试,不错
这个倒是有比较优秀的方案了 studyzy/imewlconverter
虽然 AUR 里有这个包,但是我并没有成功安装,反正 Releases 里也有 bin,直接用吧
本篇文章使用 Fcitx5 + Rime 在 Terminator + Vim 的环境下写的
在写这篇文章时,体验还是很好的,九成词语都在第一或者第二候选,不在的词语虽然需要自己去选,但并不复杂
本文所有配置文件都可以在 woshiluo/woshiluo-config 里找到
这次在写文章的时候主要参考是各个项目的 Readme 和 Wiki,以及 Arch Wiki,就不一一列出来了
这篇文章只是基于自己的配置经历所写,如果在任何地方有错误,希望你能通过评论指出
最后,安利 hosxy/fcitx5-material-color 主题,上面的截图就是这个主题,非常好看
本篇文章是一个配置案例,而并非入门指南
我一开始用 Linux 是 DDE 玩家(Deepin 对萌新及其友好),后来改用 Debian ,就开始当 Gnome 人了
Gnome 作为一个几乎开箱即用的桌面环境还是很不错的。后来也试用过 KDE,被复杂的控制劝退了,于是就一直用 Gnome
后来听机房的 c0per 学长说过 i3,不过在他 laptop 上的 i3wm 真的好简洁简陋,大概是一名高三生实在是没有时间,所以我也就没有在意过这个东西。
前两天又双遇到了 Gnome 的一堆 Bug,大概是每逢 Gnome 版本更新都有的,于是在 LK 的大力安利下入坑了
「i3 是一种动态的平铺式窗口管理器」
ArchWiki – I3_(简体中文)
反正我是没有看懂这个简介,不过让我们顺着查一下
「平铺式(或直译瓦片式)窗口管理器,其中的窗口不能够重叠,而是像瓦片一样挨个摆放。这种窗口管理器一般比较依赖键盘操作,较少使用鼠标。此类窗口管理器一般也是高度可定制的。」
ArchWiki – Window_manager_(简体中文)
简单来讲,i3wm 作为一个窗口管理器,默认会将你的窗口像瓦片一样放置于屏幕上,但你也可以令其变成浮动窗口
i3wm 和 Gnome 最大的区别,是一个是 DE,一个是 WM,前者对后者实际上是包含关系
不过我在更换 i3wm 后并没有继续使用 gdm,而是使用了 LightDM
i3wm 有 i3bar,用于显示系统的信息等
相比较 Gnome 的一套环境,i3wm 只是一个 WM,很多功能都要自己配置
所以在这里列了一些我使用 i3wm 的配置
i3wm 有一个好,配置文件里几乎能改一切
i3wm 的快捷键都在 ~/.config/i3/config
写的很清楚
我个人并没有对快捷键做什么修改
i3status 作为 i3bar 的一部分,可以用于显示系统状态之类的
我在调 i3status
调了一阵后发现 —— 这东西太简洁了,想调好看很费事
于是我选择了 greshake/i3status-rust
作为了替代
并在 i3status 中调用了一言,有那么两句中二的话刺激一下自己也挺好的
i3 中默认使用 dmenu
作为执行命令的方式
但是这个东西相当简洁,甚至不支持快速切换窗口
但是我们有替代品 rofi
$ cat ~/.config/rofi/config.rasi
configuration {
modi: "window,drun,ssh,combi";
theme: "android_notification";
font: "Fira Code 10";
combi-modi: "window,drun,ssh";
}
然后在 i3 的配置文件中写入
bindsym $mod+d exec --no-startup-id "rofi -show combi"
i3 并不会给你自动配置好 ACPI 事件, 不过这个很好处理,用 acpid
就可以了
xautolock
与 DPMS 可以轻松的完成这个任务
i3lock 使用起来挺顺手的,我个人喜欢把背景图片加个毛玻璃效果当 i3lock 的壁纸,这个 gimp 里拿滤镜搞就行了
在 i3 的配置文件中写写入
exec --no-startup-id xset s 60 120
exec --no-startup-id xss-lock -n ~/.config/i3/i3lock.sh -- i3lock -n -i ~/Pictures/Wallpaper/71849322_p0_glur.png
exec --no-startup-id ~/.config/i3/screensaver.sh
exec --no-startup-id xautolock -time 5 -locker "systemctl suspend"
$ cat ~/.config/i3/i3lock.sh
#!/bin/sh
xset dpms force off
~/.config/i3/screensaver.sh
是 https://github.com/iye/lightsOn
,用于避免在看视频的时候给 suspend 了
这个可以做到 60s 不动黑屏,180s 后开启 i3lock,300s 后 suspend
本文的所有配置都可以在 woshiluo/woshiluo-config
下找到
本文仅仅是自己配置的小小记录,如果有任何问题,请大佬在评论区指出
总的来说,i3 给我的感觉像极了 vim,配置文件坑半天,上手难度不小,不过上手了还是很爽的
反正给我的感觉比 Gnome 爽不少
虽然要自己配好多东西((
我在配置的时候参考了下面这些文章/网页,在此表达谢意
顺带 Orz LK
给定一个整数 $x(2\leq x \leq 10^9)$
求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$
多组解输出任意一个
这有啥说的,随便找个质因数让后输出 $p, x$ 就可以
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:36:48
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
int t, x;
int main() {
scanf( "%d", &t );
while( t -- ) {
scanf( "%d", &x );
int sq = std::sqrt(x) + 1;
for( int i = 1; i <= sq; i ++ ) {
if( x % i == 0 ) {
int tmp = ( x / i ) - 1;
if( tmp == 0 )
continue;
printf( "%d %d\n", i, tmp * i );
break;
}
}
}
}
给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面
问这样接完后,最长严格上升子序列的长度
因为可以接无限次,所以直接输出数字个数就可以了
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:42:47
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
int t;
int n;
int a[N];
int main() {
scanf( "%d", &t );
while( t -- ) {
scanf( "%d", &n );
for( int i = 1; i <= n; i ++ ) {
scanf( "%d", &a[i] );
}
std::sort( a + 1, a + n + 1 );
int cnt = 0, la = 0;
for( int i = 1; i <= n; i ++ ) {
if( i == 1 || a[i] != la ) {
la = a[i];
cnt ++;
}
}
printf( "%d\n", cnt );
}
}
给一棵节点数为 $n$ 的树
现在你要给每条边一个边权,要求:
现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值
请给出一种边权方案,最小化 $\max{MEX(u,v)}$
考虑每条边会被算进去多少次,记为每条边的贡献
贡献越大给越大的边就可以了
实际上可以更加简化,因为无论如何一定有一个 $MEX \geq 2$
所以我们尽可能避免 $0,1,2$ 出现在一条边上即可
随便找一个度数 $\geq 2$ 的点,把这三个数字放上去即可
如果没有这种点,那么怎么摆都会有一条 $MEX=n-1$ 的路径
// Woshiluo Luo<[email protected]>
// 2020/03/14 22:52:18
#include <cstdio>
#include <cstring>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
// Edge Start
struct edge {
int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to, int val ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
e[ecnt].val = val;
ehead[now] = ecnt;
}
// Edge End
struct node { long long val; int id; } max[N];
bool cmp( node _a, node _b ) { return _a.val < _b.val; }
int n, x, y;
int son[N], val[N];
void dfs( int now, int la ) {
son[now] = 1;
for( int i = ehead[now]; i; i = e[i].next ) {
if( e[i].to == la )
continue;
dfs( e[i].to, now );
son[now] += son[ e[i].to ];
max[ e[i].val ].val = ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) );
}
}
int main() {
#ifdef woshiluo
freopen( "c.in", "r", stdin );
freopen( "c.out", "w", stdout );
#endif
scanf( "%d", &n );
for( int i = 1, u, v; i < n; i ++ ) {
max[i].id = i;
scanf( "%d%d", &u, &v );
add_edge( u, v, i );
add_edge( v, u, i );
}
dfs( 1, 0 );
std::sort( max + 1, max + n, cmp );
for( int i = 1; i < n; i ++ ) {
val[ max[i].id ] = i - 1;
}
for( int i = 1; i < n; i ++ ) {
printf( "%d\n", val[i] );
}
}
给定两个整数 $u,v$ 求最短的数列 $a$ 满足
多解输出任意一个
无解输出 $-1$
这题感觉的 C 简单啊
满足 $xor$ 容易,满足 $v$ 的话需要难度
考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响
因此可以确定每一位的奇偶性
然后随便搞一下满足 $v$ 就可以了
// Woshiluo Luo<[email protected]>
// 2020/03/14 23:39:20
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
unsigned long long u, v;
int bit_u[110], bit_less[110], bit_cnt[110];
std::vector<unsigned long long> ans;
inline void noans() {
printf( "-1\n" );
exit(0);
}
void to_bit( unsigned long long a, int bit[] ) {
int cnt = 0;
while( a ) {
bit[ ++ cnt ] = a & 1;
a >>= 1;
}
}
int main() {
scanf( "%llu%llu", &u, &v );
if( v < u )
noans();
to_bit( v - u, bit_less );
to_bit( u, bit_u );
for( int i = 1; i <= 100; i ++ ) {
bit_cnt[i] = bit_u[i];
}
int p = 64;
int cnt = 0;
while( p ) {
bit_cnt[p] += ( cnt - ( cnt & 1 ) );
cnt = cnt & 1;
if( bit_less[p] )
cnt ++;
p --; cnt <<= 1;
}
if( cnt != 0 )
noans();
bool flag = true;
while( flag ) {
flag = false;
unsigned long long out = 0;
unsigned long long p = 1;
for( int i = 1; i <= 64; i ++, p <<= 1 ) {
if( bit_cnt[i] ) {
out = out | p;
bit_cnt[i] --;
flag = true;
}
}
if( flag )
ans.push_back(out);
}
cnt = ans.size();
printf( "%d\n", cnt );
for( int i = 0; i < cnt; i ++ ) {
printf( "%llu ", ans[i] );
}
}
给你一个长度为 $n$ 的数列,保证数列中每个数字有不超过 $7$ 个因数
请求出最短的子序列,使子序列成绩为完全平方数
这题比 F 题难吧…
首先由 保证数列中每个数字有不超过 $7$ 个因数
得每个数不会有超过两个 $1$ 和其本身以外的质因数
然后我们可以先把每个数里的完全平方数因子先除掉,因为这些不会对答案造成影响
这样下来每个数的因子只有 1 和其本身以及两个质因数(前提是这个数不是质数)
然后建图,如果这个数是质数,将其和 $1$ 连接,如过不是将其的两个质因数连接
剩下就是求最小环
// Woshiluo Luo<[email protected]>
// 2020/03/15 22:08:53
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e6 + 1e4;
const int M = 1100;
const int INF = 0x3f3f3f3f;
int n, ans = INF;
int dis[N], fa[N];
bool marked[N], pool[N];
// Edge Start
struct edge {
int cur, to, next;
} e[ N << 1 ];
int ehead[N], ecnt = 1;
inline void add_edge( int now, int to ) {
ecnt ++;
e[ecnt].cur = now;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
ehead[now] = ecnt;
}
// Edge End
int bfs( int st ) {
memset( dis, INF, sizeof(dis) );
memset( fa, 0, sizeof(fa) );
std::queue<int> q;
q.push(st); dis[st] = 0;
while( !q.empty() ) {
int cur = q.front(); q.pop();
for( int i = ehead[cur]; i; i = e[i].next ) {
if( e[i].to == fa[cur] )
continue;
if( dis[ e[i].to ] >= INF ) {
fa[ e[i].to ] = cur;
dis[ e[i].to ] = dis[cur] + 1;
q.push( e[i].to );
}
else {
return dis[cur] + dis[ e[i].to ] + 1;
}
}
}
return INF;
}
int main() {
scanf( "%d", &n );
for( int i = 1, x; i <= n; i ++ ) {
scanf( "%d", &x );
std::vector<int> a;
int cnt = std::sqrt(x) + 1;
while(cnt > 1) {
int cnt_pow = cnt * cnt;
while( x % cnt_pow == 0 )
x /= cnt_pow;
cnt --;
}
if( x == 1 )
chk_Min( ans, 1 );
if( pool[x] )
chk_Min( ans, 2 );
pool[x] = true;
int tmp = std::sqrt(x);
for( int j = 2; j <= tmp; j ++ ) {
if( x % j == 0 ) {
a.push_back(j);
a.push_back( x / j );
break;
}
}
if( a.size() == 0 ) {
add_edge( 1, x );
add_edge( x, 1 );
}
else if( a.size() != 0 ) {
add_edge( a[0], a[1] );
add_edge( a[1], a[0] );
}
}
if( ans != INF ) {
printf( "%d\n", ans );
return 0;
}
for( int i = 1; i <= 1000; i ++ ) {
if( ehead[i] )
chk_Min( ans, bfs(i) );
}
if( ans >= INF )
ans = -1;
printf( "%d\n", ans );
}
给定一个 $n$ 个节点的图
令 $glo=\lceil\sqrt{n}\rceil$
你要么找到一个长度和 $glo$ 相等的环
要么找到一个比 $glo$ 小的独立集
先试图找环,找不到肯定有独立集
// Woshiluo Luo<[email protected]>
// 2020/03/15 15:49:32
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }
const int N = 1e5 + 1e4;
const int M = 2e5 + 1e4;
int n, m, need;
int dep[N];
bool vis[N];
std::stack<int> st;
// Edge Start
struct edge { int to, next; } e[ M << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[now];
ehead[now] = ecnt;
}
// Edge End
void dfs( int now ) {
st.push(now);
dep[now] = st.size();
for( int i = ehead[now]; i; i = e[i].next ) {
if( dep[ e[i].to ] == 0 )
dfs( e[i].to );
else if( dep[now] - dep[ e[i].to ] + 1 >= need ) {
int size = dep[now] - dep[ e[i].to ] + 1;
printf( "%d\n%d\n", 2, size );
for( int i = 1; i <= size; i ++ ) {
printf( "%d ", st.top() );
st.pop();
}
exit(0);
}
}
if( !vis[now] ) {
for( int i = ehead[now]; i; i = e[i].next ) {
vis[ e[i].to ] = true;
}
}
st.pop();
}
int main() {
#ifdef woshiluo
freopen( "f.in", "r", stdin );
freopen( "f.out", "w", stdout );
#endif
scanf( "%d%d", &n, &m );
while( need * need < n )
need ++;
while( m -- ) {
int u, v;
scanf( "%d%d", &u, &v );
add_edge( u, v ); add_edge( v, u );
}
dfs(1);
printf( "%d\n", 1 );
int cnt = 0;
for( int i = 1; i <= n; i ++ ) {
if( vis[i] == false ) {
printf( "%d ", i );
cnt ++;
}
if( cnt == need )
break;
}
}