头像

incra

$$\Large\color{blue}{六年级蒟蒻}$$




在线 


最近来访(3224)
用户头像
liaoyanxu
用户头像
垫底抽風
用户头像
zs3318
用户头像
肥仔_7
用户头像
wqzgg
用户头像
源泉
用户头像
KGk
用户头像
MudNewBie
用户头像
做事要有遗逝感
用户头像
morty
用户头像
长腿鳄鱼
用户头像
百事可乐_4
用户头像
潋湄
用户头像
rd0
用户头像
种花家的兔兔
用户头像
钦泽小朋友
用户头像
TaTaTa110
用户头像
RyanRyan
用户头像
.Blank
用户头像
Detach..

活动打卡代码 AcWing 1084. 数字游戏 II

incra
7小时前
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 15,M = 110;
int l,r,p;
int f[N][10][M];
int mod (int a,int b) {
    return (a % b + b) % b;
}
void init () {
    memset (f,0,sizeof (f));
    for (int i = 0;i <= 9;i++) f[1][i][i % p] = 1;
    for (int i = 2;i < N;i++) {
        for (int j = 0;j <= 9;j++) {
            for (int k = 0;k < p;k++) {
                for (int x = 0;x <= 9;x++) f[i][j][k] += f[i - 1][x][mod (k - j,p)];
            }
        }
    }
}
int dp (int n) {
    if (!n) return 1;
    vector <int> num;
    while (n) {
        num.push_back (n % 10);
        n /= 10;
    }
    int ans = 0,last = 0;
    for (int i = num.size () - 1;i >= 0;i--) {
        int x = num[i];
        for (int j = 0;j < x;j++) ans += f[i + 1][j][mod (-last,p)];
        last += x;
        if (!i && last % p == 0) ans++;
    }
    return ans;
}
int main () {
    while (cin >> l >> r >> p) {
        init ();
        cout << dp (r) - dp (l - 1) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1083. Windy数

incra
8小时前
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int l,r;
int f[N][10];
void init () {
    for (int i = 0;i <= 9;i++) f[1][i] = 1;
    for (int i = 2;i < N;i++) {
        for (int j = 0;j <= 9;j++) {
            for (int k = 0;k <= 9;k++) {
                if (abs (j - k) >= 2) f[i][j] += f[i - 1][k];
            }
        }
    }
}
int dp (int n) {
    vector <int> num;
    while (n) {
        num.push_back (n % 10);
        n /= 10;
    }
    int ans = 0,last = -10,len = num.size ();
    for (int i = len - 1;i >= 0;i--) {
        int x = num[i];
        for (int j = (i == len - 1);j < x;j++) {
            if (abs (j - last) >= 2) ans += f[i + 1][j];
        }
        if (abs (x - last) < 2) break;
        last = x;
        if (!i) ans++;
    }
    for (int i = 1;i < len;i++) {
        for (int j = 1;j <= 9;j++) ans += f[i][j];
    }
    return ans;
}
int main () {
    init ();
    cin >> l >> r;
    cout << dp (r) - dp (l - 1) << endl;
    return 0;
}


活动打卡代码 AcWing 1082. 数字游戏

incra
21小时前
#include <iostream>
#include <vector>
using namespace std;
const int N = 20;
int l,r;
int f[N][N];    //f[i][j]表示i位且最高位是j的方案数,后面的i - 1位随意填
void init () {
    for (int i = 0;i <= 9;i++) f[1][i] = 1;
    for (int i = 2;i < N;i++) {
        for (int j = 0;j <= 9;j++) {
            for (int k = j;k <= 9;k++) f[i][j] += f[i - 1][k];
        }
    }
}
int dp (int n) {
    if (!n) return 1;
    vector <int> num;
    while (n) {
        num.push_back (n % 10);
        n /= 10;
    }
    int ans = 0,last = 0;
    for (int i = num.size () - 1;i >= 0;i--) {
        int x = num[i];
        for (int j = last;j <= x - 1;j++) ans += f[i + 1][j];
        if (last > x) break;
        last = x;
        if (!i) ans++;
    }
    return ans;
}
int main () {
    init ();
    while (cin >> l >> r) cout << dp (r) - dp (l - 1) << endl;
    return 0;
}


新鲜事 原文

incra
1天前
有人打USACO么 我T1+T3AC,用时1.5h http://usaco.org/index.php?page=viewcontest qwq



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

给定 $n$ 个变量和 $m$ 个不等式。其中 $n$ 小于等于 $26$,变量分别用前 $n$ 的大写英文字母表示。

不等式之间具有传递性,即若 $A>B$ 且 $B>C$,则 $A>C$。

请从前往后遍历每对关系,每次遍历时判断:

  • 如果能够确定全部关系且无矛盾,则结束循环,输出确定的次序;
  • 如果发生矛盾,则结束循环,输出有矛盾;
  • 如果循环结束时没有发生上述两种情况,则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据,第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行,每行包含一个不等式,不等式全部为小于关系。

当输入一行 0 0 时,表示输入终止。

输出格式

每组数据输出一个占一行的结果。

结果可能为下列三种之一:

  1. 如果可以确定两两之间的关系,则输出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次数,'yyy...y'是指升序排列的所有变量。
  2. 如果有矛盾,则输出: "Inconsistency found after t relations.",其中't'指迭代次数。
  3. 如果没有矛盾,且不能确定两两之间的关系,则输出 "Sorted sequence cannot be determined."

数据范围

$2 \le n \le 26$,变量只可能为大写字母 $A \sim Z$。

输入样例1:

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

输出样例1:

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

输入样例2:

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

输出样例2:

Inconsistency found after 6 relations.

输入样例3:

5 5
A<B
B<C
C<D
D<E
E<A
0 0

输出样例3:

Sorted sequence determined after 4 relations: ABCDE.

思路

此题可以用拓扑排序做,这里介绍一种$\text{Floyd}$的做法。
我们在一张图中,每次从较大数连向较小数一条边(输出是从大到小,所以这么写会好写一点)。然后跑$\text{Floyd}$,这里我们可以只以输入数据的两个点为中心扩展,然后每次检查比它大的数加比它小的数是否等于$n-1$。

代码

#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 30,INF = 0x3f3f3f3f;
int n,m;
int dist[N][N];
PII ans[N];
void floyd (int k) {
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) dist[i][j] = min (dist[i][j],dist[i][k] + dist[k][j]);
    }
}
bool check () {
    for (int i = 1;i <= n;i++) {
        int cnt = 0;
        for (int j = 1;j <= n;j++) {
            if (dist[i][j] != INF) cnt++;
        }
        ans[i] = {cnt,i};
        for (int j = 1;j <= n;j++) {
            if (i != j && dist[j][i] != INF) cnt++;
        }
        if (cnt != n) return false;
    }
    sort (ans + 1,ans + 1 + n);
    return true;
}
int main () {
    bool flag = false;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (i != j) dist[i][j] = INF;
        }
    }
    for (int i = 1;i <= m;i++) {
        char a,t,b;
        cin >> a >> t >> b;
        int x = a - 'A' + 1,y = b - 'A' + 1;
        if (!flag && dist[x][y] != INF) {
            cout << "Inconsistency found after " << i << " relations." << endl;
            flag = true;
        }
        dist[y][x] = 1;
        floyd (x),floyd (y);
        if (!flag && check ()) {
            cout << "Sorted sequence determined after " << i << " relations: ";
            for (int j = 1;j <= n;j++) cout << (char)(ans[j].y + 'A' - 1);
            cout << "." << endl;
            flag = true;
        }
    }
    if (!flag) puts ("Sorted sequence cannot be determined.");
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

农民John的农场里有很多牧区,有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言,你能看到至少有两个牧区不连通。

现在,John想在农场里添加一条路径(注意,恰好一条)。

一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。

考虑如下的两个牧场,每一个牧区都有自己的坐标:

1.png

图 1 是有 5 个牧区的牧场,牧区用“*”表示,路径用直线表示。

图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E,它们之间的最短路径是 A-B-E。

图 2 是另一个牧场。

这两个牧场都在John的农场上。

John将会在两个牧场中各选一个牧区,然后用一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。

注意,如果两条路径中途相交,我们不认为它们是连通的。

只有两条路径在同一个牧区相交,我们才认为它们是连通的。

现在请你编程找出一条连接两个不同牧场的路径,使得连上这条路径后,所有牧场(生成的新牧场和原有牧场)中直径最大的牧场的直径尽可能小。

输出这个直径最小可能值。

输入格式

第 1 行:一个整数 N, 表示牧区数;

第 2 到 N+1 行:每行两个整数 X,Y, 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。

第 N+2 行到第 2*N+1 行:每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。

例如,题目描述中的两个牧场的矩阵描述如下:

  A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

输入数据中至少包括两个不连通的牧区。

输出格式

只有一行,包括一个实数,表示所求答案。

数字保留六位小数。

数据范围

$1 \le N \le 150$,
$0 \le X,Y \le 10^5$

输入样例:

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

输出样例:

22.071068

思路

设$maxd_i$表示从$i$出发能到达的最长距离。
设要连的边是$(i,j)$
当$i,j$在同一连通块内时,答案就是$\sum\limits_{i \in s_i}maxd_i$,其中$s_i$表示$i$所在连通块的所有点的集合。统计答案时只需要遍历所有点即可。
当$i,j$不在同一连通块内时,答案就是$maxd_i+dis_{i,j}+maxd_j$。
其中$maxd$和$dis$数组可以在$\text{Floyd}$算法中求出。

代码

#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 160,INF = 0x3f3f3f3f;
int n;
PII q[N];
bool mp[N][N];
double g[N][N],maxd[N];
double get (int a,int b) {
    int dx = q[a].x - q[b].x,dy = q[a].y - q[b].y;
    return sqrt (dx * dx + dy * dy);
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> q[i].x >> q[i].y;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            char ch;
            cin >> ch;
            mp[i][j] = ch - '0';
            if (mp[i][j]) g[i][j] = get (i,j);
            else if (i != j) g[i][j] = INF;
        }
    }
    for (int k = 1;k <= n;k++) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                g[i][j] = min (g[i][j],g[i][k] + g[k][j]);
            }
        }
    }
    double ans1 = 0,ans2 = INF;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (g[i][j] != INF) maxd[i] = max (maxd[i],g[i][j]);
        }
        ans1 = max (ans1,maxd[i]);
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (g[i][j] == INF) ans2 = min (ans2,maxd[i] + get (i,j) + maxd[j]);
        }
    }
    printf ("%.6lf",max (ans1,ans2));
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市(零或更多)停靠。

旅行社计划旅途从 $S$ 城市出发,到 $F$ 城市结束。

由于不同旅客的景点偏好不同,所以为了迎合更多旅客,旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制,要么满足所选路线总路程为 $S$ 到 $F$ 的最小路程,要么满足所选路线总路程仅比最小路程多一个单位长度。

3463_1.png

如上图所示,如果 $S = 1,F = 5$,则这里有两条最短路线 $1 \to 2 \to 5,1 \to 3 \to 5$,长度为 $6$;有一条比最短路程多一个单位长度的路线 $1 \to 3 \to 4 \to 5$,长度为 $7$。

现在给定比荷卢经济联盟的公交路线图以及两个城市 $S$ 和 $F$,请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式

第一行包含整数 $T$,表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $N$ 和 $M$,分别表示总城市数量和道路数量。

接下来 $M$ 行,每行包含三个整数 $A,B,L$,表示有一条线路从城市 $A$ 通往城市 $B$,长度为 $L$。

需注意,线路是 单向的,存在从 $A$ 到 $B$ 的线路不代表一定存在从 $B$ 到 $A$ 的线路,另外从城市 $A$ 到城市 $B$ 可能存在多个不同的线路。

接下来一行,包含两个整数 $S$ 和 $F$,数据保证 $S$ 和 $F$ 不同,并且 $S、F$ 之间至少存在一条线路。

输出格式

每组数据输出一个结果,每个结果占一行。

数据保证结果不超过 $10^9$。

数据范围

$2 \le N \le 1000$,
$1 \le M \le 10000$,
$1 \le L \le 1000$,
$1 \le A,B,S,F \le N$

输入样例:

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

输出样例:

3
2

思路

此题和前一题类似,只要多统计一下次短路的数量即可。
更新次短路时和更新次大值的代码类似。

代码

#include <iostream>
#include <cstring>
#include <queue>
#define type first
#define id second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010,M = 20010;
int n,m,s,t;
int h[N],e[M],ne[M],w[M],idx;
int dist[2][N];
int cnt[2][N];
bool st[2][N];
void add (int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
struct cmp {
    bool operator ()(PII x,PII y) {
        return dist[x.type][x.id] > dist[y.type][y.id];
    }
};
void dijkstra () {
    memset (st,false,sizeof (st));
    memset (dist,0x3f,sizeof (dist));
    memset (cnt,0,sizeof (cnt));
    dist[0][s] = 0,cnt[0][s] = 1;
    priority_queue <PII,vector <PII>,cmp> heap;
    heap.push ({0,s});
    while (heap.size ()) {
        auto [type,t] = heap.top ();
        heap.pop ();
        if (st[type][t]) continue;
        st[type][t] = true;
        for (int i = h[t];~i;i = ne[i]) {
            int j = e[i],d = dist[type][t] + w[i],c = cnt[type][t];
            if (d < dist[0][j]) {
                dist[1][j] = dist[0][j],cnt[1][j] = cnt[0][j];
                heap.push ({1,j});
                dist[0][j] = d,cnt[0][j] = c;
                heap.push ({0,j});
            }
            else if (d == dist[0][j]) cnt[0][j] += c;
            else if (d < dist[1][j]) {
                dist[1][j] = d,cnt[1][j] = c;
                heap.push ({1,j});
            }
            else if (d == dist[1][j]) cnt[1][j] += c;
        }
    }
}
int main () {
    int T;
    cin >> T;
    while (T--) {
        memset (h,-1,sizeof (h));
        idx = 0;
        cin >> n >> m;
        while (m--) {
            int a,b,c;
            cin >> a >> b >> c;
            add (a,b,c);
        }
        cin >> s >> t;
        dijkstra ();
        int ans = cnt[0][t];
        if (dist[1][t] == dist[0][t] + 1) ans += cnt[1][t];
        cout << ans << endl;
    }
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

给出一个 $N$ 个顶点 $M$ 条边的无向无权图,顶点编号为 $1$ 到 $N$。

问从顶点 $1$ 开始,到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$,为图的顶点数与边数。

接下来 $M$ 行,每行两个正整数 $x,y$,表示有一条顶点 $x$ 连向顶点 $y$ 的边,请注意可能有自环与重边。

输出格式

输出 $N$ 行,每行一个非负整数,第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路,由于答案有可能会很大,你只需要输出对 $100003$ 取模后的结果即可。

如果无法到达顶点 $i$ 则输出 $0$。

数据范围

$1 \le N \le 10^5$,
$1 \le M \le 2 \times 10^5$

输入样例:

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例:

1
1
1
2
4

思路

设$cnt_i$表示$1\sim i$的最短路数量
对于每次$\text{SPFA}$的松弛操作中的每条边$(a,b,w)$,我们分裂讨论:

  1. 若$dist_b>dist_a+w$,则$cnt_b$应更新为$cnt_a$,因为以前的$cnt_b$不是最短路了。
  2. 若$dist_b=dist_a+w$,则$cnt_b$应加上$cnt_a$,因为这里的最短路长度相同

代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010,M = 400010,MOD = 100003;
int n,m;
int h[N],e[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];
void add (int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void spfa () {
    queue <int> q;
    q.push (1);
    memset (dist,0x3f,sizeof (dist));
    dist[1] = 0;
    cnt[1] = 1;
    st[1] = true;
    while (q.size ()) {
        int t = q.front ();
        q.pop ();
        st[t] = false;
        for (int i = h[t];~i;i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                if (!st[j]) {
                    q.push (j);
                    st[j] = true;
                }
            }
            else if (dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % MOD;
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n >> m;
    while (m--) {
        int a,b;
        cin >> a >> b;
        add (a,b),add (b,a);
    }
    spfa ();
    for (int i = 1;i <= n;i++) cout << cnt[i] << endl;
    return 0;
}


活动打卡代码 AcWing 1081. 度的数量

incra
2天前
#include <iostream>
#include <vector>
using namespace std;
const int N = 40;
int l,r,k,b;
int f[N][N];
void init () {
    for (int i = 0;i < N;i++) {
        f[i][0] = f[i][i] = 1;
        for (int j = 1;j <= i - 1;j++) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
    }
}
int dp (int n) {
    if (!n) return 0;
    int ans = 0,last = 0;
    vector <int> num;
    while (n) {
        num.push_back (n % b);
        n /= b;
    }
    for (int i = num.size () - 1;i >= 0;i--) {
        int x = num[i];
        if (x) {
            ans += f[i][k - last];
            if (x > 1) {
                if (k - last - 1 >= 0) ans += f[i][k - last - 1];
                break;
            }
            else {
                last++;
                if (last > k) break;
            }
        }
        if (!i && last == k) ans++;
    }
    return ans;
}
int main () {
    init ();
    cin >> l >> r >> k >> b;
    cout << dp (r) - dp (l - 1) << endl;
    return 0;
}


活动打卡代码 AcWing 456. 车站分级

incra
2天前
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n,m;
int a[N];
bool g[N][N];
int in_deg[N];
bool st[N];
int q[N];
int d[N];
bool top_sort () {
    int hh = 0,tt = -1;
    for (int i = 1;i <= n;i++) {
        if (!in_deg[i]) {
            q[++tt] = i;
            d[i] = 1;
        }
    }
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 1;i <= n;i++) {
            if (!g[t][i]) continue;
            d[i] = max (d[i],d[t] + 1);
            in_deg[i]--;
            if (!in_deg[i]) q[++tt] = i;
        }
    }
    return tt == n - 1;
}
int main () {
    cin >> n >> m;
    while (m--) {
        int k;
        cin >> k;
        memset (st,false,sizeof (st));
        for (int i = 1;i <= k;i++) {
            cin >> a[i];
            st[a[i]] = true;
        }
        for (int i = a[1];i <= a[k];i++) {
            if (!st[i]) {
                for (int j = 1;j <= k;j++) {
                    if (!g[i][a[j]]) {
                        g[i][a[j]] = true;
                        in_deg[a[j]]++;
                    }
                }
            }
        }
    }
    if (top_sort ()) {
        int ans = 1;
        for (int i = 1;i <= n;i++) ans = max (ans,d[i]);
        cout << ans << endl;
    }
    else puts ("-1");
    return 0;
}