#include <bits/stdc++.h>
using namespace std; int main(void) {
int d1, d2, d3;
scanf ("%d%d%d", &d1, &d2, &d3);
printf ("%d\n", min (min (2 * (min (d1, d2) + d3), 2 * (d1 + d2)), d1 + d2 + d3)); return 0;
}
构造(坑) B - Spongebob and Joke
题目不难,但是有坑点:如果可能Ambiguity的话不能直接break,因为可能是Impossible
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + 5;
int a[N], f[N], b[N];
struct Pos {
int cnt, id;
}p[N]; int main(void) {
int n, m; scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &f[i]);
p[f[i]].cnt++; p[f[i]].id = i;
}
for (int i=1; i<=m; ++i) {
scanf ("%d", &b[i]);
}
int ans = 0; //-1 Impossible 1 Ambiguity 0 Possible
for (int i=1; i<=m; ++i) {
if (p[b[i]].cnt == 0) {
ans = -1; break;
}
else if (p[b[i]].cnt > 1) {
ans = 1; //break;
}
else {
a[i] = p[b[i]].id;
}
}
if (ans == -1) puts ("Impossible");
else if (ans == 1) puts ("Ambiguity");
else {
puts ("Possible");
for (int i=1; i<=m; ++i) {
printf ("%d%c", a[i], i == m ? '\n' : ' ');
}
} return 0;
}
预处理出前缀最大值和后缀最小值
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + 5;
int a[N];
int pmx[N], pmn[N]; inline int Max(int a, int b) {
if (a > b) return a;
else return b;
} inline int Min(int a, int b) {
if (a < b) return a;
else return b;
} int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
pmx[i] = Max (pmx[i-1], a[i]);
//printf ("i: %d mx: %d\n", i, pmx[i]);
}
pmn[n+1] = 0x3f3f3f3f;
for (int i=n; i>=1; --i) {
pmn[i] = Min (pmn[i+1], a[i]);
//printf ("i: %d mx: %d\n", i, pmx[i]);
}
if (n == 1) {
puts ("1"); return 0;
}
int ans = 0, i = 1;
while (i < n) {
while (i < n && pmx[i] > pmn[i+1]) {
i++;
}
//printf ("now: %d\n", i);
if (i == n) {
ans++; break;
}
else {
ans++; i++;
if (i == n) {
ans++; break;
}
}
}
printf ("%d\n", ans); return 0;
}
找规律+暴力 D - Spongebob and Squares
题意:问有x个不同的正方形的方案数
分析:x = n * m + (n - 1) * (m -1) + ... + 1 * (m - (n-1)) = (-n^3 + 3mn^2 + (3m+1)*n ))/ 6, 可以想象成2 * 2的正方形比1*1的在行上少了1种可能,在列上也少了1种可能,以此类推.然后暴力枚举判断
#include <bits/stdc++.h>
using namespace std; typedef long long ll; ll get_m(ll x, ll n) {
ll ret = (2 * x + (n * n * n - n) / 3) / (n * n + n);
return ret;
} ll cal(ll n, ll m) {
ll ret = -n * n * n + 3 * (n * n + n) * m + n;
ret /= 6;
return ret;
} int main(void) {
set<pair<ll, ll> > S;
ll x; scanf ("%lld", &x);
for (ll i=1; i<=3000000; ++i) {
ll m = get_m (x, i);
if (m < i) break;
if (cal (i, m) == x) {
S.insert (make_pair (i, m));
if (i != m) {
S.insert (make_pair (m, i));
}
}
}
set<pair<ll, ll> >::iterator it;
printf ("%d\n", (int) S.size ());
for (it=S.begin (); it!=S.end (); ++it) {
printf ("%lld %lld\n", it->first, it->second);
} return 0;
}