头像

人间温柔




离线:1分钟前


最近来访(47)
用户头像
1只小牛马
用户头像
欢乐马_68
用户头像
cuola
用户头像
封禁用户
用户头像
TheGifted
用户头像
RyanMoriarty
用户头像
yxy.
用户头像
lyxose
用户头像
没有假如
用户头像
acwing_4280
用户头像
枫灵FengLing
用户头像
李荼荼
用户头像
大宝_0
用户头像
JIeJaitt
用户头像
123456...
用户头像
星逐月丶
用户头像
notion
用户头像
charley123
用户头像
星星_8
用户头像
Mallknow


想问一下各位大佬,c++ 有没有办法解出下面的这个方程?(x 是未知数)

$$
\dfrac{a_1}{x+b_1}+\dfrac{a_2}{x+b_2}+\ldots +\dfrac{a_n}{x+b_n}=c
$$

$a,b,c$都是输入的。




有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

数论

扩展欧几里得算法

博弈论

巴什博弈

技巧

离散化




学习笔记目录

巴什博弈——不用 for 循环的算法

有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

巴什博弈:有一堆石子,共 $n$ 个。两个人轮流从中取石子,规定每次每人最少取 $1$ 个,最多取 $m$ 个。最后,无法再取石子的人失败。若两人 $IQ$ 奇高无比,问:先手有没有必胜策略?

为了让读者更好的理解游戏规则,蒟蒻自编了一个 $cpp$ 游戏(或许这次是我第一次在学习笔记中引入游戏元素),复制到 dev-cpp 中食用更佳~。

#include<bits/stdc++.h>
#include<unistd.h>
#include<ctime>
using namespace std;
int main(){
    srand((int)time(NULL));
    int n=rand()%91+10,m=rand()%16+5;
    printf("现在有 %d 个石头,您与计算机轮流取石头,您先取,电脑后取。\n",n);
    printf("规定每人最少取 1 个石子,最多取 %d 个石子\n",m);
    int rd=1;
    while(n!=0){
        printf("========== Round %d ==========\n",rd);
        if(rd%2==1){
            printf("请您输入您想取走的石子个数: ");
            int take;
            scanf("%d",&take);
            while(take<=0 || take>m || take>n){
                if(take<=0)printf("警告:至少取走 1 个石子,请重新输入:");
                else if(take>m)printf("警告:至少取走 %d 个石子,请重新输入:",m);
                else if(take<n)printf("警告:总共只有 %d 个石子,而您取了 %d 个石子,请重新输入:",n,take);
                scanf("%d",&take);
            }
            n-=take;
            printf("现在还剩 %d 个石子。\n",n);
            if(n==0)printf("恭喜您,您获胜了!!!");
        }
        else{
            printf("请电脑输入电脑想取走的石子个数: ");
            int take;
            sleep(3);
            if(n<=m)take=n;
            else take=rand()%m+1;
            printf("%d\n",take);
            n-=take;
            sleep(1);
            printf("现在还剩 %d 个石子。\n",n);
            if(n==0)printf("恭喜电脑,电脑获胜了!!!");
        }
        rd++;
        cout<<endl; 
    }
    return 0;
}

初次看到这题,是否有些熟悉?回想一下小学奥数题:

甲乙轮流报数,最多报 $7$ 个数,最少报 $1$ 个数,从 $1$ 开始,谁先报到 $50$ 谁就胜利。甲先报,有无必胜策略?

甲有必胜策略。他先报 $2$ 个数,这样还有 $48$ 个数要报。之后每次乙报 $x$ 个数,甲都报 $8-x$ 个数,所以每一轮都会去掉 $8$ 个数字,$6$ 轮以后,甲胜利。

同理,在巴什博弈中,当 $n≡s\ (\mod m+1)\ \ (1\leq s \leq m)$ 时,即 $n$ 无法被 $m+1$ 整除,那么先手取走 $s$ 个石子。之后后手每取走 $k$ 个石子,先手都取 $m+1-k$ 个石子,若干轮之后,先手取光石子,先手获胜。

有上面的推到,我们可以知道,当 $n$ 不能被 $m+1$ 整除时,先手有必胜策略;即 $n$ 能被 $m+1$ 整除时,后手有必胜策略。

【代码】

#include <iostream>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    if(n%(m+1)==0){
        cout<<"后手必胜"<<endl;
    } else {
        cout<<"先手必胜"<<endl;
    }
    return 0;
}


新鲜事 原文

人间温柔
1个月前
蒟蒻初三,还有 23 天就要一模了,从今天开始,拒绝一切私信与一切通知。在此期间所有的私信、所有通知,均会在 1 月 14 日统一处理。


新鲜事 原文

人间温柔
2个月前
200阅读量祭


新鲜事 原文

人间温柔
2个月前
人间温柔 的运势 § 凶 § 宜:装弱 谦虚最好了 宜:刷题 成为虐题狂魔忌:发朋友圈 会被当做卖面膜的 忌:熬夜 爆肝 你已经在洛谷连续打卡了 385 天


新鲜事 原文

人间温柔
2个月前
人间温柔 的运势 § 小吉 § 宜:装弱 谦虚最好了 宜:纳财 要到好多Money忌:学习珂学 珂朵莉不知干啥不理你 忌:熬夜 爆肝 你已经在洛谷连续打卡了 378 天



人间温柔
2个月前

学习笔记目录
有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

问题:给定一个序列,求其逆序对个数。

这题很显然要用树状数组,但是在元素规模过大的情况下(如到了 $10^{12}$),树状数组会存不下。

我们考虑如下一个序列:

1 53 23 5464543 34

它的逆序对数量应该和下面这个序列是一样的:

1 4 2 5 3

可见,数字的大小与逆序对的数量无关。由此我们引入了离散化这个方法。

离散化的方法

  • 记录数据的编号,对数据排序。
  • 将原数组排序,然后去重,可使用algorithm中的unique函数。
  • 最开始记录下的数据编号,就是数据离散化后的结果。
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 100010;

int num[maxn];
int tp[maxn];
map<int,int>mp;
int id[maxn];
int real[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
        tp[i]=num[i];
    }
    sort(tp,tp+n);
    int m=unique(tp,tp+n)-tp;
    for(int i=0;i<m;i++){
        mp[tp[i]]=i+1;
        real[i+1]=tp[i];
    }
    for(int i=0;i<n;i++){
        id[i]=mp[num[i]];
        cout<<id[i]<<" ";
    }
    return 0;
}


新鲜事 原文

人间温柔
3个月前
CSP rp++



人间温柔
3个月前

想问下,交互题是什么形式的,和传统的提交答案一样嘛?

今年csp会不会考到交互题?