Codeforces Round #333 (Div. 2)
水题，但是pow的精度不高，应该是转换成long long精度丢失了干脆直接double就可以了。被hack掉了。用long long能存的下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int b1[44], b2[44];
int n, m;
int main(void) {
scanf ("%d%d", &n, &m);
double ans1 = 0, ans2 = 0;
for (int i=1; i<=n; ++i) {
scanf ("%d", &b1[i]);
}
for (int i=n; i>=1; --i) {
ans1 += pow ((double) m, n-i) * b1[i];
}
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &b2[i]);
}
for (int i=n; i>=1; --i) {
ans2 += pow ((double) m, n-i) * b2[i];
}
if (ans1 < ans2) puts ("<");
else if (ans1 > ans2) puts (">");
else puts ("=");
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int b1[44], b2[44];
int n, m;
ll _pow(int m, int x) {
ll ret = 1;
for (int i=1; i<=x; ++i) {
ret *= m;
}
return ret;
}
int main(void) {
cout << (ll) pow (39, 9) << endl;
cout << _pow (39, 9) << endl;
scanf ("%d%d", &n, &m);
ll ans1 = 0, ans2 = 0;
for (int i=1; i<=n; ++i) {
scanf ("%d", &b1[i]);
}
for (int i=n; i>=1; --i) {
ans1 += _pow (m, n-i) * b1[i];
}
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &b2[i]);
}
for (int i=n; i>=1; --i) {
ans2 += _pow (m, n-i) * b2[i];
}
if (ans1 < ans2) puts ("<");
else if (ans1 > ans2) puts (">");
else puts ("=");
return 0;
}
/*
9 39
10 20 16 36 30 29 28 9 8
9 38
12 36 10 22 6 3 19 12 34
*/
尺取法 B - Approximating a Constant Range
简单说就是维护[i, j]区间的最大值和最小值以及它们的最后的位置。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
int ans = 1, mn = a[1], mx = a[1], i = 1, j = 2;
int p1 = 1, p2 = 1;
while (j <= n) {
if (a[j] <= mn) {
mn = a[j]; p1 = j;
}
else if (a[j] >= mx) {
mx = a[j]; p2 = j;
}
if (mx - mn <= 1) {
ans = max (ans, j - i + 1);
}
else {
while (mx - mn > 1) {
if (p1 < p2 && p1 + 1 <= j) {
mn = a[p1+1]; i = p1 + 1; p1++;
}
else if (p1 >= p2 && p2 + 1 <= j) {
mx = a[p2+1]; i = p2 + 1; p2++;
}
else break;
}
ans = max (ans, j - i + 1);
}
j++;
}
printf ("%d
", ans);
return 0;
}
两点之间要不是地铁要不就是汽车，那么1到n也一样，只要一次BFS就行了，水水的。
我刚做了一道双向BFS，想套一个试试，写麻烦了，但是还是A掉了，想想还是有问题，vis数组有问题，数据水了。。因为有一个一定会在一步到达,和另一个不冲突
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e2 + 10;
const int M = N * N;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, w, nex;
Edge() {}
Edge(int v, int w, int nex) : v (v), w (w), nex (nex) {}
}edge[M];
int head[N];
bool lk[N][N];
bool vis[N][N][2];
bool vis2[N][2];
bool ok[2];
int n, m, e;
queue<int> que[2];
void init(void) {
memset (head, -1, sizeof (head));
e = 0;
}
void add_edge(int u, int v, int w) {
edge[e].v = v; edge[e].w = w; edge[e].nex = head[u];
head[u] = e++;
}
bool BFS(int typ, int tim) {
int sz = que[typ].size ();
while (sz--) {
int u = que[typ].front (); que[typ].pop ();
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (w != typ) continue;
if (v == n) {
ok[typ] = true;
if (ok[typ^1]) return true;
}
if (vis2[v][typ]) continue;
vis2[v][typ] = true;
if (vis[v][tim][typ^1]) continue;
vis[v][tim][typ] = true;
que[typ].push (v);
}
}
return false;
}
int run(void) {
que[0].push (1); que[1].push (1);
int step = 0;
while (!que[0].empty () || !que[1].empty ()) {
step++;
if (step > 800) break;
if (!ok[0]) {
if (BFS (0, step)) return step;
}
if (!ok[1]) {
if (BFS (1, step)) return step;
}
}
return -1;
}
int main(void) {
init ();
scanf ("%d%d", &n, &m);
for (int u, v, i=1; i<=m; ++i) {
scanf ("%d%d", &u, &v);
add_edge (u, v, 1);
add_edge (v, u, 1);
lk[u][v] = lk[v][u] = true;
}
int cnt = 0;
for (int i=1; i<=n; ++i) {
for (int j=i+1; j<=n; ++j) {
if (i == j || lk[i][j]) continue;
cnt++;
add_edge (i, j, 0);
add_edge (j, i, 0);
}
}
if (cnt == 0) {
puts ("-1"); return 0;
}
printf ("%d
", run ());
return 0;
}
找规律+区间端点 D - Lipshitz Sequence
题意：q次询问，询问[l, r]的所有子区间 sum (max (abs (a[i] - a[j]) / j - i)) (1 <= i < j <= n)
分析：首先要知道最大值是abs (a[i] - a[i-1])，然后要弄出多少个子区间包含了这个值，用到KMP思想，left[i]/right[i]能记录i最左边和最右边不大于该值的位置，左闭右开防止重复
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int lef[N], righ[N];
int n, m;
ll run(int l, int r) {
if (l == r) return 0;
for (int i=l+1; i<=r; ++i) {
int j = i - 1;
while (j > l && abs (a[j] - a[j-1]) <= abs (a[i] - a[i-1])) j = lef[j];
lef[i] = j;
}
for (int i=r; i>l; --i) {
int j = i + 1;
while (j <= r && abs (a[j] - a[j-1]) < abs (a[i] - a[i-1])) j = righ[j];
righ[i] = j;
}
ll ret = 0;
for (int i=l+1; i<=r; ++i) {
ret += 1ll * (i - lef[i]) * (righ[i] - 1 - i + 1) * abs (a[i] - a[i-1]);
}
return ret;
}
int main(void) {
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
for (int l, r, i=1; i<=m; ++i) {
scanf ("%d%d", &l, &r);
printf ("%I64d
", run (l, r));
}
return 0;
}
概率DP E - Kleofáš and the n-thlon
题意：n次比赛，m个人，现在给出n次比赛一个人的排名，问他最后的排名的期望
分析：转换成其余人得分少于他的概率 * 总人数 +１，dp[i][j] 表示前i次比赛，得分为j时的期望。dp[i][j] = sum + dp[i-1][j-1] - dp[i-1][j-m-1] - dp[i-1][j-a[i]]；状态转移用前缀和优化复杂度
#include <bits/stdc++.h>
using namespace std;
double dp[105][105*1005];
int a[105];
int main(void) {
int n, m; scanf ("%d%d", &n, &m);
int sum = 0;
for (int i=0; i<n; ++i) {
scanf ("%d", &a[i]); sum += a[i];
}
if (m == 1) {
printf ("%.10f
", 1.0); return 0;
}
dp[0][0] = m-1;
for (int i=1; i<=n; ++i) {
double sum = 0;
for (int j=i; j<=i*m; ++j) {
sum += dp[i-1][j-1] / (m-1);
if (j - 1 - m >= 0) sum -= dp[i-1][j-m-1] / (m-1);
dp[i][j] = sum;
if (j - a[i-1] >= 0) dp[i][j] -= dp[i-1][j-a[i-1]] / (m-1);
}
}
double ans = 1;
for (int i = 0; i < sum; i++) ans += dp[n][i];
printf("%.10f
", ans);
return 0;
}