T1[合法名字]

题目描述

仅由大小写英文字母组成且长度不超过10是合法名字

输入描述

输入第一行包含一个正整数$n$，表示名字的数量（$1 \leq n \leq 2000$）
接下来有$n$行，每行有一个由大小写英文字母，数字，下划线组成的字符串，分别表示名字，长度不超过100。

输出描述

输出只有一个整数，表示有效问卷数量。

示例1

样例输入

2
E_DB2C
DC

样例输出

1

算法

(枚举) $O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int n, ret;
string s;

bool check(string s) {
    for (auto x: s)
        if (!isalpha(x))
            return false;
    return true;
}

int main() {
    cin >> n;
    while (n -- ) {
        cin >> s;
        if (check(s) && s.size() <= 10) ret ++ ;
    }
    cout << ret;

    return 0;
}

T2[调整排列]

题目描述

给定一个1到N的排列$P_1$到$P_N$（N为偶数），初始时$P_i = i$（$1 \leq i \leq N$），现在要对排列进行M次操作，每次操作为以下两种中一种：
（1）将排列的第1个数移到末尾；
（2）交换排列的第1个数与第2个数、第3个数与第4个数、…、第N-1个数与第N个数。
求经过这M次操作后得到的排列。

输入描述

第一行包含两个整数N和M，$2 \leq N, M \leq 10^5$。
第二行包含$M$个空格隔开的整数$t_1$到$t_M$，$1 \leq t_i \leq 2$。若$t_i = 1$，则表示第i次操作为操作1；否则第i次操作为操作2。

输出描述

输出N个空格隔开的整数，即经过M次操作后得到的排列。

示例1

样例输入

4 3
1 2 1

样例输出

2 1 4 3

算法

(链表) $O(n)$

1. 奇数和偶数分别存放在两个链表中，两种操作转化为：
   • 将表头插入到尾部
   • 交换链表头部

C++ 代码

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

const int N = 1e5 + 10;

int n, m;
int op[N];

struct Node {
    int val;
    Node* ne;
    Node(int x) : val(x), ne(NULL) {}
};

Node *even = new Node(0), *odd = new Node(0);

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> op[i];

    auto p = odd, q = even;
    for (int i = 1; i < n; i += 2) p->ne = new Node(i), p = p->ne;
    for (int i = 2; i <= n; i += 2) q->ne = new Node(i), q = q->ne;

    auto p_tail = odd->ne, q_tail = even->ne;

    while (p_tail && p_tail->ne) p_tail = p_tail->ne;
    while (q_tail && q_tail->ne) q_tail = q_tail->ne;

    p = odd->ne, q = even->ne;
    for (int i = 0; i < m; i ++ ) {
        if (op[i] == 1) {
            if (p != p_tail) {
                auto t = p->ne;
                p_tail->ne = p;
                p_tail = p;
                p->ne = 0;
                p = t;
            }
        }
        swap(p, q);
        swap(p_tail, q_tail);
    }

    while (q) {
        cout << p->val << ' ' << q->val << ' ';
        p = p->ne, q = q->ne;
    }

    return 0;
}

Tips

40个选择，看代码求结果和代码填空题居多，数据结构，算法，数学
考个试，网站都能搞崩了，真有你的