头像

皓首不倦




离线:10分钟前


最近来访(85)
用户头像
阿吉迷得牛炖咖喱略
用户头像
1847497680
用户头像
也.
用户头像
科宇
用户头像
DarksideCoder
用户头像
我是灞波儿奔
用户头像
Magic_KID
用户头像
upup
用户头像
AcKing_HIT
用户头像
小松鼠1996
用户头像
凉宫
用户头像
凌乱之风
用户头像
甜菜小笼包
用户头像
咖喱鸡排饭
用户头像
15084948533
用户头像
狂气山脉
用户头像
JayZ
用户头像
joykiller
用户头像
自伤无色
用户头像
QAQlzy

活动打卡代码 AcWing 3188. manacher算法

皓首不倦
1个月前
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 20000005;       // 最长字符串长度


int P[MAX_N];       // P[i]表示以i位置为中心的最长回文子串长度
char __s[MAX_N];


// 返回最长回文子串长度
char ss[MAX_N * 2 + 5];
int manacher(char* s) {
    int n = strlen(s);
    if (n <= 1) {
        return n;
    }

    // 构造新字符串
    for (int i = 0; i < 2*n+1; i++) {
        if (i & 1) {
            ss[i] = s[i>>1];
        } else {
            ss[i] = '#';
        }
    }

    P[0] = 1;
    int L = 0, R = 0;       // 当前已经找到的所有回文子串中结束位置最靠右的回文子串的左右边界
    int max_r = 1;
    for (int i = 1; i < 2*n+1; i++) {
        if (i > R) {
            int ll = i, rr = i;
            while (ll-1 >= 0 && rr+1 < 2*n+1 && ss[ll-1] == ss[rr+1]) {
                ll--, rr++;
            }
            P[i] = rr - i + 1;
        } else {
            int j = L + R - i;
            int l_bound = j - P[j] + 1;
            if (l_bound > L) {
                P[i] = P[j];
            } else if (l_bound < L) {
                P[i] = R - i + 1;
            } else {
                int ll = i-P[j]+1, rr = i+P[j]-1;
                while (ll-1 >= 0 && rr+1 < 2*n+1 && ss[ll-1] == ss[rr+1]) {
                    ll--, rr++;
                }
                P[i] = rr - i + 1;
            }
        }

        if (i + P[i] - 1 > R) {
            R = i + P[i] - 1;
            L = i - P[i] + 1;
        }

        max_r = max(max_r, P[i]);
    }

    return max_r - 1;
}




int main(void) {
    scanf("%s", __s);
    printf("%d\n", manacher(__s));
    return 0;
}




皓首不倦
1个月前



#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;


const int MAX_TWO_SAT_N = 1000005 * 2;
const int MAX_TWO_SAT_M = MAX_TWO_SAT_N * 2;
const int INF = 0x3f3f3f3f;

int __two_sat_h[MAX_TWO_SAT_N], __two_sat_ne[MAX_TWO_SAT_M], __two_sat_e[MAX_TWO_SAT_M];
int __two_sat_dfn[MAX_TWO_SAT_N], __two_sat_low[MAX_TWO_SAT_N];
int __two_sat_node2sccid[MAX_TWO_SAT_N], __two_sat_visit[MAX_TWO_SAT_N];



struct edge {
    int a, b;
};

class TWO_SAT {
public:
    TWO_SAT(int n, vector<edge>& edges) : node_n(n), h(__two_sat_h), ne(__two_sat_ne), e(__two_sat_e),
                                          dfn(__two_sat_dfn), low(__two_sat_low), node2sccid(__two_sat_node2sccid),
                                          visit(__two_sat_visit), idx(0), time_v(0), scc_id_cnt(1) {
        memset(h, -1, sizeof(int) * (node_n*2 + 1));
        for (int i = 0; i < edges.size(); i++) {
            int a = edges[i].a, b = edges[i].b;

            int aa = a < 0 ? -a : a+n;
            int bb = b < 0 ? -b+n : b;
            __add_edge(aa, bb);

            aa = a < 0 ? -a+n : a;
            bb = b < 0 ? -b : b+n;
            __add_edge(bb, aa);
        }
    }

    bool get_solution(int* ans) {
        int max_node_num = node_n * 2;
        memset(dfn, 0x3f, sizeof(int) * (max_node_num + 1));
        memset(low, 0x3f, sizeof(int) * (max_node_num + 1));
        memset(node2sccid, 0, sizeof(int) * (max_node_num + 1));
        memset(visit, 0, sizeof(int) * (max_node_num + 1));

        time_v = 0;
        buf.clear();
        scc_id_cnt = 1;

        for (int node = 1; node <= max_node_num; node++) {
            if (h[node] == -1) {
                continue;
            }

            if (dfn[node] == INF) {
                __dfs(node);
            }
        }

        memset(ans, 0, sizeof(int) * (node_n + 1));
        for (int node = 1; node <= node_n; node++) {
            if (node2sccid[node] == node2sccid[node+node_n] && node2sccid[node] != 0) {
                return false;
            }

            if (node2sccid[node] < node2sccid[node+node_n]) {
                ans[node] = 1;
            }
        }

        return true;
    }

private:
    int node_n;
    int *h, *ne, *e;
    int *dfn, *low;
    int *node2sccid;
    int *visit;
    int idx;
    int time_v;
    int scc_id_cnt;
    vector<int> buf;

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

    void __dfs(int cur) {
        time_v++;
        dfn[cur] = low[cur] = time_v;
        buf.push_back(cur);

        int pos = buf.size() - 1;
        for (int i = h[cur]; ~i; i = ne[i]) {
            int next = e[i];
            if (visit[next]) {
                continue;
            }

            if (dfn[next] == INF) {
                __dfs(next);
                low[cur] = min(low[cur], low[next]);
            } else {
                low[cur] = min(low[cur], dfn[next]);
            }
        }

        if (low[cur] == dfn[cur]) {
            while (buf.size() > pos) {
                int node = buf.back(); buf.pop_back();
                node2sccid[node] = scc_id_cnt;
                visit[node] = 1;
            }
            scc_id_cnt += 1;
        }
    }


};

int ans[1000005];

int main() {
    int n, m;
    int a, b, v1, v2;
    scanf("%d %d", &n, &m);

    vector<edge> edges;
    while (m--) {
        scanf("%d %d %d %d", &a, &v1, &b, &v2);
        if (v1 == 0) {
            a = -a;
        }

        if (v2 == 0) {
            b = -b;
        }

        edges.push_back({a, b});
    }

    TWO_SAT algo(n, edges);
    if (algo.get_solution(ans)) {
        printf("POSSIBLE\n");
        for (int i = 1; i <= n; i++) {
            printf("%d ", ans[i]);
        }
    } else {
        printf("IMPOSSIBLE\n");
    }

    return 0;
}





皓首不倦
3个月前


#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;


int arr[1005];
int cache1[1005][1005];
int cache2[1005][1005];


int right(int i, int j);
int left(int i, int j) {
    if (cache1[i][j] != -1) {
        return cache1[i][j];
    }

    if (i == j) {
        return arr[i];
    }

    int& ret = cache1[i][j];
    int X = arr[j], L = left(i, j-1), R = right(i, j-1);
    if (X == R) {
        return ret = 0;
    }

    if (X < L && X < R) {
        return ret = X;
    }

    if (X > L && X > R) {
        return ret = X;
    }

    if (L > R) {
        return ret = X - 1;
    } else {
        return ret = X + 1;
    }
}

int right(int i, int j) {
    if (cache2[i][j] != -1) {
        return cache2[i][j];
    }

    if (i == j) {
        return arr[i];
    }

    int& ret = cache2[i][j];
    int X = arr[i], L = left(i+1, j), R = right(i+1, j);
    if (X == L) {
        return ret = 0;
    }

    if (X < L && X < R) {
        return ret = X;
    }

    if (X > L && X > R) {
        return ret = X;
    }

    if (L < R) {
        return ret = X - 1;
    } else {
        return ret = X + 1;
    }
}



int main(void) {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", arr+i);
        }

        if (n == 1) {
            printf("1\n");
            continue;
        }

        memset(cache1, -1, sizeof(cache1));
        memset(cache2, -1, sizeof(cache2));
        if (arr[0] == left(1, n-1)) {
            printf("0\n");
        } else {
            printf("1\n");
        }

    }

    return 0;
}




活动打卡代码 AcWing 1322. 取石子游戏

皓首不倦
3个月前


#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;


int arr[1005];
int cache1[1005][1005];
int cache2[1005][1005];


int right(int i, int j);
int left(int i, int j) {
    if (cache1[i][j] != -1) {
        return cache1[i][j];
    }

    if (i == j) {
        return arr[i];
    }

    int& ret = cache1[i][j];
    int X = arr[j], L = left(i, j-1), R = right(i, j-1);
    if (X == R) {
        return ret = 0;
    }

    if (X < L && X < R) {
        return ret = X;
    }

    if (X > L && X > R) {
        return ret = X;
    }

    if (L > R) {
        return ret = X - 1;
    } else {
        return ret = X + 1;
    }
}

int right(int i, int j) {
    if (cache2[i][j] != -1) {
        return cache2[i][j];
    }

    if (i == j) {
        return arr[i];
    }

    int& ret = cache2[i][j];
    int X = arr[i], L = left(i+1, j), R = right(i+1, j);
    if (X == L) {
        return ret = 0;
    }

    if (X < L && X < R) {
        return ret = X;
    }

    if (X > L && X > R) {
        return ret = X;
    }

    if (L < R) {
        return ret = X - 1;
    } else {
        return ret = X + 1;
    }
}



int main(void) {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", arr+i);
        }

        if (n == 1) {
            printf("1\n");
            continue;
        }

        memset(cache1, -1, sizeof(cache1));
        memset(cache2, -1, sizeof(cache2));
        if (arr[0] == left(1, n-1)) {
            printf("0\n");
        } else {
            printf("1\n");
        }

    }

    return 0;
}



皓首不倦
3个月前




'''
枚举B1所有约数,然后验证约数和b0的最小公倍数是不是b1, 以及和a0的最大公约数是不是a1
枚举约数时候用dfs枚举质因数的次幂的组合方案的方式进行
'''



def get_prime(N):
    prime_vals = []
    flag = [True] * (N+1)
    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)

        for p_val in prime_vals:
            if val * p_val > N:
                break

            flag[val * p_val] = False

            if val % p_val == 0:
                break

    return prime_vals

primes = get_prime(100000)


# 分解质因数函数,返回元组数组[ (质因子1, 次幂1), (质因子2, 次幂2), (质因子3, 次幂3) ...... ]
# 质因子的数值升序排列
def devide_prime(val):
    ans = []

    for i in primes:
        if i*i > val:
            break

        if val % i == 0:
            cnt = 0
            while val % i == 0:
                val //= i
                cnt += 1

            ans.append((i, cnt))

        if val == 1:
            break

    # 特判最后可能剩下的大于sqrt(val)的最大的质因子
    if val != 1:
        ans.append((val, 1))

    return ans

# 获取所有约数的函数
def get_approximate_numbers(val):
    ans = []
    primes = devide_prime(val)

    def dfs(idx, prev_val):
        if prev_val*prev_val > val:
            return

        if idx >= len(primes):
            ans.append(prev_val)
            if val // prev_val != prev_val:
                ans.append(val // prev_val)

            return

        base = None
        for pow_val in range(primes[idx][1]+1):
            if pow_val == 0:
                base = 1
            else:
                base *= primes[idx][0]

            dfs(idx+1, prev_val * base)
    dfs(0, 1)

    return ans

def gcd(a, b):
    if a > b:
        a, b, = b, a

    while a:
        a, b = b % a, a
    return b


n = int(input())
for _ in range(n):
    a0, a1, b0, b1 = map(int, input().split())
    app_vals = get_approximate_numbers(b1)

    cnt = 0
    for app_val in app_vals:
        if b0 * app_val == b1 * gcd(app_val, b0):
            if gcd(app_val, a0) == a1:
                cnt += 1

    print(cnt)





活动打卡代码 AcWing 1053. 修复DNA

皓首不倦
3个月前


# import sys
# sys.stdin = open("data.txt", "r")


'''
基于AC自动机的DP
'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
    def __init__(self, fa):
        self.s = ''             # end节点自己本身的单词
        self.fail_s = []        # fail指针指向的节点序列的单词列表(如果fail指针指向的节点是一个end节点,此字段保存所有这些单词的列表)
        self.next = {}          # 边和子节点映射
        self.is_end = False     # 是否是end节点
        self.fail = None        # ac自动机的fail指针
        self.fa = fa            # 父节点指针
        self.id = 0             # 节点的id号

class AcTrie:
    def __init__(self):
        self.root = AcTrieNode(None)
        self.__idx = 1

    def append(self, s: str):
        cur = self.root
        for ch in s:
            if ch not in cur.next:
                new_node = AcTrieNode(cur)
                new_node.id = self.__idx
                self.__idx += 1

                new_node.s = cur.s + ch
                cur.next[ch] = new_node

            cur = cur.next[ch]
        cur.is_end = True

    # 构建ac自动机接口
    def build(self, s_list = []):
        # 第一步是构建普通的Trie
        for s in s_list:
            self.append(s)

        # 层次遍历构建Fail指针
        que = deque()
        que.append(self.root)

        depth = 0
        while len(que) > 0:
            node_num = len(que)

            for _ in range(node_num):
                cur = que.popleft()
                if depth == 1:
                    # 根节点下面的第一层word长度是1,是没有后缀的,fail指针全部指向root
                    cur.fail = self.root
                elif depth != 0:
                    cur.fail = self.root

                    # 循环找最长后缀的候选
                    p = cur.fa.fail
                    last_ch = cur.s[-1]
                    while True:
                        if not p:
                            break

                        if last_ch in p.next:
                            cur.fail = p.next[last_ch]

                            f = cur.fail
                            if f.is_end:
                                # 如果fail指针指向的节点是一个end节点,或者这个节点的fail_s列表不为空,需要添加这些单词到cur节点的fail_s列表中
                                cur.fail_s.append(f.s)

                            # fail指针指向的节点中fail_s里面的单词必须全部继承下来,因为这些单词也是后缀的备选
                            for s in f.fail_s:
                                cur.fail_s.append(s)

                            break
                        else:
                            p = p.fail

                for new_node in cur.next.values():
                    que.append(new_node)

            depth += 1

    # 获取节点状态转移的表 [0号点转移表,1号点转移表, ......]
    def get_stat_map(self):
        ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

        def dfs(node: AcTrieNode):
            for ch in 'AGCT':
                if ch in node.next:
                    if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
                        # 发生了匹配,下一个字符不可能是ch
                        ans[node.id][ch] = None
                    else:
                        ans[node.id][ch] = node.next[ch].id

                else:
                    cur = node
                    while True:
                        if ch in cur.next:
                            if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
                                # 发生了匹配,下一个字符不可能是ch
                                ans[node.id][ch] = None
                            else:
                                ans[node.id][ch] = cur.next[ch].id

                            break

                        else:
                            if cur.fail is not None:
                                cur = cur.fail
                            else:
                                ans[node.id][ch] = cur.id
                                break

            for child in node.next.values():
                dfs(child)

        dfs(self.root)
        return ans

case_id = 1
while True:
    n = int(input())
    if n == 0:
        break

    ac_trie = AcTrie()

    for _ in range(n):
        ac_trie.append(input())

    ac_trie.build()
    stat_map = ac_trie.get_stat_map()

    s = input().strip()
    cache = [[None]*(len(s)+1) for _ in range(20*n)]
    n = len(s)

    # dp(stat, ii)表示Ac自动机状态为stat情况下,继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
    def dp(stat, ii):
        if ii == n:
            return 0

        if cache[stat][ii] is not None:
            return cache[stat][ii]

        ans = 0x7fffffff
        for ch in 'AGCT':
            if stat_map[stat][ch] is None:
                continue

            t = 0
            if s[ii] != ch:
                t += 1

            t += dp(stat_map[stat][ch], ii+1)
            ans = min(ans, t)

        # print(stat, ii, ans, n)
        cache[stat][ii] = ans
        return ans

    ans = dp(ac_trie.root.id, 0)
    print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
    case_id += 1




皓首不倦
3个月前



# import sys
# sys.stdin = open("data.txt", "r")


'''
基于AC自动机的DP
'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
    def __init__(self, fa):
        self.s = ''             
        self.fail_s = []        
        self.next = {}          
        self.is_end = False     
        self.fail = None        
        self.fa = fa            
        self.id = 0             

class AcTrie:
    def __init__(self):
        self.root = AcTrieNode(None)
        self.__idx = 1

    def append(self, s: str):
        cur = self.root
        for ch in s:
            if ch not in cur.next:
                new_node = AcTrieNode(cur)
                new_node.id = self.__idx
                self.__idx += 1

                new_node.s = cur.s + ch
                cur.next[ch] = new_node

            cur = cur.next[ch]
        cur.is_end = True

    def build(self, s_list = []):
        for s in s_list:
            self.append(s)

        que = deque()
        que.append(self.root)

        depth = 0
        while len(que) > 0:
            node_num = len(que)

            for _ in range(node_num):
                cur = que.popleft()
                if depth == 1:
                    cur.fail = self.root
                elif depth != 0:
                    cur.fail = self.root

                    p = cur.fa.fail
                    last_ch = cur.s[-1]
                    while True:
                        if not p:
                            break

                        if last_ch in p.next:
                            cur.fail = p.next[last_ch]

                            f = cur.fail
                            if f.is_end:
                                cur.fail_s.append(f.s)

                            for s in f.fail_s:
                                cur.fail_s.append(s)

                            break
                        else:
                            p = p.fail

                for new_node in cur.next.values():
                    que.append(new_node)

            depth += 1

    # 获取节点状态转移的表 [0号点转移表,1号点转移表, ......]
    def get_stat_map(self):
        ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

        def dfs(node: AcTrieNode):
            for ch in 'AGCT':
                if ch in node.next:
                    if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
                        # 发生了匹配,下一个字符不可能是ch
                        ans[node.id][ch] = None
                    else:
                        ans[node.id][ch] = node.next[ch].id

                else:
                    cur = node
                    while True:
                        if ch in cur.next:
                            if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
                                # 发生了匹配,下一个字符不可能是ch
                                ans[node.id][ch] = None
                            else:
                                ans[node.id][ch] = cur.next[ch].id

                            break

                        else:
                            if cur.fail is not None:
                                cur = cur.fail
                            else:
                                ans[node.id][ch] = cur.id
                                break

            for child in node.next.values():
                dfs(child)

        dfs(self.root)
        return ans

case_id = 1
while True:
    n = int(input())
    if n == 0:
        break

    ac_trie = AcTrie()

    for _ in range(n):
        ac_trie.append(input())

    ac_trie.build()
    stat_map = ac_trie.get_stat_map()

    s = input().strip()
    cache = [[None]*(len(s)+1) for _ in range(20*n)]
    n = len(s)

    # dp(stat, ii)表示Ac自动机状态为stat情况下,继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
    def dp(stat, ii):
        if ii == n:
            return 0

        if cache[stat][ii] is not None:
            return cache[stat][ii]

        ans = 0x7fffffff
        for ch in 'AGCT':
            if stat_map[stat][ch] is None:
                continue

            t = 0
            if s[ii] != ch:
                t += 1

            t += dp(stat_map[stat][ch], ii+1)
            ans = min(ans, t)

        # print(stat, ii, ans, n)
        cache[stat][ii] = ans
        return ans

    ans = dp(ac_trie.root.id, 0)
    print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
    case_id += 1





皓首不倦
3个月前




import sys





'''
S(i) 表示开始工作时间小于等于i的雇佣员工的总数
需要满足的差分约束:
1. S(i) >= S(i-1) (i=1,2,3,4,....23)
2. S(0) >= 0

对于i >= 0 and i <= 8 而言
3. S(i) + S(23) - S(i+16) >= arr[i]
对于i >= 9 and i <= 23 而言
3. S(i) - S(i-8) >= arr[i]

4. S(i) - S(i-1) <= cnt[i], cnt[i]是从i时间开始工作的人的数量

从0到1000枚举S(23), 如果有一个S(23)能够让差分系统的最小解 小于等于 申请人的数量
就找到了一组可行解,找最小的S(23)即是答案

'''


from collections import Counter
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getInfo(min_path=True)

    # 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMaxPathLen(self):
        return self.getInfo(min_path=False)

    # min_path表示求的是最短路径还是最长路径
    def getInfo(self, min_path = True):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if (min_path == True and w < 0) and (min_path == False and w > 0):
                    # 有正环或者负环提前退出
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:

                    if dis[a] == 0x7fffffff:
                        if w == -0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = 0x7fffffff

                    elif dis[a] == -0x7fffffff:
                        if w == 0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = -0x7fffffff
                    else:
                        new_dis = dis[a] + w


                    if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
                        dis[b] = new_dis
                        update_flag = True

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return [[node, dis[node]] for node in range(1, self.max_node_num+1)]



t = int(input())
for _ in range(t):
    arr = list( map(int, input().split()) )
    n = int(input())
    possible = [0] * 24
    for i in range(n):
        possible[int(input())] += 1

    if sum(possible) == 0:
        print(0)
    else:
        find_ans = False
        min_cost = 0x7fffffff
        for S23 in range(0, n+1):
            # 为了方便计算,所有数值下标都往后移动了一个位置, 超级源点已定义为23, 实际存储时候用24的位置
            edges = []

            # S(i) >= S(i-1) (i=1,2,3,4,....22)
            for i in range(1, 23):
                edges.append((i-1+1, i+1, 0))

            # S(22) <= S(23)
            edges.append((24, 22+1, 0))

            # S(i) >= S(i+16) - S23 + arr[i]
            for i in range(8):
                edges.append((i+16+1, i+1, arr[i]-S23))

            # S(i) >= S(i-8) + arr[i]
            for i in range(8, 23):
                edges.append((i-8+1, i+1, arr[i]))

            # S(23) - S(15) >= arr[23], S(15) <= S(23) - arr[23]
            edges.append((15+1, 24, -(S23 - arr[23])))

            # S(0) <= possible[0]
            edges.append((0+1, 24, -possible[0]))

            # S(i) - S(i-1) <= possible[i] i = 1, 2, 3..... 22
            for i in range(1, 23):
                edges.append((i+1, i-1+1, -possible[i]))

            # S(23) - S(22) <= possible[23] => S(22) >= S(23) - possible[23]
            edges.append((24, 22+1, S23 - possible[23]))


            # 虚拟源点向所有点添加边 S(i) >= 0, i = 0, 1, 2, ..... 22
            for i in range(23):
                edges.append((24, i+1, 0))

            algo = SPFA(24, edges, is_directed=True, max_node_num=24)
            ans = algo.getMaxPathLen()
            if ans is None:
                continue

            find_ans = True
            min_cost = min(min_cost, S23)

        if find_ans:
            print(min_cost)
        else:
            print('No Solution')






皓首不倦
3个月前

import sys

'''
将1号节点固定在0位置,构造超级源点建图,单源最短路求最大解,如果图里面有负环,则无解
如果最大解最后一个数值能够到0x7ffffffe, 则最前面和最后面的奶牛之间的距离可以无穷大
剩下的情况就是正常的查分约束的解
'''

from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getInfo(min_path=True)

    # 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMaxPathLen(self):
        return self.getInfo(min_path=False)

    # min_path表示求的是最短路径还是最长路径
    def getInfo(self, min_path = True):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if (min_path == True and w < 0) and (min_path == False and w > 0):
                    # 有正环或者负环提前退出
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        cnt = [0] * (self.max_node_num + 1)
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:
                    if dis[a] == 0x7fffffff:
                        if w == -0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = 0x7fffffff

                    elif dis[a] == -0x7fffffff:
                        if w == 0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = -0x7fffffff
                    else:
                        new_dis = dis[a] + w


                    if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
                        dis[b] = new_dis
                        cnt[b] = cnt[a] + 1
                        update_flag = True

                        if cnt[b] >= self.max_node_num:
                            return None

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return dis

edges = []
n, m1, m2 = map(int, input().split())
for i in range(m1):
    a, b, w = map(int, input().split())
    if a > b:
        a, b = b, a

    # val(b) - val(a) <= w
    edges.append((a, b, w))

for i in range(m2):
    a, b, w = map(int, input().split())
    if a > b:
        a, b = b, a

    # val(b) - val(a) >= w
    edges.append((b, a, -w))


for i in range(2, n+1):
    # 后一个要大于等于前一个
    # val(i) >= val(i-1)
    edges.append((i, i-1, 0))

    # 从2开始的每一个点都小于等于一个极大值,这样才能让超级源点对每一个点都是可达的,注意这里不能取0x7fffffff, 这个数值表示的是不可达
    edges.append((n+1, i, 0x7ffffffe))

# 超级源点是n+1, 要求1号点固定在0位置
edges.append((1, n+1, 0))
edges.append((n+1, 1, 0))


# print(edges)
algo = SPFA(n+1, edges, is_directed=True, max_node_num=n+1)
ans = algo.getMinPathLen()
if ans is None:
    print(-1)
else:
    if ans[n] == 0x7ffffffe:
        print(-2)
    else:
        print(ans[n])



活动打卡代码 AcWing 900. 整数划分

皓首不倦
4个月前
cache = [[None]* 1005 for _ in range(1005)]

# dp(i, j)表示用小于等于j的数凑i的所有方案的数量
def dp(i, j):
    if i == 0:
        return 1

    if j == 1:
        return 1

    if cache[i][j] is not None:
        return cache[i][j]

    if j > i:
        ans = dp(i, i)
    else:
        ans = dp(i-j, j) + dp(i, j-1)

    cache[i][j] = ans % 1000000007
    return ans % 1000000007

n = int(input())
print(dp(n, n))