数列分段 (100)

给定一个整数数列,数列中连续相同的最长整数序列算成一段,问数列中共有多少段?

输入格式

输入的第一行包含一个整数 n,表示数列中整数的个数。

第二行包含 n 个整数 a1,a2,…,an,表示给定的数列,相邻的整数之间用一个空格分隔。

输出格式

输出一个整数,表示给定的数列有多个段。

数据范围 1≤n≤1000,0≤ai≤1000

输入样例:

8
8 8 8 0 12 12 8 0

输出样例:

5

题目分析

思维题

代码实现

联机算法

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, a[N], cnt;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a[0];
    for(int i = 1; i < n; ++i) {
        cin >> a[i];
        if(a[i] != a[i - 1]) ++cnt;
    }
    cout << cnt + 1;
    return 0;
} 

日期计算 (100)

给定一个年份 y 和一个整数 d,问这一年的第 d 天是几月几日?

注意闰年的 2 月有 29 天。

满足下面条件之一的是闰年:

  • 年份是 4 的整数倍,而且不是 100 的整数倍;
  • 年份是 400 的整数倍。

输入格式

输入的第一行包含一个整数 y,表示年份,年份在 1900 到 2015 之间(包含 1900 和 2015)。

输入的第二行包含一个整数 d,d 在 1 至 365 之间。

输出格式

输出两行,每行一个整数,分别表示答案的月份和日期。

数据范围 1900≤y≤2015, 1≤d≤365

输入样例1:

2015
80

输出样例1:

3
21

输入样例2:

2000
40

输出样例2:

2
9

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
using namespace std;

int y, d;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool loop(int y, int m) {
    if(m != 2) return 0;
    return (y
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> y >> d;
    for (int m = 1; m <= 12; ++m) {
        for(int day = 1; day <= days[m] + loop(y,m); ++day) {
            if(!(--d)) {
                cout << m << '\n' << day;
                return 0;
            }
        }
    }
    return 0;
} 

模板生成系统 (100)

成成最近在搭建一个网站,其中一些页面的部分内容来自数据库中不同的数据记录,但是页面的基本结构是相同的。

例如,对于展示用户信息的页面,当用户为 Tom 时,网页的源代码是

<!DOCTYPE html>
<html>
<head>
<title>User {{ name }}</title>
</head>
<body>
<h1>{{ name }}</h1>
<p>Email: <a href="mailto:{{ email }}">{{ email }}</a></p>
<p>Address: {{ address }}</p>
</body>
</html>

而当用户为 Jerry 时,网页的源代码是

<!DOCTYPE html>
<html>
<head>
<title>User {{ name }}</title>
</head>
<body>
<h1>{{ name }}</h1>
<p>Email: <a href="mailto:{{ email }}">{{ email }}</a></p>
<p>Address: {{ address }}</p>
</body>
</html>

这样的例子在包含动态内容的网站中还有很多。

为了简化生成网页的工作,成成觉得他需要引入一套模板生成系统。

模板是包含特殊标记的文本。

成成用到的模板只包含一种特殊标记,格式为 {{ VAR }},其中 VAR 是一个变量。

该标记在模板生成时会被变量 VAR 的值所替代。

具体的规则如下:

  • 变量名由大小写字母、数字和下划线 _ 构成,且第一个字符不是数字,长度不超过 16 个字符。
  • 变量名是大小写敏感的,Name 和 name 是两个不同的变量。
  • 变量的值是字符串。
  • 如果标记中的变量没有定义,则生成空串,相当于把标记从模板中删除。
  • 模板不递归生成。也就是说,如果变量的值中包含形如 {{ VAR }} 的内容,不再做进一步的替换。

输入格式

输入的第一行包含两个整数 m, n,分别表示模板的行数和模板生成时给出的变量个数。

接下来 m 行,每行是一个字符串,表示模板。

接下来 n 行,每行表示一个变量和它的值,中间用一个空格分隔。值是字符串,用双引号 " 括起来,内容可包含除双引号以外的任意可打印 ASCII 字符(ASCII 码范围 32,33,35−126)。

输出格式

输出包含若干行,表示模板生成的结果。

数据范围 0≤m≤100, 0≤n≤100, 输入的模板每行长度不超过 80 个字符(不包含换行符)。 输入保证模板中所有以 {{ 开始的子串都是合法的标记,开始是两个左大括号和一个空格,然后是变量名,结尾是一个空格和两个右大括号。 输入中所有变量的值字符串长度不超过 100 个字符(不包括双引号)。 保证输入的所有变量的名字各不相同。(同一变量在模板中可能出现多次,参见样例)

输入样例:

11 2
<!DOCTYPE html>
<html>
<head>
<title>User {{ name }}</title>
</head>
<body>
<h1>{{ name }}</h1>
<p>Email: <a href="mailto:{{ email }}">{{ email }}</a></p>
<p>Address: {{ address }}</p>
</body>
</html>
name "David Beckham"
email "david@beckham.com"

输出样例:

<!DOCTYPE html>
<html>
<head>
<title>User David Beckham</title>
</head>
<body>
<h1>David Beckham</h1>
<p>Email: <a href="mailto:david@beckham.com">david@beckham.com</a></p>
<p>Address: </p>
</body>
</html>

题目分析

模拟

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
#include <unordered_map>
using namespace std;
const int N = 110;

int n, m, ne[N][N];
string s;
vector <string> keys, ps;
unordered_map <string, string> mp;
bool check(string& s) {
    int op[4] = {0,0,0,0};
    for(auto& ch : s) {
        if(ch == ' ') ++op[0];
        else if (ch == '{') ++op[1];
        else if (ch == '}') ++op[2];
    }
    return op[0] == op[1] && op[1] == op[2] && op[0] == 2;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin.ignore();
    while(getline(cin,s), n--) {
        ps.push_back(s);
    }
    while(getline(cin, s), m--) {
        int t = 0;
        while(s[t] != ' ') ++t;
        string temp, key = "{{ ", val;
        temp = s.substr(0, t);
        key = key + temp + " }}";
        val = s.substr(t + 2);
        mp[key] = val;
        keys.push_back(key);
    }
    for(auto s : ps) {
        for(int i = 0; i < s.length(); ++i) {
            if(s[i] == '{') {
                int l = i, r = i;
                while(s[r] != '}') ++r;
                ++r;
                string buf = s.substr(l, r - l + 1);
                if(check(buf)) {
                    cout << mp[buf];
                    i = r;    
                }
                else cout << s[i];
            }
            else cout << s[i];
        }
        cout << '\n';
    }
    return 0;
} 

高速公路 (100)

某国有 n 个城市,为了使得城市间的交通更便利,该国国王打算第一阶段先在部分城市之间修一些单向的高速公路。

现在,大臣们帮国王拟了一个修高速公路的计划。

看了计划后,国王发现,有些城市之间可以通过高速公路直接(不经过其他城市)或间接(经过一个或多个其他城市)到达,而有的却不能。

如果城市 A 可以通过高速公路到达城市 B,而且城市 B 也可以通过高速公路到达城市 A,则这两个城市被称为便利城市对。

国王想知道,在大臣们给他的计划中,有多少个便利城市对。

输入格式

输入的第一行包含两个整数 n, m,分别表示城市和单向高速公路的数量。

接下来 m 行,每行两个整数 a, b,表示城市 a 有一条单向的高速公路连向城市 b。

输出格式

输出一行,包含一个整数,表示便利城市对的数量。

数据范围 前 3 前 6 所有评测用例满足 1≤n≤10000, 1≤m≤100000。

输入样例:

5 5
1 2
2 3
3 4
4 2
3 5

输出样例:

3

题目分析

Tarjan

代码实现

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10;

int n, m, idx, h[N], e[M], ne[M], timestamp, ssc_cnt, dfn[N], low[N], id[N], Cnt[N];
stack <int> stk;
bool in_stk[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int p) {
    dfn[p] = low[p] = ++timestamp;
    stk.push(p);
    in_stk[p] = 1;
    for(int i = h[p]; ~i; i = ne[i]) {
        int u = e[i];
        if(!dfn[u]) {
            tarjan(u);
            low[p] = min(low[p], low[u]);
        }
        else if(in_stk[u]) low[p] = min(low[p], dfn[u]);
    }
    if(low[p] == dfn[p]) {
        int t;
        ++ssc_cnt;
        do {
            t = stk.top(); stk.pop();
            in_stk[t] = 0;
            id[t] = ssc_cnt;
            ++Cnt[ssc_cnt];
        }while(t != p);
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m--) {
        int a, b;
        cin >> a >> b;
        add(a,b);
    }
    for(int i = 1; i <= n; ++i) 
        if(!dfn[i]) tarjan(i);
    int ans = 0;
    for(int i = 1; i <= ssc_cnt; ++i) {
        int t = Cnt[i] - 1;
        if(Cnt[i] > 1) ans += t + (t * (t - 1)) / 2 ;
    }
    cout << ans;
    return 0;
} 

最佳文章

小明最近在研究一门新的语言,叫做 Q 语言。

Q 语言单词和文章都可以用且仅用只含有小写英文字母的字符串表示,任何由这些字母组成的字符串也都是一篇合法的 Q 语言文章。

在 Q 语言的所有单词中,小明选出了他认为最重要的 n 个。

使用这些单词,小明可以评价一篇 Q 语言文章的“重要度”。

文章“重要度”的定义为:在该文章中,所有重要的 Q 语言单词出现次数的总和。其中多次出现的单词,不论是否发生包含、重叠等情况,每次出现均计算在内。

例如,假设 n=2,小明选出的单词是 gvagv 和 agva。

在文章 gvagvagvagv 中,gvagv 出现了 3 次,agva 出现了 2 次,因此这篇文章的重要度为 3+2=5。

现在,小明想知道,一篇由 m 个字母组成的 Q 语言文章,重要度最高能达到多少。

输入格式

输入的第一行包含两个整数 n, m,表示小明选出的单词个数和最终文章包含的字母个数。

接下来 n 行,每行包含一个仅由英文小写字母构成的字符串,表示小明选出的这 n 个单词。

输出格式

输出一行一个整数,表示由 m 个字母组成的 Q 语言文章中,重要度最高的文章的重要度。

数据范围 在评测时将使用 10 个评测用例对你的程序进行评测。 设 s 为构成 n 个重要单词字母的总个数,例如在样例中,s=4+7+6=17;a 为构成 n 个重要单词字母的种类数,例如在样例中,共有 3 种字母 a,g,v,因此 a=3。 评测用例 1 和 2 满足 2≤n≤3,1500≤m≤2000,s=40; 评测用例 3 和 4 满足 m=20,2≤a≤3; 评测用例 5、6 和 7 满足 2000≤m≤100000; 评测用例 8 满足 n=2; 所有的评测用例满足 1≤s≤100,1≤m≤10^15,每个单词至少包含 1 个字母,保证单词中仅出现英文小写字母,输入中不含多余字符,不会出现重复的单词。

输入样例:

3 15
agva
agvagva
gvagva

输出样例:

11

题目分析

AC自动机 DP 快速幂


0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status