A. Altruistic Amphibians
Upsolved.
题意：
$有n只青蛙，其属性用三元组表示 <l_i, w_i, h_i> l_i是它能跳的高度，w_i是它的体重,h_i是它的身高$
一只青蛙的承重不能超过它的体重，它可以踩在别的青蛙上面跳
一口井的深度为$d， 一只青蛙能够跳出去当且仅当它离井口的距离严格小于它的l_i$
$离井口的距离为d - 它所踩的青蛙的身高和，当然可以不踩其他青蛙$
求最多跳出去多少只青蛙
思路：
显然，重量最大的青蛙肯定只能在最下面
那么按重量大小排个序
然后考虑递推到下面
$dp[i] 表示 重量为i的青蛙最高能处在什么样的高度$
有
$dp[j - a[i].w] = dp[j] +a[i].h \;\;j \in [a[i].w, 2 * a[i].w)$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
const int D = (int)1e8 + ;
int n, d;
struct node
{
int l, w, h;
void scan() { scanf("%d%d%d", &l, &w, &h); }
bool operator < (const node &r) const { return w > r.w; }
}a[N];
int dp[D]; int main()
{
while (scanf("%d%d", &n, &d) != EOF)
{
for (int i = ; i <= n; ++i) a[i].scan();
sort(a + , a + + n);
int res = ;
for (int i = ; i <= n; ++i)
{
if (dp[a[i].w] + a[i].l > d) ++res;
for (int j = a[i].w; j < min( * a[i].w, (int)1e8 + ); ++j)
dp[j - a[i].w] = max(dp[j - a[i].w], dp[j] + a[i].h);
}
printf("%d\n", res);
}
return ;
}
B. Baby Bites
Solved.
签到。
#include <bits/stdc++.h>
using namespace std; int n;
int pre, now;
string s; int f()
{
if (s == "mumble") return -;
int res = ;
for (int i = , len = s.size(); i < len; ++i) res = res * + s[i] - '';
return res;
} bool solve()
{
bool flag = ;
pre = ;
for (int i = ; i <= n; ++i)
{
cin >> s;
now = f();
if (now == -) ++pre;
else if (now != pre + ) flag = ;
else pre = now;
}
return flag;
} int main()
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
while (cin >> n) cout << (solve() ? "makes sense" : "something is fishy") << "\n";
return ;
}
C. Code Cleanups
Solved.
签到。
#include<bits/stdc++.h> using namespace std; int n;
int vis[]; int main()
{
while(~scanf("%d", &n))
{
memset(vis, , sizeof vis);
for(int i = , num; i <= n; ++i)
{
scanf("%d", &num);
vis[num]++;
}
int ans = ;
int tmp = ;
int pre = ;
for(int i = ; i <= ; ++i)
{
tmp += vis[i];
pre += tmp;
if(pre >= )
{
++ans;
pre = ;
tmp = ;
}
}
if(pre) ans++;
printf("%d\n", ans);
}
return ;
}
D. Delivery Delays
Upsolved.
题意：
有一张无向图，顶点1有一家披萨店，时不时会有一点发布订单表示它在$s_i时刻要一份披萨，这份披萨要在t_i时刻才能好$
$只有一个送货员，必须满足先到先服务的原则，如何安排送货流程使得等待时间最长的顾客的等待时间最短$
思路：
先预处理出任意两点之间的最短路径，再考虑二分答案
$用dp验证$
$dp[i][j][k] 表示已经送完前i个点，拿到前j个披萨，k \in [0, 1]$
$0 表示 目前处于第i个点，1表示目前处于披萨店$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1010
#define INFLL 0x3f3f3f3f3f3f3f3f
struct Graph
{
struct node
{
int to, nx, w;
node () {}
node (int to, int nx, int w) : to(to), nx(nx), w(w) {}
}a[N << ];
int head[N], pos;
void init()
{
memset(head, -, sizeof head);
pos = ;
}
void add(int u, int v, int w)
{
a[++pos] = node(v, head[u], w); head[u] = pos;
a[++pos] = node(u, head[v], w); head[v] = pos;
}
}G;
#define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; ~it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w) int n, m, q;
ll dist[N][N];
namespace Dij
{
struct node
{
int to; ll w;
node () {}
node (int to, ll w) : to(to), w(w) {}
bool operator < (const node &r) const { return w > r.w; }
};
bool used[N];
void run()
{
for (int st = ; st <= n; ++st)
{
for (int i = ; i <= n; ++i) dist[st][i] = INFLL, used[i] = false;
priority_queue <node> q; q.emplace(st, ); dist[st][st] = ;
while (!q.empty())
{
int u = q.top().to; q.pop();
if (used[u]) continue;
used[u] = ;
erp(u) if (!used[v] && dist[st][v] > dist[st][u] + w)
{
dist[st][v] = dist[st][u] + w;
q.emplace(v, dist[st][v]);
}
}
}
}
} ll dp[N][N][];
// dp[i][j][0] 表示已经送完前i个点，拿到前j个披萨，目前处于第i个点的最小时间
// dp[i][j][1] 表示已经送完前i个点，拿到前j个披萨，目前处于披萨店的最小时间
int s[N], u[N], t[N];
bool check(ll x)
{
memset(dp, 0x3f, sizeof dp);
dp[][][] = ;
for (int i = ; i < q; ++i)
{
for (int j = i; j <= q; ++j)
{
for (int o = ; o < ; ++o)
{
if (!o)
{
dp[i][j][] = min(dp[i][j][], dp[i][j][] + 1ll * dist[u[i]][]);
if (j > i)
{
ll T = dp[i][j][] + dist[u[i]][u[i + ]];
if (s[i + ] + x >= T)
dp[i + ][j][] = min(dp[i + ][j][], T);
}
}
else
{
if (j < q)
dp[i][j + ][] = min(dp[i][j + ][], max(dp[i][j][], 1ll * t[j + ]));
if (j > i)
{
ll T = dp[i][j][] + dist[][u[i + ]];
if (s[i + ] + x >= T)
dp[i + ][j][] = min(dp[i + ][j][], T);
}
}
}
}
}
return dp[q][q][] != INFLL;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
G.init();
for (int i = , u, v, w; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G.add(u, v, w);
}
Dij::run();
scanf("%d", &q);
for (int i = ; i <= q; ++i) scanf("%d%d%d", s + i, u + i, t + i);
ll l = , r = INFLL, res = -;
while (r - l >= )
{
ll mid = (l + r) >> ;
if (check(mid))
{
res = mid;
r = mid - ;
}
else
l = mid + ;
}
printf("%lld\n", res);
}
return ;
}
E. Explosion Exploit
Solved.
题意：
你有$n个随从，对方有m个随从，你现在可以发动一个技能，造成d点伤害$
$每点伤害都会等概率的下落到敌方的随从身上，求发动一次技能，敌方随从全部死亡的概率$
思路：
概率记忆化搜索
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, d;
int sum[][];
map <ll, double>dp; ll calc()
{
ll res = ;
for(int i = ; i <= ; ++i)
{
res += sum[][i];
res *= ;
}
for(int i = ; i <= ; ++i)
{
res += sum[][i];
res *= ;
}
return res;
} double DFS(ll S, int limit)
{
if(dp.count(S)) return dp[S];
int cnt = ;
for(int i = ; i <= ; ++i) cnt += sum[][i];
if(!cnt) return ;
if(limit == ) return ;
for(int i = ; i <= ; ++i) cnt += sum[][i];
double res = ;
for(int i = ; i < ; ++i)
{
for(int j = ; j <= ; ++j)
{
if(sum[i][j] == ) continue;
sum[i][j]--;
sum[i][j - ]++;
double tmp = DFS(calc(), limit - );
sum[i][j]++;
sum[i][j - ]--;
res += 1.0 * sum[i][j] / cnt * tmp;
}
}
dp[S] = res;
return res;
} int main()
{
while(~scanf("%d %d %d", &n, &m, &d))
{
dp.clear();
memset(sum, , sizeof sum);
for(int i = , num; i <= n; ++i)
{
scanf("%d", &num);
sum[][num]++;
}
for(int i = , num; i <= m; ++i)
{
scanf("%d", &num);
sum[][num]++;
}
double ans = DFS(calc(), d);
printf("%.10f\n", ans);
}
return ;
}
F. Firing the Phaser
Unsolved.
G. Game Scheduling
Unsolved.
H. House Lawn
Solved.
题意：
有一些割草机，工作一段时间，休息一段时间
求哪些机器在T周至少割草T次，如果有，按输入顺序输出价格最低的
思路：
因为$周期是LCM(t + r, 10080), 如果这个周期内是可以的，那就是可以的$
因为如果中间有一周割不完了，那么后面肯定是割不完的
因为开始的局面相当于满电让你割，那么对于后面的情况
每周平均割草的次数肯定小于等于前面的
#include <bits/stdc++.h>
using namespace std; #define N 110
#define ll long long ll l; int m;
ll Min; ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a % b);
} ll lcm(ll a, ll b)
{
return a * b / gcd(a, b);
} struct qnode
{
string name;
ll p, c, t, r;
bool flag;
void scan()
{
flag = false;
p = , c = , t = , r = ;
name = "";
string s;
getline(cin, s);
int i, len = s.size();
for (i = ; s[i] != ','; ++i)
name += s[i];
for (++i; s[i] != ','; ++i) p = p * + s[i] - '';
for (++i; s[i] != ','; ++i) c = c * + s[i] - '';
for (++i; s[i] != ','; ++i) t = t * + s[i] - '';
for (++i; i < len; ++i) r = r * + s[i] - '';
//cout << p << " " << c << " " << t << " " << r << endl;
}
void f()
{
ll need = l % (c * t) == ? l / (c * t) : l / (c * t) + ;
ll remind = ;
if (l % (c * t)) remind = t - (l - (c * t) * (need)) % c;
ll tot = need * (t + r);
tot -= remind;
flag = tot <= ;
if (flag) Min = min(Min, p);
}
void F4()
{
flag = false;
ll circle = lcm(t + r, );
ll T = circle / ;
if(circle / (t + r) * c * t>= T * l)
{
flag = true;
Min = min(Min, p);
}
}
}qarr[N]; int main()
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
while (cin >> l >> m)
{
string s;
getline(cin, s);
Min = 0x3f3f3f3f3f3f3f3f;
for (int i = ; i <= m; ++i) qarr[i].scan(), qarr[i].F4();
vector <string> res;
for (int i = ; i <= m; ++i) if (qarr[i].flag && qarr[i].p == Min) res.push_back(qarr[i].name);
for (auto it : res) cout << it << "\n";
if (res.empty()) cout << "no such mower\n";
}
return ;
}
I. Intergalactic Bidding
Solved.
简单模拟。
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define DLEN 4
#define MAXN 9999
int n; class BigNum
{
private:
int a[N];
int len;
public:
BigNum() { len = ; memset(a, , sizeof a); }
BigNum(const char *s)
{
int t, k, index, L, i;
memset(a, , sizeof a);
L = strlen(s);
len = L / DLEN;
if (L % DLEN) ++len;
index = ;
for (int i = L - ; i >= ; i -= DLEN)
{
t = ;
k = i - DLEN + ;
if (k < ) k = ;
for (int j = k; j <= i; ++j)
t = t * + s[j] - '';
a[index++] = t;
}
}
bool operator == (const BigNum &T) const
{
if (len != T.len) return false;
for (int i = ; i < len; ++i) if (a[i] != T.a[i])
return false;
return true;
}
bool operator < (const BigNum &T) const
{
if (len != T.len) return len < T.len;
for (int i = len - ; i >= ; --i) if (a[i] != T.a[i])
return a[i] < T.a[i];
return true;
}
BigNum& operator = (const BigNum &n)
{
int i;
len = n.len;
memset(a, , sizeof a);
for (int i = ; i < len; ++i) a[i] = n.a[i];
return *this;
}
BigNum operator - (const BigNum &T) const
{
int i, j, big;
BigNum t1, t2;
t1 = *this, t2 = T;
big = t1.len;
for (i = ; i < big; ++i)
{ if (t1.a[i] < t2.a[i])
{
j = i + ;
while (t1.a[j] == ) ++j;
t1.a[j--]--;
while (j > i) t1.a[j--] += MAXN;
t1.a[i] += MAXN + - t2.a[i];
}
else t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[t1.len - ] == && t1.len > )
{
t1.len--;
big--;
}
return t1;
}
void print()
{
cout << a[len - ];
for (int i = len - ; i >= ; --i)
printf("%04d", a[i]);
puts("");
}
}; char str[N];
BigNum s; struct node
{
string name;
BigNum val;
void scan()
{
cin >> name;
cin >> str;
val = BigNum(str);
}
bool operator < (const node &r) { return r.val < val; }
}arr[N]; vector <string> res;
int main()
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
while (cin >> n)
{
res.clear();
cin >> str; s = BigNum(str);
for (int i = ; i <= n; ++i) arr[i].scan();
sort(arr + , arr + + n);
for (int i = ; i <= n; ++i) if (arr[i].val < s)
{
s = s - arr[i].val;
res.push_back(arr[i].name);
}
if (!(s == BigNum(""))) cout << "0\n";
else
{
cout << res.size() << "\n";
for (auto it : res) cout << it << "\n";
}
}
return ;
}
J. Jumbled String
Solved.
题意：
要求构造一个01串，使得所有子序列中，$00出现a次，01出现b次，10出现c次，11出现d次$
思路：
显然，如果$a > 0, b > 0， 那么其中0的个数和1的个数是固定的$
而且有$b + c == cnt[0] \cdot cnt[1]$
$此处cnt 表示 0的个数或者1的个数$
$那么刚开始0全放全面,1全放后面，然后把1往前面挪动，直到满足条件$
记得特判几种特殊情况以及$Impossible$
#include <bits/stdc++.h>
using namespace std; #define ll long long
ll a, b, c, d;
ll n, m, need, remind; ll f(ll x)
{
for (ll i = ; ; ++i)
{
if ((i * (i - ) / ) > x) return -;
if (i * (i - ) / == x) return i;
}
} int main()
{
while (scanf("%lld%lld%lld%lld", &a, &b, &c, &d) != EOF)
{
if (!a && !b && !c && !d) puts("");
else if (!b && !c && !d)
{
n = f(a);
if (n == -) puts("impossible");
else
{
for (int i = ; i <= n; ++i) putchar('');
puts("");
}
}
else if (!a && !b && !c)
{
m = f(d);
if (m == -) puts("impossible");
else
{
for (int i = ; i <= m; ++i) putchar('');
puts("");
}
}
else
{
n = f(a), m = f(d);
if (n == - || m == - || n * m != (b + c)) puts("impossible");
else
{
need = b / n;
remind = b % n;
for (int i = ; i <= m - need - (remind ? : ); ++i) putchar('');
for (int i = ; i <= n; ++i)
{
putchar('');
if (i == remind) putchar('');
}
for (int i = ; i <= need; ++i) putchar('');
puts("");
}
}
}
return ;
}
K. King's Colors
Solved.
题意：
给出一棵树，相邻结点不能染相同颜色，求恰好染k种颜色的方案数。
思路：
因为是一棵树，那么如果所求的是$<=k种颜色的方案数 答案就是k * (k - 1)^ {n -1}$
$因为根节点有k种选择，其他结点都有k - 1种选择$
但实际上这包含了$k - 2, k - 3, k - 4 \cdots 2的方案数 容斥一下即可$
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = ;
const ll MOD = 1e9 + ; ll fac[maxn], invfac[maxn], inv[maxn]; ll qpow(ll x,ll n)
{
ll res = ;
while(n)
{
if(n & ) res = res * x % MOD;
x = x * x % MOD;
n >>= ;
}
return res;
} void Init()
{
fac[] = invfac[] = inv[] = ;
fac[] = invfac[] = inv[] = ;
for(int i = ; i < maxn; ++i)
{
fac[i] = fac[i - ] * i % MOD;
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
invfac[i] = invfac[i - ] * inv[i] % MOD;
}
} ll calc(int n, int m)
{
if (n < || m < ) return ;
if (n == m || m == ) return ;
return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
} int n, k; int main()
{
Init();
while(~scanf("%d %d",&n, &k))
{
for(int i = , num; i < n; ++i) scanf("%d", &num);
int flag = ;
ll ans = ;
for(int i = k; i >= ; --i, flag = !flag)
{
if(flag) ans = (ans + calc(k, i) * i % MOD * qpow(i - , n - ) % MOD) % MOD;
else ans = (ans - calc(k, i) * i % MOD * qpow(i - , n - ) % MOD + MOD) % MOD;
}
printf("%lld\n", ans);
}
return ;
}