A. Catch the Coin
题意:在一个二维坐标系上有一个硬币每秒y轴坐标减一，而你每秒可以向旁边八个方向移动，问你有没有一个时刻你会和硬币重叠。
思路：注意到在y小于-2时，我们无论如何都追不到硬币，而其他时候我们可以采取向左下或者右下的策略来保持和硬币y轴下落同步移动的时候接近硬币的x轴位置。所以判断一下y是否小于等于-2即可。
注意每个题都是折叠代码段！
点击查看代码
void solve()
{
cin >> n;
for (int i = 1;i <= n;i++)
{
int x, y;
cin >> x >> y;
if (y <= -2) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
B. Substring and Subsequence
题意：给你一个a串和b串，让你在a串中添加字母，使得b串必须是a串的子串。
思路：我们可以想到如果a,b两个字符串没有字母重叠的话，答案就是a+b的长度，那么如果存在重叠的话答案就是a+b-max(重叠)。考虑到以b串每个字母为起点去遍历a有多长连续字符答案是不一样的，所以我们贪心的枚举每个b子串中的字母为起点的情况，就可以找到重叠的max值。
点击查看代码
void solve()
{
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
a = " " + a, b = " " + b;
int ans = 0;
for (int i = 1;i <= m;i++)
{
int cnt = i;
for (int j = 1;j <= n;j++)
{
if (b[cnt] == a[j]) cnt++;
}
ans = max(ans, cnt - i);
}
cout << n + m - ans << endl;
}
C. Two Movies
题意：有两部电影，n个人打分。每个人打的分为1电影评分加一，0不变，-1减一。你可以看到每个人对两部电影的评分，而你要选择其中一个使用，就是说如果a对一电影打了1分，对二电影打了0分，你可以选择让1电影加一分或者2电影分不变。最后你的答案就是分最低电影的评分。
思路：我们贪心的去想，如果是有(-1,0),(1,0),(-1,1)的情况，我们肯定是能选择加分就加分，能不减分就不变。而需要特殊处理的就是(1,1),(-1,-1)两种情况，因为这两种情况必须选一个加分选一个减分。所以我们记录这两种情况出现的次数，然后贪心思考怎么去把分加给或者减给1,2两部电影会得到最优解。这里我是采用先算出1,2此时的平均值，然后先把分加给最小达到平均值，把最大的减分减到平均来消耗减分项。然后分情况有加分或减分有剩余或没剩余。
点击查看代码
void solve()
{
int a1 = 0, b1 = 0;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) cin >> b[i];
int cnt1 = 0, cnt2 = 0;
for (int i = 1;i <= n;i++)
{
if (a[i] == b[i] && a[i] == 1)
{
cnt1++;
}
else if (a[i] == 0 || b[i] == 0)
{
if (a[i] == 1) a1 ++;
else if (b[i] == 1) b1 ++;
}
else if (a[i] == 1 || b[i] == 1)
{
if (a[i] == 1) a1++;
else if (b[i] == 1) b1++;
}
else if (a[i] == b[i] && a[i] == -1)
{
cnt2++;
}
}
int k = (a1 + b1) / 2;
if (min(a1, b1) + cnt1 <= max(a1, b1) - cnt2) cout << min(a1, b1) + cnt1 << endl;
else {
int c = a1;
a1 = min(c, b1);
b1 = max(c, b1);
if (k - a1 <= cnt1) {
cnt1 -= (k - a1);
a1 = k;
if (b1 - k <= cnt2) {
cnt2 -= (b1 - k);
b1 = k;
cnt1 -= cnt2;
if (cnt1 == 0) cout << k << endl;
else if (cnt1 > 0) cout << k + cnt1 / 2 << endl;
else {
cnt1 = -cnt1;
cout << k - ceil(cnt1 / 2.0) << endl;
}
}
else {
b1 -= cnt2;
if (b1 - a1 >= cnt1) cout << a1 + cnt1 << endl;
else cout << b1 + (cnt1 - (b1 - a1)) / 2 << endl;
}
}
else {
a1 += cnt1;
if (b1 - k <= cnt2) {
cnt2 -= (b1 - k);
if (b1 - a1 >= cnt2) cout << b1 << endl;
else cout << b1 - ceil((cnt2 - (b1 - a1)) / 2.0) << endl;
}
else {
cout << b1 << endl;
}
}
}
}
D. Smithing Skill
题意：你可以消耗金属获得经验，然后每次消耗完都会返还给你一些金属，而这个过程也会给你经验。就是如果存在(9,8)的话，就是你用掉9金属然后得到8金属，最后只消耗了1金属获得了两点经验。而你有m个金属堆，金属堆中不同的金属不能叠加，所以要算每个堆的答案最后加起来。最后问你能用这些金属最多获得多少经验。
思路：首先我们能想到肯定是用转化率最多的金属最优，也就是a-b越小越好。然后我们做一个d数组用来存在每个大小段你能使用的最优转化。比如有(4,3),(3,1)那么我们可以得到d[4]=1,d[3]=2,同理d[5]=1,d[6]=1....但d[1],d[2]因为不存在小于等于2金属数量才能做到的转化，所以我们初始它们为无穷大。
所以我们在这里得到一个递推关系d[i]=min(d[i-1],d[i])。
得到每个金属个数最优转化解后我们将其转化为经验，在这里我们做一个f数组，得到递推关系f[i]=max(f[i],f[i-d[i]]+2)
然后我们将以上两个递推O(n)的递推到1e6的数据就可以得到每个金属个数的最大经验。但注意Cj能跑到1e9,所以我们对于大于1e6的数据先用1e6的最优解砍到1e6以下然后再加上f[cj]即可。
点击查看代码
void solve()
{
cin>>n>>m;
vector<int> d(1e6+5,1e7);
vector<int> f(N);
for(int i=1;i<=n;i++) {
cin>>a[i];
}
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++){
d[a[i]]=min(d[a[i]],a[i]-b[i]);
}
for(int i=1;i<=1e6;i++){
d[i]=min(d[i],d[i-1]);
}
for(int i=1;i<=1e6;i++){
if(d[i]==1e7) continue;
f[i]=max(f[i],f[i-d[i]]+2);
}
int res=0;
for(int i=1;i<=m;i++){
int x;
cin>>x;
if(x>1e6)
{
int s=1e6;
int k=(x-s)/d[s]+1;
x-=k*d[s];
res+=k*2;
}
res+=f[x];
}
cout<<res<<endl;
}