NOIP2017提高组题解&总结
本篇题解借鉴和参考了洛谷题解区的同学所写的题解以及部分博文，由于未能记录全面，并没能将这些 …
作者： KSkun
DEAREST DROP/田所あずさ 日中罗马音歌词
DEAREST DROP
作词：Q-MHz / 藤本記子 / 結城アイラ
作曲：Q-MHz / 俊龍 / 神田ジョン
歌：田所あずさ
歌词来源：DEAREST DROP（TV动画《末日时在做什么? 有没有空? 可以来拯救吗?》片头曲 / TVアニメ「終末なにしてますか? 忙しいですか？救ってもらっていいですか?」OPテーマ） – 田所あずさ – 单曲 – 网易云音乐
翻译来源：DEAREST DROP（TV动画《末日时在做什么? 有没有空? 可以来拯救吗?》片头曲 / TVアニメ「終末なにしてますか? 忙しいですか？救ってもらっていいですか?」OPテーマ） – 田所あずさ – 单曲 – 网易云音乐
翻译作者：Sylvatic – 用户 – 网易云音乐
信息来源：DEAREST DROP | Bangumi 番组计划
罗马音来源：自制 航空母艦飛龍 – 用户 – 网易云音乐
协力：Google 翻译
どうしたら
Dōshitara
究竟要怎样
あなたに愛を刻めるんだろう？
Anata ni ai o kizamerun darou
才能将这份爱意铭刻在你心上？
知らない
Shiranai
所体会到的
気持ちばかり覚えたよ
Kimochi bakari oboeta yo
尽是陌生的情绪
忘れかたも教えて
Wasure-kata mo oshiete
也请教我如何遗忘
言葉だけじゃなくてさ
Kotoba dake janakute sa
并非仅用语言而已
震える指の温度から
Furueru yubi no ondo kara
还有那颤抖的手指的温度
それは誰の希望？
Sore wa dare no kibō
那又是谁的希望？
私からあふれ出した願いの雫
Watashi kara afure dashita negai no DROP
自我心间满溢而出的心愿点滴
消えても消えても
Kiete mo kiete mo
就算几度消散隐没
生まれてくるけど
Umarete kurukedo
仍旧会不断地涌现
答えなき酷い未来
Kotae naki hidoi mirai
没有答案的残酷未来
何回目の明日が来るのか
Nankaime no ashita ga kuru no ka
将要到来的是第几个明天呢
わからない夜なら
Wakaranai yorunara
若是身处陌生的夜
名前を呼ばれたい
Namae o yoba retai
便想要被人呼唤我的名字
だって胸が痛い
Datte munega itai
因为胸口传来阵阵疼痛
痛くて張り裂けそうだ
Itakute harisake-sōda
好似要撕心裂肺
どうしたら
Dōshitara
究竟要怎样
あなたに愛を刻めるんだろう？
Anata ni ai o kizamerun darou
才能将这份爱意铭刻在你心上？
私がいつか
Watashi ga itsuka
在我终有一天
空に溶け去る前に
Sora ni toke saru mae ni
消逝于这片天空之前
強い想いで
Tsuyoi omoi de
心怀强烈的思念
いまを守りたくなった理由は
Ima o mamoritaku natta riyū wa
想要去守护此时此刻的理由
あなたをもっと見ていたいから
Anata o motto mite itaikara
不过是我想要更长久地守望着你
程良い笑顔なんていらないよ
Hodo yoi egao nante iranai yo
我不需要什么恰到好处的笑容
甘い嘘で隠した
Amai uso de kakushita
甜美谎言所掩盖的伤痛
傷を分かちあえたら
Kizu o wakachi aetara
若是能够并肩承担
嘆き飲みこむ意味がある
Nageki nomikomu imi ga aru
嘴边咽下的叹息也有了意义
そして夢に変われ
Soshite yume ni kaware
而后化作一场幻梦
あなたへと伝えたい誓いの雫
Anata e to tsutaetai chikai no DROP
想要传达给你的誓言的点滴
叶わない叶わない
Kanawanai kanawanai
无法实现这一点
気づいてる
Kidzui teru
虽已有所察觉
だけどね捧げるんだ祈りを
Dakedo ne sasagerun da inori o
但是啊我仍将献上祈祷
永遠じゃない存在でも
Eien janai sonzai demo
即使是无法永恒的存在
確かな光を欲しがる
Tashikana hikari o hoshigaru
也想在命途多舛中
危うい運命だよ
Ayaui unmeida yo
寻求那真切的光芒
もっと一緒にいてよ
Motto issho ni iteyo
想更多地和你在一起
世界が壊れても
Sekai ga kowarete mo
即便世界毁灭
いつだって
Itsu datte
不论何时
こころは愛を止められない
Kokoro wa ai o tomerarenai
爱在心上都是情不自已
あなたはいつも
Anata wa itsumo
你一刻不停
何を探しているの？
Nani o sagashite iru no
是在找寻着什么呢？
暗い闇へと
Kurai yami e to
虽然而今已是
いまは向かうべきだけれど
Ima wa mukaubekidakeredo
面临那无尽黑暗的时刻
それまであなたを側で
Sore made anata o soba de
但在那之前就陪在你身旁吧
見つめていよう
Mitsumete iyou
将目光定格你身上
もしもと言いかけて
Moshimo to ii kakete
如果二字刚说出口
声は風のなか小さくなってく
Koe wa kaze no naka chīsaku natte ku
声音便伴在风中渐行渐弱
すべてを話してよ
Subete o hanashite yo
好想向你倾诉我的所有
そっと抱きしめてあげたいよ
Sotto dakishimete agetai yo
好想默默将你拥入怀抱
なのに流れる時間が示すのは
Nanoni nagareru jikan ga shimesu no wa
但是光阴流转所呈现的
すれ違いながら遠ざかる二人
Surechigainagara tōzakaru futari
却是擦身而过渐行渐远的两人
どうしたら
Dōshitara
究竟要怎样
あなたに愛を刻めるの？
Anata ni ai o kizameru no
才能将这爱铭刻你心上？
いつだって
Itsu datte
不论何时
こころは愛を止められない
Kokoro wa ai o tomerarenai
爱在心上都是情不自已
あなたはいつも
Anata wa itsumo
你一刻不停
何を探しているの？
Nani o sagashite iru no
是在找寻着什么呢？
強い想いで
Tsuyoi omoi de
心怀强烈的思念
いまを守りたくなった理由は
Ima o mamoritaku natta riyū wa
想要去守护此时此刻的理由
あなたをもっと見ていたくて
Anata o motto mite itakute
不过是我想要更长久地守望着你
ああ空に溶け去るまでは
Ā sora ni toke saru made wa
于消逝在远空之前
![[NOIP1999]旅行家的预算 题解](https://ksmeow.moe/wp-content/uploads/2017/10/KS头像预备3-1-533x400.jpg)
归并排序和逆序对问题
归并排序
归并排序是O(nlogn)排序算法（归并、快排、堆排）中最有分治特点的一个。它的核心正如其名“归并”，也就是分治解决子问题并合并子问题。
分析
谈到分治，我们可以对这个问题进行划分：
主问题：使一堆无序的数字变得有序；
子问题：二分数字，使两边分别变得有序；
合并子问题：见下分析。
如何将2个有序的数列合并成1个有序的数列呢？这个时候我们可以把两个数列并排着放，使他们的小端对齐。定义两个指针分别指向两个小端，如下图[3]。
首先我们可以确定的是，两堆数的最小值肯定是两堆数小端的其中一个数，既然如此，我们比较两个小端数并取出最小的。利用上面得到的结论可以推演，每次从小端取最小数，取完为止，这样得到的数列一定是升序的。这样我们就完成了合并子问题的设计。
代码
int arr[1005], tmp[1005];
void msort(int l, int r) {
if(l == r) return;
int m = (l + r) >> 1;
msort(l, m);
msort(m + 1, r);
int i = l, j = m + 1, k = l; // i, j管理arr, k管理tmp
while(i <= m && j <= r) { if(arr[i] > arr[j]) {
tmp[k++] = arr[j++]; // 小的在前
} else {
tmp[k++] = arr[i++];
}
}
// 处理两部分长度不等的情况
while(i <= m) {
tmp[k++] = arr[i++];
}
while(j <= r) {
tmp[k++] = arr[j++];
}
for(int i = l; i <= r; i++) {
arr[i] = tmp[i];
}
}逆序对问题 洛谷P1908
这个问题是这样的：我们有一个数列a1, a2, …, an，现在我们规定满足条件i < j且ai > aj的数对(ai, aj)为该数列的一个逆序对。给定数列{an}，求数列中所有的逆序对数。
分析
这个问题的解决方法有很多，但是我们可以参考归并排序的设计方法，也设计分治的结构：
主问题：得到数列中逆序对的数量
子问题：二分，得到两边各有多少逆序对
合并问题：两边逆序对数加起来并找出跨两边的逆序对数量
好了，现在还剩下的问题是怎么找出跨两边的逆序对数量。我们想起了归并排序两个有序数列的选择方式。如果我们把左边右边并排放，选小端，左边的小端数大于右边的小端数，这意味着右边的小端数与左边小端数和左边比小端数大的那些数都可构成逆序对，这就可以统计跨越两边的逆序对。仔细分析，我们发现右边的每一个数都会只被这样统计一遍，因此不会计重解或漏解。算法的正确性得证。
代码
#include <cstdio>
int arr[40005], tmp[40005];
int msort(int l, int r) {
int cnt = 0;
if(l == r) return 0;
int m = (l + r) >> 1;
cnt += msort(l, m);
cnt += msort(m + 1, r);
int i = l, j = m + 1, k = l; // i, j管理arr, k管理tmp
while(i <= m && j <= r) { if(arr[i] > arr[j]) {
tmp[k++] = arr[j++]; // 小的在前
cnt += m - i + 1;
} else {
tmp[k++] = arr[i++];
}
}
// 处理两部分长度不等的情况
while(i <= m) {
tmp[k++] = arr[i++];
}
while(j <= r) {
tmp[k++] = arr[j++];
}
for(int i = l; i <= r; i++) {
arr[i] = tmp[i];
}
return cnt;
}
int n;
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("%d ", msort(0, n - 1));
return 0;
}以上代码已通过洛谷P1908评测。
