头像

chen_zhe_Aya

洛谷知名管理员chen_zhe




离线:11分钟前


最近来访(656)
用户头像
RyanMoriarty
用户头像
GhostinLCL
用户头像
1746705086
用户头像
Infmelon
用户头像
Aaron_luomiao
用户头像
扁鹊
用户头像
SUPERDOGE
用户头像
yam
用户头像
BigJoker
用户头像
QWQ___Ralph
用户头像
明太子
用户头像
国伟爸爸
用户头像
greater
用户头像
lzy2008214
用户头像
zrq071211
用户头像
用户头像
werasdxcv345
用户头像
死亡之主
用户头像
KK_St
用户头像
Suzt_Automution

新鲜事 原文

前几天的那一片文章“点赞+私信之后互关”,如果没有关注的给我打一个1,然后我去看一下。 如果你是说谎,取消关注!


活动打卡代码 AcWing 95. 费解的开关

Enjoy Coding!

代码不想sq(上去穿)了,fz(防止)超代码




这是一道我所认为的比较重要的题目(尽管对于很多人来说很简单)。

首先,这是一道很容易识破的并查集裸题(也许我看完题解前不会这么说),按照题目要求我们可以先排个序,把合并操作(题目中数字表示为1,即两个变量相等)放在前面预先执行,再进行判断操作(数字表示为0,即两个变量不相等)。

但是由于题目中x的数量级达到了10^9,随意开一个这样大小的并查集数组,那么MLE以及CE什么的都在前方欢迎您。这里就要用到本蒟蒻不会的比较高级 的离散化(因为只有10^6个操作,不可能$1\sim 10^9$所有的变量都用到了)。

离散化以后一切就比较简单了(都是些基本操作)。

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

int X;
const int N = 1000010;
inline int Get()
{
    scanf ("%d", &X);
    return X;
}

struct node
{
    int x, y, op;
} que[N];
int a[N];
int fa[N];

inline int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline void Union(int x, int y)
{
    int tx = find(x);
    int ty = find(y);
    if (tx != ty)
        fa[ty] = tx;
}

void work()
{
    int tot = 0;
    int n = Get();
    for (int i = 1; i <= n; i ++)
        a[++ tot] = que[i].x = Get(), a[++ tot] = que[i].y = Get(), a[++ tot] = que[i].op = Get();
    sort (a + 1, a + tot + 1);
    int m = unique(a + 1, a + tot + 1) - a - 1;
    for (int i = 1; i <= n; i ++)
    {
        que[i].x = lower_bound(a + 1, a + m + 1, que[i].x) - a;
        que[i].y = lower_bound(a + 1, a + m + 1, que[i].y) - a;
    }
    for (int i = 1; i <= m; i ++)
        fa[i] = i;
    for (int i = 1; i <= n; i ++)
        if (que[i].op == 1)
            Union(que[i].x, que[i].y);
    for (int i = 1; i <= n; i ++)
        if (que[i].op == 0 && find(que[i].x) == find(que[i].y))
        {
            puts("NO");
            return ;
        }
    puts("YES");
}

int main()
{
    // 能鸽善鹉
    int T;
    cin >> T;
    while (T --)
        work();
    return 0;
}

NB




$\mathcal{SOL}$

  • 看到这个题脑子嗡了一下。
  • 请看后面。

我们可以把每一个联通块看做是一个物品,然后就变成了一个简单的 $01$ 背包问题了。

在这里插入图片描述

比如说这个图,我们可以把它看做两个物品,一个物品是 $0, 1, 2, 5$,另外的一个物品是 $3, 4, 6, 7$。然后对这两个物品做 $01$ 背包就可以了。

如何判断联通快?我们可以使用并查集,通过“找父亲”这个操作来记录联通块以及联通块的价值。

#include <bits/stdc++.h>
#define I_AKIOI ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;

int p[1000010];
int v[1000010], w[1000010];
int dp[1000010];

namespace IAKIOI
{
    int find(int x)  // 并查集
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void main()
    {
        I_AKIOI;
        int n, m;
        cin >> n >> m;
        int vol;
        cin >> vol;
        for (int i = 1; i <= n; i ++)
            p[i] = i;
        for (int i = 1; i <= n; i ++)
            cin >> v[i] >> w[i];
        while (m --)
        {
            int a, b;
            cin >> a >> b;
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                v[pb] += v[pa];
                w[pb] += w[pa];
                p[pa] = pb;
            }
        }
        for (int i = 1; i <= n; i ++)
            if (p[i] == i)
                for (int j = vol; j >= v[i]; j --)
                    dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        cout << dp[vol];
        exit(0);
    }
}

signed main()
{
    IAKIOI::main();
}




$\mathcal{SOL}$

  • 看到这个题脑子嗡了一下。

  • 请看后面。

我们可以把图中的每一个点看做图当中的点,把图中的每一个边看做图中的边。当我们发现图中出现环的时候,就等于是这两个点在连边之前,就已经在同一个联通块当中了。

所以说每一步是否会形成环,就等价于是说这两个点在连边之前有没有在集合里。如果已经出现过了,就代表会形成环,否则就不会形成环。

这样,我们就可以使用路径压缩的并查集来判重了。

据说有人想用 spfa 来判环。。。spfa 不是判负环的吗?

时间复杂度 $\mathcal O(n+m)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 40010;
int n, m;
int p[N];

inline int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

inline int Get(int x, int y)
{
    return x * n + y;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n * n; i ++)
        p[i] = i;
    long long res = 0;
    for (int i = 1; i <= m; i ++)
    {
        int a, b;
        char d;
        cin >> a >> b >> d;
        int x = a, y = b;
        x --;
        y --;
        a = Get(x, y);
        if (d == 'D')
            b = Get(x + 1, y);
        else
            b = Get(x, y + 1);
        int pa = find(a);
        int pb = find(b);
        if (pa == pb)
        {
            res = i;
            break;
        }
        p[pa] = pb;
    }
    if (res)
        cout << res;
    else
        cout << "draw";
    return 0;
}



新鲜事 原文

@yxc



好吧,第一篇一题一解,求点赞

$\mathcal{SOL}$

  • 看到这个题脑子嗡了一下。
  • 请看后面。

难题:如何把所有可行的方案一个不漏的枚举出来,然后在上述条件满足的情况下尽量不枚举错误的情况,不重复枚举情况。(剪枝要领)

很明显是一个搜索题。但是这一个题如果枚举所有的方案是 $9^{81}$ 种情况,跑到世界末日也跑不完($100$ 年之后的计算机有可能能跑完),所以这一个题我们需要使用剪枝来优化搜索 dfs or bfs?

我们输入的时候,是一个没有填完的数独。

然后每一个点填哪一个数,是有很多种选择的。

在搜索的时候,我们可以先随意选择一个空格子,枚举这一个格子可以填哪些数字,在这个时候我们可以先写一个可行性剪枝,也就是说,我们先看一下这一个格子填在这里,是不是在所在的行,所在的列,所在的宫里都没有出现过。

比方说,后面的这一个格子是可以填 $2$,$4$,$5$,$9$ 的,那么我们填完这些数之后,继续做类似的操作,随意选择一个空格子,枚举这一个空格子可以填哪一些数字,每一种枚举方案都是一个分支。

那么什么时候终止呢?当这一个数独都填完之后,我们将计数器自增 $1$,就可以回溯了。

这样就写出了一个基本的 dfs 框架,但是这样会 $\color{darkblue}\text{TLE}$。

最优化剪枝:我们可以随意选择一个空格子。假设我们枚举到了两个格子,有一个格子有 $9$ 种填法,有一个格子有两种填法,那么我们应该先去选择填法较少的那一个格子。

所以现在我们已经不在是一开始随便选择一个空格子了,进而优化到了选择一个填法较少的格子。

当然,这是一个贪心的思想,我们是无法知道选择哪一个格子是最好的的。如果我们现在有一个格子有 $6$ 种选择方案,后续都有 $5$ 种继续选择的余地。然后另外一个格子有 $8$ 中选择方案,后续都有 $3$ 种继续选择的余地。这一个时候是应该选择 $8\times 3$ 的那一种方案的,但是对于这一个剪枝,他会选择 $6\times 5$ 的那一种方案。这样,这一个剪枝的效果就不一定是正确的了。

位运算优化:在这一个问题里,位运算可以快速的帮助我们去判断一个行,列,宫里是否存在一个和它相同的数。

与运算(&),对于每一个二进制位,同为 $1$ 才为 $1$,否则为 $0$。

或运算(|),对于每一个二进制位,同为 $0$ 才为 $0$,否则为 $1$。

异或运算(^),对于每一个二进制位,相同为 $0$,不同为 $1$。

左移运算(<<),$x\ \text{<<}\ y = x\times 2^y$。

右移运算(>>),$x\ \text{<<}\ y = \lfloor\frac{x}{2^y}\rfloor$。

常数为 $\frac{1}{8\times \text{sizeof}(\text{类型})}$。

在我们枚举 $3$,$5$,$9$ 这些数的时候,可以使用循环来枚举,常数为 $\frac{1}{4}\times \text{sizeof}(\text{类型})$。也可以使用常数为 $\frac{1}{8\times \text{sizeof}(\text{类型})}\times \text{二进制表示中}1\text{的个数}$ 的 lowbit 运算来枚举。$\text{lowbit}(x)=x\text{\&}\;\text{-}x$,代表取 $x$ 二进制表示中从后往前第一个 $1$ 的二进制中的位置。

然后 $x\&\;(x-1)$ 可以删除最末尾的那一个 $1$,这样我们就可以快速找到哪一些位置不能用了!位运算大法真好用。

这个就是这一个题目的三个优化方式:搜索位置优化,可行性剪枝,位运算优化。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if (!cnt) return true;

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }

    return 0;
}




#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ios>
#include <locale>
#include <clocale>
#include <cassert>
#include <cstdarg>
#include <cstddef>
#include <ctime>
#include <cctype>
#include <limits>
#include <climits>
#include <cfloat>
#include <cerrno>
#include <cmath>
#include <cstalign>
#include <istream>
#include <ostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <list>
#include <initalizer_list>
#include <queue>
#include <memory.h>
#include <malloc.h>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <bitset>
#include <atomic>
#include <valarray>
#include <cwchar>
#include <chrono>
#include <cfenv>
#include <algorithm>
#include <regex>
#include <tuple>
#include <utility>

#include <bits/c++io.h>
#include <bits/stdc++.h>
#include <bits/move.h>
#include <bits/stdtr1c++.h>
#include <hash_map>
#include <backward/hash_map.h>
#include <hash_set>
#include <backward/hash_set.h>


活动打卡代码 AcWing 3124. BSGS

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

define int long long

using namespace std;

int ksc(int x, int y,int z)
{
if(! y) return 0;
int ans = ksc(x, y >> 1, z);
ans = (ans + ans) % z;
if(y & 1) ans = (ans + x) % z;
return ans;
}

int ksm(int x, int y, int z)
{
if(! y) return 1;
int ans = ksm(x, y >> 1, z);
ans = ksc(ans, ans, z);
if(y & 1) ans = ksc(ans, x, z);
return ans;
}

int solve(int a, int b, int p)
{
int s = (int) (sqrt(p) + 0.01); // 代表每一行有几个数
set [HTML_REMOVED] se;
int ans = 1; // s^0
for(int i = 0; i < s; i)
{
se.insert(ans);
ans = 1LL * ans * a % p;
}
ans = ksm(ans, p-2, p);
int c = b;
for(int i = 0; i < p - 1; i += s)
{
if(se.count(c) != 0)
{
int v = ksm(a, i, p);
while(v != b)
{
v = 1LL * v * a % p;
i
;
}
return i;
}
c = 1LL * c * ans % p;
}
return -1;
}

main()
{
int p, b, n;
cin >> p >> b >> n;
int an = solve(b, n, p);
if(~ an) cout << solve(b, n, p) << endl;
else cout << “No Solution” << endl;
return 0;
}



活动打卡代码 AcWing 4073. 找规律输出

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int main()
{
int n;
cin >> n;
int m = n - 1;
for (int i = 1; i <= m; i ++)
{
if (i & 1) printf (“I hate that “);
else printf (“I love that “);
}
if (n & 1) printf (“I hate it “);
else printf (“I love it “);
return 0;
}