头像

只想白嫖

xs




在线 


最近来访(69)
用户头像
LYNbz
用户头像
二十四_5
用户头像
阿飞被注册了
用户头像
SolitudeAlma
用户头像
Skywalker767
用户头像
ACwisher
用户头像
胡图图
用户头像
Seeker
用户头像
kyz
用户头像
wyhyr
用户头像
阿飘
用户头像
haniwn
用户头像
RyanMoriarty
用户头像
ITSanta
用户头像
Arthur_5
用户头像
whlbest
用户头像
15922191810
用户头像
DisguisedLove
用户头像
L_5
用户头像
阿凯

活动打卡代码 AcWing 1319. 移棋子游戏

只想白嫖
3小时前

== 解题方法 ==:如果所有石子数量的异或和!=0则先手必胜(因为此时先手可以将局面变为异或和为0抛给后手,后手不管怎样取,先手都镜像取,使得每次先手的局面的异或和都不为0,抛给后手的局面异或和都是0.)反之先手必输。

a1 ^ a2 ^ … ^ an = X

==1证明:当X!=0可以拿走一定数量的石子使得局面异或和为0==: 设X二进制最高位1在第K位,此时一定至少存在一个ai的第K位也为1

(==证:==X = ==1==aaaa,ai = bbb==1==cbcb, X ^ ai = bbb==0==zxcv, 此时X^ai一定 < ai)

我们拿走ai-X^ai个石子,那么第i堆还剩下ai-(ai-X^ai) = X ^ ai个石子:a1 ^ a2 ^ … ^ ==ai ^ X== ^ … ^ an = ==X ^ X== = 0,得证。

==2证明:当X == 0,拿走一定量石子之后局面异或和一定不为0==

反证:设从ai中拿出一定的石子变为a1 ^ a2 ^ … ^ ai^1^ ^ … ^ an = 0,与

a1 ^ a2 … ^ ai ^ … ^ an = 0左右同时异或:ai^1^ ^ ai = 0 ^ 0 = 0而==ai != ai^1^!=0==所以产生矛盾,即证当==X == 0,拿走一定量石子之后局面异或和一定不为0==

//author: A Fei
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 2010, M = 6010;
int h[N], e[M], ne[M], idx;
int n, m, k;
int sg[N], out[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int SG(int u)
{
    if(sg[u] != -1) return sg[u];
    if(!out[u]) return sg[u] = 0;

    set<int>s;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        s.insert(SG(j));
    }
    int now = 0;
    while(s.count(now)) now ++;
    sg[u] = now;
    return sg[u];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for(int i = 0; i <= n; i ++) h[i] = -1, sg[i] = -1;

    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        out[a] ++;
    }

    int res = 0;
    while(k --)
    {
        int x;
        scanf("%d", &x);
        res ^= SG(x);
    }

    if(res) puts("win");
    else puts("lose");

    return 0;
}


活动打卡代码 AcWing 1321. 取石子

只想白嫖
4小时前

关于博弈论能用dp推出来的原因

因为: 博弈论的某个状态一定可以由前面的状态得到, 一定相当于是有向无环图即:拓扑图. 故可以使用记忆化搜索(DP)得到.
在这里插入图片描述

/*
author: A Fei
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[51][50050];
int T;
int n;

int dp(int a, int b)
{
    int &v = f[a][b];
    if(v != -1) return v;
    if(!a) return b & 1;
    if(b == 1) return dp(a + 1, 0);

    if(b && !dp(a, b - 1)) return v = 1;
    if(a && !dp(a - 1, b)) return v = 1;
    //若b==0则合并a两堆,b+2(两颗石子);若b > 0则合并a两堆,b+3(两颗石子+一堆)
    if(a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
    if(a && b && !dp(a - 1, b + 1)) return v = 1;

    return v = 0;
}

int main()
{
    scanf("%d", &T);
    memset(f, -1, sizeof f);
    while(T --)
    {

        scanf("%d", &n);

        int a = 0, b = 0;
        for(int i = 1; i <= n; i ++)
        {
            int x;
            scanf("%d", &x);

            if(x == 1) a ++;
            else b += b ? x + 1 : x;
            //若b = 0,那么可操作数为x;若b > 0, 那么可操作数为x + 1.
        }

        if(dp(a, b)) puts("YES");
        else puts("NO");
    }


    return 0;
}
}


活动打卡代码 AcWing 1308. 方程的解

// Author:A Fei
///solution: 隔板法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1000][100][150];

// 快速幂
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }

    return res;
}

// 高精加
void add(int c[], int a[], int b[])
{
    for(int i = 0, t = 0; i < 150; i ++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    int n, k;
    scanf("%d%d", &k, &n);

    n = qmi(n % 1000, n, 1000);

    //求C(n - 1, k - 1);
    // C(n, m) = C(n - 1, m - 1) + C(n - 1, m);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= i && j < k; j ++)
            if(!j) f[i][j][0] = 1;
            else add(f[i][j], f[i - 1][j - 1], f[i - 1][j]);

    // 重定义一下,方便
    int *g = f[n - 1][k - 1];
    int idx = 149;
    // 从非零位输出
    while(!g[idx]) idx--;
    for(int i = idx; i >= 0; i --) printf("%d", g[i]);

    return 0;
}


活动打卡代码 AcWing 1307. 牡牛和牝牛

/*
author: A Fei
solution: -- 递推法
    状态表示f[i]:最后一个一在i的串个数
    状态转移:f[i] = f[1] + f[2] + ... + f[i - k - 1] --> s[i - k + 1]
    f[0] = 1是因为这样子初始f[1]是正确的
    若i - k - 1 < 0 则f[i] = 1;

    所有满足条件的串的个数为:f[1] + f[2] + ... + f[n] --> s[n]
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10, mod = 5000011;

int f[N], s[N];
int n, k;

int main()
{
    scanf("%d%d", &n, &k);

    f[0] = s[0] = 1;
    for(int i = 1; i <= n ; i ++)
    {
        f[i] = s[max(0, i - k - 1)];
        s[i] = (f[i] + s[i - 1]) % mod;
    }

    printf("%d", s[n]);

    return 0;
}



题目描述

自从曹冲搞定了大象以后,曹操就开始琢磨让儿子干些事业,于是派他到中原养猪场养猪,可是曹冲很不高兴,于是在工作中马马虎虎,有一次曹操想知道母猪的数量,于是曹冲想狠狠耍曹操一把。

举个例子,假如有 16 头母猪,如果建了 3 个猪圈,剩下 1 头猪就没有地方安家了;如果建造了 5 个猪圈,但是仍然有 1 头猪没有地方去;如果建造了 7 个猪圈,还有 2 头没有地方去。

你作为曹总的私人秘书理所当然要将准确的猪数报给曹总,你该怎么办?

样例

输入格式
第一行包含一个整数 n,表示建立猪圈的次数;

接下来 n 行,每行两个整数 ai,bi,表示建立了 ai 个猪圈,有 bi 头猪没有去处。

你可以假定 ai,aj 互质。

输出格式
输出仅包含一个正整数,即为曹冲至少养猪的数目。

数据范围
1≤n≤10,
1≤bi≤ai≤1100000
所有ai的乘积不超过 1018
输入样例:
3
3 1
5 1
7 2
输出样例:
16

中国剩余定理裸题

在这里插入图片描述

参考文献

提高课5.3

C++ 代码

/*
author: A Fei
solution: 同余方程组
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
int a[11], m[11];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    scanf("%d", &n);

    LL M = 1;
    for(int i = 0; i < n; i ++) scanf("%d%d", &m[i], &a[i]), M *= m[i];

    LL res = 0;
    for(int i = 0; i < n; i ++)
    {
        LL mi = M/m[i];
        LL t, y;
        exgcd(mi, (LL)m[i], t, y);
        // t = (t % m[i] + m[i]) % m[i];
        res += (LL)a[i] * t * mi;
    }

    printf("%lld\n", (res % M + M) % M);//对于任意x+kM都是满足要求的解,但目标是输出最小的正整数x,因此取模即可

    return 0;
}


活动打卡代码 AcWing 1298. 曹冲养猪

/*
author: A Fei
solution: 同余方程组
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
int a[11], m[11];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    scanf("%d", &n);

    LL M = 1;
    for(int i = 0; i < n; i ++) scanf("%d%d", &m[i], &a[i]), M *= m[i];

    LL res = 0;
    for(int i = 0; i < n; i ++)
    {
        LL mi = M/m[i];
        LL t, y;
        exgcd(mi, (LL)m[i], t, y);
        // t = (t % m[i] + m[i]) % m[i];
        res += (LL)a[i] * t * mi;
    }

    printf("%lld\n", (res % M + M) % M);//对于任意x+kM都是满足要求的解,但目标是输出最小的正整数x,因此取模即可

    return 0;
}



题目描述

8 是中国的幸运数字,如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。

现在给定一个正整数 L,请问至少多少个 8 连在一起组成的正整数(即最小幸运数字)是 L 的倍数。

样例

输入格式
输入包含多组测试用例。

每组测试用例占一行,包含一个整数 L。

当输入用例 L=0 时,表示输入终止,该用例无需处理。

输出格式
每组测试用例输出结果占一行。

结果为 Case i:+一个整数 N,N 代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在,则 N=0。

数据范围
1≤L≤2×109
输入样例:
8
11
16
0
输出样例:
Case 1: 1
Case 2: 2
Case 3: 0

算法1

在这里插入图片描述

参考文献

提高课5.3

C++ 代码

//author: A Fei
//trick: 快速幂那里会爆LL,要龟速乘。

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

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

LL euler(LL n)
{
    LL res = n, t = n;
    for(LL i = 2; i <= t / i; i ++)
    {
        if(t % i == 0)  
        {
            while(t % i == 0) t /= i;
            res = res / i * (i - 1);
        }
    }
    if(t > 1) res = res / t * (t - 1);
    return res;
}

LL qmul(LL a, LL k, LL mod)
{
    LL res = 0;
    while(k)
    {
        if(k & 1) res = (res + a) % mod;
        k >>= 1;
        a = (a + a) % mod;
    }

    return res;
}

LL qmi(LL a, LL k, LL mod)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = qmul(res, a, mod);
        k >>= 1;
        a = qmul(a, a, mod);
    }
    return res;
}

int main()
{
    LL T = 0, L;
    while(cin >> L, L)
    {
        LL d = gcd(L, 8);
        LL t = 9 * L / d;
        LL ans = 1e18;
        if(gcd(t, 10) != 1) ans = 0;
        else
        {
            LL x = euler(t);
            for(LL i = 1; i <= x / i; i ++)
                if(x % i == 0 ) 
                {
                    if(qmi(10, i, t) == 1)ans = min(ans, i);
                    if(qmi(10, x / i, t) == 1) ans = min (ans, x / i);
                }
        }
        printf("Case %lld: %lld\n", ++T, ans);
    }
}


活动打卡代码 AcWing 202. 最幸运的数字

//author: A Fei
//trick: 快速幂那里会爆LL,要龟速乘。

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

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

LL euler(LL n)
{
    LL res = n, t = n;
    for(LL i = 2; i <= t / i; i ++)
    {
        if(t % i == 0)  
        {
            while(t % i == 0) t /= i;
            res = res / i * (i - 1);
        }
    }
    if(t > 1) res = res / t * (t - 1);
    return res;
}

LL qmul(LL a, LL k, LL mod)
{
    LL res = 0;
    while(k)
    {
        if(k & 1) res = (res + a) % mod;
        k >>= 1;
        a = (a + a) % mod;
    }

    return res;
}

LL qmi(LL a, LL k, LL mod)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = qmul(res, a, mod);
        k >>= 1;
        a = qmul(a, a, mod);
    }
    return res;
}

int main()
{
    LL T = 0, L;
    while(cin >> L, L)
    {
        LL d = gcd(L, 8);
        LL t = 9 * L / d;
        LL ans = 1e18;
        if(gcd(t, 10) != 1) ans = 0;
        else
        {
            LL x = euler(t);
            for(LL i = 1; i <= x / i; i ++)
                if(x % i == 0 ) 
                {
                    if(qmi(10, i, t) == 1)ans = min(ans, i);
                    if(qmi(10, x / i, t) == 1) ans = min (ans, x / i);
                }
        }
        printf("Case %lld: %lld\n", ++T, ans);
    }
}



题目描述

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。

它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。

可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。

不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。

但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。

为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经 0 度处为原点,由东往西为正方向,单位长度 1 米,这样我们就得到了一条首尾相接的数轴。

设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐标是 y。

青蛙 A 一次能跳 m 米,青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。

纬度线总长 L 米。

现在要你求出它们跳了几次以后才会碰面

样例

输入格式
输入只包括一行 5 个整数 x,y,m,n,L。

输出格式
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行 Impossible。

数据范围
x≠y<2000000000,
0<m,n<2000000000,
0<L<2100000000
输入样例:
1 2 3 4 5
输出样例:
4

算法

在这里插入图片描述

参考文献

提高课5.3

C++ 代码

//author: author
//aolution:见题解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #define long long int;
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main()
{
    LL m, n, a, b, l;
    scanf("%lld%lld%lld%lld%lld", &a, &b, &m, &n, &l);

    LL x, y;
    int d = exgcd(m - n, l, x, y);
    if((b - a) % d) puts("Impossible");
    else
    {
        int t = abs(l / d);
        x *= (b - a) / d;
        // cout << t << endl;
        printf("%lld\n", (x % t + t) % t);
    }

    return 0;
}


活动打卡代码 AcWing 222. 青蛙的约会

//author: author
//aolution:见题解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #define long long int;
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main()
{
    LL m, n, a, b, l;
    scanf("%lld%lld%lld%lld%lld", &a, &b, &m, &n, &l);

    LL x, y;
    int d = exgcd(m - n, l, x, y);
    if((b - a) % d) puts("Impossible");
    else
    {
        int t = abs(l / d);
        x *= (b - a) / d;
        // cout << t << endl;
        printf("%lld\n", (x % t + t) % t);
    }

    return 0;
}