AT #284 A~F

A:

Description:

​ 给出 $n\ (1 \le n \le 10)$ 个字符串 $s_1,s_2,......s_n$ ，要求倒序输出这些字符串。

​ 此处的倒序指按照 $s_n,s_{n-1},s_{n-2},......s_{2},s_{1}$ 的顺序，单个字符串 $s_i$ 内部不需要倒转。

Solution:

​ 数据结构 (也可以是STL) 的简单应用。

​ 注意到栈的性质：先进后出。所以可以直接实现一个存储 string 类型的栈，然后全部压入再弹出即可。

​ 当然，因为这个数据范围小，所以暴力或者递归乱搞都是可以过的。

Code:

#include <bits/stdc++.h>
using namespace std;
stack<string> stk;
int n;string temp;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> temp,
        stk.push(temp);
    while(!stk.empty())
        cout << stk.top() << "\n",
        stk.pop();
    return 0;
}

B:

Description:

​ 单个测试点内共有 $T\ (1 \le T \le 100)$ 组数据。每组数据有一行一个 $n\ (1 \le n \le 100)$ 和一行 $n$ 个正整数序列 $A = \{A_1,A_2,......A_n\} \ (\forall i \in [1,n],1 \le A_i \le 10^9)$ 。要求分 $T$ 行输出这 $T$ 组数据的 $A$ 中分别由多少个奇数。

Solution:

​ 这个也很简单。因为数据范围小，所以直接输入然后判断即可，不需要啥优化直接 $O(Tn)$ 暴力即可。同时因为不考虑多项之间的联系所以也没必要开数组，用变量 t 接收当前的 $A_i$ ，然后用 res 记录个数即可。注意 res 每次要清空。

Code:

#include <bits/stdc++.h>
using namespace std;
int T,n,t,res;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n;res = 0;
        for(int i = 1;i <= n;i++)
            cin >> t,res += (t % 2);
        cout << res << "\n";
    }
    return 0;
}

C:

Description:

​ 给出一张 $n \ (1 \le n \le 100)$ 个点， $m\ (0 \le m \le \min(2 \times 10^5,\frac{n(n-1)}{2}))$ 条边的无向图，问这个图内共有多少个连通分量。

​ 此处的连通分量定义为：将图 $G$ 划分为 $k$ 个子图，保证这 $k$ 个子图两两之间都没有交集，则称 $G$ 有 $k$ 个连通分量。

Solution:

​ 又是一道数据结构应用。

​ 考虑到没有加减边操作，我们要做的就是利用一个可以静态维护集合状态的数据结构。状态压缩的并查集可以满足此要求。考虑建立一个大小为 $n$ 的并查集，若给出连接 $u,v$ 的点则等同于合并 $u,v$ 所在的集合。单次合并的时间复杂度最高为 $O(\log n)$ ，则总体时间复杂度为 $O(m \log n)$ ，可以通过。

​ 当然，可以进一步优化并查集。若在路径压缩基础上同时使用按轶合并可以做到单次合并 $O(\alpha(n))$ ，更快。

​ 此处的 $\alpha(n)$ 是反阿克曼函数，可以理解为将阿克曼函数的数量级和参数倒过来，即输入数量级输出其参数。基本就是常数。

​ Oi-Wiki严格证明

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,res,p[N];

inline int find(int x)
{
    if(p[x] == x) return x;
    else return p[x] = find(p[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        p[i] = i;
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        cin >> u >> v;
        int x = find(u),y = find(v);
        if(x != y) p[x] = y;
    }
    for(int i = 1;i <= n;i++)
        if(find(i) == i) res++;
    cout << res << "\n";
    return 0;
}

D:

Description:

​ 有 $T\ (1 \le T \le 10)$ 个正整数 $N\ (1 \le N \le 9 \times 10^{18})$，保证所有的 $N$ 均可以被表示成 $p^2q$ 的形式，其中 $p,q$ 均为质数。现在给出 $N_1,N_2,......N_T$ 。对于每个 $N_i$ ，试求 $p_i,q_i$。

Solution:

​ 首先想到的一定是暴力(因为确实没啥好的优化)。作者的数学水平没法用更加高级的做法求出来。那么现在剩下三条路：枚举 $p$ 求 $q$ ，枚举 $q$ 求 $p$ 或直接枚举质数。这三个方法孰优孰劣有眼睛就能看出来，所以选择直接枚举质数。即对于枚举到的质数 $P_i$，若 $N$ 能被其整除，则尝试 $N$ 是否能被 $P_i^2$ 整除。若能则为题目中的 $p$ ，$q = \frac{N}{p^2}$ 可以 $O(1)$ 求出。若不能则为题目中的 $q$ ，$p = \sqrt{\frac{N}{q}}$ 可以 $O(\log \frac{N}{q})$ 求出。若设共有 $cnt$ 个质数，则总体时间复杂度为 $O(cnt + 1)$ 或 $O(cnt + \log \frac{N}{q})$ 。都是线性算法。

​ 接下来分析 $cnt$ 的大小到底在哪个量级。显而易见的是， $p,q$ 最大不会超过 $\sqrt{N}$ ，也就是大约 $3 \times 10^9$ 的级别。但事实上还可以做到更小。若 $p$ 十分接近这个量级边缘，则 $q$ 作为另一个乘数相应的会十分小。那么我们在一开始扫描的时候就能找到。例如 $p \approx 10^{9}$ ，则 $p^2 \approx 10^{18}$ 。若此时 $p^2$ 仍小于 $N$ ，则因为 $N \le 9 \times 10^{18}$ ，所以 $q$ 最大就是 $9$ ，在扫描之初就能被找到。

​ 那么，试着向另一个极端靠拢：试着让 $p,q$ 尽量相等。此时会发现 $p,q \approx \lceil \ \sqrt[3]{N}\ \rceil = 10^6$ 。因为上述算法是线性的，所以 $T$ 组数据最多只有大约 $10^7$ 级别次计算。这个数量级的枚举计算完全可以接受。那么预处理出 $3 \times 10^6$ 级别的质数(用线性筛)，这样虽然一开始费时间，但在对于每个 $N$ 求答案时却能枚举更少的数(因为除法毕竟还是慢)。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
typedef __int128 LL; //一定要注意这个啊！
LL cnt,primes[N];bool st[N];
int T;LL x;

inline void get_P(LL x)
{
    for(LL i = 2;i <= x;i++)
    {
        if(!st[i]) primes[++cnt] = i;
        for(int j = 1;j <= cnt && primes[j] * i <= x;j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
    return ;
}

template<typename T>
inline void INP(T &x)
{
    x = 0;short sign = 1;
    char ch = getchar();
    while(ch < 48 || ch > 57)
        sign = (ch == 45) ? -1 : 1,
        ch = getchar();
    while(ch <= 57 && ch >= 48)
        x = (x<<1) + (x<<3) + ch - '0',
        ch = getchar();
    x *= sign;return ;
}

template<typename T>
inline void OUT(T x)
{
    if(x < 0)
        putchar(45),
        x = -x;
    if(x > 9)
        OUT(x / 10);
    putchar(x % 10 + 48);
}

inline LL sqrt(LL x) //手写整数平方根，可以稳定在 O(log n) 级别
{
    LL l = 0,r = x;
    while(l < r)
    {
        LL mid = (l + r) >> 1;
        if(mid * mid == x)
            return mid;
        else if(mid * mid > x) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

inline void solve()
{
    INP(x); //读入x(实际上就是N)
        for(int i = 1;i <= cnt&&primes[i]<=x;i++) //开始枚举
            if(x % primes[i] == 0) //如果符合整除性质
            {
                LL v = primes[i] * primes[i];
                if(x % v == 0) // case P
                    OUT(primes[i]),putchar(' '),
                    OUT(x / v),putchar('\n');
                else // case Q
                {
                    LL another = sqrt(x/primes[i]);
                    OUT(another),putchar(' '),
                    OUT(primes[i]),putchar('\n');
                }
                return ;//发现有解立即返回
            }
    return ;
}

int main()
{
    INP(T);get_P((LL)3e6+5);
    while(T--)
        solve();
    return 0;
}

E:

Description:

​ 给出一张 $n\ (1 \le n \le 2 \times 10^5)$ 个点， $m \ (0 \le m \le \min(2 \times 10^5,\frac{n(n-1)}{2}))$ 条边的无向图。问以点 $1$ 为源点，共能向外延伸出多少条简单路径(即路径上无环)？记答案为 $cnt$ ，则输出 $\min(cnt,10^6)$ 。

Solution:

​ 不妨先拿第一个样例看看。这个样例共有两个连通分量：点 $1$ 所在的分量是一条 $3$ 个点的链，另一个分量是一个孤点 $4$ 。

​ 样例输出为 $3$ ，共有 $1,1 \to 2,1 \to 2 \to 3$ 这 $3$ 种情况。

​ 那么我们可以发现：若点 $1$ 所在的联通分量为一条链，设链上的点数为 $len$ ，则答案就是 $len$ 。

​ 接着，不妨分析树的情况。请看下图例子，图中的箭头表示遍历顺序：

​ 此时可以发现，树可以被拆成若干条链，然后分别计数即可。你要是真写高级算法我也拦不住，但事实上用一个布尔数组 vis[] 记录每个点在这次链的遍历中是否有经过，保证遍历方向以及遍历过所有点均最多只遍历过一次(不然会有环)即可。

​ 再往下进行讨论：如果是一般的图呢？请看下面例子：

​ 模拟一次就会发现：在每一次遍历时，因为不允许有环的存在，所以不会出现头连尾的情况，也就是图上本身自带的环会在单次递归中被规避。实际上还是枚举下一个点然后增加答案即可。所以使用 dfs 枚举每条链的思路仍成立。其时间复杂度可以写成 (函数调用次数 * 每次调用分支个数) 的形式。因为答案上界为 $10^6$ ，所以如果答案大于 $10^6$ 则无需继续计算，直接输出 $10^6$ 即可。所以最多调用 $10^6$ 次。题目中给出了所有点中最大的度数为 $10$ ，所以最多只会向外扩展 $10$ 次。总体计算次数上界为 $10 \times 10^6 = 10^7$ ，可以稳定通过。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int MAX = 1e6;
int n,m;int e[N<<1],ne[N<<1],h[N],idx;
bool vis[N];int ans = 0;

inline void insert_edge(int u,int v)
{e[idx] = v,ne[idx] = h[u],h[u] = idx++;}

inline void dfs(int u,int fa)
{
    ans++;vis[u] = true;
    if(ans >= MAX) return ;
    for(int i = h[u];~i;i=ne[i])
        if(e[i] != fa && !vis[e[i]])
            dfs(e[i],u);
    vis[u] = false;
    return ;
}

int main()
{
    memset(h,-1,sizeof(h));

    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        insert_edge(u,v);
        insert_edge(v,u);
    }

    dfs(1,1);
    printf("%d\n",min(ans,MAX));
    system("pause");
    return 0;
}

F:

为叙述方便，下文中 ${\rm rev}(s)$ 表示将字符串 $s$ 倒转， $s_{[l,r]}$ 表示 $s$ 从左端点 $l$ 到右端点 $r$ 这一子串(包括左右端点)。

同时，字符串的下标统一从 $1$ 而非 $0$ 开始。即若 $|S| = n$ ，则 $S = \{S_1,S_2,......,S_n \}$ 。

Description:

​ 给出一个长度 $n \ (1 \le n \le 10^6)$ 和一个长为 $2n$ 的字符串 $T$ ，数据保证 $\forall i \in [1,2n],T_i \in [\texttt{‘a’,’z’}]$ 。

​ 要求构造出一个长为 $n$ 的字符串 $s$ 和一个整数 $i$ ，使得 $T = s_{[1,i]} + {\rm rev}(s) + s_{[i+1,n]}$ 。

Solution:

​ 分析题目，首先因为 $0 \le i \le n$ ，所以可以在下标范围 $[1,n]$ 中枚举 $i$ 。

​ 如果当前的 $i$ 满足条件，则其必然满足以下两个结论：

​ 结论一： $T$ 中必有 $T_{[1,i]} + T_{[i+n+1,2n]} = {\rm rev}(T_{[i+1,i+n]})$ 。这个显而易见：根据定义， $T_{[1,i]} + T_{[i+n+1,2n]}$ 就是原串 $S$ 。而 $T_{[i+1,i+n]}$ 就是 ${\rm rev}(S)$ 。所以此二者相等。

​ 结论二： 根据结论一，不难推出 $T_{[i+1,i+n]}$ 的前 $n-i$ 位实际上就是倒转的 $S_{[i+1,n]}$ ，也就是 $T_{[i+n+1,2n]}$ 。进而可以发现 $T_{[i+1,i+n]}$ 的后 $i$ 位，也就是 $T_{[n+1,n+i]}$ 和 $T_{[1,i]}$ 相等。那么可以使用哈希 $O(n)$ 预处理 $T$ 的每个前缀和后缀，然后 $O(n)$ 枚举 $i$ 并进行 $O(1)$ 判定即可。代码中加了一个 $O(n)$ 的 check 。但是因为 C++ 中逻辑与运算具有短路性质(即一方为 $0$ 直接出 $0$ ，所以不会影响时间复杂度。)

Code:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u;
const int N = 2e6 + 10;
const int P = 13331;
int n,len;char T[N];
u f[N],b[N],st[N];

inline u get_frt(int l,int r){return f[r] - f[l - 1] * st[r - l + 1];}
inline u get_bck(int l,int r){return b[l] - b[r + 1] * st[r - l + 1];}

inline bool is_legal(int idx)
{
    string o = "",d = "";
    for(int i = 1;i <= idx;i++)o += T[i];
    for(int i = idx + 1;i <= idx + n;i++)d += T[i];
    for(int i = idx + n + 1;i <= len;i++)o += T[i];
    reverse(d.begin(),d.end());
    return d == o;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);st[0] = 1;
    cin >> n >> T + 1;len = n << 1;
    for(int i = 1;i <= len;i++)
        st[i] = st[i - 1] * P,
        f[i] = f[i - 1] * P + (T[i] - 'a');
    for(int i = len;i >= 1;i--)
        b[i] = b[i + 1] * P + (T[i] - 'a');

    for(int i = 1;i <= n;i++)
    {
        u frt = get_frt(1,i),bck = get_frt(i + n + 1,len);
        u daozhuan = get_bck(i + 1,i + n),ori = frt * st[n - i] + bck;
        if(daozhuan == ori && is_legal(i))
        {
            for(int j = i + n;j > i;j--)
                cout << T[j];
            cout << endl << i << endl;
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}