Fcitx5 & Rime 配置小记

输入过程截图
Fcitx5 输入截图

0 Rime 是什么

在很多情况下,如果你直接带着 Linux 输入法 这样的关键字去 Google 搜索

那么你得到的通常都是 Google Pinyin,或者 Sogou Pinyin

Google Pinyin 年久失修,Sogou 的话,维护也不算多上心

如果你再认真一点,你也许可以找到 Sunpinyin 和 Libpinyin

这两个的体验已经相当不错了,但你也会发现,在准确率上,还是差了点,而且在词库大的时候,还会很卡

这个时候,你就会查到 Rime —— 中州韵输入法引擎


聪明的输入法懂我心意

这是 Rime 自己的标语

Rime 具有更强大的定制性,更优秀的词语联想,以及跨平台的支持

如果你不相信 Sogou(相信我,没几个人相信 Sogou 不会上传你的数据),那么 Rime 是目前最优秀的选择

0.1 环境 & 我的需求

Arch Linux

小鹤双拼用户

1 Rime 的安装

对于 Arch Linux,我们首先需要选择一个输入平台,我选择的是 Fcitx5

关于 Fcitx5,你可以查阅 Fcitx5 – ArchWiki

(虽然这个东西在 Waylnd 下的功能还很残缺,但是,Wayland 本身问题也不少)

关于 Rime,Arch Wiki 有 这个页面

这个页面简单的介绍了 Rime 的安装方式与使用方式,不过并没有关于 Fcitx5 的介绍

所以我来简单的记录一下

1.1 Fcitx5 的安装

pacman -S fcitx5 fcitx5-qt fcitx5-gtk
pacman -S fcitx5-chinese-addons fcitx-rime

此时,Fcitx5 的配置文件在 ~/.config/fcitx5

1.2 Rime 的安装

pacman -S librime 
pacman -S rime-double-pinyin #需要双拼的话,安装这个

此时,Rime 的配置文件在 ~/.local/share/fcitx5/rime

1.3 Fcitx5 的配置

你可以选择使用 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 [email protected]=fcitx5
export QT_IM_MODULE=fcitx5

这个是使用 Xorg 时才有效的

关于使用 Wayland 时的环境变量设置,请查阅 Environment variables (简体中文) – Arch Wiki

然后将 Fcitx5 加入自启动后,重启即可

2 Rime 的配置

2.0 安利时间

Github 上有许多优秀的 rime 的配置文件

通常情况下,你只需要将整个项目 clone 到本地,便可以直接使用

这里推荐 wongdean/rime-settings

以及,这也是一个不错 Rime 配置 https://sh.alynx.one/posts/My-RIME/

下面,就是我的折腾环节

2.1 极光拼音

明月拼音不是不香

就是每次在打词库里没有的词组的时候,经常会出现一堆繁体好几页,我还找不到自己想要的

这个问题显然是简体繁体之间转换除了什么奇怪的问题,不过,这个问题显然不好解决

既然解决不了,不如搞一个基于简体的输入方案

显然,不止我一个这么想

hosxy/rime-aurora-pinyin 就是这样一种输入方案,码表全部为简体中文,并且几乎只有 「通用规范汉字表」 中的汉字

然后你兴冲冲的下载了,开始用了,发现有一个问题

这个输入方案,没有词组……

2.2 寻找词库

通常情况下, Sogou 词库 里能找到我们需要的词库

但是这次不一样,这个输入方案里一点词库都没有

所以即使从 Sogou 词库里鼓捣几个下来,输入体验也不是很好

这个时候,我们需要一份中文常用词汇表

我找到了这个 indiejoseph/现代汉语常用词表.txt

简单处理一下(Vim 都可以处理),就可以用做 Rime 的词库了

再来试试,不错

2.3 Sogou 词库的导入

这个倒是有比较优秀的方案了 studyzy/imewlconverter

虽然 AUR 里有这个包,但是我并没有成功安装,反正 Releases 里也有 bin,直接用吧

3 结

本篇文章使用 Fcitx5 + Rime 在 Terminator + Vim 的环境下写的

在写这篇文章时,体验还是很好的,九成词语都在第一或者第二候选,不在的词语虽然需要自己去选,但并不复杂

本文所有配置文件都可以在 woshiluo/woshiluo-config 里找到

这次在写文章的时候主要参考是各个项目的 Readme 和 Wiki,以及 Arch Wiki,就不一一列出来了

这篇文章只是基于自己的配置经历所写,如果在任何地方有错误,希望你能通过评论指出

最后,安利 hosxy/fcitx5-material-color 主题,上面的截图就是这个主题,非常好看

i3wm 从初识到真香

本篇文章是一个配置案例,而并非入门指南

0 怎么认识的 i3wm

我一开始用 Linux 是 DDE 玩家(Deepin 对萌新及其友好),后来改用 Debian ,就开始当 Gnome 人了

Gnome 作为一个几乎开箱即用的桌面环境还是很不错的。后来也试用过 KDE,被复杂的控制劝退了,于是就一直用 Gnome

后来听机房的 c0per 学长说过 i3,不过在他 laptop 上的 i3wm 真的好简洁简陋,大概是一名高三生实在是没有时间,所以我也就没有在意过这个东西。

前两天又双遇到了 Gnome 的一堆 Bug,大概是每逢 Gnome 版本更新都有的,于是在 LK 的大力安利下入坑了

1 什么是 i3wm

「i3 是一种动态的平铺式窗口管理器」

ArchWiki – I3_(简体中文)

反正我是没有看懂这个简介,不过让我们顺着查一下

「平铺式(或直译瓦片式)窗口管理器,其中的窗口不能够重叠,而是像瓦片一样挨个摆放。这种窗口管理器一般比较依赖键盘操作,较少使用鼠标。此类窗口管理器一般也是高度可定制的。」

ArchWiki – Window_manager_(简体中文)

简单来讲,i3wm 作为一个窗口管理器,默认会将你的窗口像瓦片一样放置于屏幕上,但你也可以令其变成浮动窗口

i3wm 和 Gnome 最大的区别,是一个是 DE,一个是 WM,前者对后者实际上是包含关系

不过我在更换 i3wm 后并没有继续使用 gdm,而是使用了 LightDM

i3wm 有 i3bar,用于显示系统的信息等

2 配置

相比较 Gnome 的一套环境,i3wm 只是一个 WM,很多功能都要自己配置

所以在这里列了一些我使用 i3wm 的配置

2.1 快捷键

i3wm 有一个好,配置文件里几乎能改一切

i3wm 的快捷键都在 ~/.config/i3/config 写的很清楚

我个人并没有对快捷键做什么修改

2.2 i3status

i3status 作为 i3bar 的一部分,可以用于显示系统状态之类的

我在调 i3status 调了一阵后发现 —— 这东西太简洁了,想调好看很费事

于是我选择了 greshake/i3status-rust 作为了替代

并在 i3status 中调用了一言,有那么两句中二的话刺激一下自己也挺好的

2.3 rofi

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"

2.4 acpi 配置

i3 并不会给你自动配置好 ACPI 事件, 不过这个很好处理,用 acpid 就可以了

2.5 自动锁屏/睡眠

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.shhttps://github.com/iye/lightsOn,用于避免在看视频的时候给 suspend 了

这个可以做到 60s 不动黑屏,180s 后开启 i3lock,300s 后 suspend

3 结

本文的所有配置都可以在 woshiluo/woshiluo-config 下找到

本文仅仅是自己配置的小小记录,如果有任何问题,请大佬在评论区指出

总的来说,i3 给我的感觉像极了 vim,配置文件坑半天,上手难度不小,不过上手了还是很爽的

反正给我的感觉比 Gnome 爽不少

虽然要自己配好多东西((

3.1 致谢

我在配置的时候参考了下面这些文章/网页,在此表达谢意

顺带 Orz LK

Codeforces Contest #1325 解题报告 & 题目大意

A EhAb AnD gCd

题目大意

给定一个整数 $x(2\leq x \leq 10^9)$

求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$

多组解输出任意一个

Code

这有啥说的,随便找个质因数让后输出 $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;
            }
        }
    }
}

B CopyCopyCopyCopyCopy

题目大意

给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面

问这样接完后,最长严格上升子序列的长度

Code

因为可以接无限次,所以直接输出数字个数就可以了

// 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 );
    }
}

C Ehab and Path-etic MEXs

题目大意

给一棵节点数为 $n$ 的树

现在你要给每条边一个边权,要求:

  • 边权为一个整数 $v(0\leq v \leq n – 2)$
  • 每条边的边权不能和别的边的相同

现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值

请给出一种边权方案,最小化 $\max{MEX(u,v)}$

思路

考虑每条边会被算进去多少次,记为每条边的贡献

贡献越大给越大的边就可以了

实际上可以更加简化,因为无论如何一定有一个 $MEX \geq 2$

所以我们尽可能避免 $0,1,2$ 出现在一条边上即可

随便找一个度数 $\geq 2$ 的点,把这三个数字放上去即可

如果没有这种点,那么怎么摆都会有一条 $MEX=n-1$ 的路径

Code

// 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] );
    }
}

D Ehab the Xorcist

给定两个整数 $u,v$ 求最短的数列 $a$ 满足

  • $$ \sum a = v $$
  • xor 和为 $u$

多解输出任意一个

无解输出 $-1$

题目大意

这题感觉的 C 简单啊

满足 $xor$ 容易,满足 $v$ 的话需要难度

考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响

因此可以确定每一位的奇偶性

然后随便搞一下满足 $v$ 就可以了

Code

// 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] );
    }

}

E Ehab’s REAL Number Theory Problem

题目大意

给你一个长度为 $n$ 的数列,保证数列中每个数字有不超过 $7$ 个因数

请求出最短的子序列,使子序列成绩为完全平方数

思路

这题比 F 题难吧…

首先由 保证数列中每个数字有不超过 $7$ 个因数 得每个数不会有超过两个 $1$ 和其本身以外的质因数

然后我们可以先把每个数里的完全平方数因子先除掉,因为这些不会对答案造成影响

这样下来每个数的因子只有 1 和其本身以及两个质因数(前提是这个数不是质数)

然后建图,如果这个数是质数,将其和 $1$ 连接,如过不是将其的两个质因数连接

剩下就是求最小环

Code

// 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 );
}

F Ehab’s Last Theorem

题目大意

给定一个 $n$ 个节点的图

令 $glo=\lceil\sqrt{n}\rceil$

你要么找到一个长度和 $glo$ 相等的环

要么找到一个比 $glo$ 小的独立集

Code

先试图找环,找不到肯定有独立集

// 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;
    }
}

Codeforces Contest #1312 解题报告 & 部分翻译

比赛链接:Educational Codeforces Round 83 (Rated for Div. 2)

A Two Regular Polygons

1 题目大意

给你两个正多边形,一个 $n$ 条边 $A$ ,一个 $m$ 条边 $B$

问 $B$ 有没有可能被 $A$ 包含且所有顶点都与 $A$ 的某一个节点重合

有输出 YES ,否则输出 NO

2 Code

判 $n \bmod m = 0$ 就可以了

#include <cstdio>

int T;
int n, m;

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d", &n, &m );
        printf( "%s\n", ( n % m == 0 )? "YES": "NO" );
    }
}

B Bogosort

1 题目大意

给你一个长度为 $n$ 的序列 $a$, 你可以将 $a$ 重新排序,使其满足 $j – a_j \neq i – a_i$

输出任何一个即可

保证有解

$n \leq 100$

2 思路

$$
\begin{aligned}
j – a_j & \neq i – a_i \\
j – i & \neq a_j – a_i
\end{aligned}
$$

直接从大到小输出

3 Code

// Woshiluo Luo<[email protected]>  
// 2020/03/09 22:40:32 
#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 = 110;

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 );
        for( int i = n; i >= 1; i -- ) {
            printf( "%d ", a[i] );
        }
        printf( "\n" );
    }
}

C Adding Powers

1 题目大意

给你两个长度为 $n$ 的数列 $a,v$

其中 $a$ 通过输入提供,$v$ 初始所有值为 $0$

接下来,对于第 $i$ 次操作(从 $0$ 计数),你可以

  • 选择任意一个 $v_i$ 增加 $k^i$
  • 什么都不做

问你是否通过多次操作后,使 $v$ 变成 $a$

能输出 YES ,否则输出 NO

2 思路

首先对于每个数字 $a$, 考虑其是否可以变成多个 $k^i$ 的和(不能有重复的 $i$)

能的话算出来,看看有没有和之前重复的,有就不可能

不能的话直接没有可能

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 22:58:45
#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 = 110;

int T;
int n;
long long k;
bool vis[N];
long long a[N];

inline void wrong() {
    printf( "NO\n" );
}

inline void right() {
    printf( "YES\n" );
}

void calc() {
    for( int i = 1; i <= n; i ++ ) {
        if( a[i] == 0 ) {
            continue;
        }
        long long cur = a[i];
        int cnt = 1;
        while( cur ) {
            int tmp = cur % k;
            if( tmp > 1 ) {
                wrong();
                return ;
            }
            if( tmp == 1 ) {
                if( vis[cnt] == false )
                    vis[cnt] = true;
                else {
                    wrong();
                    return ;
                }
            }
            cur /= k;
            cnt ++;
        }
    }
    right();
}

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        memset( vis, 0, sizeof(vis) );

        scanf( "%d%lld", &n, &k );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%lld", &a[i] );
        }

        calc();
    }
}

D Count the Arrays

1 题目大意

你需要寻找这样的数列个数

  • 有 $n$ 个元素
  • 每个数字都是 $1$ 到 $m$ 之间的整数
  • 只有恰好一对数字相等
  • 数列先严格递增,再严格递减

个数对 $998244353$ 取模后输出

$2 \leq n \leq m \leq 2 \times 10^5$

2 思路

式子题,看 Code 去

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 23:21: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 = 2e5 + 1e4;
const int mod = 998244353;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while(p) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}

inline int get_inv( int a ) { return ksm( a, mod - 2 ); }

int n, m, sum, ans;
int fact[N], inv[N];

void init() {
    fact[1] = 1;
    for( int i = 2; i <= m; i ++ ) {
        fact[i] = mul( fact[ i - 1 ], i );
    }
    inv[m] = get_inv( fact[m] );
    for( int i = m - 1; i >= 1; i -- ) {
        inv[i] = mul( inv[ i + 1 ], i + 1 );
    }
    inv[0] = 1;
    fact[0] = 1;
}

// Get C^a_b
inline int C( int a, int b ) {
    if( a <= 0 )
        return 1;
    if( b <= 0 )
        return 1;
    return mul( mul( fact[b], inv[ b - a ] ), inv[a] );
}

int main() {
#ifdef woshiluo
    freopen( "d.in", "r", stdin );
    freopen( "d.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    init();

    for( int i = n - 1; i <= m; i ++ ) {
        add_eq( sum, mul( C( n - 3, i - 2 ), mul( m - i + 1, n - 2 ) ) );
    }

    for( int i = 2; i < n; i ++ ) {
        add_eq( ans, mul( sum, C( i - 2, n - 3 ) ) );
    }

    printf( "%d\n", ans );
}

E Array Shrinking

1 题目大意

这好像是个原题

给你一个长度为 $n$ 的数列 $a$

如果 $a_i = a_{i + 1}$, 那么这两个数可以合并成 $a_i + 1$

问最小数列长度

$1 \leq a_i \leq 1000, 1 \leq n \leq 500$

2 思路

区间 dp

设 $f_{i,j}$ 为 $i$ 到 $j$ 最小长度

$merged_{i,j}$ 为 $i$ 到 $j$ 合并出来的数字

然后就是标准板子了

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/10 15:50:48
#include <cstdio>
#include <cstring>

#include <algorithm>

const int N = 510;

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 n;
int a[N];
int f[N][N], merged[N][N];

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%d", &a[i] );
        f[i][i] = 1;
        merged[i][i] = a[i];
    }
    for( int len = 2; len <= n; len ++ ) {
        for( int left = 1, rig = len; rig <= n; left ++, rig ++ ) {
            f[left][rig] = rig - left + 1;
            for( int mid = left; mid < rig; mid ++ ) {
                int &f_left = f[left][mid], &f_rig = f[ mid + 1 ][rig],
                &merge_left = merged[left][mid], &merge_rig = merged[ mid + 1 ][rig];
                chk_Min( f[left][rig], f_left + f_rig );
                if( f_left == 1 && f_rig == 1 && merge_left == merge_rig ) {
                    f[left][rig] = 1;
                    merged[left][rig] = merge_left + 1;
                }
            }
        }
    }
    printf( "%d\n", f[1][n] );
}

AGC 034 F RNG and XOR

题目连接: https://atcoder.jp/contests/agc034/tasks/agc034_f

道理我都懂,可是不看题解不到啊……

$$\newcommand \xor{\mathbin{\mathbf{xor}}}$$

1 题意

给定一个数字 $n$

对于 $0 \cdots 2^n – 1$ 中每个数字都有一个 $a_i$

现在有一个数 $X$, 一开始为 $0$

每一次操作会随机选择一个数字 $i$ (其中 $0 \leq i \leq 2^n – 1$,选中 $i$ 的概率为 $\frac{a_i}{\sum a}$)

然后令 $X = X \xor i$

问使 $X=i$ 的期望次数

2 思路

先令
$$p_i=\frac{a_i}{\sum a}$$

令 $f_i$ 表示从 $i$ 到 $0$ 的期望次数,这和从 $0$ 到 $i$ 显然是一样的

接着有一个非常显然的式子

$$
\begin{aligned}
f_i &= f_{i \xor j} \times p_j + 1 ( i \neq 0 )\\
f_i – 1 &= f_{i \xor j } \times p_j ( i \neq 0 )
\end{aligned}
$$

然后我们就可以得到这个式子

$$ (f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( x, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} – 1 ) $$

但是 $x$ 是未知的

注意到 $\sum p = 1$ 所以左边右边的和是相等的

所以
$$
\begin{aligned}
x &= \sum_{i=0}^{2^n-1} f_i – \sum_{i=1}^{2^n-1} f_i – 1 \\
&= f_0 + 2^n – 1
\end{aligned}
$$

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( f_0 + 2^n – 1, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} -1 )
$$

我们需要的使其中两个式子没有未知数

注意到如果使 $p_0 = p_0 – 1$

那么右边每一个数都会减去 $f_i$

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
$$

于是就可以放进 FWT 里直接做

然后你就发现这东西跑出来是错的……

为什么呢


$$
\begin{aligned}
\mathbf{P} & = (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
\mathbf{A} & = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
\end{aligned}
$$

因为 $\mathbf{P}$ 和 $\mathbf{A}$ FWT 后第一位都是 $0$

没有办法倒推出来 $f_0$

但是可以发现 $f$ 的值是可以平移的

$$ f_i + k = \sum_{i=0}^{2^n-1} p_j(f_{i \xor j} + k) + 1 = \sum_{i=0}^{2^n-1} f_{i \xor j} \times p_j + k + 1 $$

那么我们又知道 $f_i = 0$

所以将 $f$ 每一位都减去 $f_0$ 即可

3 Code

#include <cstdio> 

const int N = 1 << 20;
const int mod = 998244353;

int n;
int a[N], b[N], p[N], sum;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while( p ) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}
inline int inv( int a ) { return ksm( a, mod - 2 ); }

void XOR( int *f, int len, int x = 1 ) {
    for( int o = 2, k = 1; o <= len; o <<= 1, k <<= 1 ) {
        for( int i = 0; i < len; i += o ) {
            for( int j = 0; j < k; j ++ ) {
                add_eq( f[ i + j ], f[ i + j + k ] );
                f[ i + j + k ] = add( f[ i + j ], add( - f[ i + j + k ], - f[ i + j + k ] ) );
                mul_eq( f[ i + j ], x ); mul_eq( f[ i + j + k ], x );
            }
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "F.in", "r", stdin );
    freopen( "F.out", "w", stdout );
#endif
    scanf( "%d", &n );
    n = 1 << n;
    for( int i = 0; i < n; i ++ ) {
        scanf( "%d", &a[i] );
        sum += a[i];
        b[i] = mod - 1;
    }
    sum = inv(sum);
    for( int i = 0; i < n; i ++ ) {
        p[i] = mul( a[i], sum );
    }

    b[0] = n - 1; p[0] -= 1;
    XOR( b, n ); XOR( p, n );
    for( int i = 0; i < n; i ++ ){
        mul_eq( b[i], inv( p[i] ) );
    }
    XOR( b, n, inv(2) );
    for( int i = 0; i < n; i ++ ) {
        printf( "%d\n", ( ( add( b[i], -b[0] ) + mod ) % mod ) );
    }
}

将 Bilibili 缓存转换成视频

0 环境 & 提示

  • 电脑
    • PHP
    • Bash
  • 手机
    • Bilibili 国内版 5.54.0

这样子转换出来还是有水印的,请不要在未经 UP 主同意的情况下传播或用在非法行为

1 过程

因为要备份手机,就想着能不能把 Bilbili 的缓存转换成普通视频留在电脑上

然后看了一下下载目录,里面有一个 video.m4saudio.m4s

mpv 一打开,发现刚好一个是视频一个是音频…

剩下的事情就是拿 ffmpeg 合并一下的事情…

随便胡个脚本就行了

2 脚本

covert.sh
# Author: Woshiluo<[email protected]>
#!/bin/bash

work_dir=`pwd`;
fa_php=`pwd`"/fa.php";
part_php=`pwd`"/part.php";

echo $part_php;
mkdir -p "$work_dir/output"

function covert() {
	cp "$fa_php" ./
	cp "$part_php" ./
	fa=`php fa.php`
	part=`php part.php`
	echo "[INFO] Coverting $fa $part..."
	rm fa.php part.php
	mkdir -p "$work_dir/output/$fa"
	for file in `ls`; do
		if [ -d $file ]; then 
			cd $file
			ffmpeg -i video.m4s -i audio.m4s -c copy "$work_dir/output/$fa/$part.mkv" -y >/dev/null 2>&1
			cd ..
		fi
	done
	echo "[INFO] Done!"
}

for file in `ls`; do
	if [ -d $file ] && [ $file != "output" ]; then
		cd ./$file
		for video in `ls`; do
			if [ -d $video ]; then
				cd ./$video
				covert
				cd ..
			fi
		done
		cd ..
	fi
done
fa.php
<?php

$_file = file_get_contents( "./entry.json" );

$desc = json_decode( $_file );

echo $desc -> title;
part.php
<?php

$_file = file_get_contents( "./entry.json" );

$desc = json_decode( $_file );

echo $desc -> page_data -> part;

随便胡的脚本

把这三个文件放到 Bilibili 的下载目录下,然后执行 covert.sh 就行了

执行过后转换过的文件会在 output 目录下

NOIP 2017 提高组 Day2 T3 列队

题目链接: https://loj.ac/problem/2319

Also: https://www.luogu.com.cn/problem/P3960

1 思路

很明显,这个题目需要我们维护 $ n + 1 $ 个序列

这些序列要支持

  • 查询第 $k$ 个
  • 删除第 $k$ 个
  • 在末尾插入

动点脑子的话,树状树组上二分也是可行的,反正我不会

不动脑子的话, Splay 下高问题也不大

2 实现细节

如果把每个节点都单独储存的话,空间 $O(n + m)$ 承受不能

但是考虑到总修改次数很小,而且 Splay 维护的很多节点都是连续的

所以可以让 Splay 把连续的区间当作一个节点

空间问题就解决了

这样时间大概是 $O(q\log m)$ 的…

但是 Splay 的常数巨大…

于是就被 LibreOJ 无情卡常了

大概大力卡还是能过,但是我懒得搞了,反正 Luogu 上过了

3 Code

#include <cstdio>

inline long long seg_len( long long left, long long rig ) { return rig - left + 1; }
template <class T>
T read() {
	T res = 0; char x = getchar();
	while( x < '0' || x > '9' ) {
		x = getchar();
		continue;
	}
	while( x >= '0' && x <= '9' ) {
		res = res * 10 + x - '0';
		x = getchar();
	}
	return res;
}

int st_cnt, st[30];
template <class T>
void write( T res ) {
	while( res ) {
		st_cnt ++;
		st[ st_cnt ] = res % 10;
		res /= 10;
	}
	while( st_cnt ) {
		putchar( st[ st_cnt ] + '0' );
		st_cnt --;
	}
}

const int N = 3e5 + 1e4;

int n, m, q;

struct splay_node {
	splay_node *son[2], *fa;
	long long left, rig, size;
	splay_node( long long _left = 0, long long _rig = 0 ) {
		son[0] = son[1] = fa = 0; size = seg_len( _left, _rig );
		left = _left, rig = _rig;
	}
	void push_up() {
		this -> size = ( this -> son[0]? this -> son[0] -> size: 0 ) 
			+ ( this -> son[1]? this -> son[1] -> size: 0 ) 
			+ seg_len( left, rig );
	}
	bool get_son() { 
		if( this -> fa && this -> fa -> son[1] ) 
			return ( this -> fa -> son[1] ) == this;
		return 0;
	}
	inline long long len() { return seg_len( this -> left, this -> rig ); }
};

struct Splay {
	splay_node *rt;
	void init( long long left, long long rig ) {
		splay_node *c = new splay_node( left, rig );
		rt = c;
		rt -> push_up();
	}
	void rotate( splay_node *cur ) {
		bool kind = cur -> get_son();
		splay_node *tmp_fa = cur -> fa;
		if( tmp_fa == 0 ) 
			return ;
		if( tmp_fa -> fa == 0 ) 
			rt = cur;
		else 
			tmp_fa -> fa -> son[ tmp_fa -> get_son() ] = cur;
		cur -> fa = tmp_fa -> fa;
		tmp_fa -> son[kind] = cur -> son[ kind ^ 1 ];
		if( tmp_fa -> son[kind] )
			tmp_fa -> son[kind] -> fa = tmp_fa;
		cur -> son[ kind ^ 1 ] = tmp_fa; tmp_fa -> fa = cur;
		tmp_fa -> push_up(); cur -> push_up();
	}
	void splay( splay_node *from, splay_node *to = 0 ) {
		while( from -> fa != to ) {
			splay_node *fa = from -> fa;
			if( fa -> fa != to ) 
				rotate( ( fa -> get_son() ) == ( from -> get_son() )? fa: from );
			rotate(from);
		}
	}
	splay_node* find_kth( long long k ) {
		if( k == 0 ) 
			return 0;
		splay_node *cur = rt;
		while( cur ) {
			if( cur -> son[0] ) {
				if( cur -> son[0] -> size < k )
					k -= cur -> son[0] -> size;
				else {
					cur = cur -> son[0];
					continue;
				}
			}
			if( k <= cur -> len() ) 
				break;
			k -= cur -> len();
			if( cur -> son[1] ) {
				cur = cur -> son[1];
				continue;
			}
			return 0;
		}
		return cur;
	}
	splay_node* split_kth( long long k ) {/*{{{*/
		splay_node *cur = find_kth(k); splay(cur);
		if( cur -> son[0] ) 
			k -= cur -> son[0] -> size;
		k = ( cur -> left ) + k - 1;
		splay_node *ori_left = cur -> son[0], *ori_rig = cur -> son[1],
			*left = 0, *rig = 0, *mid;
		mid = new splay_node( k, k );
		if( cur -> left <= k - 1 ) {
			left = new splay_node( cur -> left, k - 1 );
			left -> fa = mid;
		}
		if( k + 1 <= cur -> rig ) {
			rig = new splay_node( k + 1, cur -> rig );
			rig -> fa = mid;
		}

		mid -> son[0] = left; mid -> son[1] = rig;
		splay_node *tmp_left = (left? left: mid), *tmp_rig = (rig? rig: mid);
		tmp_left -> son[0] = ori_left; tmp_rig -> son[1] = ori_rig;
		if( ori_left )
			ori_left -> fa = tmp_left; 
		if( ori_rig )
			ori_rig -> fa = tmp_rig;

		if( left ) 
			left -> push_up();
		if( rig ) 
			rig -> push_up();

		mid -> push_up();
		if( rt == cur ) 
			rt = mid;
		delete( cur );
		return mid;
	}/*}}}*/
	void del_kth( long long k ) {
		splay_node *cur = split_kth(k);
		splay_node *left = find_kth( k - 1 ), *rig = find_kth( k + 1 );
		if( left == 0 || rig == 0 ) {
			splay( cur );
			rt = ( cur -> son[ left == 0 ] ); rt -> fa = 0;
			delete( cur );
			return ;
		}
		splay( left ); splay( rig, left );
		delete( rt -> son[1] -> son[0] );
		rt -> son[1] -> son[0] = 0;
		rt -> son[1] -> push_up(); rt -> push_up();
	}
	void pull_up( splay_node *cur ) {
		if( cur ) {
			cur -> push_up();
			pull_up( cur -> fa );
		}
	}
	splay_node* push_back( long long val ) {
		splay_node *cur = rt;
		while( cur ) {
			if( cur -> son[1] ) {
				cur = cur -> son[1];
				continue;
			}
			cur -> son[1] = new splay_node( val, val );
			cur -> son[1] -> fa = cur;
			cur = cur -> son[1];
			break;
		}
		pull_up( cur );
		splay(cur);
		return cur;
	}
#ifdef debug
	void zxbl( splay_node *cur ) {
		if( cur == 0 ) 
			 return ;
		zxbl( cur -> son[0] );
		for( int i = cur -> left; i <= cur -> rig; i ++ ) 
			printf( "%2lld ", i );
		zxbl( cur -> son[1] );
	}
	void _zxbl() {
		zxbl( this -> rt );
	}
#endif
} T[N];

int main() {
#ifdef woshiluo
	freopen( "luogu.3960.in", "r", stdin );
	freopen( "luogu.3960.out", "w", stdout );
#endif
	n = read<int>(); m = read<int>(); q = read<int>();
	T[0].init( m, m );
	T[1].init( 1, m - 1 );
	for( int i = 2; i <= n; i ++ ){
		T[i].init( 1LL * ( i - 1 ) * m + 1, 1LL * i * m - 1 );
		T[0].push_back( 1LL * i * m );
	}
	while( q -- ) {
		int x, y;
		x = read<int>(); y = read<int>();
		if( y == m ) {
			long long cur = T[0].split_kth(x) -> left;
			write(cur);
			printf( "\n" );
			T[0].push_back(cur); T[0].del_kth(x);
		}
		else {
			Splay &tree = T[x];
			long long cur = tree.split_kth(y) -> left;
			write(cur);
			printf( "\n" );
			tree.push_back( T[0].split_kth(x) -> left ); tree.del_kth(y);
			T[0].push_back(cur); T[0].del_kth(x); 
		}
#ifdef debug
		printf( "%d %d\n", x, y );
		for( int i = 0; i <= n; i ++ ) {
			printf( "T[%d]: ", i );
			T[i]._zxbl();
			printf( "\n" );
		}
#endif
	}
}

Atcoder ARC 103 F Distance Sums

0 写在之前

这几天写的题目并不算少

然而这道题是唯一一个看过去傻了的题目…

应该以前听过,题面看着眼熟

可是死活不会做…

1 思路

基本上可以明确是到构造题

这里依赖两个性质:

树的中心的 $D$ 值是最小的

$$ D(fa) = D(x) – n + 2 \times size[i] $$

这个就是标准的树和树的重心的性质

可以推出来如果以重心做根,那么 $D$ 越大越在下面

所以尝试生成一颗以重心为根的树就行了

然后我发现我不会判否

结果发现最后生成出来树判断一次就行了…

2 实现

读入 $D$ 排序

从大到小依此根据上面的式子找父亲

最后判断一下是否正确就可以了

3 Code

// User: woshiluo
// Email: [email protected]
// Problem link: https://atcoder.jp/contests/arc103/tasks/arc103_d
// Comment: 
// Why the problem id is 'F', but the link is 'arc103_d'
// Interesting

#include <cstdio>
#include <cstdlib>

#include <map>
#include <algorithm>

const int N = 1e5 + 1e3;

int n;
int size[N], father[N];

struct node{
	int id;
	long long d;
} a[N];

std::map<long long, int> mp;

void wrong() {
	printf( "-1\n" );
	exit(0);
}
bool cmp( node _a, node _b ) { return _a.d < _b.d; }

int main() {
#ifdef woshiluo
	freopen( "F.in", "r", stdin );
	freopen( "F.out", "w", stdout );
#endif
	scanf( "%d", &n );
	for( int i = 1; i <= n; i ++ ) {
		scanf( "%lld", &a[i].d );
		a[i].id = i;
		size[i] = 1;
		mp[ a[i].d ] = i;
	}
	std::sort( a + 1, a + n + 1, cmp );
	int rt_d, rt;
	rt = a[1].id; rt_d = a[1].d;
	for( int i = n; i > 1; i -- ) {
		int fa = mp[ a[i].d + 2LL * size[ a[i].id ] - n ];
		if( fa == 0 ) {
			wrong();
			return 0;
		} 
		size[fa] += size[ a[i].id ];
		father[ a[i].id ] = fa;
	}
	for( int i = 1; i <= n; i ++ ) {
		if( i == rt ) 
			continue;
		 rt_d -= size[i];
	}
	if( rt_d != 0 ) 
		wrong();

	for( int i = 1; i <= n; i ++ ) {
		if( i == rt ) 
			continue;
		printf( "%d %d\n", father[i], i );
	}
}

HDU 4507 恨7不成妻

思路

裸的要死的数位 DP 题目

一眼看过去,平方和,有点懵

但是维护平方和也是老套路了

维护 $sum$, $cnt$, $pow_sum$ 就可以了

代码

代码写的着急,会有一些不太好看

#include <cstdio>

const int mod = 1e9 + 7;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline int power( int a ) { return mul( a, a ); }

int T, max_len;
long long left, rig;
int _count[110][2][10][10][10], _sum[110][2][10][10][10], _pow[110][2][10][10][10];
int max_count[110][2][10][10][10], max_sum[110][2][10][10][10], max_pow[110][2][10][10][10];
bool _vis[110][2][10][10][10];
int a[110];

inline int length( int cur, int len ) {
	int res = cur;
	while( len > 0 ) {
		res = mul( 10, res );
		len --;
	}
	return res;
}

struct node {
	int len, cur, seven, rem, base_rem;
	bool max;
	int& count() {
		if( max ) 
			return max_count[len][seven][rem][cur][base_rem];
		return _count[len][seven][rem][cur][base_rem];
	}
	int& sum() {
		if( max )
			return max_sum[len][seven][rem][cur][base_rem];
		return _sum[len][seven][rem][cur][base_rem];
	}
	int& pow() {
		if( max ) 
			return max_pow[len][seven][rem][cur][base_rem];
		return _pow[len][seven][rem][cur][base_rem];
	}
	bool& vis() {
		return _vis[len][seven][rem][cur][base_rem];
	}
	void print() {
//		printf( "%d %d %d %d %d %d\n", len, cur, seven, rem, base_rem, max );
//		printf( "%d %d %d\n", count(), sum(), pow() );
	}
};

int dfs( node cur ) {
	if( ( ! cur.max ) && cur.vis() )
		return cur.pow();
	if( cur.len == 0 ) {
		if( cur.seven || cur.rem == 0 || cur.base_rem == 0 ) {
			cur.count() = cur.sum() = cur.pow() = 0;
			return cur.pow();
		}
		cur.count() = 1; cur.sum() = cur.cur; cur.pow() = power( cur.cur );
		return cur.pow();
	}
	int &cur_count = cur.count();
	int &cur_sum = cur.sum();
	int &cur_pow = cur.pow();
	if( cur.max ) 
		cur_count = cur_sum = cur_pow = 0;
	for( int i = 0; i <= ( cur.max? a[cur.len]: 9 ); i ++ ) {
		node nxt = cur;
		nxt.len -= 1; nxt.seven = ( cur.seven || ( i == 7 ) ); nxt.cur = i; nxt.max = ( cur.max && i == a[cur.len] );
		nxt.rem = ( cur.rem * 10 + i ) % 7; nxt.base_rem = ( cur.base_rem + i ) % 7;
		dfs( nxt );
		cur_count = add( cur_count, nxt.count() );
		cur_sum = add( cur_sum, add( mul( length( cur.cur, cur.len ), nxt.count() ), nxt.sum() ) );
		cur_pow = add( cur_pow, add( nxt.pow(), add( mul( nxt.count(), power( length( cur.cur, cur.len ) ) ), 
						mul( mul( 2, length( cur.cur, cur.len ) ), nxt.sum() ) ) ) );
	}
	if( cur.max == false )
		cur.vis() = true;
	cur.print();
	return cur_pow;
}

int sum( long long _a ) {
	if( _a == 0 ) 
		return 0;
	if( _a < 0 )
		return 0;
	max_len = 0;
	while( _a ) { 
		a[ ++ max_len ] = _a % 10;
		_a /= 10;
	}
//	printf( "ans: %d\n", dfs( (node){ max_len, 0, 0, 0, 0, true } ) );
	return dfs( (node){ max_len, 0, 0, 0, 0, true } );
}

int main() {
#ifdef woshiluo
	freopen( "hdu.4507.in", "r", stdin );
	freopen( "hdu.4507.out", "w", stdout );
#endif
	scanf( "%d", &T );
	while( T -- ) {
		scanf( "%lld%lld", &left, &rig );
		if( left == 0 ) 
			printf( "%d\n", ( sum(rig) + mod ) % mod );
		else 
			printf( "%d\n", ( add( sum(rig), - sum( left - 1 ) ) + mod ) % mod );
	}
}

Luogu P3177 [HAOI 2015] 树上染色

题目链接: https://www.luogu.com.cn/problem/P3177

0 说在之前

树形 DP 要么模板题,要么神仙题

这个题就属于不太正常的

1 思路

$f_{i,j}$

其中 $i$ 代表当前节点

$j$ 代表子树中选择 $j$ 个黑点,所能对答案产生的贡献

有了这个思路,后面的东西就是标准的树上背包了

2 Code

#include <cstdio>
#include <cstring>

inline int Min(int a, int b) { return a < b? a : b; }
inline long long Max(long long a, long long b) { return a > b? a : b; }

const int N = 2100;

int n, m;
int size[N];

// Edge Start
struct edge {
    int to, val, next;
} e[N << 1];
int ehead[N], ecnt;

inline void add_edge(int now, int to, int val) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

// DP Start
long long f[N][N];
void dp(int now, int la) {
    size[now] = 1;
    f[now][0] = f[now][1] = 0;
    for(int i = ehead[now]; i; i = e[i].next) {
        if( e[i].to == la )
            continue;
        dp(e[i].to, now);
        size[now] += size[ e[i].to ];
        for(int j = Min(size[now], m); j >= 0; j--) {
            for(int k = 0; k <= Min(size[ e[i].to ], j); k++) {
                if( f[now][ j - k ] == -1 )
                    continue;
                long long val = 1LL * ( 1LL * k * ( m - k ) + 1LL * ( size[ e[i].to ] - k ) * ( n - m - size[ e[i].to ] + k ) ) * e[i].val;
                f[now][j] = Max( f[now][j], f[now][j - k] + f[ e[i].to ][k] + val);
            }
        }
    }
}
// DP End

int main() {
#ifdef woshiluo
    freopen("luogu.3177.in", "r", stdin);
    freopen("luogu.3177.out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    memset(f, -1, sizeof(f));
    dp(1, 0);

    printf("%lld", f[1][m]);
    fclose(stdin);
    fclose(stdout);
}