UOJ Logo NaCl的博客

博客

标签

puts("hello, 2021")

2020-12-31 13:17:53 By NaCl

这个 OJ 的降生也已满三年。

虽万难君未死也,唯一路尔而行之。

只用等比数列求和过掉 #115

2020-12-20 00:32:56 By NaCl

分治题解见此处

显然,若 $a\mod b=c$,则 $ah\mod bh=ch$。

因此先以 $(a-1)m$ 为模数作快速幂,再除以 $(a-1)$ 即可。

#include <stdio.h>
#include <stdlib.h>

int power_mod(int base, long long int exp, int mod)
{
    long long int result = 1, b2 = base;
    while (exp) {
        if (1 & exp) result = result * b2 % mod;
        b2 = b2 * b2 % mod;
        exp >>= 1;
    }
    return (int)result;
}

int main()
{
    int a, m, m1;
    long long int k;
    scanf("%d%lld%d", &a, &k, &m);
    m1 = m * (a - 1);
    printf("%d\n",
        (m - 1 + (m1 - 1 + power_mod(a, 1 + k, m1)) % m1 / (a - 1)) % m);
    return 0;
}

祝愿++

2020-12-09 22:58:23 By NaCl

原文在此

高三选手,文化课加油,请一如既往。

高二选手,再接再厉,请走下去

高一选手,欢迎来到 OI,请坚持。

对于高二选手

请看这里

题解:#373. 赤壁怀古

2020-12-02 21:00:19 By NaCl
不保证最优,若有更优解法请回复告知。

数位动规。

必须承认本题出得不好(我太菜了),因为「子树有序」这条件实在不优雅。

将 $n$ 节点、子树有序的有根树转化为长度为 $2(n-1)$ 的括号序列,问题便相当显豁了。

会了吧?

——

———

————

———

——

设状态 $s_{i,j}$ 代表括号序列的前 $i$ 位、左括号比右括号多 $j$ 个的情况数。当 $j\gt0$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j-1}$;当 $j\lt k-1$ 时,$s_{i,j}$ 可以转移到 $s_{i+1,j+1}$。

初始条件为 $s_{0,0}=1$,答案为 $s_{2(n-1),0}$,效率为 $\Theta(nk)$。

由于是大水题,代码非常好写,就不放标程了。

——故国神游,多情应笑我,早生华发。

各代学弟学妹找我啊

2020-11-19 11:21:35 By NaCl

本人,二代阁员,也基大学新生。

不太了解我离开后 LFYZOI 现状,故希望诸君来找我~

鄙 QQ:1362432220

鄙 邮箱:yaosite@139.com

鄙 博客:http://cn-0xis.gitee.io

请叫我「0xis」或「物灵」,OJ 改不了名所以帐号才是 NaCl。

少年不惧黑夜长 城市慷慨永亮光

2019-11-23 22:44:44 By NaCl

敬逆风的鸢尾花:

标题引自宋佳娴《奉君歌》

可能有人不知道我是谁。我是高三的前阁员 0xis,去年 NOIP 只得到省三。退役后,百炼钢化为绕指柔,似乎有些东西再也回不去了。我从提交记录能刷十页,变得整天昏昏欲睡流着油汗,退役一年使我感到的是害怕,以及「为什么是这样?为什么不能那样?」的迷思。

我想了很久究竟说些什么。今天 18 点多,我不管行色匆匆的同学,独自站在孔子像边,看着图艺楼喑哑,高树伫立,疏影横斜,天空现出凌烟阁的应援色。或许某年某月,在这样的薄暮校园中,破池和巫人曾挽着手经行。

——退役对于您们真的没有什么可怕的。

如果您害怕失去 OI,那么,您还拥有的其实很多。据我观察,您们都深耕在自己的圈子,有着过硬的朋友、精湛的才华以及出众的人格,为旁人所瞩目。人是一面多棱镜,当您在彼岸精进,当您在越来越多广阔的丛林间塑造自我,这也在使 OI 继续发光。

如果您对文化课感到不安,那么,种树最好的时机是现在。高二年级组尽职尽责,讲究全流程管理,至少我们当初没这待遇。此去赓续着 OI 的炬火,电光火石,定将扳回一城反败为胜。

如果您对生活惶惑不解,那么,您失去的并没有那般多。人为考试而学习只是学习的一小部分。当您在其他领域拓殖,某个不为人知的时刻,OI 或许会悄然归来,为您抚去征尘,使您发现世界上的许多美好其实相通。

紫海未暗,天佑凌烟。OI 已是你我不可磨灭的印记。恐慌中,岑寂中,当一息尚存,徘徊踟蹰时,尽管您可能已找不回凌烟阁,但您的心,我们的心,都是一样的。

还有什么问题,请站内私信我吧。

顺颂
时绥

0xis (Chaihang Yiu)

LFYZOI 编年史

2019-03-17 13:38:44 By NaCl

……其时,我的胸中
没有此般凶暴的狂烈。眼下,
我们的人血肉模糊,横躺沙场,倒死在
普里阿摩斯之子赫克托耳手下:宙斯正使他获取光荣。
——《荷马史诗》

待续

本 Online Judge 历史

  • 最早,校内 Online Judge 基于 TJOJ,搭建于内网。
  • 2017 年末改用现网站。
  • 2018 年 2 月 22 日,A_minor 提交了第 1,000 个程序
  • 2018 年 9 月 22 日,cyx 提交了第 10,000 个程序

363 水题题解

2019-02-12 20:16:57 By NaCl

前排接受高一 julao 光环照耀

明明 363 才是最水的…

非常显然的数位 DP,记录两个状态:⑴当前位置;⑵当前异或和。

此时我们发现询问不同的数,可以共用 DP 到的值,因为状态转移与询问的数无关。(否则会 TLE)

#include <cstdio>
#include <cstring>
#include <ctime>
const int KB = 100001;
const int MOD = 1000000007;

char n[KB]; int ca[KB][45]; // n - 读入的数,ca - 存 DP 值
// 因为询问数长度不同,ca 数组只能正着存
// 即 ca[KB - 1] 对应个位,ca[KB - 2] 对应十位…
// 因此下面查询需要一个 nr 代表这一位置

int ss(int cr, int nr, bool lim, int o) {
// cr - 当前位置,nr - 对应 DP 值位置,lim - 是否设限,o - 当前异或和
  int de, cn = n[cr] - '0', re = 0; de = lim? cn: 9;
  if(!n[cr]) return o; if(!lim && ~ca[nr][o]) return ca[nr][o];
  for(int i = 0; i <= de; ++i)
    re = (re + ss(cr + 1, nr + 1, lim && i == cn, o ^ i)) % MOD;
  return lim? re: (ca[nr][o] = re); }

int dp() { scanf("%s", n); return ss(0, KB - strlen(n), 1, 0); }

int main() {
  int t; memset(ca, -1, sizeof ca); scanf("%d", &t); while(t--) {
    int a = dp(), lv = 0, rs; for(int i = 0; n[i]; ++i) lv ^= n[i] - '0';
// 我们用 (从 1 到 N) - (从 1 到 M) 得到 (从 M + 1 到 N)
// 而题目问 (从 M 到 N),故应将 M 的值(lv)加上去
    rs = dp() + lv + MOD - a; printf("%d\n", rs >= MOD? rs - MOD: rs); }
  return 0; }

换言之,也可直接预处理 DP 值

原创题题解索引

2018-09-12 23:18:16 By NaCl

关于高二 T3 的疑问

2018-08-28 17:24:48 By NaCl

为何只有 40 分?

为证明归并排序正确,归并排序已交 #133 通过。

#include <cstdio>
#include <algorithm>
#define F(z, u, v) for(int z = (u); z <= (v); z++)
typedef long long int LINT;
const int MAXN = 1000001, INF = 0x7fffffff;
int n, a[MAXN], ra[MAXN]; LINT re[MAXN], rr[MAXN], ans = 0;

void Mgs(int* ar, LINT* ge, int l, int r) {
 static int tp[MAXN]; int mid = l + r >> 1;
 if(l >= r) return;
 Mgs(ar, ge, l, mid); Mgs(ar, ge, mid + 1, r);
 for(int i = l, j = mid + 1, g = l; g <= r; ) {
  int pi = i <= mid? ar[i]: INF, pj = j <= r? ar[j]: INF;
  if(pi > pj) tp[g++] = pj, ge[j++] += mid - i + 1;
  else tp[g++] = ar[i++]; }
 F(i, l, r) ar[i] = tp[i]; }

int main() {
 scanf("%d", &n);
 F(i, 1, n) { scanf("%d", a + i); ra[n + 1 - i] = ~a[i]; }
 Mgs(a, re, 1, n); Mgs(ra, rr, 1, n);
 F(i, 1, n) ans += re[i] * rr[n + 1 - i];
 printf("%lld", ans); }
共 18 篇博客