incra

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

8.6万

liaoyanxu

zs3318

wqzgg

KGk
MudNewBie

morty

rd0

TaTaTa110
RyanRyan
.Blank
Detach..

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;
}


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;
}


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天前

incra
1天前

# <—点个赞吧QwQ

### 宣传一下算法提高课整理

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

#### 输出格式

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.


#### 代码

#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将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。

#### 输入格式

  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


#### 代码

#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

### 宣传一下算法提高课整理

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

#### 数据范围

$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;
}
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

### 宣传一下算法提高课整理

#### 数据范围

$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


#### 思路

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;
}
spfa ();
for (int i = 1;i <= n;i++) cout << cnt[i] << endl;
return 0;
}


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;
}


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;
}