POJ - 1860 最短路 判正环
题意
一开始，在点有
个金币，而点
的过程会产生
的变化，问是否有一条路线可以使得最终的
。
分析
要是最找的增加，有两种可能性：
- 原本路径中就纯在这样的边权
- 有正环的存在，因为
而双向的通路，而若纯在一个正环，在环中走一些，不断的松弛操作后，最终会变成一个无穷大的数字，这样无论环中是否存在点
都可以通过回路达到
所以本题能够利用的思想去解题。 因此初始化
而源点到其他点的距离（权值）初始化为无穷小（0），当
到其他某点的距离能不断变大时，说明存在最大路径；如果可以一直变大（也就是松弛次数超过
次），说明存在正环。
本题因为数据范围不大，使用都可以。我此题采用的是
。复杂度
，SPFA的玄学常数，不过本题数据小无所谓。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int vis[maxn];
int head[maxn], cnt, ans[maxn];
double dis[maxn];
int n, m, S;
double V;
struct node {
int v, next;
double r, c;
}e[maxn << 1];
void init() {
memset(head, -1, sizeof(head));
cnt = 0;
}
void add(int u, int v, double r, double c) {
e[cnt].v = v;
e[cnt].r = r, e[cnt].c = c;
e[cnt].next = head[u];
head[u] = cnt++;
}
bool SPFA(int s) {
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = V;
vis[s] = 1;
ans[s] ++;
while (!q.empty()) {
int u = q.front();
vis[u] = 0;
q.pop();
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
double r = e[i].r;
double c = e[i].c;
double w = (dis[u] - c) * r;
if (dis[v] < w) {
dis[v] = w;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
if (++ans[v] >= n) return true;
}
}
}
}
if (dis[s] > V) return true;
return false;
}
int main(void) {
FAST_IO;
init();
cin >> n >> m >> S >> V;
for (int i = 0; i < m; i++) {
int u, v;
double rab, cab, rba, cba;
cin >> u >> v >> rab >> cab >> rba >> cba;
add(u, v, rab, cab);
add(v, u, rba, cba);
}
if (SPFA(S)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
} POJ - 1511 双向建图
题意
给定一张单向通路图（同时只能单向行驶），然后个人从
号点出发，到剩余
个宣传点，然后再回到
号点汇报结果，求所有人往返路径和的最小值，保证有解。
分析
本题的唯一难点在于的最短路可能不同。所以，需要一次正向存边,一次反向存边，相当于从源点到其他店和从其他到源点，跑两次最短路。
值得一题的是，本想想偷懒，用来存图，但
到自闭。。必须使用前向星。愿意应该是本题的
数据都是超大，vector的清空，复杂度需要
，而前向星清空的复杂度只需要
。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
ll dis[2][maxn];
struct node {
int v, w, next;
}e[2][maxn];
int cnt1, cnt2, head[2][maxn];
int vis[maxn];
void init(int n) {
memset(head, -1, sizeof(head));
memset(dis, 0x3f, sizeof(dis));
cnt1 = 0;
cnt2 = 0;
}
void add(int id, int u, int v, int w, int &cnt) {
e[id][cnt].v = v;
e[id][cnt].w = w;
e[id][cnt].next = head[id][u];
head[id][u] = cnt++;
}
void dijkstra(int id) {
memset(vis, 0, sizeof(vis));
priority_queue<pair<ll, int> >q;
q.push(make_pair(0, 1));
dis[id][1] = 0;
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[id][u]; ~i; i = e[id][i].next) {
int v = e[id][i].v;
ll w = e[id][i].w;
if (dis[id][v] > dis[id][u] + w) {
dis[id][v] = dis[id][u] + w;
q.push(make_pair(-dis[id][v], v));
}
}
}
}
int main(void) {
FAST_IO;
int t;
// cin >> t;
scanf("%d", &t);
while (t--) {
int n, m;
// cin >> n >> m;
scanf("%d %d", &n, &m);
init(n);
for (int i = 0; i < m; i++) {
int u, v, w;
// cin >> u >> v >> w;
scanf("%d %d %d", &u, &v, &w);
add(0, u, v, w, cnt1);
add(1, v, u, w, cnt2);
}
dijkstra(0);
dijkstra(1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
// cout << dis[0][i] << " " << dis[1][i] << endl;
ans += dis[1][i] + dis[0][i];
}
// cout << ans << endl;
printf("%lld\n", ans);
}
return 0;
} POJ - 3087 暴力模拟
题意
现有字符串s1、s2、s12，其中s1、s2的长度为len，s12的长度为2*len。
是否可以通过一些操作使s1和s2转换合并成s12。无论怎么变换都不会得到s12，那么输出 -1。
变换的操作规则如下：
- 假设
- 变换后的序列
- 如果s和s12完全相同，那么输出变换次数。如果不完全相等，s的前半部分作为s1，后半部分作为s2，重复上述过程。
分析
按照题意，暴力模拟字符即可。。这种水题居然会在搜索里。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int main(void) {
FAST_IO;
int t;
cin >> t;
int nt = 0;
while (t--) {
int n;
cin >> n;
string s1, s2, s, ans;
cin >> s1 >> s2 >> ans;
s = s1 + s2;
int cnt = 0;
while (s != ans) {
if (cnt != 0 && s == s1 + s2) {
cnt = -1;
break;
}
// cout << s << endl;
string temp = s;
for (int i = 0, j = 0; i < 2 * n; i += 2, j++) {
s[i] = temp[n + j];
s[i + 1] = temp[j];
}
cnt++;
}
cout << ++nt << " " << cnt << endl;
}
return 0;
} HDU - 1556 差分裸题
题意
有n个气球，给出M条染色信息表示这个区间内被染色1次。求最后每个气球的染色次数。
分析
本题N、M、L、R的范围都是。暴力跑一定超时。
这时候可以采用差分数组。
令。而原数组可以同差分数组前缀和获得，即
。
查询
而若是需要对区间内的元素同时增加
，可以通过差分
完成。证明此处省略。
更新。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 100000 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
int d[maxn];
int main(void) {
FAST_IO;
int n;
while (cin >> n) {
if (n == 0) break;
// for (int i = 1; i <= n; i++) d[i] = 1;
memset(d, 0, sizeof(d));
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
d[l]++;
d[r + 1]--;
}
for (int i = 1; i <= n; i++) {
d[i] = d[i] + d[i - 1];
cout << d[i];
if (i != n) cout << " ";
}
cout << endl;
}
return 0;
} 送外卖 美团面试题 反向建图，两次搜索
题意
外卖员从0开始到n-1送外卖，都到一个点，就有两种选择，用字母ab来表示选择的方式。要求输出字典序最小的情况，无法到达
输出
,如果字符串无限长，就输出
分析
首先需要判定是否可以到达点，本题是一个有向图，所有需要判断终点和起点是否连通，并且确定哪些点是可达点。
所以先反向建图，从终点开始经行一次
，记录可达点，并且确定连通性。若是不连通则输出"No solution!"。
再从0点开始，更加可达点二次搜索，因为要字典序最小，所以若是a可达就优先选择a的方案。若是其中存在回路，则表示字符串无限长。
AC代码
//#include <bits/stdc++.h>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <list>
#include <set>
#include <sstream>
#include <stack>
#include <string>
//#include <array>
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <map>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
struct node {
int v, next;
} e[maxn];
int head[maxn], cnt, flag;
int a[maxn], b[maxn];
int vis[maxn];
string ans;
int n;
void add(int u, int v) {
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
void init(void) {
memset(head, -1, sizeof(head));
cnt = 0;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
dfs(e[i].v);
}
}
void dfs2(int u, int step) {
if (u >= n || u < 0 || !vis[u] || step >= n) {
return;
}
if (u == n - 1) {
flag = 1;
return;
}
int v1 = u + a[u], v2 = u + b[u];
if (vis[v1] && v1 < n && v1 >= 0) {
ans += 'a';
dfs2(v1, step + 1);
} else if (vis[v2] && v2 < n && v2 >= 0) {
ans += 'b';
dfs2(v2, step + 1);
}
}
int main(void) {
FAST_IO;
init();
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
for (int i = 0; i < n; i++) {
if (i + a[i] >= 0 && i + a[i] < n) {
add(i + a[i], i);
}
}
for (int i = 0; i < n; i++) {
if (i + b[i] >= 0 && i + b[i] < n) {
add(i + b[i], i);
}
}
dfs(n - 1);
if (!vis[0]) {
cout << "No solution!" << endl;
} else {
ans = "";
flag = 0;
dfs2(0, 0);
if (!flag)
cout << "Infinity!" << endl;
else
cout << ans << endl;
}
return 0;
} 题意 有n块石头，每块石头有两种属性
，同时对于每块石头有两种不同的操作：
x+a[i], y-b[i]
y+c[i], x-d[i]
数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0
求若按照1-n的顺序操作视同，如何是的最后x*y的值最大。
对于20%的数据，1≤n≤2
对于100%的数据，1≤n≤15，0≤ai,bi,ci,di≤1,000,000
分析
数据较小，可以使用搜索或则状态压缩枚举所有过程。
AC代码
状压解法
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 15 + 10;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
ll a[maxn], b[maxn], c[maxn], d[maxn];
ll dp[maxn];
int main(void) {
FAST_IO;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
ll ans = 0;
for (int i = 0; i < (1 << n); i++) {
ll x = 0, y = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
x += a[j];
y -= b[j];
} else {
x -= d[j];
y += c[j];
}
x = x < 0 ? 0 : x;
y = y < 0 ? 0 : y;
}
ans = max(ans, x * y);
}
cout << ans << endl;
return 0;
}
x+a[i], y-b[i]
y+c[i], x-d[i]
对于20%的数据，1≤n≤2
对于100%的数据，1≤n≤15，0≤ai,bi,ci,di≤1,000,000
初心如金 结论，瞎搞
题意
详细见链接。
分析
可以更加当前输入数字的奇偶性判断，因为输入的都是奇数，所以若是出现偶数，则表示二进制末尾的几个是，否则便是
,因此可以直接根据后面询问的奇偶性判断上一次的答案。瞎搞的结论题。
AC代码
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;
int const maxn = 1e5 + 10;
inline int lc(int x) {return x << 1;}
inline int rc(int x) {return x << 1 | 1;}
template <typename T>
int read(T &x) {
x = 0;
int ch = getchar(), f = 1;
while (ch > '9' || ch < '0') {
if (ch == EOF) return 0;
if (ch == '-') f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return 1;
}
template <typename T>
void out(T x) {
if (x < 0) putchar('-'),x = -x;
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
int isprime(ll a) {
if (a == 1) return 0;
for (ll i = 2; i * i <= a; ++i) {
if (a % i == 0) return 0;
}
return 1;
}
int main(void) {
FAST_IO;
int n;
read(n);
ll a;
int x = 0;
read(a);
// x = isprime(a);
for (int i = 1; i < n; i++) {
read(a);
out(!(a & 1));
printf("\n");
}
return 0;
} 最短Hamilton路径 状压 Floyd最短路
题意
给定一张 n 个点的带权无向图，点从
标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且a[x,y]+a[y,z]≥a[x,z]a[x,y]+a[y,z] \geq a[x,z]a[x,y]+a[y,z]≥a[x,z]。
分析
首先我们要思考如果让这个NP完全题目复杂度降低，那么可以优先考虑到使用位运算，状态压缩等解决思路。
然后接着思考，我们可以发现，我们所需要的不是整个方案，而只是方案最优解，所以我们只需要记录当前这个方案的最优解即可，那么我们考虑的状态，不久只有，在当前方案i中，目前抵达的点是j。
现在既然装填已经确定好了当前点j，那么这个j点是由哪一个状态移动而来的呢？我们可以选择k，也就是说我们的状态转移方程可以为
i^(1<<j)的意思是，i 异或 1右移j位，具体来说就是i这个方案集合 xor 10……0,(其中1的位置在第j位)。其作用是：
- 第一点它是在判断第j位的情况
- 第二点位运算速度快
AC代码
#include <bits/stdc++.h>
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(nullptr),std::cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
int const maxn = 21;
int dp[1 << maxn][maxn];
int d[maxn][maxn];
int const INF = 0x3f3f3f3f;
int main(void) {
FAST_IO;
memset(dp, INF, sizeof(dp));
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> d[i][j];
}
}
dp[1][0] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i >> j & 1) {
for (int k = 0; k < n; k++) {
if ((i ^ 1 << j) >> k & 1) {
dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + d[k][j]);
}
}
}
}
}
cout << dp[(1 << n) - 1][n - 1] << endl;
return 0;
} 
京公网安备 11010502036488号