月度归档: 2017年12月

secret base ~君がくれたもの~/茅野愛衣等 日中罗马音歌词

secret base ~君がくれたもの~/茅野愛衣等 日中罗马音歌词

secret base ~君がくれたもの~

作词:町田紀彦
作曲:町田紀彦
歌:茅野愛衣 / 戸松遥 / 早見沙織

下载Word格式文档(.docx)

歌词来源:secret base ~君がくれたもの~ (10 years after Ver.)(TV动画《我们仍未知道那天所看见的花的名字》片尾曲) – 茅野愛衣/戸松遥/早見沙織 – 单曲 – 网易云音乐
翻译来源:secret base ~君がくれたもの~ (10 years after Ver.)(TV动画《我们仍未知道那天所看见的花的名字》片尾曲) – 茅野愛衣/戸松遥/早見沙織 – 单曲 – 网易云音乐
翻译作者:sSkirt – 用户 – 网易云音乐
信息来源:secret base ~君がくれたもの~ | Bangumi 番组计划
罗马音来源:自制 航空母艦飛龍 – 用户 – 网易云音乐
协力:Google 翻译

君と夏の終わり 将来の夢
Kimi to natsunoowari shōrai no yume
与你在夏末约定 将来的梦想
大きな希望 忘れない
Ōkina kibō wasurenai
远大的希望 别忘记
10年後の8月
Jūnengo no hachigatsu
十年后的八月
また出会えるのを 信じて
Mata deaeru no o shinjite
我相信我们还能再相遇
最高の思い出を…
Saikō no omoide o
共创最美好的回忆…

出会いは ふっとした 瞬間 帰り道の交差点で
Deai wa futto shita shunkan kaerimichi no kōsaten de
相识 是在那麼不经意的瞬间 我在回家途中的十字路口
声をかけてくれたね 「一緒に帰ろう」
Koe o kakete kureta ne issho ni kaerou
听见你的一声『一起回家吧』
僕は 照れくさそうに カバンで顔を隠しながら
Boku wa terekusa-sō ni kaban de kao o kakushinagara
我当时有点尴尬 还拿书包遮著脸
本当は とても とても 嬉しかったよ
Hontōwa totemo totemo ureshikatta yo
其实我心里好高兴 真的好高兴

あぁ 花火が夜空 きれいに咲いて ちょっとセツナク
A~a hanabi ga yozora kirei ni saite chotto setsunaku
啊 烟火在夜空中灿烂盛开 几许伤感
あぁ 風が時間とともに 流れる
A~a kaze ga jikan to tomoni nagareru
啊 风和时间一起飘过
嬉しくって 楽しくって 冒険も いろいろしたね
Ureshikutte tanoshikutte bōken mo iroiro shita ne
很高兴 很愉快 曾到处冒险
二人の 秘密の 基地の中
Futari no himitsu no kichi no naka
就在我们的秘密基地中

君と夏の終わり 将来の夢 大きな希望 忘れない
Kimi to natsunoowari shōrai no yume ōkina kibō wasurenai
与你在夏末约定 将来的梦想 远大的希望 别忘记
10年後の8月 また出会えるのを 信じて
Jūnengo no hachigatsu mata deaeru no o shinjite
我相信十年后的八月 我们还能再相遇
君が最後まで 心から 「ありがとう」叫んでいたこと
Kimi ga saigomade kokoro kara arigatō sakende ita koto
你最后一直在心底呼喊著『谢谢你』
知っていたよ
Shitteita yo
我是知道的
涙をこらえて 笑顔でさようなら せつないよね
Namida o koraete egao de sayōnara setsunai yo ne
很难过呢 强忍著泪水笑著说再见
最高の思い出を…
Saikō no omoide o
那一段最美好的回忆

あぁ 夏休みも あと少しで 終っちゃうから
A~a natsuyasumi mo atosukoshi de owatchaukara
啊 暑假就快要过完了
あぁ 太陽と月 仲良くして
A~a taiyō to tsuki nakayoku shite
啊 太阳和月亮 默契十足
悲しくって 寂しくって 喧嘩も いろいろしたね
Kanashikutte sabishikutte kenka mo iroiro shita ne
想来令人悲伤 或许有些寂寥 我们也多有争吵
二人の 秘密の 基地の中
Futari no himitsu no kichi no naka
就在我们的秘密基地中

君が最後まで 心から 「ありがとう」叫んでいたこと
Kimi ga saigomade kokoro kara arigatō sakende ita koto
你最后一直在心底呼喊著『谢谢你』
知っていたよ
Shitteita yo
我是知道的
涙をこらえて 笑顔でさようなら せつないよね
Namida o koraete egao de sayōnara setsunai yo ne
很难过呢 强忍著泪水笑著说再见
最高の思い出を…
Saikō no omoide o
那一段最美好的回忆

突然の 転校で どうしようもなく
Totsuzen no tenkō de dō shiyō mo naku
你突然要转学 你我都无可奈何
手紙 書くよ 電話もするよ 忘れないでね 僕のことを
Tegami kaku yo denwa mo suru yo wasurenaidene boku no koto o
我会写信给你 也会打电话给你 千万别忘记我的事情
いつまでも 二人の 基地の中
Itsu made mo futari no kichi no naka
无论什么时候 那段在秘密基地中的日子

君と夏の終わり ずっと話して
Kimi to natsunoowari zutto hanashite
与你在夏末 聊了那麼多
夕日を見てから星を眺め
Yūhi o mitekara hoshi o nagame
从黄昏到繁星点点
君の頬を 流れた涙は ずっと忘れない
Kimi no hoho o nagareta namida wa zuttowasurenai
泪水流过你的双颊 我永远不会忘记
君が最後まで 大きく手を振ってくれたこと
Kimi ga saigomade ōkiku te o futte kureta koto
直到最后 你紧紧握住我的手 这感觉也将长在我心中
きっと忘れない
Kittowasurenai
一定不会忘记的
だから こうして 夢の中で ずっと永遠に…
Dakara kōshite yumenonakade zutto eien ni
就这样 让我们永远在梦中相会吧
君と夏の終わり 将来の夢 大きな希望 忘れない
Kimi to natsunoowari shōrai no yume ōkina kibō wasurenai
与你在夏末约定 将来的梦想 远大的希望 别忘记
10年後の8月 また出会えるのを 信じて
Jūnengo no hachigatsu mata deaeru no o shinjite
我相信十年后的八月 我们还能再相遇
君が最後まで 心から 「ありがとう」叫んでいたこと
Kimi ga saigomade kokoro kara arigatō sakende ita koto
你最后一直在心底呼喊著『谢谢你』
知っていたよ
Shitteita yo
我是知道的
涙をこらえて 笑顔でさようなら せつないよね
Namida o koraete egao de sayōnara setsunai yo ne
很难过呢 强忍著泪水笑著说再见
最高の思い出を…
Saikō no omoide o
那一段最美好的回忆
最高の思い出を…
Saikō no omoide o
那一段最美好的回忆

二分图匹配的一种算法:匈牙利算法

二分图匹配的一种算法:匈牙利算法

这里不介绍算法,只提供模板代码。所有代码基于【P3386】【模板】二分图匹配 – 洛谷一题。

匈牙利算法

// Code by KSkun, 2017/12
#include <cstdio>
#include <cstring>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
};

io ip;

#define read ip.read 

std::vector<int> vec[2005]; 

int n, m, e;
bool vis[2005];
int match[2005];

inline bool dfs(int u) {
    for(int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if(!vis[v]) {
            vis[v] = true;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
} 

inline int hungarian() {
    int ans = 0;
    memset(match, -1, sizeof match);
    for(int i = 1; i <= n; i++) {
        if(match[i] == -1) {
            memset(vis, 0, sizeof vis);
            if(dfs(i)) ans++;
        }
    }
    return ans;
}

int ut, vt;

int main() {
    n = read();
    m = read();
    e = read();
    for(int i = 0; i < e; i++) {
        ut = read();
        vt = read();
        if(ut > n || vt > m) continue;
        vec[ut].push_back(n + vt);
        vec[n + vt].push_back(ut);
    }
    printf("%d", hungarian());
    return 0;
}
郧阳中学12/3周考题解

郧阳中学12/3周考题解

这周周考被基础算法虐翻了。%%%wxgdalao

命题人

wxg

题目列表

赛题 #A: zcr搞破坏 | 贪心
赛题 #B: zcr爱吃鸡2 | 离散化,二分答案,枚举,模拟
赛题 #C: zcr解谜题 | DP,最大子矩阵

zcr搞破坏

回到列表

一句话题意

给出一个无向图,要求删掉图上的所有点。每一次删点的消耗是所有跟该点相连的所有未删除点的点权和。分别求最大权删法和次小权删法的消耗和。保证数据中无自环,且两点间最多有1条连边。

解法

100% 1 \leq n,\ m,\ a_i \leq 10^6

本题考察贪心思想。
试想对于边 (u, v) ,其中必然会有一个点会被加入最终答案。得到此性质后,考虑如何求最大权和最小权。对于求最大权的情况,我们需要把边中权值较大的点加入答案,而删除较小的点。
正确性的证明方面,我们应该考虑上面这个操作的完整形式。对于求最大权的情况,完整的操作应当是先对边以其中的较大权点的权值进行降序排序,再以该顺序删除每边中较大权的点。在这个过程中,大权点一定比小权点先被删除,因此能够保证求出答案的最优性。由于该操作要对每一条边进行,排序自然就没有必要,因此才有了上面的那种操作。
最小权的操作类比于最大权的操作。
关于求次小权,次小权一定存在于将最优删点顺序中相邻两点调换后的顺序的答案中,因此我们枚举调换的是哪两个点。考虑调换后对答案产生的影响,由于相邻两点的调换不会影响这两点之前、之后序列的单调性,因此只有两点间的连边会对答案造成影响。由于最多只可能有一条这样的边,我们检查是否有边,若无边则次小权等于最小权(无边对答案无影响),否则维护两点权值差的绝对值(即对答案产生的影响),次小权即是最小权加上前面影响的最小值。
总复杂度 O(nlogn)

代码

// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

int n, m, kase, a[1000005], order[1000005], ut, vt;
long long resmax = 0, resmin = 0;
std::vector<int> vec[1000005];

inline bool cmp(int u, int v) {
    return a[u] < a[v];
}

int main() {
    n = read();
    m = read();
    kase = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        if(kase == 2) order[i] = i;
    }
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        resmax += std::max(a[ut], a[vt]);
        if(kase == 2) {
            vec[ut].push_back(vt);
            vec[vt].push_back(ut);
            resmin += std::min(a[ut], a[vt]);
        }
    }
    printf("%lld ", resmax);
    if(kase == 1) {
        return 0;
    }
    std::sort(order + 1, order + n + 1, cmp);
    long long minn = 1e15;
    for(int i = 1; i < n; i++) {
        int u = order[i];
        bool success = false;
        for(int j = 0; j < vec[u].size(); j++) {
            int v = vec[u][j];
            if(v == order[i + 1]) {
                success = true;
                break;
            } 
        }
        minn = std::min(minn, 0ll + a[order[i + 1]] - a[u]);
        if(!success) {
            minn = 0;
            break;
        }
    }
    printf("%lld", resmin + minn);
    return 0;
}

zcr爱吃鸡2

回到列表

一句话题意

给出一些点,求能够包含其中C个点的最小正方形边长。

解法

100% n \leq 1000

本题考察二分答案和枚举。
代码中,check()函数用于枚举行,check1()函数用于枚举列。
二分答案确定正方形边长的取值。然后枚举可能的正方形并且检验即可。
总复杂度O(n^2logn)

代码

// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

std::vector<std::pair<int, int> > points; 
std::vector<int> tmp;
int c, n, xt, yt;

inline bool check1(int l, int r, int p) {
    // 枚举列
    if(r - l + 1 < c) return false;
    tmp.clear();
    for(int i = l; i <= r; i++) {
        tmp.push_back(points[i].second);
    }
    sort(tmp.begin(), tmp.end());
    for(int i = c - 1; i < tmp.size(); i++) {
        if(tmp[i] - tmp[i - c + 1] <= p) return true;
    }
    return false;
} 

inline bool check(int p) {
    // 枚举行
    int lastp = 0;
    for(int i = 0; i < n; i++) {
        if(points[i].first - points[lastp].first > p) {
            //printf("i %d lastp %d\n", points[i].first, points[lastp].first);
            if(check1(lastp, i - 1, p)) return true;
            while(points[i].first - points[lastp].first > p) lastp++;
        }
    } 
    if(check1(lastp, n - 1, p)) return true;
    return false;
}

int main() {
    c = read();
    n = read();
    for(int i = 0; i < n; i++) {
        xt = read();
        yt = read();
        points.push_back(std::make_pair(xt, yt));
    }
    std::sort(points.begin(), points.end());
    int l = 0, r = 10005, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        //printf("mid %d\n", mid);
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%d", r + 1);
    return 0;
}

感想

本题中有一些暴力技巧降低复杂度,可以学习。

zcr解谜题

回到列表

一句话题意

给出一个矩阵,求最大子矩形。其中,你有一次机会把任何数字改成给定值。

解法

80% n, m \leq 100

显然我们需要更改的只有可能是选中的矩形的最小值。
最小子矩形DP+预处理最小值。
总复杂度O(n^4)

100% n, m \leq 300

考虑使用DP来递推“是否修改数字”这一状态。
dp[k][0/1]表示第k行未修改过(0)/修改过(1)数字的结果,状态转移方程如下
\begin{array}{l} dp[k][0] = max\{dp[k-1][0], 0\} + sum[k] \\ dp[k][1] = max\{dp[k-1][1], dp[k-1][0] + P - min[k]\} + sum[k] \end{array}
其中sum[k]代表当前选中的左右边界中第k行的和,min[k]代表边界中第k行的最小值。
答案在每个dp状态中,所以完成一次转移就要更新答案。
我们枚举矩形的左右边界,每一次枚举进行DP,即可得到总答案。
其实上述DP方法应该说是最大子矩形DP的一种变形,基本思路是一致的。

标程 by wxg

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,p,a[305][305],sum[305],qz[305][305],minn[305],dp[305][2],ans;
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j],qz[i][j]=qz[i][j-1]+a[i][j];
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        minn[j]=a[j][i];
        for(int j=i;j<=m;j++)
        {
            for(int k=1;k<=n;k++)
            {
                minn[k]=min(minn[k],a[k][j]);
                sum[k]=qz[k][j]-qz[k][i-1];
            }
            dp[0][0]=0,dp[0][1]=-0x3f3f3f3f;
            for(int k=1;k<=n;k++)
            {
                dp[k][0]=max(dp[k-1][0],0)+sum[k];
                dp[k][1]=max(dp[k-1][1]+sum[k],max(dp[k-1][0],0)+sum[k]-minn[k]+p);
            }
            for(int k=1;k<n;k++) ans=max(ans,max(dp[k][0],dp[k][1]));
            if(i==1&&j==m)
            {
                ans=max(ans,dp[n][1]);
                int cnt=0;
                for(int k=n;k>1;k--)
                cnt+=sum[k],ans=max(ans,cnt);
            }
            else ans=max(ans,max(dp[n][0],dp[n][1]));
        }
    }
    cout<<ans<<endl;
    return 0;
}

感想

本题是最大子矩形的一个变种,简单DP,有一些思维量。写的时候才发现我连最大子矩形都忘完了,药丸。