头像

WangJY

$$\LARGE{封禁家族,Py家族}$$目前在洛谷上活动,有事可以找我的洛谷号 $\href{https://www.luogu.com.cn/user/714562}{blue\_ice}$




离线:1天前


最近来访(1717)
用户头像
垫底抽風
用户头像
Sufferingcreatinglife
用户头像
南街戏子
用户头像
人间过客_追梦人
用户头像
多次拒绝刘亦菲
用户头像
HeXing
用户头像
2580000
用户头像
Linclon
用户头像
CharlesLC
用户头像
handsomepyp
用户头像
太雪菜
用户头像
zz哲
用户头像
天道酬薪
用户头像
Finn2009
用户头像
stOtue
用户头像
浅陌-夜未央
用户头像
cc1号
用户头像
米兰的小铁匠12
用户头像
来时山有雪
用户头像
guo_0

活动打卡代码 AcWing 312. 乌龟棋

WangJY
3天前
#include <iostream>

using namespace std;

const int N = 360, M = 45, C = 6;

int n, m;
int a[N], cnt[C];
int f[M][M][M][M];

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) cin >> a[i];

    while (m -- )
    {
        int b;
        cin >> b, cnt[b] ++ ;
    }

    f[0][0][0][0] = a[0];

    for (int i = 0; i <= cnt[1]; i ++ )
        for (int j = 0; j <= cnt[2]; j ++ )
            for (int k = 0; k <= cnt[3]; k ++ )
                for (int l = 0; l <= cnt[4]; l ++ )
                {
                    int step = i + (j << 1) + (k << 1) + k + (l << 2);

                    if (!step) continue;

                    int &x = f[i][j][k][l];
                    if (i) x = max(x, f[i - 1][j][k][l]);
                    if (j) x = max(x, f[i][j - 1][k][l]);
                    if (k) x = max(x, f[i][j][k - 1][l]);
                    if (l) x = max(x, f[i][j][k][l - 1]);

                    x += a[step];
                }

    cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];

    return 0;
}



WangJY
8天前

题目描述

给定一个非负整数 $a$,请你计算方程 $a-(a \oplus x)-x=0$ 的非负整数解的数量。

其中 $\oplus$ 指按位异或。

输入格式

第一行包含整数 $T$,表示共有 $T$ 组测试数据。

每组数据占一行,包含一个非负整数 $a$。

输出格式

每组数据输出一行结果,一个整数,表示方程的非负整数解的数量。

可以证明方程的非负整数解数量总是有限的。

数据范围

前 $3$ 个测试点满足 $1 \le T \le 3$。
所有测试点满足 $1 \le T \le 1000$,$0 \le a \le 2^{30}-1$。

输入样例:

3
0
2
1073741823

输出样例:

1
2
1073741824

算法

(数学) $O(\log a)$

重新排列方程,得以下形式:$a-x=a \oplus x$。
考虑 $a$ 在二进制表示下的第 $i$ 位 $a_i$:
如果 $a_i=0$,则 $x$ 的第 $i$ 位 $x_i$ 只能是 $0$;
否则,$x_i$ 既可以是 $0$,又可以是 $1$。
由上可知,答案为 $2^{a\ 在二进制表示下\ 1\ 的个数}$

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int a;
        cin >> a, cout << (1 << __builtin_popcount(a)) << '\n'; // __builtin_popcount(a) 表示 a 在二进制表示下 1 的个数
    }

    return 0;
}


新鲜事 原文

WangJY
8天前
AK 周赛!(话说好像这次周赛好氵啊)


分享 快读模板

WangJY
11天前

更好的阅读体验
其实是在 @Register_int 的快读模板上修改了一点。

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define INPUT_OPTIMIZE
#define OUTPUT_OPTIMIZE

namespace IO
{
#ifdef INPUT_OPTIMIZE
    #define IMAX 1000000    
    static char ibuf[IMAX], *p1 = ibuf, *p2 = ibuf;
    #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, IMAX, stdin), p1 == p2) ? EOF : *p1 ++ )
#endif
#ifdef OUTPUT_OPTIMIZE
    #define OMAX 1000000
    static char obuf[OMAX], *p = obuf;
    #define flush() fwrite(obuf, 1, p - obuf, stdout), p = obuf;
    inline void putchar(char x) 
    {
        if (p - obuf == OMAX) flush();
        *p ++ = x;
    }
#else
    #define flush() 0
#endif
    struct Flusher
    {
        ~Flusher()
        {
            flush();
        }
    }flusher;
    inline bool read(char *t)
    {
        memset(t, 0, sizeof t);
        char *p = t, c = getchar();
        while (isspace(c) && c ^ EOF) c = getchar();
        while (!isspace(c) && c ^ EOF) *p ++ = c, c = getchar();
        return c == EOF;
    }
    template<class T> inline bool read(T &t)
    {
        t = 0; char c = getchar(); bool f = true;
        while (isspace(c) && c ^ EOF) c = getchar(); 
        if (c == '-') f = false, c = getchar();
        while (isdigit(c) && c ^ EOF) t = (t << 3) + (t << 1) + (c ^ 48), c = getchar();
        t *= f ? 1 : -1;
        return c == EOF;
    }
    template<class T, class ...Args> inline bool read(T &t, Args &...args)
    {
        return read(t) ? true : read(args...);
    }
    inline void write(const char* s)
    {
        int l = strlen(s);
        for (int i = 0; i < l; i ++ ) putchar(s[i]);
    }
    template<class T> inline void write(T x)
    {
        if (x < 0) putchar('-'), x = -x;
        if (!x) return putchar('0'), void();
        static char t[40], p = 0;
        while (x) t[ ++ p] = (x % 10) ^ 48, x /= 10;
        while (p) putchar(t[p -- ]);
    }
    template<class T, class ...Args> inline void write(T &t, Args &...args)
    {
        write(t), write(args...);
    }
}

using namespace IO;


新鲜事 原文

WangJY
23天前
https://www.luogu.com.cn/problem/U243018 数位 DP 能不能过?求助


活动打卡代码 AcWing 275. 传纸条

WangJY
1个月前
#include <iostream>

using namespace std;

const int N = 55;

int n, m;
int g[N][N];
int f[N * 2][N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];

    for (int k = 2; k <= n + m; k ++ )
        for (int i = max(1, k - m); i <= n && i < k; i ++ )
            for (int j = max(1, k - m); j <= n && j < k; j ++ )
                for (int a = 0; a <= 1; a ++ )
                    for (int b = 0; b <= 1; b ++ )
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m)
                            t += g[j][k - j], f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                    }

    cout << f[n + m][n][n];

    return 0;
}


新鲜事 原文

WangJY
1个月前
。。。这次周赛又要挂了


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

WangJY
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 5, D = 5, S = 6;

int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};

int n, cnt;
char g[N][N], t[N][N];

void press(int x, int y)
{
    for (int i = 0; i < D; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (~a && a < N && ~b && b < N) g[a][b] ^= 1;
    }

    cnt ++ ;
}

int main()
{
    cin >> n;

    while (n -- )
    {
        for (int i = 0; i < N; i ++ ) cin >> t[i];

        int minstep = S + 1;

        for (int st = 0; st < 1 << N; st ++ )
        {
            memcpy(g, t, sizeof t);

            cnt = 0;

            for (int i = 0; i < N; i ++ )
                if (st >> i & 1)
                    press(0, i);

            for (int i = 1; i < N; i ++ )
                for (int j = 0; j < N; j ++ )
                    if (g[i - 1][j] == '0')
                        press(i, j);

            bool on = true;

            for (int i = 0; i < N; i ++ )
                if (g[N - 1][i] == '0')
                {
                    on = false;
                    break;
                }

            if (on && cnt < minstep) minstep = cnt;
        }

        if (minstep > S) minstep = -1;

        cout << minstep << '\n';
    }
}



WangJY
1个月前
#include <iostream>

using namespace std;

const int N = 11;

int n;
int a[N];
bool st[N];

void dfs(int u)
{
    if (u >= n)
    {
        for (int i = 0; i < n; i ++ ) cout << a[i] << ' ';
        cout << '\n';
        return ;
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        {
            st[i] = true, a[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}



WangJY
1个月前
#include <iostream>

using namespace std;

const int N = 30;

int n, m;
int a[N];
bool st[N];

void dfs(int u, int last)
{
    if (u == m)
    {
        for (int i = 0; i < m; i ++ ) cout << a[i] << ' ';
        puts("");
        return ;
    }

    for (int i = last + 1; i <= n; i ++ )
        if (!st[i])
        {
            st[i] = true, a[u] = i;
            dfs(u + 1, i);
            st[i] = false;
        }
}

int main()
{
    cin >> n >> m;

    dfs(0, 0);

    return 0;
}