FXJFXJ
0%

发表于 更新于 分类于
本文字数： 291 阅读时长 ≈ 1 分钟

[[../../ACM/数论/威尔逊定理]]

给定 \(n\), 计算

\(\sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor\)

思路： 容易想到威尔逊定理

  1. 若 \(3k+7\) 是质数，则 \((3k+6)!\equiv-1\pmod{3k+7}\)
阅读全文 »

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 4 分钟

1004 智能车

Description

看是否存在若干中方案使得 \(p_{x_{1}}+p_{x_{2}}+p_{x_{3}}+\dots=c\) ## Input 一共 \(T\) 组数据，对于每一组数据： \(\boxed{\begin{array}&n&c\\p_{1}&p_{2}&p_{3}&\dots&p_{n}\end{array}}\) 数据范围： - \(1\leq T\leq 10\) - \(1\leq n\leq 5\times 10^4\) - \(1\leq c\leq 500\) - \(1\leq p_{i}\leq c\) ## Output 找出一个方案满足最大值和最小值相差最小，求出最小的差值。如果不存在满足条件的方案，输出−1。 ## Sample Input 

1
2
3
1
4 10
3 7 2 5
## Sample Output 
1
3
阅读全文 »

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 15 分钟

summary: 第十一届重庆市大学生程序设计竟赛西南大学, 2023 年 12 月 17 日

A Yesterday Once More

原题

2 seconds

256 megabytes

阅读全文 »

发表于 更新于 分类于
本文字数： 3.5k 阅读时长 ≈ 13 分钟

需要多加训练 Codeforces Round 913 (Div. 3) #div3

A Rook

比较简单 #cf800 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int t;
string a;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>t;
    while(t--)
    {
        cin>>a;
        for (int i = 1; i <= 8;i++)
        {
            if(i==a[1]-48)
                continue;
            cout << a[0] << i << '\n';
        }
        for (int i = 'a'; i <= 'h';i++)
        {
            if(i==a[0])
                continue;
            cout << (char)i << a[1] << '\n';
        }
    }
}

阅读全文 »

发表于 更新于 分类于
本文字数： 134 阅读时长 ≈ 1 分钟

1 用到了 [[../../ACM/数论/裴蜀定理]]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> dp;
int n, l[310], c[310];
int gcd(int a, int b)
{
    return !b ? a : gcd(b, a % b);
}
void solve()
{
    dp[0] = 0;
    map<int, int>::iterator it;
    for (int i = 1; i <= n; i++)
    {
        for (it = dp.begin(); it != dp.end(); it++)
        {
            int temp = gcd(l[i], it->first);
            if (dp.find(temp) != dp.end())
                dp[temp] = min(dp[temp], c[i] + it->second);
            else
                dp[temp] = c[i] + it->second;
        }
    }
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    solve();
    if (dp.find(1) == dp.end())
    {
        cout << "-1" << endl;
        return 0;
    }
    cout << dp[1] << endl;
}

发表于 更新于 分类于
本文字数： 892 阅读时长 ≈ 3 分钟

Description

狐狸 Ciel 即将发表一篇关于 FOCS (狐狸操作计算机系统，读作 "狐狸")的论文。她听到一个传言：论文的作者列表总是按照 lexicographical 顺序排列。 在查看了一些例子后，她发现有时并非如此。在一些论文中，作者姓名并不是按照正常意义上的 lexicographical 顺序排列的。但是，在对字母表中的字母顺序进行某些修改后，作者姓名的顺序就会变成lexicographical顺序，这是事实！ 她想知道，是否存在一种字母顺序，可以使她提交的论文中的姓名按照 lexicographical 顺序排列。如果有，你应该找出这样的顺序。

lexicographical 顺序的定义如下。当我们比较 \(s\) 和 \(t\) 时，首先要找到最左侧位置上的不同字符（\(s_{i} ≠ t_{i}\)） .如果没有这样的位置 (即 \(s\) 是 \(t\) 的前缀，反之亦然)，则最短字符串较少。否则，我们将根据字母表中的顺序比较字符 \(s_i\) 和 \(t_i\) 。

Input

第一行包含一个整数 \(n ( 1 ≤ n ≤ 100 )\)：名称数量。

阅读全文 »

发表于 更新于 分类于
本文字数： 1.7k 阅读时长 ≈ 6 分钟

B-Christmas Trees

Description

有一条向东西两侧无限延伸的道路，从这条道路上的某一参考点向东 \(x\) 米处的点的坐标定义为 \(x\)。其中，从参考点向西 \(x\) 米处的一点的坐标为 \(-x\)。

斯努克将从坐标为 \(A\) 的点开始，以 \(M\) 米的间隔在路上的各点摆放圣诞树。换句话说，他将在每一个可以用某个整数 \(k\) 表示为 \(A+kM\) 的点上摆放一棵圣诞树。

高桥和青木分别站在坐标为 \(L\) 和 \(R\) 的点上。\((L\leq R)\)。求在高桥和青木之间（包括他们所站的点）将会有多少棵圣诞树。 ### Constraints - \(-10^{18}\leq A \leq 10^{18}\) - \(1\leq M \leq 10^9\) - \(-10^{18}\leq L\leq R \leq 10^{18}\) - All input values are integers. ### Input \(\boxed{\begin{align}&A&M&&L&&R\end{align}}\) ### Output 打印将在高桥和青木之间设置的圣诞树数量（包括他们所站的位置）。 ### Sample Input

阅读全文 »

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 5 分钟

最近公共祖先 - OI Wiki (塔杨算法) Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。

Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如 - 求各种连通分量的 Tarjan 算法， - 求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。 - 并查集、Splay、Toptree 也是 Tarjan 发明的。

连通分量的 Tarjan 算法

DFS 生成树

300 返祖边 横叉边 前向边

阅读全文 »

发表于 更新于 分类于
本文字数： 347 阅读时长 ≈ 1 分钟

可以判断是否有负环，可与 [[图论/dijkstra]] 连用 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

P3385

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
struct{
    int v, w, next;
} a[100000];
int head[50000],dis[50000],cnt[50000];
bool vis[50000];
int edge;
queue<int> q;
void add(int u,int v,int w)
{
    a[++edge].v = v;
    a[edge].w = w;
    a[edge].next = head[u];
    head[u] = edge;
}
void spfa()
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    while(!q.empty())
        q.pop();
    dis[1] = 0;
    vis[1] = 1;
    q.push(1);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i;i=a[i].next)
        {
            int v = a[i].v, w = a[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if(cnt[v]>=n)
                {
                    cout << "YES" << endl;
                    return;
                }
                if(!vis[v])
                    vis[v] = 1, q.push(v);
            }
        }
    }
    cout << "NO" << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--)
    {
        memset(head, 0, sizeof head);///////
        cin >> n >> m;
        while(m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
            if(w>=0)
                add(v, u, w);
        }
        spfa();
    }
}
阅读全文 »