头像

小熊熊

中原工学院




离线:1小时前


最近来访(191)
用户头像
cyjdashuaib
用户头像
封禁用户
用户头像
ShiyuanJack
用户头像
Andy0229
用户头像
诗人kris
用户头像
zecoy
用户头像
iChenwei
用户头像
Leoooo小天才FOREVER
用户头像
chenhaowei
用户头像
RyanMoriarty
用户头像
DLRzzz
用户头像
追跡する
用户头像
菊花
用户头像
william-luo
用户头像
兰德朔
用户头像
大饺子
用户头像
只爱玩诺手
用户头像
Honey
用户头像
luxcgo
用户头像
清水洗脸

活动打卡代码 AcWing 4077. k显性字符

小熊熊
3小时前

优化后的版本,因为字符串每个位置只能是那个字母,通过空间换时间。时间复杂度为$O(n)$

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

const int N = 100010, L = 26;

int n;
char str[N];
int last[L], d[L]; //last从0开始,因为需要包含首个字符,那么就从首个字符的下一个字符。

int main()
{
    scanf("%s", str + 1); //因为下标从1开始,故输入也应该提前。
    n = strlen(str + 1); //求字符串的长度

    for (int i = 1; i <= n; i ++){
        int x = str[i] - 'a';
        d[x] = max(d[x], i - last[x]);
        last[x] = i;
    }

    for (int i = 0; i < 26; i ++){
        d[i] = max(d[i], n + 1 - last[i]); //因为要包含最后一个字符,那么就从最后一个字符的下一个字符开始。
    }

    int res = 0x3f3f3f3f;
    for (int i = 0; i < 26; i ++)
        res = min(res, d[i]);

    printf("%d\n", res);
    return 0;
}

python3代码

  • 开指定大小的列表
  • ord()函数的使用
  • python中的无穷大和无穷小。
s = list(input())
n = len(s)

N, L = 100010, 26

last = [0] * L
d = [0] * L

for i in range(n):
    x = ord(s[i]) - ord('a')
    d[x] = max(d[x], i + 1 - last[x])
    last[x] = i + 1;

for i in range(26):
    d[i] = max(d[i], n + 1 - last[i])

res = float("inf")
for i in range(26):
    res = min(res, d[i])

print(res)

没有优化版本,枚举所有字母。时间复杂度为$O(26n)$

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

int main()
{
    string str;
    cin >> str;
    int res = 0x3f3f3f3f;

    for (int i = 0; i < 26; i ++){
        char c = 'a' + i;
        int l = -1;
        int ans = 0;
        for (int j = 0; j < str.length(); j ++){
            if (str[j] == c && l == -1){
                ans = max(ans, j + 1);
                l = j;
            } else if (str[j] == c){
                ans = max(ans, j - l);
                l = j;
            }
        }
        int len = str.length();
        if (l != -1) ans = max(ans, len - l);
        if (ans) res = min(res, ans);
    }
    cout << res << endl;

    return 0;
}


分享 未完待续

小熊熊
6小时前

shell语法:
循环语句

for ((i = 0; i < 3; i ++)) #√
for ((int i = 0; i < 3; i ++)) #×

循环语句中的变量i单独使用需要加${},当作为数组角标直接使用。

tmux:查看session Ctrl + a + s

expr的规范

`expr "字符串" "${变量}" 'shell中的特殊字符'`
read n < $1     #从stdin重定向到当前文件
echo ${sum} > $2    #从stdout重定向到参数$2文件中

使用expr的多个计算符号时,不能再一个公式中使用,应分成几步。

输出全排列中第几个全排列注意事项

  • 函数的输入参数用$1,$2
  • 函数内的局部变量
  • echo -e命令的使用
  • 时刻注意变量取值${}

scp -r 文件夹名 #服务器名:路径,.表示本地。
supported.d文件夹:不要以为后面加个后缀就是文件了。



分享 一线之间

如果图形中有零个奇数点(即图中全为偶数点),可以从任意一点出发,一笔画回到起点。

如果图形中有两个奇数点,只能从一点奇数点出发,一笔画回到另一个奇数点。

奇数点再多就不能一笔画了。

科普——奇数点

奇数点就是从该点出发有奇数条线,如果这个图形奇数点多于两个,那么就不可能一笔画,而且不存在只有一个奇数点的图形。


参考资料:

  1. 奇数点有几个如何判断
  2. 一线之间





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

$mex()$运算

设集合$S$是一个非负整数集合,定义$mex(S)$为求出不属于S的最小非负整数的运算,即:$mex(S)=min[x]$,其中$x$属于自然数,且$x$不属于$S$。(就是找出集合$S$中不存在的最小自然数。)


SG函数

$SG():$在有向图中,对于每个节点$x$,设从$x$出发共有$k$条有向边,分别达到节点$y1,y2……yk$,定义$SG(x)$为$x$的后继节点的$SG$值构成的集合执行$mex()$运算后的值。
即:$SG(x)=mex(SG(y1),SG(y2)…SG(yk))$
特别的整个图$G$的$SG$值被定义为起点$s$的$SG$值,即$SG(G)=SG(s)$。终点的$SG(x) = 0$。
上图标红的值就是每一个节点的$SG$值
性质:1. $SG(i)=k$,则$i$最大能到达的点的$SG$值为$k−1$。
           2. 非$0$可以走向$0$
           3. $0$只能走向非$0$


当仅有一堆石子时,如果SG(x) != 0时,先手必胜。否则先手必败。
当有多堆石子时,如果$SG(x_{1}) \wedge SG(x_{2}) \wedge \cdots \wedge SG(x_{n}) != 0$,则先手必胜。反之,先手必败。


C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_set>
using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

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

    unordered_set<int> S;
    for (int i = 0; i < m; i ++)
    {
        int sum = s[i];
        if (x >= sum) S.insert(sg(x - sum));
    }

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

int main()
{
    cin >> m;
    for (int i = 0; i < m; i ++) cin >> s[i];
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

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

    return 0;
}


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

小熊熊
10天前

首先,读题可知,该题目满足NIM游戏的三个条件。那么接下来需要找到先手必胜态。

当台阶为偶数时,石子从偶数级台阶拿到地面需要偶数次石子个数=偶数。是先手必败态,不是我们要找的。
当台阶为奇数时,石子从奇数级台阶拿到地面需要奇数次
石子个数=偶数或奇数取决于石子的个数,当所有奇数阶台阶的异或值为0时,根据Nim游戏规则可知,先手必败。


C++代码如下

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

int main()
{
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        if (i % 2) res ^= x; 
    }

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

    return 0;
}


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

小熊熊
12天前

若一个游戏满足:

  • 由两名玩家交替行动
  • 在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
  • 不能行动的玩家判负

则称该游戏为一个公平组合游戏。

尼姆游戏(NIM)属于公平组合游戏,但常见的棋类游戏,比如围棋就不是公平组合游戏,因为围棋交战双方分别只能落黑子和白子,胜负判定也比较负责,不满足条件2和3。

NIM游戏存在两种状态

先手必胜态:可以走到某一个必败状态,先手总是存在一种方式使后手失败。
先手必败态:走不到任何一个必败状态,先手总是不存在一种方式使后手失败。


博弈论可以暴搜。
这种题可以找规律。

结论:

  • 当$a_{1}\wedge a_{2}\wedge \cdots \wedge a_{n} == 0$,先手必败
  • 当$a_{1}\wedge a_{2}\wedge \cdots \wedge a_{n} != 0$,先手必胜

位异或运算符(^)

运算规律:两个操作数的补码按位相同则结果为0,不同则结果为1。
如:15^2
a 的值是15,转换成二进制为1111,而b 的值是2,转换成二进制为0010,根据异或的运算规律,可以得出其结果为1101 即13。

补:这是一种典型的例子m ^ n ^ n = m,可以用来做图片的解密加密操作。


python代码如下:

n = int(input())
a = list(map(int, input().split(" ")))

res = 0
for i in range(n):
    res ^= a[i]

if res == 0:
    print("No")
else:
    print("Yes")


活动打卡代码 AcWing 4075. 染色

小熊熊
13天前

并查集 时间复杂度: O(n)

分析:

我们可以把颜色需要相同的所有小球放在一个集合中,并查集可以快速地合并集合。
然后需要找出每个集合中颜色最多的小球,就是该集合需要改变的颜色。这时我们开一个数组存储每个集合中各个颜色个数,边查边找最大值。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int n, m, k;
int p[N], col[N], cnt[N];
//p表示并查集的father数组。
//col表示每一个球的颜色。
//cnt表示每一种颜色出现的次数。
vector<int> S[N]; //存储集合中的每一个元素。

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

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

    for (int i = 1; i <= n; i ++) cin >> col[i];
    while (m --)
    {
        int l, r;
        cin >> l >> r;
        p[find(l)] = find(r);
    }

    for (int i = 1; i <= n; i ++) S[find(i)].push_back(i);

    int res = 0;
    for (int i = 1; i <= n; i ++)
        if (S[i].size())
        {
            int t = 0;
            //cnt记录当前集合各个颜色的个数,所以每次都需要恢复现场。
            for (auto x : S[i]) t = max(t, ++ cnt[col[x]]);
            res += S[i].size() - t;
            for (auto x : S[i]) -- cnt[col[x]];
        }

    cout << res << endl;
    return 0;
}



小熊熊
14天前

我配置好环境的网址:

公网IP:端口/路由
域名/路由
AcApp


我的项目地址:

https://git.acwing.com/fashen/game_warlock


我的django项目笔记

https://www.acwing.com/activity/content/code/content/2035370/


canvas自适应屏幕大小

screen.availWidth:屏幕可用宽度。
screen.availHeight:屏幕可见高度。

canvas.width = screen.availWidth;
canvas.height = screen.availHeight;

js实时获取窗口大小变化的实例代码

$(window).resize(function(){ 
  var Height = $(window).height();
  var Width = $(window).width();
})


活动打卡代码 AcWing Django-5.1. 上课笔记

小熊熊
14天前

部署nginx与对接AcApp

部署nginx的目的: 通过部署nginx之后就能通过域名代替公网IP:端口号的形式进行访问,同时对接http协议。
没有对接http协议的网站浏览器就会显示不安全。就比如:公网IP:端口号的方式进行访问。


这节课的目标:上线acapp
上线acapp需要对接http协议,所以需要部署nginx
对接httphttps协议需要开启80443端口。

1. 增加容器的映射端口:80与443

第一步,登录容器,关闭所有运行中的任务。

第二步,登录装载docker容器的服务器,然后执行:

docker commit CONTAINER_NAME django_lesson:1.1  # 将容器保存成镜像,将CONTAINER_NAME替换成容器名称
docker stop CONTAINER_NAME  # 关闭容器
docker rm CONTAINER_NAME # 删除容器

# 使用保存的镜像重新创建容器
docker run -p 20000:22 -p 8000:8000 -p 80:80 -p 443:443 --name CONTAINER_NAME -itd django_lesson:1.1
#端口作用: 20000是负责ssh登录,8000是负责调试,80是http端口,443是https端口。

第三步,去云服务器控制台,在安全组配置中开放80和443端口。
2021-11-13_095206.jpg

总结: 就是将容器变成镜像然后在重新生成时添加两个端口。

注: 其实给正在运行的容器添加端口的方法也是存在的,相比之下感觉这个好用。

2. 创建AcApp,获取域名、nginx配置文件及https证书


在服务器IP一栏填入自己服务器的公网ip地址。


创建AcApp之后就自动分配域名了。填写完IP地址后,就只用配置nginx和https证书文件。

配置nginx

nginx.conf中的内容写入容器的/etc/nginx/nginx.conf文件中。
$\color{red}{如果django项目路径与配置文件中不同,注意修改路径。}$

#普通用户修改根目录中的文件需要通过sudo提高权限。
sudo vim /etc/nginx/nginx.conf

sudo cp .vimrc .tmux.conf /root
#在root权限下找回初恋的感觉。
#.bashrc就算了,因为在root用户下存在一种特殊的用法。

sudo vim /etc/nginx/nginx.conf #修改nginx配置文件。
#先将原有的配置内容全部删除,然后将需要的配置内容放入即可。

2021-11-13_175549.jpg

acapp.key中的内容写入服务器/etc/nginx/cert/acapp.key文件中。
acapp.pem中的内容写入服务器/etc/nginx/cert/acapp.pem文件中。

cd /etc/nginx
#因为我们现在使用普通用户来改变根目录的内容需要使用sudo指令。
sudo mkdir cert
sudo vim acapp.key
sudo vim acapp.pem
#将两者的配置文件放入即可。

然后启动nginx服务:

sudo /etc/init.d/nginx start
sudo nginx -s reload #重新加载nginx配置

2021-11-13_103127.jpg


sudo(详细)

sudoLinux系统管理指令,是允许系统管理员让普通用户执行一些或者全部的root命令的一个工具,如haltrebootsu等等。这样不仅减少了root用户的登录 和管理时间,同样也提高了安全性。sudo不是对shell的一个代替,它是面向每个命令的。


3. 修改django项目的配置

  • 打开settings.py文件:
    • 将分配的域名添加到ALLOWED_HOSTS列表中。注意只需要添加https://后面的部分。域名代替了公网IP:端口号
    • DEBUG = False,将django框架转变成生产环境。
  • 归档static文件:
    • python3 manage.py collectstatic

配置Django框架为生产环境的注意事项(DEBUG=False)


这时,我们的打包脚本更新一下,方便我们操作。

vim compress_game_js.sh
---------------------------------------------------------------------------------
#! /bin/bash

JS_PATH=/home/mofan/game_warlock/game/static/js/
JS_PATH_DIST=${JS_PATH}dist/
JS_PATH_SRC=${JS_PATH}src/

find $JS_PATH_SRC -type f -name '*.js' | sort | xargs cat > ${JS_PATH_DIST}game.js

echo yes | python3 manage.py collectstatic
---------------------------------------------------------------------------------
./scripts/compress_game_js.sh

python3 manage.py runserver 0.0.0.0:8000
之前通过8000端口访问django。
现在通过443端口或80端口访问nginx,然后运行uwsgi服务作为桥梁访问django。

4. 配置uwsgi

django项目中添加uwsgi的配置文件:scripts/uwsgi.ini,内容如下:

[uwsgi]
socket          = 127.0.0.1:8000
chdir           = /home/acs/acapp ;django工程的绝对路径。
wsgi-file       = acapp/wsgi.py ;根模块中的wsgi.py
master          = true
processes       = 2
threads         = 5
vacuum          = true

启动uwsgi服务:

uwsgi --ini scripts/uwsgi.ini

至此,当我们填写完并创建好App后,通过域名或者打开应用的方式就能访问我们的网站了。