头像

qiao

AcWing




离线:1小时前


最近来访(126)
用户头像
GHOSTANDBREAD
用户头像
皮卡pika
用户头像
qwwjh
用户头像
acwing_1482
用户头像
不褪色的褪色者
用户头像
陆修远
用户头像
一只羊驼qwq
用户头像
上下求索
用户头像
AmazingMing
用户头像
小郑同学
用户头像
Dasseinzumtode
用户头像
o_28
用户头像
13170082479@163.com
用户头像
昕丶羽
用户头像
风_16
用户头像
txk666
用户头像
yxc
用户头像
小鲨鱼停止了思考
用户头像
ffhhyy
用户头像
cai_bird_565

活动打卡代码 AcWing 894. 拆分-Nim游戏

qiao
18小时前
#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n;

int f[N];

int sg(int x)
{
    if (f[x] != -1)return f[x];

    set<int> S;
    for (int i = 0; i < x; i++)
        for (int j = 0; j <= i; j++)
            S.insert(sg(i) ^ sg(j));

    for (int i = 0;; i++)
        if (!S.count(i))return f[x] = i;
}

int main()
{
    memset(f, -1, sizeof(f));
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int t; scanf("%d", &t);
        res ^= sg(t);
    }
    if (res)puts("Yes");
    else puts("No");
}






活动打卡代码 AcWing 893. 集合-Nim游戏

qiao
1天前
#include<bits/stdc++.h>
using namespace std;

int k,n;
int s[110],f[10010];

int sg(int x)
{
    if (f[x] != -1)return f[x];
    set<int> S;
    for (int i = 1; i <= k; i++)
    {
        int det = s[i];
        if (x - det >= 0)S.insert(sg(x - det));
    }

    for (int i = 0;; i++)
        if (!S.count(i))return f[x]=i;
}

int main()
{
    memset(f, -1, sizeof(f));
    cin >> k;
    for (int i = 1; i <= k; i++)scanf("%d", &s[i]);
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int t;
        scanf("%d", &t);
        res ^= sg(t);
    }

    if (res)puts("Yes");
    else puts("No");
}


活动打卡代码 AcWing 892. 台阶-Nim游戏

qiao
2天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int t;
        scanf("%d", &t);
        if(i&1)res ^= t;
    }
    if (res)puts("Yes");
    else puts("No");

}




活动打卡代码 AcWing 891. Nim游戏

qiao
2天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int t;
        scanf("%d", &t);
        res ^= t;
    }
    if (res)puts("Yes");
    else puts("No");

}

/*

必胜态:存在一种走法可以使下一步成为(先手)必败态
必败态:无论如何去走下一步都是(先手)必胜态

*/



qiao
1个月前

759312B1C7550E1A35DAC22ECFEC7586.png

C++ 代码

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

const int N = 5e4 + 10;

int p[N], d[N];//d[x]表示:x到父节点的距离(经路径压缩后才为到root的距离)

int find(int x)
{
    if (p[x] != x)
    {
        int t = p[x];
        p[x] = find(p[x]);
        d[x] += d[t];//经过路径压缩后,p[t]一定为root,因此d[t]表示为父节点到root的距离
    }
    return p[x];
}

int main()
{
    int res = 0;
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++)p[i] = i;
    while (k--)
    {
        int D, x, y; cin >> D >> x >> y;
        int px = find(x), py = find(y);
        if (x > n || y > n) { res++; continue; }
        if (D == 2 && x == y) { res++; continue; }//不加continue就会多计数

        if (px != py)
        {
            if (D == 1)//同类合并
            {
                d[px] += d[y] - d[x];
                p[px] = py;
            }
            else if (D == 2)//捕食合并
            {
                d[px] += -1 + d[y] - d[x];
                p[px] = py;
            }
        }
        else
        {
            if (D == 1 && (d[x] - d[y]) % 3 != 0)res++;
            if (D == 2 && (d[x] + 1 - d[y]) % 3 != 0)res++;
        }
    }
    cout << res;
}


分享 三分法

qiao
2个月前

E6FC6ADAC3A01687DCE4FFF6398DF022.png

int main()
{
    //函数的凹凸性质可以使用打表制作图像,或者求导判断

    //三分本质:每次消去不可能存在正确答案的区间

    int l = 0, r = 3.14159265 / 2;//取值范围
    //浮点型凹函数
    while (r - l > 1e-7)
    {
        int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
        if (f(lmid) > f(rmid))l = lmid;
        else r = rmid;
    }
    //浮点型凸函数
    while (r - l > 1e-7)
    {
        int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
        if (f(lmid) < f(rmid))l = lmid;//>改为<
        else r = rmid;
    }
    //整型凹函数
    while (l < r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (f(lmid) > f(rmid))l = lmid + 1;
        else r = rmid - 1;
    }
    //整型凸函数
    while (l < r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (f(lmid) < f(rmid))l = lmid + 1;
        else r = rmid - 1;
    }
}



qiao
2个月前

C++ 代码

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

const int N = 1e6+10;
int n;
int num[11];

int calc(int l, int r)
{
    int res = 0;
    for (int i = l; i <= r; i++)res = res * 10 + num[i];
    return res;
}

int main()
{
    int cnt = 0;
    for (int i = 1; i <= 9; i++)num[i] = i;
     cin >> n;

     do
     {
         //枚举中间区间(分为三段,枚举出中间段,其余两段自然可得)
         for (int i = 2; i <= 8; i++)
             for (int j = i; j <= 8; j++)
             {
                 int a = calc(1, i - 1);
                 int b = calc(i, j);
                 int c = calc(j + 1, 9);
                 // 注意判断条件,因为C++中除法是整除,所以要转化为加减乘来计算
                 if (c * (n - a) == b)cnt++;
             }
     } while (next_permutation(num+1,num+10));

     cout <<cnt;
}


/*

next_permutation函数
    组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end)
    ,和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,
    后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后
    ,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1.

    next_permutation(首地址,首地址+长度)
    作用:将区间内数组修改为下一个全排列(按照字典序),如果成功return 1 如果当前是最后一个则return 0
    因为返回的是下一个,所以一般配合do while使用
*/



qiao
3个月前

775DD5022D3AB5F2F80EBD1F2D41C42F.png

C++ 代码

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

const int N = 6e3 + 10;

//h[N]内部存的是idx,e[N], ne[N]是用于描述idx的,(idx,e[N], ne[N]共同组成节点)
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

//添加有向边 u->v
void add(int u, int v)//因为只有上司有多位下属,而下属只有一位上司,因此邻接表的方向是父节点->子节点
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        dfs(v);//计算方向为:自下而上,因此必须先计算好子节点,然后以此计算父节点

        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
    memset(h, -1, sizeof(h));

    for (int i = 0; i < n - 1; i++)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = 1;
    }

    int root = 1;//注意:此为题中的节点(1~N)而不是idx
    while (has_fa[root])root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}





qiao
3个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 6e3 + 10;

//e[N], ne[N]是用于描述idx的,而h[N]内部存的就是idx
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int u, int v)//添加有向边 u->v
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        dfs(v);

        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
    memset(h, -1, sizeof(h));

    for (int i = 0; i < n - 1; i++)
    {
        int a, b; scanf("%d%d", &a, &b);
        add(b,a);
        has_fa[a] = 1;
    }

    int root = 1;
    while (has_fa[root])root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}




活动打卡代码 AcWing 900. 整数划分

qiao
3个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int f[N];

int main()
{
    int n; cin >> n;
    f[0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % MOD;
    cout << f[n];
}