头像

acwing_1553




离线:2小时前


最近来访(18)
用户头像
积极生长者
用户头像
Raylv
用户头像
MarkCup马克杯
用户头像
TyZErr233
用户头像
WangJY
用户头像
Homie
用户头像
Lemon_8
用户头像
srz
用户头像
ningmeng
用户头像
有点丶
用户头像
yxc
用户头像
WAWA鱼
用户头像
云朵有点儿甜
用户头像
霍雨浩
用户头像
kuan525
用户头像
TDS_
用户头像
拓念
用户头像
SanShi

活动打卡代码 LeetCode 1282. 用户分组

acwing_1553
5小时前
        unordered_map<int, vector<int>> hash;
        for(int i = 0; i < groupSizes.size(); i++) {

            hash[groupSizes[i]].push_back(i);
        }
        vector<vector<int>> res;
        for(auto[key, val] : hash) {

            if(val.size() == key) {
                res.push_back(val);
            }else if(val.size() > key) {
               int n = val.size() / key;
               for(int i = 1; i <= n; i++ ) {
                   vector<int> path(val.begin() + key *(i - 1), val.begin() + key*i );
                   res.push_back(path);
               }
            }
         }
        return res;



string str;
将字符串转化为整数 stoi(s.substr(k, k + u))




1, 记忆性搜索,
当需要广搜地图的时候,最后求得是最大数相关的时候, 最值一般用动态规划
对地图进行方向式搜索, 并且对搜索的每个点做标记, 就是利用另外一个二维数组,记录搜索的每个数。每次搜索的一个符合要求的数都是在上一个数的基础上加一。
int f[N][N]; memset(f, -1,sizeof f), 遍历的时候有, int & c =f[u][v] if(c == -1) return c;
c = 1;
之后开始方向性搜索
c = max(c, dfs(x, y) + 1); 最终return c ;就行了。
2, 树形dp
层次相关的,就是点与点之间能够形成一条边, 并且有父子关系。
这样的话,需要先找到根,就是那个父亲, 可以用一个数组对有父亲的节点进行标记, 遍历这个数组, 就能得到父亲;
然后开始遍历, 对于每个节点有选择和不选择两种状态;
dfs(u) {
f[u][1] = hp[u];
for(int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);先找出来以这个节点为父节点的所有节点, 然后在进行判断该节点选与不选和子节点选与不选的最值。
f[u][0]+= max(f[j][0], f[j][1]);
f[u][1] += f[u][0];
}
}

3, 蒙德里安的梦想
f[i][j] 表示的是从i- 1 列伸入到第i列的并且状态为 j的方案数。
f[i - 1][k] 表示的是从第i- 2列伸入到第i- 1列的并且状态为k的方案数
先进行插,然后在进行列插。
对于行来说, 每一列不能出现重叠状态,就是 这个位置不能既是上一列的插入,又是下一列的伸出。
对于每一列来说,连续的零的个数要为 偶数才可以。否则也是无效状态。
枚举所有的状态, 去除掉不合法的状态。

预处理1 先进性行预处理,去掉重叠的状态并且去掉奇数个0的状态 每一行用状态进行处理, 表示到每一行的最大状态数中, 连续0的个数有多少。
每一行中按照位置进行遍历, 如果这个位置是1的话,表示前面有插入, 看他前面的0是奇数个还是偶数个,如果是奇数个的话,则是无效状态。则该数之前的是一个无效状态,直接重新直接接着枚举就行,
存储一下状态就行。
预处理2 开始看每一列中的状态,如果是记录一下,这里一列中的1的状态。
对于每一列是按照行进行枚举的。
这个也是表表按列进行枚举存储列的状态。
for(int i = 0; i < 1<<n; i) {
for(int j = 0; j < 1 << n; j
) {

    }
}

最后开始进行状态计算, 遍历每一列, 对于每一列枚举状态然后记录就行。
for(int i = 1; i <= m; i) {
for(int j = 0; j < 1 << n; j
) {
for(auto k : state) {
f[i][j] += f[i - 1][k];
}
}
}
最后输出f[m][0];

*******输入的技巧输入两个数并且两个都不为0的时候可以使while(cin >> n >> m, n || m)

状态法 , 用二进制区表示这个几位数的能够表示的状态是多少。
这个题要对他进行每个状态是否合法,然后在对每个状态进行枚举, 枚举这个时候是插入的上一列的状态。




题目描述

01数, 这个题意是求1~n中有少个01数,就是该数字中每一位均由0 或者1组成
可以暴力这个范围的数
1~10^9, 位数为10位, 故整个数大约有2^10次方个数字。即1024个
但是对于10位数, 只有一个即1000000000, 故实际上是10的9次方个数位512个数不能并且所有的数都是从1开始的
故我们可以对每一个数位上的数进行遍历, 采用的是2进制遍历,但是每一位都是对应的十进制中的数

include[HTML_REMOVED]

using namespace std;
int main() {
int n;
cin >> n;
int res = 0;
for(int i = 1; i < 1 << 10; i) {
int x = 0;
for(int j = 0; j < 10; j
) {
x = x * 10 + (i >> j & 1);

    }
   if(x <= n) res ++;

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

}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


分享 华为机试

对于输入整个字符串的化可以用getline(cin, str);
万能的头文件描述符 #include[HTML_REMOVED]




如何让用户登陆:

用户(Client)每次一刷新,就会先给后台服务器(Server)发送一个请求(Request):getinfo获取用户信息,然后后台就会返回一个响应(Response),表示用户信息(用户名,头像)或者登录失败的响应。
创建账号系统:
首先是在django提供的后台数据库管理系统上进行扩充,扩充一个数据表就是创建一个类让他继承于django中的Model类, 使用delete=models.CASCADE当user删除的时候要一起删除,user就是User的一个对象

1.HttpResponse、render、redirect介绍
1.1.HttpResponse
作用为:内部传递一个参数,返回给浏览器

from django.shortcuts import HttpResponse

def from_request(request):
# Todo
return HttpResponse(‘OK’)

JosnResponse是HttpResponse的一个子类,JosnResponse会自动把字典转换成josn格式,HttpResponse需要手动转换。

render会调用HttpResponse函数

可接受三个参数,分别为请求request, 需要渲染的模板template,以及向模板传递的参数context,render(request, ‘template’, context)

from django.shotcuts import render

def from_request(request):
# Todo
# return render(request, ‘template.html’, context)
# or
return render(request, ‘template.html’)

1.3.redirect
接受一个URL参数,表示让浏览器跳转去指定的URL

from django.shotcuts import redirect

def from_request(request):
# Todo
return redirect(request, ‘page’)

2.Django请求和响应过程:
当一个web请求链接进来时,django会创建一个HttpRequest对象来封装和保存所有请求相关的信息,并且会根据请求路由载入匹配的view函数,每个请求的视图函数都会把HttpRequest作为参数,并且返回一个HttpResponse对象。

4.QueryDict
HttpRequest对象中的GET和POST属性都是QueryDict类的对象,与Python字典很像,不同的是QueryDict对象一个键可以保存多个值

4.1.get()方法可以通request.GET。get()获取, 整个项目是前后端分离的, 需要传入一个参数,来判断请求来自哪一个平台,
根据键获取值

如果一个键同时拥有多个值,将获取最后一个值

如果键不存在则返回None值,可以设置返回自定义的默认值

dict.get(‘键’, 默认值)




统一标准:
联机对战,多人模式要求所有的玩家在同一居游戏中, 所以 地图大小, 玩家大小等等游戏界面的所有东西都应该按照玩家的电脑界面比例来设定, 不能够直接确定出实际大小,否则的话玩 某些玩家屏幕大的话,游戏中的各种实际元素大小就偏大, 传输数据到小屏幕玩家电脑上就会造成不协调,同时如果玩家将网页界面缩小的话, 里面的元素也应该缩小,所以要将游戏界面的大小变为按照页面大小大小来确定实际大小。

python3中的async与await

并发: 是指两个或多个事件在同一时间间隔内发生。 是指一个时间段中有有多个 程序都处在运行状态到运行完毕之间,并且这几个程序都是在同一个处理机上运行。

并行:是指两个 或多个事件在同一时刻发生, 即在任何时间点上, 有多个程序运行在多个CPU上。

同步: 是指代码调用IO操作时, 必须等待IO操作完成才能返回的调用方式

异步: 是指代码调用IO操作时, 不必须等待I操作完成就能返回的调用方式

协程: 协程可以理解为纯用户态的线程, 其通过协作而不是抢占来进行切换, 相对于线程或者进程,协程所有的操作都可以在用户态完成, 创建和切换的效率更低。 传统函数调用过程为A->B->C->D,若需要一个可以暂停的函数,并且可以在适当的时候恢复该函数继续执行,这便是协程, 当程序中的方法需要等待时间的话,就可以用协程。
函数正在执行的 过程中是不能中断的, 所以如果需要写一个能够中断的函数, 则需要添加async关键字。
async 用来声明一个函数为异步函数, 异步函数的特点是能在函数执行的过程中挂起, 去执行其他的异步函数,等到挂起条件消失后,也就是1秒到了再回来执行被挂起的函数

await 用来声明程序挂起, 比如异步程序执行到某一步时需要等待的时间很长,就将此挂起, 去执行其他的异步程序。

def demo():
async def wash1():
do
do
await______
do
do
函数在执行过程中,发生了请求而我们等待得到回复,而在这个过程中,程序是不能运行的比较浪费时间,可以采用协程也就是异步去解决此问题,在等待的时候去做其他的事情,由此来节省时间提高效率, 只有被async函数声明了的方法才能发生协程, 并且只有在await后面的被async声明的函数或者是asyncio库里的函数发生了等待在会发生协程挂起该异步函数去执行其他程序。

利用django_channels来进行前端与后端的通信来维护我们游戏的实时对局信息。http协议是单向通信,也就是前端向后端发出请求,后端接受请求,进行处理并返回结果给前端,但是不能后端主动给前端发送信息,而https则是对http进行加密的协议,ws就是WebSocket协议是双向通信,前端可以给后端发送信息,同样后端也可以给前端发送信息,而wss就是对ws进行加密的协议,django要支持wss协议的话就需要django_channels来实现。同时在我们游戏的逻辑中,我们通信之后要使同一局玩家游戏界面情况相同,就要将游戏数据存储起来,这里可能你会想存储到普通数据库中不就可以了,但是我们是一个多人对战游戏对实时性要求比较高,采用redis来存储数据,这样我们存取效率就会比较高,为了时django_channels能够连接redis并使用它需要下载channels_redis

前端之间的每个窗口之间是如何通信的当前端通过链接试图与我们建立通道时,我们会执行connect()函数,然后我们假定房间号是0~999,那么遍历每一个房间,当某个房间没有被创建或者说房间内人数不满的时候就确定该连接的玩家房间号,并执
行accept()函数建立连接,然后,如果房间不存在的话就创建,然后遍历房间内其他玩家信息通过send()函数向前端发送信息,channel_layer.group_add(self.room_name, self.channel_name)此函数作用是,将该通道加到组名为room_name的组中,并且该通道的名字是channel_name,receive(self, text_data)函数作用是接收前端发送来的信息,
wss协议传输的是字符串,所以我们前后端不断要执行字典与字符串相互转化的操作

python中

json.dumps(字典) #将字典转化成字符串
json.loads(字符串) #将字符串转化成字典
js中

JSON.parse(字符串) //将字符串转化成字典
JSON.stringify(字典) //将字典转化成字符串

前端——写自定义send函数和自定义receive函数,负责与服务器的信息交互
后端——写对应的自定义receive函数
无论前端还是后端都要再写一下路由
什么路由——意思就是,在前后端信息交互的时候真正负责通信的是框架提供的api函数,而我们为了代码可读性更高所以会根据接收的信息标志而用不同的自定义函数去处理信息,但是框架又不晓得我们的自定义函数,所以我们就会在api函数中调用我们写的自定义函数。这就是写路由。

如何同步玩家信息
整合django_channels,用websocket实现:

每个客户端需要给主机实时发送请求,“主机”的建立会在后面详解
主机也需要实时向每个客户端发送广播。
客户端在收到广播后要更新自己的信息

广播移动玩家就要移动目标点, 对于玩家移动的话, 为了避免传递方向和移动距离
move_to”

y总采用的方法是广播移动玩家将要移动的目标点,其实由于网络延迟原因,只传递目标将要移动的目标点的话,如果玩家快速并且多次点击移动事件,那么就有可能出现误差,比如一个玩家在两个屏幕同一位置,此时玩家向右移动,然后另一块屏幕接收到传递信息后进行移动,但是此次接收信息的延迟比较大,此玩家还未到达目的地的时候玩家更改移动目的地的话,就会再次传递信息,另一块屏幕接收信息后换方向移动,此次延迟比较小,由于两次延迟造成,坐标出现差错,为了同步信息而且我们视角是以自己为中心,传递目的地坐标比较麻烦(需要反复计算实际坐标),所以我们采用传递方向和移动距离,但是与上面同理,同样会造成坐标偏差(两个屏幕同一玩家坐标不同),我们采用每三次移动事件就更新下玩家坐标,减少偏差。

“shoot_fireball”

同步发射火球函数,传递发射火球玩家,火球uuid与方向,接收函数只要调用玩家发射火球函数就可以

“attack”

击中玩家事件,我们设定只有自己发射的火球才能有判定是否击中的能力,其他玩家的火球,在其他玩家电脑中进行判定,这样设计不会导致同一火球有的玩家屏幕中火球击中,有的玩家屏幕中火球未击中,当发生了击中函数时,传递被击中玩家的uuid,和击中玩家的火球,还有击中产生的后退方向

“shoot_shield”

释放护盾事件,与发射火球事件一样,传递玩家信息,这里由于误差小就不在采用,火球击中事件的判定方法,没个护盾自行判断消除火球

“eat_dot”

吃”小豆豆”事件,传递被吃小豆豆的uuid与新坐标,还有玩家的uuid,这里采用跟火球一样的机制,自己吃的豆豆才回去发送事件,保持统一



分享 Django项目

本地前端 实现两个部分:
文本输入框和历史记录显示框
用户按下[HTML_REMOVED] 后, 游戏界面弹出文本输入框, 然后聚集于文本输入框, 且同时弹出历史记录显示框3秒
然后用户输入信息后, 按下[HTML_REMOVED]后发出信息, 接着信息会显示在历史记录显示框最下方, 并弹出历史记录显示框3秒




使用 terser 进行加密压缩, js代码
terser不仅支持文件输入, 也支持标准输入, 结果会输出到标准输出中 terser XXX.js -c -m
可以通过AcwingOs.api.window.on_close(func)关闭之前触发的事件
再同一个页面中, js 代码只会加载一次, 因此全局变量在同一个页面, 同一个acapp窗口共用
各自创建的局部变量是对立的, 比如 new ACGame()创建出的对象每个窗口是独立的
可以给每个窗口创建uid, 根据不同的uid进行事件解绑

创建游戏结束界面, 这个界面在游戏结束的时候渲染出来即可,结束界面要覆盖在游戏界面之上,在每一帧渲染的内容最后在渲染, 从而实现结束界面叠加在游戏界面之上的效果

游戏结束的逻辑判断,竞赛状态, 且只有一名玩家, 并且是我,则胜利,否则失败
渲染结束界面, 同时在结束并返回主菜单的时候, 重置游戏元素
更新战绩
在处理广播的时候,先要额外的留一个参数hp, 围绕该hp进行续写, 若当前时间内hp大于0 的玩家少于一个, 则对与所有的hp为0 的玩家减rank分, 大于0的玩家加rank分




1 利用 thrift 创建客户端和服务端的接口 , 利用该接口来完成一个匹配系统。
thrift 是一种接口描述语言和二进制通讯协议, 它被用来定义和创建跨语言的服务。。。 被当做一个远程过程调用(RPC)框架来使用, 是有facebook为大规模跨语言服务而开发的
基础的数据类型 bool i32 i16, i8, i64, double, string, binary, map[HTML_REMOVED], list[HTML_REMOVED], set[HTML_REMOVED]
可以转化成任何类型的语言 namespace c1 tutorial等
结构体定义
struct work
{
1: i32 num = 0,
2: i32 num2,
3: string name,
}
functional 定义 i32 add(1: i32 num, 2: i32 num 2)
实现的框架有
游戏应用端 : 与匹配系统服务器的服务端交互
匹配系统服务端:
1. 服务端: 与游戏应用端的客户端交互
2, 客户端: 与数据存储服务器的服务端交互、
数据存储服务器(已经实现)
服务端:与匹配系统服务器的客户端交互

首先 创建一个matc。thrift 接口文件
匹配系统服务器的 服务端 用于实现游戏应用端与匹配服务器的交互的service;
对于一个用户 保留他的分数 名字, id , photo , openid 在服务端 每当添加用户的时候, 同时相匹配词中添加该用户,
删除的时候, 删除用户的信息, 同时在匹配池中将其删除。

匹配系统服务器的客户端 运行match.thrift接口文件在匹配系统服务器端生成C++ 源文件
原始的thrift生成文件语法: thrift -r –gen cpp ../../thrift/match.thrift
match _server 与游戏应用端进行交互, client_server 与数据存储服务器交互

编译 所有的。cpp文件生成 .o 文件 g -c main.cpp match_server/*.cpp(-c后面的都是文件名)
链接 所有的.o文件生成可执行文件 .exe g
[文件1.o][文件2.o].....-o[需要额外添加动态库] lthrift的thrift动态库
g++ .o -o main -lthrift
运行可执行文件 ./main
git add .
git restore –stage
.o #.o文件是编译文件, 不加入暂存区
git restore –stage main ## main是可执行文件, 不加入暂存区
git commit -m “add match server”
git push

游戏应用端的一个客户端
运行match.thrift 在游戏应用端生成python3源文件, 这里只有客户端
利用官方文档提供的模板编写客户端文件 client.py

在终端输入的信息的话需要from sys import stdin
将通信中的main函数可以改写成operator 函数, 每次需要的时候调用一次建立通信传递传递信息 目的是可以一直不断处理信息, 然后重写main函数, 使其不断地从终端读入信息

在 匹配系统服务器中给匹配系统开一个线程
运用到了 操作系统中的 pv 原语以及生产者和消费者模型
需要一个线程, 能够引入一个头文件 [HTML_REMOVED]

include[HTML_REMOVED] 互斥信号量 [HTML_REMOVED] 条件变量, 用于阻塞和唤醒 线程

include[HTML_REMOVED] 用于模拟消息队列 其中消息队列中的的元素有用户名 和 string type

消息队列结构体包含 消息队列本体, mutex互斥信号量 condition_mutex条件变量 , 用于阻塞唤醒线程 message_queue

匹配池的实现
可以向匹配池中加入用户, 删除用户(根据id来进行删除), 记录成功匹配的信息,
采用vector来保存匹配池中的用户

匹配机制 :
添加用户以及实现删除用户
这两个均是下面的过程
访问临界区的时候 unique_lock[HTML_REMOVED] lck(message_queue.m); 先上锁
message_queue.q.push({user, “add”}) 把新消息加入消息队列
message_queue.cv.notify_all(); 唤醒阻塞的线程

对于生产者-消费者模型 的线程
访问临界区的时候一定要先上锁, unique_loack[HTML_REMOVED] lck(mesaage_queue.m);
如果该队列为空就要阻塞进程 messsage_queue.cv.wait(lck)
否则的话:
取出消息队列的对头元素
临界区访问结束之后直接解锁, lck.unlock();避免后续没有用到临界区的信息, 而长时间占用锁

在进行后续的任务
之后调用线程运行 thread matching_thread(consumer_task); // 调用一个线程运行 consumer_task

数据存储器与服务器交互
数据存储器服务的服务端
主要存储 用户名以及密码采用MD5sum加密后的前8 为MD5哈希函数可以获得服务器密码的哈希值
用户名密码验证成功之后会返回0, 验证失败后会返回1
验证成功后结构将会保存到云服务器中
i32 save_data (1:string username,2: stringpassword, 3: i32 player1_id, 4: i32 player2_id);
匹配系统客户端中, 记录用户匹配的信息
重写save_result(int a, int b) ; 记录匹配结果,将数据存储到数据存储服务器中

之后运行的时候,只运行save_client即可
g -c main.cpp save_client/*.cpp
g
*.o -o main -lthrift -pthread
./main
可以在游戏应用端, 中输入用户信息(编号, 名字, 分数) 并添加到匹配系统服务器中, 进行匹配, 可以在数据存储服务器中查看存储的数据

该匹配系统有一个消息队列 + 生产者——消费者模型 + 匹配池完成

对于匹配 每次匹配分差小于50的用户
可以考虑重写main.cpp文件中的部分功能
当消息队列为空的时候, 不再是阻塞直到唤醒为止, 可以让他每次经过一秒就进行一次match()调用, 可能会出现匹配池中有用户等待, 而消息队列此时仍然为空
若采用先前的策略, 可能会导致进程卡死
当队列为空的时候, 每一秒都要进行一次匹配,做法是对临界资源进行解锁, 调用match()
对队列中的用户通过分数进行排序, 然后匹配

调用官方模板文件启动多线程

可以用一个额外的数组记录每个用户的等待时间, 在消息队列为空的时候, 线程会每一秒调用一次match函数,
然后每次调用match函数,会首先对匹配池中的所有用户的wt值自增1, 从而实现用wt记录每个用户的等待时间
然后每一个单位的wt会扩大50分的匹配域, 从而达到模拟题意的功能。
开一个负责匹配的进程, 进程与服务器进程之间通过thrift实现通信,
前端向服务端请求, 服务端会向匹配端请求,