A：
水。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INFLL = 0x3f3f3f3f3f3f3f3f; ll n, m, h, w; ll solve()
{
ll cnt = ;
ll tn = n, tm = m;
while(tn > h)
{
tn = (tn + ) >> ;
cnt++;
}
while(tm > w)
{
tm = (tm + ) >> ;
cnt++;
}
return cnt;
} int main()
{
while(~scanf("%lld %lld %lld %lld", &n, &m, &h, &w))
{
ll ans = INFLL;
ans = min(ans, solve());
swap(h, w);
ans = min(ans, solve());
printf("%lld\n", ans);
}
return ;
}
B：留坑。
C:
题意：有n道题目，总时间为T,对于每一道题目有完成的时间和可以得到的分数，做题策略为按照一定顺序做题，如果时间足够，那么就可以得到这道题的分数，安排一个顺序，使得得到的分数最少
思路：如果总时间<=T 那么直接输出所有分数
反之 ，考虑一定存在至少一道题目恰好不能被完成
枚举这道题目，考虑所有时间小于这道题目的所有题目都要被完成
对于每道题目，还需要枚举剩下的时间，使得它完不成
那么排序之后枚举，左边的题目都要做完，右边的做01背包
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 2010
#define pll pair <ll, ll>
#define INF 0x3f3f3f3f3f3f3f3f
int n, m;
pll a[N];
ll dp[N][N];
ll tot_time, tot_sco; int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
tot_time = , tot_sco = ;
for (int i = ; i <= n; ++i)
{
scanf("%lld%lld", &a[i].first, &a[i].second);
tot_time += a[i].first;
tot_sco += a[i].second;
}
if (tot_time <= m)
{
printf("%lld\n", tot_sco);
continue;
}
sort(a + , a + + n);
memset(dp, 0x3f, sizeof dp);
dp[n + ][] = ;
for (int i = n; i > ; --i)
{
for (int j = m; j >= a[i].first; --j)
dp[i][j] = min(dp[i][j], dp[i + ][j - a[i].first] + a[i].second);
for (int j = ; j <= m; ++j) dp[i][j] = min(dp[i][j], dp[i + ][j]);
}
ll step = , tot = , res = INF;
for (int i = ; i <= n; ++i)
{
ll tmp = INF;
for (int j = m - step; j + a[i].first + step > m && j >= ; --j) tmp = min(tmp, tot + dp[i + ][j]);
res = min(tmp, res);
step += a[i].first;
tot += a[i].second;
}
printf("%lld\n", res);
}
return ;
}
D：
题意：给出一棵树中每个点的度数，构造这一棵树
思路：将点按度数从大到小排序，每个点会有一个父亲，最多连出n - 1个点。
#include <bits/stdc++.h>
using namespace std; #define N 200010
#define pii pair <int, int>
int n, d[N], pos[N], fa[N]; bool cmp (int a, int b) { return d[a] > d[b]; } int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", d + i), pos[i] = i;
sort(pos + , pos + + n, cmp);
for (int i = ; i <= n; ++i) --d[pos[i]];
int id = ;
for (int i = ; i <= n; ++i)
{
while (d[pos[i]]--)
fa[pos[++id]] = pos[i];
}
for (int i = ; i <= n; ++i) if (i != pos[])
printf("%d %d\n", fa[i], i);
}
return ;
}
E：
水。
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1000010
char s[N]; int main()
{
while (scanf("%s", s + ) != EOF)
{
int cnt = ;
for (int i = , len = strlen(s + ); i <= len; ++i) cnt += (s[i] == 'A');
ll res = ;
for (ll i = ; ; ++i)
{
if (i * (i + ) / > cnt) break;
res = i;
}
printf("%lld\n", res);
}
return ;
}
F：留坑。
G：
题意：给出一个n 要构造一个长度为n的序列，满足题目要求
思路：
如果是奇数
那么存在 起始点3 有 $2 \cdot 5 \cdot 6 = 3 \cdot 4 \cdot 5$
#include <bits/stdc++.h>
using namespace std; int n; int main()
{
while (scanf("%d", &n) != EOF)
{
if (n == ) puts("NO");
else if (n & )
{
puts("YES");
puts("");
printf("-++");
for (int i = ; i <= n; ++i) printf("%c", "+-"[i & ]);
puts("");
}
else
{
puts("YES");
puts("");
for (int i = ; i <= n; ++i) printf("%c", "-+"[i & ]);
puts("");
}
}
return ;
}
H：
题意：给出0-9每个数字的个数，构造一个最大的数，使得任意连续三位连起来都是3的倍数。数字可以不用完
思路：先将所有数字模3
就是三种数字 0， 1， 2
再考虑 排列
显然 三个一组三个一组，三个中012至少出现一次，即012的全排列，一共6种，
再考虑 全放0, 1, 2 又是三种
再考虑 只有一位或者两位，可以任意摆放
一共十种情况，去掉前导0之后取最大即可。
#include <bits/stdc++.h>
using namespace std; #define N 100010
int cnt[], tmp_cnt[], cntt[], tmp_cntt[], tar[], Max[], tmp_Max[];
char ans[][N];
int pos; void g()
{
for (int i = ; i < ; ++i) tmp_cnt[i] = cnt[i];
for (int i = ; i < ; ++i)
{
tmp_cntt[i] = cntt[i];
tmp_Max[i] = Max[i];
}
} void f()
{
for (int i = ; i < ; ++i) cnt[i] = tmp_cnt[i];
for (int i = ; i < ; ++i)
{
cntt[i] = tmp_cntt[i];
Max[i] = tmp_Max[i];
}
} void solve(int ide, int *tar)
{
pos = ;
while ()
{
for (int i = ; i < ; ++i)
{
int id = tar[i];
if (!cntt[id])
return;
if (cnt[Max[id]] == )
{
Max[id] = -;
for (int i = ; i >= ; --i) if (i % == id && cnt[i])
{
Max[id] = i;
break;
}
if (Max[id] == -) return;
}
ans[ide][++pos] = Max[id] + '';
--cntt[id];
--cnt[Max[id]];
}
}
} void work(int id)
{
pos = ;
while (cntt[id])
{
if (!cnt[Max[id]])
{
Max[id] = -;
for (int i = ; i >= ; --i) if (i % == id && cnt[i])
{
Max[id] = i;
break;
}
if (Max[id] == -) return;
}
ans[id + ][++pos] = Max[id] + '';
--cnt[Max[id]];
--cntt[id];
}
} bool cmp(char *a, char *b)
{
int lena = strlen(a + ), lenb = strlen(b + );
if (lena != lenb) return lena < lenb;
for (int i = ; i <= lena; ++i) if (a[i] != b[i])
return a[i] < b[i];
return ;
} void cle(int id)
{
int len = strlen(ans[id] + );
pos = len + ;
for (int i = , len = strlen(ans[id] + ); i <= len; ++i) if (ans[id][i] != '')
{
pos = i;
break;
}
if (pos == len + )
{
ans[id][] = '';
ans[id][] = ;
}
else
{
for (int i = ; i + pos - <= len; ++i)
ans[id][i] = ans[id][i + pos - ];
ans[id][len - pos + ] = ;
}
} int main()
{
while (scanf("%d", cnt) != EOF)
{
memset(cntt, , sizeof cntt);
memset(Max, -, sizeof Max);
memset(ans, , sizeof ans);
for (int i = ; i <= ; ++i) scanf("%d", cnt + i);
for (int i = ; i < ; ++i) if (cnt[i])
{
cntt[i % ] += cnt[i];
Max[i % ] = i;
}
int res = ;
for (int i = ; i >= && res < ; --i) if (cnt[i])
{
res = res * + i;
if (res < && cnt[i] > )
res = res * + i;
}
g();
pos = ;
while (res)
{
ans[][++pos] = res % + '';
res /= ;
}
ans[][pos + ] = ;
reverse(ans[] + , ans[] + pos + );
tar[] = , tar[] = , tar[] = ;
int ide = ;
do
{
f();
solve(ide, tar); ans[ide][pos + ] = ;
++ide;
} while (next_permutation(tar, tar + ));
for (int i = ; i < ; ++i)
{
f(); pos = ; work(i);
ans[i + ][pos + ] = ;
}
for (int i = ; i < ; ++i) cle(i);
pos = ;
for (int i = ; i < ; ++i) if (cmp(ans[pos], ans[i]))
pos = i;
printf("%s\n", ans[pos] + );
}
return ;
}
I：
题意：阅读理解题。有一个类似游泳圈的东西，有四道大道路，内圈，外圈，上圈，下圈，每个国家有四个城市，四个城市分别属于四道大道路上，定义经过一个国家为至少经过一条该国家的道路，有从任意一个国家的内城市出发，经过所有城市的最短路径
思路：考虑两种走法，
一种是两个国家之间都走内圈，还有一种是间隔走，走一下内圈，走一下上圈，取Min
#include <bits/stdc++.h>
using namespace std; #define ll long long
const double PI = acos(-1.0);
ll r, R, n; int main()
{
while (scanf("%lld%lld%lld", &r, &R, &n) != EOF)
{
if (n == )
{
printf("%.15f\n", PI * r / );
continue;
}
double len1 = (R - r) * 2.0 * PI / n;
double len2 = R * 2.0 * PI / n;
double ans1 = ( * n - ) * PI * r / + (n - ) * len1;
double ans2 = n * PI * r / + (n / ) * len2 + ((n - ) / ) * len1;
printf("%.15f\n", min(ans1, ans2));
}
return ;
}
J：留坑。
k：留坑。
L：水。
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1010
int n, k, x, cnt;
char s[];
ll Bit[]; ll f(char *s)
{
ll res = ;
for (int i = , len = strlen(s + ); i <= len; ++i)
res = res * + s[i] - '';
return res;
} int main()
{
Bit[] = ;
for (int i = ; i <= ; ++i) Bit[i] = Bit[i - ] * ;
while (scanf("%d", &n) != EOF)
{
cnt = ; ll Min = ;
for (int i = ; i <= n; ++i)
{
scanf("%s", s + );
cnt = max(cnt, (int)strlen(s + ));
Min = max(Min, f(s));
}
Min = max((ll)n, Min);
Min = max(Min, Bit[cnt]);
printf("%lld\n", Min);
for (int i = ; i <= cnt; ++i) putchar(''); putchar('\n');
}
return ;
}