第一题（100%）
维护前缀递减、后缀递增数组。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 1005;
int T, n, A[MAXN];
int pre[MAXN], suf[MAXN];
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-1.txt", "r", stdin);
#endif // __LOCAL_WONZY__
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> A[i];
for (int i = 1; i <= n; ++i) {
pre[i] = 1;
for (int j = 1; j < i; ++j) {
if (A[j] > A[i]) pre[i] = max(pre[j] + 1, pre[i]);
}
}
for (int i = n; i >= 1; --i) {
suf[i] = 1;
for (int j = i + 1; j <= n; ++j) {
if (A[i] < A[j]) suf[i] = max(suf[j] + 1, suf[i]);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (A[i] == A[j]) {
ans = max(ans, 2 * min(pre[i], suf[j]));
}
}
}
cout << ans << endl;
}
return 0;
} 第二题（100%）
暴力枚举答案。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 10;
int n, A[MAXN];
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-2.txt", "r", stdin);
#endif // __LOCAL_WONZY__
while (cin >> n) {
for (int i = n; i >= 0; --i) cin >> A[i];
const double infd = 100;
vector<int> ans;
for (double x = -infd; x < infd; x += 0.01) {
double val_1 = 0;
for (int i = 0; i <= n; ++i) {
val_1 += A[i] * pow(x - 0.005, i);
}
double val_2 = 0;
for (int i = 0; i <= n; ++i) {
val_2 += A[i] * pow(x + 0.005, i);
}
double val = 0;
for (int i = 0; i <= n; ++i) {
val += A[i] * pow(x, i);
}
if (val_1 * val_2 < 0 || fabs(val) < 1e-6) {
ans.push_back(round(x * 100));
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
if (ans.empty())
cout << "No" << endl;
else {
for (int i = 0; i < ans.size(); ++i) {
cout << fixed << setprecision(2) << ans[i] / 100.;
if (i == ans.size() - 1)
cout << endl;
else
cout << " ";
}
}
}
return 0;
} 第三题（100%）
暴力模拟，调调随机数，调调模拟次数，就 ac 了。当然也可以求公式。#include <bits/stdc++.h>
using namespace std;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
double randf(double minv, double maxv) { return minv + rand() / double(RAND_MAX / (maxv - minv)); }
int mock(double L, const double& d) {
if (L <= d) return 0;
double le = randf(0, L);
return mock(L - le, d) + 1;
}
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-3.txt", "r", stdin);
#endif // __LOCAL_WONZY__
int L, d;
while (cin >> L >> d) {
vector<int> cnt;
for (int _ = 0; _ < 25000000; ++_) {
cnt.push_back(mock(L, d));
}
double ans = accumulate(cnt.begin(), cnt.end(), 0);
ans /= cnt.size();
cout << fixed << setprecision(4) << ans << endl;
}
return 0;
} 第四题（100%）
hash 数组
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const unsigned long long base = 23333;
const int MAXN = 100005;
int T, n, A[MAXN][6];
unsigned long long hash_func(int ar[]) {
unsigned long long ret = 0;
for (int i = 0; i < 6; ++i) {
ret = ret * base + ar[i];
}
return ret;
}
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-4.txt", "r", stdin);
#endif // __LOCAL_WONZY__
cin >> T;
while (T--) {
cin >> n;
unordered_set<unsigned long long> st;
bool suc = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 6; ++j) {
scanf("%d", &A[i][j]);
}
if (suc) continue;
sort(A[i], A[i] + 6);
unsigned long long hash_val = hash_func(A[i]);
suc |= st.find(hash_val) != st.end();
st.insert(hash_val);
}
cout << (suc ? "YES" : "NO") << endl;
}
return 0;
} 第五题（100%）
Dijkstra 求一个两次最短路#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 2005;
const int MAXE = 1e5 + 5;
int T, N, M;
struct Edge {
int v, next, w;
Edge() {}
Edge(int v, int next, int w) : v(v), next(next), w(w) {}
} edge[MAXE];
int ESZ, head[MAXN];
void init() {
ESZ = 0;
memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w) {
edge[ESZ] = Edge(v, head[u], w);
head[u] = ESZ ++;
}
struct Dij {
struct QNode {
int u, cost;
QNode() {}
QNode(int u, int cost) : u(u), cost(cost) {}
bool operator > (const QNode& e) const {
return cost > e.cost;
}
} cur;
priority_queue<QNode, vector<QNode>, greater<QNode> > Q;
long long cost[MAXN];
bool vis[MAXN];
void init() {
while(!Q.empty()) Q.pop();
memset(vis, false, sizeof(vis));
memset(cost, 0x3f, sizeof(cost));
}
long long run(int src, int dst) {
int u, v, w;
Q.push(QNode(src, cost[src] = 0));
while(!Q.empty()) {
cur = Q.top();
Q.pop();
u = cur.u;
if(vis[u]) continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].next) {
v = edge[i].v, w = edge[i].w;
if(!vis[v] && cost[v] > cost[u] + w) {
Q.push(QNode(v, cost[v] = w + cost[u]));
}
}
}
return cost[dst];
}
} dij;
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-5.txt", "r", stdin);
#endif // __LOCAL_WONZY__
while(cin >> N >> M >> T) {
init();
for(int i = 1; i <= M; ++i) {
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
}
dij.init();
long long ans = dij.run(1, N);
dij.init();
ans += dij.run(N, 1);
cout << ans * T << endl;
}
return 0;
} 
全部评论
(2) 回帖