https://blog.csdn.net/qq_42417071/article/details/136328807

你现在是一个对歌词里日语的汉字标注假名的助手，
用户会给出日语歌词的原始文本，

1.你需要为歌词中出现的汉字标注假名，标注格式见此例：
	'日（ひ）'
注意：
1.take a deep breath and think step by step.

记住这一点

- 阅读剩余部分 -

# 16.6
import hashlib

def calc_md5(password):
    md5 = hashlib.md5()
    md5.update(password.encode('utf-8'))
    return md5.hexdigest()

db = {
    'michael': 'e10adc3949ba59abbe56e057f20f883e',
    'bob': '878ef96e86145580c38c87f0410ad153',
    'alice': '99b1c2188db85afee403b1536010c2c9'
}

def login(user, password):
    if calc_md5(password) == db[user]:
        return True
    else:
        return False

# 测试:
assert login('michael', '123456')
assert login('bob', 'abc999')
assert login('alice', 'alice2008')
assert not login('michael', '1234567')
assert not login('bob', '123456')
assert not login('alice', 'Alice2008')
print('ok')

# 16.6_2
import hashlib, random

def get_md5_(text):
    md5 = hashlib.md5()
    md5.update(text.encode('utf-8'))
    return md5.hexdigest()

db = {}

def register(username, password):
    db[username] = get_md5(password+username+'the-Salt')


class User(object):
    def __init__(self, username, password):
        self.username = username
        self.salt = ''.join([chr(random.randint(48, 122)) for i in range(20)])
        self.password = get_md5_(password + self.salt)

db = {
    'michael': User('michael', '123456'),
    'bob': User('bob', 'abc999'),
    'alice': User('alice', 'alice2008')
}

def get_md5(user, pws):
    return get_md5_(text=pws+user.salt)

def login(username, password):
    user = db[username]
    return user.password == get_md5(user, pws=password)

# 测试:
assert login('michael', '123456')
assert login('bob', 'abc999')
assert login('alice', 'alice2008')
assert not login('michael', '1234567')
assert not login('bob', '123456')
assert not login('alice', 'Alice2008')
print('ok')

# 天气获取
from urllib import request
import json
def fetch_data(url):
    req = request.Request(url)
    req.add_header('User-Agent','Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/127.0.0.0 Safari/537.36 Edg/127.0.0.0')
    with request.urlopen(req) as f:
        print('Status:',f.status,f.reason)
        for k,v in f.getheaders():
            print('%s: %s' % (k,v))
        return json.loads(f.read().decode('utf-8'))

# 测试
URL = 'https://api.weatherapi.com/v1/current.json?key=b4e8f86b44654e6b86885330242207&q=Xunwu&aqi=no'
data = fetch_data(URL)
print(data)

第二周周报

提交时间

2024/07/13

本周解决的问题

图的搜索算法

高速路网项目

遇到的困难

1.剪枝和启发式搜索的trick太难想了

2.高速路网调试挺难调

解决方法：

1.多做题积累灵感

2.一些#define DEBUG之类的输出调试方法，和一些gdb的断点调试方法

收获

1.更熟悉了一点gdb的操作

2.复习了git的操作

3.实操补充实现了一个小项目（高速路网）

经验

1.跑这个项目的调试可能还是得熟悉一下linux的相关操作

2.分工要合理 比如谁来写输出调试信息的接口 谁写核心算法 谁进行项目重构 不要像我一样在开发的途中写一堆debug输出

3.c语言实现这个项目的话感觉挺麻烦的...

对本周课程安排 意见 | 建议

暂无

对助教管理方式&教学方式 意见 | 建议

暂无

其他

暂无

高速路网-爱来自第三学期

这是一个项目题。

题目描述

题意分析

分为2个部分： 1.将图片转换为Graph 2.对Graph进行次短路算法

实现思路：

1.将图片转换为Graph

1.对读取的PNG进行广度优先染色，相同颜色的标一个id，并将每一个州的中心点记录 2.对染色后的地图的每一个州进行六个方向的查询，进行建边

2.次短路

使用迷阵题的代码，注意如果有多条最小路径，不能输出最小路径，要输出次小路径。 使用优先队列优化时间。

代码：

小学期结束后填坑。

https://se.jisuanke.com/_996/graph_lab（已填坑）

#include "state.h"
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <set>
void init_State(struct State *s)
{
    s->industry = nullptr;
    s->pre = nullptr;
    s->count = 0;
    s->cord.push_back({0, 0});
    s->mind = 0;
    s->Edge.clear();
    // TODO
}
void delete_State(struct State *s)
{
    // TODO
    delete[] s->industry;
    delete[] s->pre;
    std::vector<std::vector<edge>>().swap(s->Edge);
    std::vector<std::pair<int, int>>().swap(s->cord);
}
void parse(struct State *s, struct PNG *p)
{
    // TODO
    // 即统计图片中联通块的个数，或者叫做统计州
    // s中要存所有州的信息，以及他们的相邻关系
    // 便于后续查找最短路径
    // p->image 为读入的位图数据
    // 思路：循环对每个结点进行编号
    // 对每个结点进行6个方向的循环加边
    // p->image max_size 5000*5000

    // -1代表白色 -2代表黑色 1-n代表该像素块属于的编号
    int *ids = new int[p->width * p->height]();

    int id = 1;
    for (int y = 0; y < p->height; y++)
    {
        for (int x = 0; x < p->width; x++)
        {
            if (ids[y * p->width + x] == 0)
            {
                PXL *pixel = get_PXL(p, x, y);
                if (pixel->blue == 0 && pixel->green == 0 && pixel->red == 0)
                { // black
                    int tmpx, tmpy;
                    color(p, ids, -1, x, y, tmpx, tmpy);
                }
                else if ((pixel->red == 255 && pixel->blue == 255 && pixel->green == 255))
                { // white
                    int tmpx, tmpy;
                    color(p, ids, -2, x, y, tmpx, tmpy);
                }
                else
                { // 正常格子
                    int tmpx, tmpy;
                    color(p, ids, id, x, y, tmpx, tmpy);
                    s->cord.push_back({tmpx, tmpy});
                    id++;
                }
            }
        }
    }
    // 染色标记完毕

    // 开始记录每个州的发达程度industry
    s->count = id - 1;
    s->industry = new int[s->count + 1]();
    s->Edge.resize(s->count + 1);
    for (int y = 0; y < p->height; y++)
    {
        for (int x = 0; x < p->width; x++)
        {
            if (ids[y * p->width + x] != -1 && ids[y * p->width + x] != -2)
            {
                int _id = get_id(ids, x, y, p->width, p->height);
                if (s->industry[_id] != 0)
                {
                    continue;
                }
                PXL *pixel = get_PXL(p, x, y);
                s->industry[_id] = cal_industry(pixel);
            }
        }
    }

    // 对每个州进行六方向连接 建边  标记某个顶点是否已经扩展好边
    int dir[6][2] = {
        {-8, 0}, {8, 0}, {-4, -8}, {4, -8}, {-4, 8}, {4, 8}};
    for (size_t i = 1; i <= s->count; i++)
    {
        std::pair<int, int> cord = s->cord[i];
        for (int j = 0; j < 6; j++)
        {
            int tx = cord.first + dir[j][0];
            int ty = cord.second + dir[j][1];

            if (in(tx, ty, p->width, p->height))
            {
                int toid = get_id(ids, tx, ty, p->width, p->height);
                if (toid != 0 && toid != -1 && toid != -2)
                {
                    s->Edge[i].push_back({toid, s->industry[toid], 1});
                }
            }
        }
    }

#ifdef DEBUG
    for (int i = 1; i <= s->count; i++)
    {
        printf("(%d,%d) ", s->cord[i].first, s->cord[i].second);
    }
    puts("");
#endif // 打印每个州的中心点

#ifdef DEBUG
    int cnt = 0;
    for (int i = 1; i <= s->count; i++)
    {
        for (edge node : s->Edge[i])
        {
            printf("%d %d %d\n ", i, node.v, node.w);
            cnt++;
        }
    }
    printf("%d %d\n", s->count, cnt);
#endif // 打印每个顶点的邻接表

#ifdef DEBUG
    for (int i = 1; i <= s->count; i++)
    {
        std::cout << s->industry[i] << " ";
    }
    puts("");
#endif // 打印每个州的发达程度

#ifdef DEBUG
    for (int i = 0; i < p->height; i++)
    {
        for (int j = 0; j < p->width; j++)
        {
            std::cout << std::setw(5) << ids[i * p->width + j] << " ";
        }
        puts("");
    }
#endif // 打印染色后的图

    delete[] ids;
}

int solve1(struct State *s)
{
    int ans = dij2(s, 1);
    return ans;
}

int solve2(struct State *s)
{
    // TODO
    if (s->pre == nullptr)
    {
        solve1(s);
    }
    int *path = new int[s->count + 1]();
    int pathid = 0;
    getpath(path, s->count, pathid, s->pre);
#ifdef DEBUG_PATH
    printf("----This is Shortest PATH----\n");
    for (int i = 0; i < pathid; i++)
    {
        printf("%d", path[i]);
        if (i != pathid - 1)
        {
            printf("->");
        }
    }
    puts("");
    printf("-----------------------------\n");
#endif
    long long ans = 0x3f3f3f3f;
    for (int i = 0; i < pathid - 1; i++)
    {
        int u = path[i];
        int v = path[i + 1];
        for (edge &e : s->Edge[u])
        {
            if (e.v == v)
            {
                e.f = 0;
            }
        }

        // int *pre = nullptr;
        long long tmp = dij2(s, 0); // ans
        // int *tmppath = new int[s->count + 1]();
        // int tmpid = 0;
        // getpath(tmppath, s->count, tmpid, pre);
#ifdef DEBUG_TMP_PATH
        printf("----This is the Second Shortest PATH----\n");
        for (int i = 0; i < tmpid; i++)
        {
            printf("%d", tmppath[i]);
            if (i != tmpid - 1)
            {
                printf("->");
            }
        }
        printf(" value:%d",tmp);
        puts("");
        printf("-----------------------------\n");
#endif
        // delete[] tmppath;
        if (ans > tmp)
        {
            if(s->mind&&tmp>s->mind)
            {
                ans = tmp;
            }
        }
        for (edge &e : s->Edge[u])
        {
            if (e.v == v)
            {
                e.f = 1;
            }
        }
    }
    delete[] path;
    return ans;
}

// long long dij3(struct State *s, int *(&pre))
// {
//     if (pre == nullptr)
//     {
//         pre = new int[s->count + 1]();
//     }
//     struct node
//     {
//         long long dis, u;

//         bool operator>(const node &a) const { return dis > a.dis; }
//     };
//     const long long inf = 0x3f3f3f3f;
//     long long *dis = new long long[s->count + 1];
//     int *vis = new int[s->count + 1]();
//     std::priority_queue<node, std::vector<node>, std::greater<node>> q;
//     for (size_t i = 0; i < s->count + 1; i++)
//     {
//         dis[i] = inf;
//     }
//     dis[1] = 0;
//     q.push({0, 1});
//     while (!q.empty())
//     {
//         int u = q.top().u;
//         q.pop();
//         if (vis[u])
//             continue;
//         vis[u] = 1;
//         for (auto ed : s->Edge[u])
//         {
//             int v = ed.v, w = ed.w;
//             if (ed.f)
//             {
//                 if (dis[v] > dis[u] + w)
//                 {
//                     dis[v] = dis[u] + w;

//                     pre[v] = u;
// #ifdef DEBUG_DIJPATH
//                     printf("%d->%d:%d\n", u, v, w);
// #endif

//                     q.push({dis[v], v});
//                 }
//             }
//         }
//     }
// #ifdef DEBUG_1
//     for (int i = 0; i < s->count; i++)
//     {
//         printf("pre[%d]:%d ", i, s->pre[i]);
//     }
// #endif
//     long long ans = dis[s->count];
//     delete[] vis;
//     delete[] dis;
//     return ans;
// }

long long dij2(struct State *s, int opt)
{
    if (s->pre == nullptr && opt)
    {
        s->pre = new int[s->count + 1]();
    }
    struct node
    {
        long long dis, u;

        bool operator>(const node &a) const { return dis > a.dis; }
    };
    const long long inf = 0x3f3f3f3f;
    long long *dis = new long long[s->count + 1];
    int *vis = new int[s->count + 1]();
    std::priority_queue<node, std::vector<node>, std::greater<node>> q;
    for (size_t i = 0; i < s->count + 1; i++)
    {
        dis[i] = inf;
    }
    dis[1] = 0;
    q.push({0, 1});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto ed : s->Edge[u])
        {
            int v = ed.v, w = ed.w;
            if (ed.f)
            {
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    if (opt)
                    {
                        s->pre[v] = u;
#ifdef DEBUG_DIJPATH
                        printf("%d->%d:%d\n", u, v, w);
#endif
                    }
                    q.push({dis[v], v});
                }
            }
        }
    }
#ifdef DEBUG_1
    for (int i = 0; i < s->count; i++)
    {
        printf("pre[%d]:%d ", i, s->pre[i]);
    }
#endif
    long long ans = dis[s->count];
    if(opt)
    {
        s->mind = ans;
    }
    delete[] vis;
    delete[] dis;
    return ans;
}

/// @brief 获取路径
/// @param path 路径存入path
/// @param x 从x往前推
/// @param pathid path大小存入pathid
/// @param pre 前驱结点数组
void getpath(int *path, int x, int &pathid, int *pre)
{
    if(pre==nullptr)
    {
        return;
    }
    if (x == 1)
    {
        path[pathid++] = x;
        return;
    }
    getpath(path, pre[x], pathid, pre);
    path[pathid++] = x;
}

inline bool in(int x, int y, int width, int height)
{
    return x >= 0 && x < width && y >= 0 && y < height;
}

// aid function
// 对图进行染色 用来标记id
void color(struct PNG *p, int *map, const int id, const int sx, const int sy, int &center_x, int &center_y)
{
    int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    int max_x = -1, max_y = -1;
    int min_x = INT_MAX, min_y = INT_MAX;
    std::queue<std::pair<int, int>> q;
    q.push({sx, sy});
    PXL *origin_pxl = get_PXL(p, sx, sy);
    map[sy * p->width + sx] = id;
    while (!q.empty())
    {
        std::pair<int, int> coordinate = q.front();
        q.pop();

        max_x = max(max_x, coordinate.first);
        max_y = max(max_y, coordinate.second);
        min_x = min(min_x, coordinate.first);
        min_y = min(min_y, coordinate.second);

        for (int i = 0; i < 4; i++)
        {
            int tx = coordinate.first + dir[i][0];
            int ty = coordinate.second + dir[i][1];
            if (in(tx, ty, p->width, p->height))
            {
                PXL *pixel = get_PXL(p, tx, ty);
                if ((*pixel == *origin_pxl) && map[ty * p->width + tx] == 0)
                {
                    map[ty * p->width + tx] = id;
                    q.push({tx, ty});
                }
            }
        }
    }
    center_x = (max_x + min_x) / 2;
    center_y = (max_y + min_y) / 2;
}

int get_id(int *ids, int x, int y, int width, int height)
{
    if (!in(x, y, width, height))
    {
        return 0;
    }
    return ids[y * width + x];
}

int cal_industry(PXL *pxl)
{
    return (255 * 255 * 3 - pxl->red * pxl->red - pxl->green * pxl->green - pxl->blue * pxl->blue);
}

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    return b;
}

int min(int a, int b)
{
    if (a < b)
    {
        return a;
    }
    return b;
}