2019组队赛第二场(ACM International Collegiate Programming Contest, Arabella Collegiate 解题报告 Apare_xzc

<mark>2019组队赛第二场</mark>(ACM International Collegiate Programming Contest, Arabella Collegiate 解题报告

by xzc,zx,lj

先扔一个codeforces链接
vj链接：CCNUACM Team Contest 2019 Round #2
这次比赛我们队(zx,lj,xzc)出了8个题，还是挺好的

A. Multiplication Dilemma
题意：
定义漂亮数为满足这样条件的整数x:

-1E9<=x<1E9
x要么是一位数，要么首尾不为零，后面跟若干个零

现在给你一个a x b(1e9<=a,b<=1e9),比如17 x 20，你要把它拆成若干个“漂亮数”的乘积之和。
样例:

input
2
55 20
70 17
output
60 x 20 - 5 x 20
-3 x 70 + 70 x 20

思路:
按数位展开，然后两重for输出即可
例如12345 * 789 = (10000+2000+300+40+5) * (700+80+9)
然后展开即可。

我们的代码<-(点这里)

B. Updating the Tree
全场没人出，先不写了
可能以后会补题吧 ~~应该不会了~~，补了题再来更新
loading…

C. Shortest Path！
分析：
题意都懒得说了，不是最短路，就是个将军饮马问题+勾股定理
lj推出公式以后，我敲上去，一发过(我们好像除了签到题D题和和E题读错题意剩下好像都是一发过)

我们的代码

D. Wooden Fence
签到题
题意：
给栅栏涂色，有n段(n为奇数)，必须黑白相间，而且必须先涂黑色(第一发wa在了这里)，黑油漆能涂x段，白油漆能涂y段，问能不能涂完n段？
分析：
只要满足x > floor(n/2) 且 y >= floor(n/2)即可

我们的代码

E. Stupid Submissions
没有细看题，队友做的，大致是模拟codeforces判题吧。我们题意读错了好久，不过最后还是AC了
分析：
这道题我们最初读错题认为WA的是小样本就计数，没搞清k是干什么的。
正确题意应该是给出测试数n、提交数m、初始可见样本范围k（1-k为可见样本），而可见样本中只有小样本能看见全部测试数据。
若WA在可见的小样本则定义为愚蠢提交，输出愚蠢提交数。
搞明白题意就很暴力地模拟一下就好啦。
两个注意点是：

如果WA在第x个样本，无论样本是大是小都更新k=x；
AC之后全部错误提交小样本都是愚蠢的。

我们的代码

F. I’m Bored!
题意：
大致是有个人有好多卡片，每个卡片上都有一个英文的小写字母，现在他可以用这些卡片拼成若干个回文串，其中每个回文串中相同的英文字母出现次数不能超过2，求能拼成的最长的回文串的长度，以及这么长的回文串能拼出几个？

分析：

这道题先找最长串，若某个字母出现次数仅为1，不难得出最长串必为奇数，记这样的字母个数为one。
某个字母出现次数>=2，则它必定成对出现在最长串中，记这样的字母个数为K，将每个>=2的字符都/2，计算然后求最小值min。
若one不为0，则x=2*k+1，y为min与one中较小者；否则，x = 2 * k，y=min；
(我们队w了一发，因为太粗心没有初始化x,y。)

我们的代码

G. Minimax
题意：
这题是给一个矩阵，在矩阵中找一个点，横向纵向各切一刀，把矩形分割成4份，令x = 4个部分的最大值中最大的减去最小的差，求x的最小值
这道题zx写的二维前缀和
分析：

这道题很暴力地存了四个二维数组：从左上右上左下右下四个方向出发到（i,j）的方块内的最大值。
遍历分割线，分别取四个方块从各自方向出发得出的二维数组在(i-1,j-1)(i-1,j+1)(i+1,j-1)(i+1,j+1)的值，就能求差啦~

我们的代码

H. Beautiful Substrings
题意：
有a,b两个字符串，给定K，取出a中所有长度为K的子串，找出这些子串的首尾head和tail，问在b中有多少序列可以和这些首尾匹配？
分析：

先处理a串，把所有的head和tail记录下来，然后去重(我用的vector<<pair<int,int> >)
再处理b串，把每个字母出现过的位置都存到相应的vector里
然后对去重后的每个pair(head,tail), 在head的vector里面枚举head对应的字母出现的位置，然后在tail对应的字母的vector里面二分查找在这个位置后出现的tail的个数

//我觉得这波操作是真的6，越来越喜欢用vector了
int solve(int head,int tail,vector<int>& h,vector<int>&t)
{
    int ans =0;
    for(auto &x:h)
        ans += t.end() - upper_bound(t.begin(),t.end(),x);
    return ans;
}

有个要注意的地方，就是如果head==tail，那么一个字母也可以匹配上，要在答案上加上b串中这个字母的个数(队友厉害)

我们的代码

I. Secret Project
应该是个组合数学，没有碰那道题

J. Even Numbers
题意：
求杨辉三角第i行偶数的个数
这题zx很早就打表看出了每行奇数的个数是一个嵌套的等比数列，但是不好写，可能可以递归吧。后来最后我们知道了一个结论：第i行奇数的个数就是2的i的二进制位数次幂
上队友补了题的代码：
这是lj的~
这是zx的~
温馨提示队友们：题目没有让取模，答案也肯定没有爆long long, 所以求2的cnt次幂的时候不用for一遍或者预处理了，直接上位操作(1ll << cnt)搞定~

K. Cyclic Shift
题意：
两个字符串，如果原本就相同或者把其中一个字符串的一个子序列循环右移一位后两个字符串相同，则输出yes,否则输出no

我们的代码

2019/3/18