A. Kitchen Utensils
Water.
#include <bits/stdc++.h>
using namespace std; #define N 110
int n, k, cnt[N]; int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
memset(cnt, , sizeof cnt);
for (int i = , x; i <= n; ++i)
{
scanf("%d", &x);
++cnt[x];
}
int Max = ;
for (int i = ; i <= ; ++i) Max = max(Max, cnt[i] % k == ? cnt[i] / k : cnt[i] / k + );
int res = ;
for (int i = ; i <= ; ++i) if (cnt[i])
{
res += Max * k - cnt[i];
}
printf("%d\n", res);
}
return ;
}
B. Personalized Cup
Water.
#include <bits/stdc++.h>
using namespace std; #define INF 0x3f3f3f3f
#define N 110
int pos[N], w[N], h[N], n;
string s; void init()
{
memset(w, 0x3f, sizeof w);
memset(h, 0x3f, sizeof h);
memset(pos, -, sizeof pos);
for (int i = ; i >= ; --i)
{
for (int j = ; j <= i; ++j) if (i % j == )
{
int a = i / j, b = j;
if (a > b) swap(a, b);
if (a <= && b <= && a <= w[i])
{
pos[i] = i;
w[i] = a;
h[i] = b;
}
if (w[i + ] < w[i])
{
pos[i] = pos[i + ];
w[i] = w[i + ];
h[i] = h[i + ];
}
}
}
} int main()
{
init();
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
while (cin >> s)
{
n = s.size();
cout << w[n] << " " << h[n] << "\n";
int need = pos[n] - n;
int must = need / w[n];
int remind = need % w[n];
for (int i = , pos = ; i <= w[n]; ++i)
{
int j = ;
for (; j <= must; ++j) cout << "*";
if (remind) cout << "*", ++j, --remind;
for (; j <= h[n]; ++j) cout << s[pos++];
cout << "\n";
}
}
return ;
}
C. Playing Piano
Upsolved.
思路：每一位枚举，记忆化搜索。$dp[i][j] 表示第i位放j是否可以$
#include <bits/stdc++.h>
using namespace std; #define N 100010
int n, a[N], res[N], dp[N][]; int DFS(int i, int num)
{
if (i > n) return ;
int &x = dp[i][num];
if (x != -) return x;
if (a[i] > a[i - ])
{
for (int j = num + ; j <= ; ++j)
{
x = DFS(i + , j);
if (x) return res[i] = j, x = ;
}
}
else if (a[i] < a[i - ])
{
for (int j = ; j < num; ++j)
{
x = DFS(i + , j);
if (x) return res[i] = j, x = ;
}
}
else
{
for (int j = ; j <= ; ++j) if (j != num)
{
x = DFS(i + , j);
if (x) return res[i] = j, x = ;
}
}
return x = ;
} int main()
{
while (scanf("%d", &n) != EOF)
{
memset(dp, -, sizeof dp);
a[] = ;
for (int i = ; i <= n; ++i) scanf("%d", a + i);
if (DFS(, )) for (int i = ; i <= n; ++i) printf("%d%c", res[i], " \n"[i == n]);
else puts("-1");
}
return ;
}
D. Barcelonian Distance
Solved.
题意：
在一个二维平面中，有一条直线，有两点个点，只能走这条直线上或者方格线上，求两点最短路径
思路：
考虑每个点到直线上通过方格线走只有两种方式，即横着走，纵着走
那么通过直线的方式即有四种
还有一种直接是曼哈顿距离，取$Min$即可
#include <bits/stdc++.h>
using namespace std; #define ll long long
const double eps = 1e-;
ll a, b, c, x[], y[];
double xa[], ya[], xb[], yb[]; double dis(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) * 1.0 + (y1 - y2) * (y1 - y2) * 1.0);
} double calcx(ll y)
{
return -(b * y + c) * 1.0 / a;
} double calcy(ll x)
{
return -(a * x + c) * 1.0 / b;
} int main()
{
while (scanf("%lld%lld%lld", &a, &b, &c) != EOF)
{
for (int i = ; i < ; ++i) scanf("%lld%lld", x + i, y + i);
double res = abs(x[] - x[]) + abs(y[] - y[]);
xa[] = x[]; ya[] = calcy(x[]);
xa[] = calcx(y[]); ya[] = y[];
xb[] = x[]; yb[] = calcy(x[]);
xb[] = calcx(y[]); yb[] = y[];
for (int i = ; i < ; ++i)
{
for (int j = ; j < ; ++j)
{
res = min(res, dis(x[], y[], xa[i], ya[i]) + dis(x[], y[], xb[j], yb[j]) + dis(xa[i], ya[i], xb[j], yb[j]));
}
}
printf("%.15f\n", res);
}
return ;
}
E. The Unbearable Lightness of Weights
Upsolved.
题意：
有n个砝码，知道所有砝码的重量，但是不知道每个砝码和重量的对应关系，可以有一次询问，问用k个砝码组成总重量为m的方案，求最后你最多知道多少个砝码的具体重量
思路：
如果不同重量的砝码种类不超过2，直接输出n
01背包求出拼成重量为w, 物品个数为k的方案数，然后对于每种重量的砝码枚举个数，当且仅当当前个数和数量只有唯一一种方式组成时，那么这个数量就是合法的，可以用来更新答案
#include <bits/stdc++.h>
using namespace std; #define N 110
int n, sum, tot, a[N], dp[N * N][N], cnt[N], C[N][N]; void init()
{
for (int i = ; i <= ; ++i) for (int j = ; j <= i; ++j)
{
if (j == || j == i) C[i][j] = ;
else C[i][j] = C[i - ][j - ] + C[i - ][j];
}
} void Run()
{
init();
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i)
{
scanf("%d", a + i), sum += a[i], ++cnt[a[i]];
if (cnt[a[i]] == ) ++tot;
}
if (tot <= )
{
printf("%d\n", n);
continue;
}
dp[][] = ;
for (int i = ; i <= n; ++i)
{
for (int j = sum; j >= a[i]; --j) for (int k = ; k <= n; ++k)
dp[j][k] += dp[j - a[i]][k - ];
}
int res = ;
for (int i = ; i <= ; ++i) if (cnt[i])
{
for (int j = ; j <= cnt[i]; ++j)
{
if (dp[i * j][j] == C[cnt[i]][j])
res = max(res, j);
}
}
printf("%d\n", res);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
F. Vasya and Maximum Matching
Unsolved.
G. Chattering
Unsolved.