TOP
目录
\(202006-1\) 线性分类器
\(202006-2\) 稀疏向量
\(202006-3\) Markdown渲染器

$202006 – 1$ 线性分类器

\(AC\) 代码：

#include<cstdio>
using namespace std;
const int N = 1000;
typedef long long LL;
struct point
{
    int x,y;
    char type;
}p[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d %c", &p[i].x, &p[i].y, &p[i].type);
    }
    for (int i = 0; i < m; ++i) {
        LL theta0, theta1, theta2;
        scanf("%lld%lld%lld", &theta0, &theta1, &theta2);
        bool flag = true;

        bool t = p[0].type == \'A\' && theta0 + theta1 * p[0].x + theta2 * p[0].y > 0
            || p[0].type == \'B\' && theta0 + theta1 * p[0].x + theta2 * p[0].y < 0;

        for (int j = 0; j < n; ++j) {

            flag = 
            t == (p[j].type == \'A\' && theta0 + theta1 * p[j].x + theta2 * p[j].y > 0
            || p[j].type == \'B\' && theta0 + theta1 * p[j].x + theta2 * p[j].y < 0);

            if (!flag) {
                puts("No");
                break;
            }
        }
        if (flag) puts("Yes");
    }
    return 0;
}

#if 0
    要点：利用 theta0 + theta1 * x + theta2 * y 的正负标记直线两侧。
    样例1:
        9 3
        1 1 A
        1 0 A
        1 -1 A
        2 2 B
        2 3 B
        0 1 A
        3 1 B
        1 3 B
        2 0 A
        0 2 -3
        -3 0 2
        -3 1 1

#endif // 0

$202006-2$ 稀疏向量

题目就是求两个 \(n\) 维向量的内积，并保证

估算出结果最大为 \(\sum_{i=1}^{5\times 10^5} 10^6\times 10^6=5\times 10^{17}\) ，而 \(max(long\text{ }long)\gt 9.2\times 10^{18}\) ，故结果可用 \(long\text{ }long\) 装下。

然后很容易想到，将输入数据根据维度排序或者用 \(map\) 映射，时间复杂度最多不过 \(O((a+b)\,\log\,(a+b))\) ，之后进行累乘只需线性复杂度。

\(AC\) 代码：

#include<cstdio>
#include<map>
using namespace std;
map<int, int> mp;
long long ans = 0;
int main()
{
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);

    int index, value;
    for (int i = 0; i < a; ++i) {
        scanf("%d%d", &index, &value);
        mp[index] = value;
    }

    map<int, int>::iterator it; // 一定要定义在循环体外！
    for (int i = 0; i < b; ++i) {
        scanf("%d%d", &index, &value);
        it = mp.find(index);
        if (it == mp.end()) continue;
        ans += 1LL * value * it->second;
    }
    printf("%lld", ans);
    return 0;
}

#if 0
    样例输入:
        10 3 4
        4 5
        7 -3
        10 1
        1 10
        4 20
        5 30
        7 40

#endif // 0

\(17\) 行的迭代器我第一次定义在函数体内，结果运行超时，真是被自己玩死了。

$202006-3$ Markdown渲染器

不愧是第 \(3\) 题，出场总是如此霸气，一个题硬生生就占了 \(5\) 页，整个第 \(19\) 次认证的 \(1/3\) ！

硬着头皮读完题目，发现其实并没有那么可怕，不就是一个渲染段落和项目列表的模拟嘛，要是我考试的时候也能这么说就好了。

思路

• 统计渲染后的字符数 tot （空行计为 \(w\) 个字符，中间不满 \(w\) 个字符的行需填充），最后向上整除屏幕宽度得到行数 (tot + w - 1) / w 。

• 输入数据不超过 \(20MB\)，即 \(20971520B\) ，可以考虑用 getchar() 读取。

• 变量 stat 记录上一行状态： 空行 、 段落 、项目 。初始化为 空行 。
• 若当前行为 空行
  • 若上一行不为 空行 ，则填充上一行 tot = (tot + w - 1) / w * w
  • 否则不处理
• 若当前行为 “* ” 开头的 项目
  • 填充上一行并在新的一行添加三个字符 tot = (tot + w - 1) / w * w + 3
  • 若上一行为 段落 则增加一个空行
  • 从除行首的 \’*\’ 以外的第一个非空字符开始按照 普通段落 处理。
• 若当前行为 ” ” 开头的 项目
  • 若上一行字符数多于 \(3\) 个且未满一行，则增加一个空格
  • 从第一个非空字符开始按照 普通段落 处理，注意每次换到新的一行需先增加 \(3\) 个字符（空格）
• 若当前行为 段落
  • 若上一行为 项目 ，则填充上一行并增加一个空行 tot = (tot + w - 1) / w * w + w
  • 若上一行为 段落 且字符数未满一行，则增加一个空格。
  • 从第一个非空字符开始按照 普通段落 处理

\(AC\) 代码：

#include<cstdio>

enum{paragraph, space, item = 3} stat = space;
char c;
int w;
long long tot = 0;

char aLine()
{
    int cnt = 0;
    while((c = getchar()) == \' \') ++cnt;
    if (c == \'\n\' || c == EOF) {
        /*当前行为空行*/

        if (stat != space) {
            tot = (tot + w - 1) / w * w;
            stat = space;
            tot += w;
        }
        return c;
    }

    if (cnt == 0 && c == \'*\') {
        c = getchar();
        if (c == \' \') {
            /*当前行为项目*/
            tot = (tot + w - 1) / w * w + 3;
            if (stat == paragraph) tot += w;
            while ((c = getchar()) == \' \');
            stat = item;
        }
        else {
            /*当前行为段落*/
            if (stat == item) {
                tot = (tot + w - 1) / w * w + w;
            }
            else if (tot % w) ++tot;
            tot += 1;
            stat = paragraph;
        }
    }
    else if (cnt >= 2 && stat == item) {
        /*当前行为项目*/
        if (tot % w > 3) ++tot;
    }
    else {
        /*当前行为段落*/
        if (stat == item) {
            tot = (tot + w - 1) / w * w + w;
        }
        else if (tot % w) ++tot;
        stat = paragraph;
    }


    cnt = 0;
    /*非空行剩余字符*/
    while (c != \'\n\' && c != EOF) {
        if (c != \' \') {
            if (tot % w == 0) tot += stat;
            ++tot;
            cnt = 0;
        }
        else if (tot % w) {
            ++tot;
            ++cnt;
        }
        c = getchar();
    }
    tot -= cnt;
    return c;
}

int main()
{
    scanf("%d", &w);

    while((c = getchar()) != \'\n\' && c != EOF);

    while(~aLine()); // 一行行处理
    if (stat == space && tot > w) tot -= w;

    printf("%lld", (tot + w - 1) / w);
    return 0;
}

#if 0
样例1:
10
CSP

CSP is
a real realrealrealrealreal
     competition.


Come   and   join   us



样例2:
10
* CSP

*   CSP is
  * a real
     competition.
*
  * Come!   and   join.
*Tel:
* 12345
*

#endif // 0

像这种大模拟还是得细心呐！