ranba

4258

ranba
5天前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 1e4+10;
int n, m1, m2, s;
int a[100],b[100], cnt;

int main() {
cin >> n >> m1 >> m2;

int factor = 1;
for (int i = 2; i <= m1; i ++) {
if (m1%i == 0) {
factor *= i;
cnt ++;
a[cnt] = i;
b[cnt] ++;
m1 /= i;

while (m1%i == 0) {
b[cnt] ++;
m1 /= i;
}
}
}

for (int i = 1; i <= cnt; i ++) {
b[i] *= m2;
}

bool flag = true;
int minn = 1e9, maxx;
for (int i = 1; i <= n; i ++) {
cin >> s;
if (s%factor == 0) {
flag = false;
maxx = 0;
for (int j = 1; j <= cnt; j ++) {
int t = s, count = 0;
while (t%a[j] == 0) {
count ++;
t /= a[j];
}
maxx = max(maxx, int(ceil(b[j]*1.0/count)));
}
minn = min(minn, maxx);
}
}

if (flag) cout << -1;
else cout << minn;

return 0;
}


ranba
4个月前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;       //n表示点数
int g[N][N];    //用邻接矩阵存储所有边
int dist[N];    //存储其它点到点集st的距离(代价)
bool st[N];     //标记每个点是否已经被加入到集合

//如果图不连通，则返回INF；否则返回最小生成树的边权之和
int prim() {
int res = 0;
//初始化所有点的距离为正无穷
memset(dist, 0x3f, sizeof(dist));

//开始时可以将任意一个点的距离设为0，这样第一次循环时，就会把该点加入到集合
//因为n >= 1，所以选点1
//因为是第一个点，所以dist[1] = 0
dist[1] = 0;

//因为要找n个点，所以循环n次
for (int i = 1; i <= n; i ++) {
//从其它点中，寻找到集合距离最短(代价最小)的一个点，记为t
int t = 0;
for (int j = 1; j <= n; j ++) {
if (!st[j] && dist[j] < dist[t]) {
t = j;
}
}

//如果t == 0，意味着其它点和集合中的点均没有连接，这种情况下不存在最小生成树
if (t == 0) return INF;

//将边权之和加上点t到集合的距离；把点t标记为在集合中
res += dist[t];
st[t] = true;

//点t是距离最短(代价最小)的点，用它来更新剩余点到集合的距离(代价)
for (int j = 1; j <= n; j ++) {
if (!st[j]) dist[j] = min(dist[j], g[t][j]);
}
}

return res;
}

int main() {
scanf("%d%d", &n, &m);

int u, v, w;
memset(g, 0x3f, sizeof(g));
for (int i = 1; i <= m; i ++) {
scanf("%d%d%d", &u, &v, &w);
g[u][v] = g[v][u] = min(g[u][v], w);    //如果两点之间有重边，存储最小的权重
}

int t = prim();

if (t == INF) puts("impossible");
else printf("%d\n", t);

return 0;
}


ranba
7个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;
int n, m, e[N][N], dist[N];
bool vst[N];

int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 1; i < n; i ++ ) {
int t = -1;
for (int j = 1; j <= n; j ++ ) {
if (!vst[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
vst[t] = true;

for (int j = 1; j <= n; j ++ ) {
dist[j] = min(dist[j], dist[t] + e[t][j]);
}
}

}

int main() {
cin >> n >> m;

memset(e, 0x3f, sizeof(e));

int x, y, z;
for (int i = 1; i <= m; i ++ ) {
cin >> x >> y >> z;
e[x][y] = min(e[x][y], z);
}

dijkstra();

if (dist[n] == 0x3f3f3f3f) cout << -1;
else cout << dist[n] << endl;

}


ranba
7个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 105;
int e[N][N], d[N][N];
int n, m;

struct node{
int x, y;
} q[11000];
int hh, tt;

void bfs() {
memset(d, -1, sizeof d);
d[1][1] = 0;
q[++tt] = {1,1};

while (hh < tt) {
int a = q[hh + 1].x;
int b = q[hh + 1].y;

if (a-1>=1 && d[a-1][b] == -1 && !e[a][b]) q[++tt] = {a-1, b}, d[a-1][b] = d[a][b] + 1;
if (a+1<=n && d[a+1][b] == -1 && !e[a][b]) q[++tt] = {a+1, b}, d[a+1][b] = d[a][b] + 1;
if (b-1>=1 && d[a][b-1] == -1 && !e[a][b]) q[++tt] = {a, b-1}, d[a][b-1] = d[a][b] + 1;
if (b+1<=m && d[a][b+1] == -1 && !e[a][b]) q[++tt] = {a, b+1}, d[a][b+1] = d[a][b] + 1;

hh ++ ;
}
}

int main() {
cin >> n >> m;

for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
cin >> e[i][j];
}
}

bfs();

// for (int i = 1; i <= n; i ++ ) {
//     for (int j = 1; j <= m; j ++ ) {
//         cout << d[i][j] << ' ';
//     }
//     cout << endl;
// }

cout << d[n][m] << endl;

return 0;
}


ranba
7个月前
#include <iostream>

using namespace std;

int n, path[10];
bool vst[10];

void dfs(int u) {
if (u > n) {
for (int i = 1; i <= n; i ++ ) cout << path[i] << ' ';
cout << endl;

return;
}

for (int i = 1; i <= n; i ++ ) {
if (!vst[i]) {
vst[i] = true;
path[u] = i;

dfs(u + 1);
vst[i] = false;
}
}
}

int main() {
cin >> n;

dfs(1);

return 0;
}


ranba
7个月前
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 210;
int e[N][N], n, m, Q;
int INF = 1e9;

int main() {
cin >> n >> m >> Q;

for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
if (i == j) e[i][j] = 0;
else e[i][j] = INF;
}
}

int x, y, z;
while (m -- ) {
cin >> x >> y >> z;
e[x][y] = min(e[x][y], z);      //可能有重边
}

for (int k = 1; k <= n; k ++ ) {
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
}
}

while (Q -- ) {
cin >> x >> y;
if (e[x][y] > INF / 2) cout << "impossible" << endl;
else cout << e[x][y] << endl;
}

return 0;
}


ranba
7个月前
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

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

int bfs() {
memset(d, -1, sizeof d);

queue<int> q;
d[1] = 0;
q.push(1);

while (q.size()) {
int t = q.front();
q.pop();

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];

if (d[j] == -1) {
d[j] = d[t] + 1;
q.push(j);
}
}
}

return d[n];
}

int main() {
scanf("%d %d", &n, &m);
memset(h, -1, sizeof h);        //一定要初始化！！

for (int i = 0; i < m; i ++ ) {
int a, b;
scanf("%d %d", &a, &b);
}

cout << bfs();

return 0;
}



ranba
7个月前
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10, M = 2 * N;

int n, h[N], e[M], ne[M], idx;
int ans = N;
bool vst[N];

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

int dfs(int u) {
vst[u] = true;

int size = 0, sum = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (vst[j]) continue;

int s = dfs(j);
size = max(size, s);
sum += s;
}

size = max(size, n - 1 - sum);
ans = min(ans, size);

return sum + 1;
}

int main() {
scanf("%d", &n);
memset(h, -1, sizeof h);

for (int i = 1; i < n; i ++ ) {
int a, b;
scanf("%d %d", &a, &b);
}

// for (int i = 1; i <= n; i ++ ) {
//     cout << endl << i << ':';
//     for (int j = h[i]; j != -1; j = ne[j]) {
//         cout << e[j] << ' ';
//     }
// }

dfs(1);

printf("%d\n", ans);

return 0;
}



ranba
8个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 5010;

int main(){
int n, k[N], s[N];
double m;
cin >> n >> m;

for(int i = 1; i <= n; i++){
cin >> k[i] >> s[i];
}
//paixv
for(int i = n; i > 1; i--){
int t = i;
for(int j = 1; j <= i; j++){
if(s[j] < s[t]) t = j;
else if(s[j] == s[t]){
if(k[j] > k[t]) t = j;
}
}

swap(k[i], k[t]);
swap(s[i], s[t]);
}

//shaixuan
int ress, resk = 0;
for(int i = 1; i <= n; i++){
ress = s[int(m*1.5)];
if(s[i] >= s[int(m*1.5)]){
resk ++;
}
}

cout << ress <<' '<< resk<<endl;
for(int i = 1; i <= n; i++){
if(s[i] >= s[int(m*1.5)]){
cout << k[i]<<' '<< s[i]<<endl;
}
}

return 0;
}


ranba
8个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int main(){
string a, b;
getline(cin, a);
getline(cin, b);

for(int i = 0; i < a.size(); i ++){
if(a[i] >= 'A' && a[i] <= 'Z') a[i] += 32;
}
for(int i = 0; i < b.size(); i ++){
if(b[i] >= 'A' && b[i] <= 'Z') b[i] += 32;
}

int cnt = 0, min = 1e6;
for(int i = 0; i < b.size(); i ++){
int j = i;
while(b[j] != ' ' && j <= b.size()) j ++;

if(b.substr(i, j-i) == a) {
cnt ++;
if(i < min) min = i;
}

i = j;

}

if(cnt == 0) cout << -1;
else cout << cnt <<' '<< min;

return 0;
}