2023年9月22日
哎，再一次意识到弱小。。
Acwing1127 香甜的黄油
题目理解
求n遍最短路，求出每个点到某个点到所有牧场的最短路即可。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7, N = 810, M = 3000;
const int INF = 0x3f3f3f3f;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }
int h[N], e[M], ne[M], w[M], idx;
int p, n, k;
int id[N];
int d[N], q[M];
bool st[N];
int spfa(int u)
{
memset(d, INF, sizeof d);
memset(st, 0, sizeof st);
int hh = 0, tt = 1;
d[u] = 0;
q[0] = u;
st[u] = true;
while(hh != tt)
{
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
if(!st[j])
{
q[tt++] = j;
if(tt == N) tt = 0;
st[j] = true;
}
}
}
}
int sum = 0;
for(int i = 1; i <= p; i++)
{
if(d[id[i]] == INF) return INF;
sum += d[id[i]];
}
return sum;
}
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int ans = INF;
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &p, &n, &k);
for(int i = 1; i <= p; i++)
scanf("%d", &id[i]);
for(int i = 1; i <= k; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for(int i = 1; i <= n; i++)
ans = min(ans, spfa(i));
printf("%d", ans);
return 0;
}
Acwing 1126最小花费
题目理解
因为每次会扣除手续费那么比如x元，就是x * (1 - rate1) * (1 - rate2) * (1 - rate3) ... ，这样下去。那么我们就需要。
其实就是乘积的最大路，然后让100 / rate积即可。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7, N = 2010;
const int INF = 0x3f3f3f3f;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }
double g[N][N];
int n, m;
double d[N];
bool st[N];
double dijkstra(int a, int b)
{
d[a] = 1;
for(int i = 1; i <= n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
if(!st[j] && (t == -1 || d[j] > d[t]))
t = j;
st[t] = true;
for(int j = 1; j <= n; j++)
d[j] = max(d[j], d[t] * g[t][j]);
}
return d[b];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
double z = (100.0 - c) / 100;
g[a][b] = g[b][a] = max(g[a][b], z);
}
int a, b;
cin >> a >> b;
double rate = dijkstra(a, b);
printf("%.8lf", 100 / rate);
return 0;
}
Acwing920 最优乘车
题目理解
这个题的建图方式比较特殊，要按照公交车的路线去建图。而且能到哪个？每个站台都要建图。
比如4 5 6 7，就要4 5\ 4 6\ 4 7\ 5 6\ 5 7\ 6 7\都进行建边，这样就可以求出1到n站的最小乘车次数，那么最小的转车次数就是最小乘车次数 - 1。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7, N = 510;
const int INF = 0x3f3f3f3f;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }
int g[N][N], d[N] ,stop[N];
bool st[N];
int n, m;
int dijkstra()
{
memset(d, INF, sizeof d);
d[1] = 0;
for(int i = 1; i <= n; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
if(!st[j] && (t == -1 || d[j] < d[t]))
t = j;
st[t] = true;
for(int j = 1; j <= n; j++)
d[j] = min(d[j], d[t] + g[t][j]);
}
return d[n];
}
int main()
{
memset(g, INF, sizeof g);
cin >> m >> n;
string line;
getline(cin, line);
while (m -- )
{
getline(cin, line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) stop[cnt ++ ] = p;
for (int j = 0; j < cnt; j ++ )
for (int k = j + 1; k < cnt; k ++ )
g[stop[j]][stop[k]] = 1;
}
int t = dijkstra();
if(t == INF)
cout << "NO";
else
cout << max(0, t - 1);
return 0;
}
牛客周赛 A题
题目理解
这周赛就会一个题。。。
这个题就是奇数项个，第一个是谁谁就多。如何判断第l项是谁？那就直接把他们拆开，因为数据范围比较大，不能进行(l - 1) * k,python的话就好办了
如果是偶数项个：
- 那么就看所有的序列是不是都是偶数，如果是那么只能输出
-1。都是偶数的话就是首项和公差都是偶数即可。 - 都是奇数就是首项是奇数，公差是偶数
- 不然就相等
代码实现
#include<iostream>
using namespace std;
typedef long long ll;
ll a, k, q, l, r;
int main()
{
cin >> a >> k >> q;
while(q -- )
{
cin >> l >> r;
ll t = r - l + 1;
if(t % 2) // 奇数项
{
// 判断第一个是奇还是偶数
if(a % 2 == 1 && k % 2 == 1 && (l - 1) % 2 == 1)
cout << -1 << endl;
else if(a % 2 == 0 && ((l - 1) % 2 == 0 || k % 2 == 0))
cout << -1 << endl;
else
cout << 1 << endl;
}else{
if(a % 2 == 1 && k % 2 == 0)
cout << 1 << endl;
else if(a % 2 == 0 && k % 2 == 0)
cout << -1 << endl;
else
cout << 0 << endl;
}
}
return 0;
}