IOI周赛-普及组24题解
题目并不难，没有人AK我觉得主要是因为 T3 的题意不清晰，非常抱歉。
先说声对不起！因为出题人的语言描述能力不强，导致T3的题意出现大锅，深感抱歉！相比之下T4的数据范围问题倒是小锅了(小声bb。
A:二进制？十进制！
按照题意模拟即可,签到题。
前 是给没有开
童鞋的。
满分和 分只差一个
满分代码：
运行时间:2ms，内存占用：424kb (牛客网评测机评测结果，下面的不再赘述)
#include <iostream>
int main() {
long long A,B,c = 0,d = 0,flag = 1;
std::cin >> A >> B;
while(A) c += flag * (A % 2) , A >>= 1ll , flag *= 10;flag =1;
while(B) d += flag * (B % 2) , B >>= 1ll , flag *= 10;
std::cout << c + d;
return 0;
} B:数字串
小清新简单字符串比对题。
介绍各部分分写法：
前三个数据点随便乱搞就能过？
第 4 以及 第 5 个测试点 ，因为 ,
，按照快读的方法字符串转化为正整数，就可以直接过掉(其实出题人也不知道这个部分分该怎么做......但是还是给了)。
满分做法
满足条件的子段长度一定是要大于等于 的长度小于等于
的长度（没有前导零的情况下）
只需要在字符串长度等于 或者等于
的条件下判断一下即可，中间的肯定是可以的（没有前导零的情况下）。
本题的一个小 主要在于对于前导零的处理，实际上只需要忽略所有前导零，然后统计前导零就行了，然后每次前导零后面第一个满足条件的子段对答案的贡献加上前导零个数即可。
用到上面的 就可以不用考虑前导零做出本题，就比较简单的做出了这题。
总的复杂度为: O()
满分代码如下：
运行时间:22ms，内存占用：1MB
#include <iostream>
std::string s;
std::string L,R;
int len, lenl, lenr, Ans = 0, cnt = 0;
bool check(int l,int r) {
if(r >= len) return 0;
if(r - l + 1 == lenl)
for(int i = l ; i <= r ; i ++) {
if(s[i] > L[i - l]) break;
if(s[i] < L[i - l]) return 0;
}
if(r - l + 1 == lenr) //长度跟 r 相同的时候才需要比对
for(int i = l ; i <= r ; i ++) {
if(s[i] < R[i - l]) break;
if(s[i] > R[i - l]) return 0;
}
return 1;
}
int main() {
std::cin >> L >> R;
std::cin >> s;
len = s.length() , lenl = L.length() , lenr = R.length(); //分别获取三个串的长度
for(int i = 0 ; i < len ; i ++) {
if(s[i] == '0') {cnt ++; continue;} //统计前导零，遇到前导零就不算答案
for(int j = lenl ; j <= lenr ; j ++)
Ans += check(i, i + j - 1) * (cnt + 1); // 统计累加起来的答案。
cnt = 0;
}
std::cout << Ans;
return 0;
} C:银杏林
直接被踩（
清新”小“模拟。（其实出题人都被恶心哭了）。
这道题是来平衡码量的，也考察了分类讨论的思想。
直接上正解吧。
分类讨论:
:
&&
这时候我们发现阳光其实就是一条从下往上的垂直于 轴的一条射线，按照题意枚举每一列，然后从下到上判断每一行即可。
:
这时候我们发现阳光其实就是一条从上往下的垂直于 轴的一条射线，按照题意枚举每一列，然后从上到下判断每一行即可。
:
&&
这时候的阳光是一条从左到右的垂直于 轴的射线，枚举每一行，然后从左到右判断每一列即可。
:
&&
这时候的阳光是一条从右到左的垂直于 轴的射线，枚举每一行，然后从右到左判断每一列即可。
:
并且
这种情况下，可以把阳光抽象一次函数: (
=
)
同时按照题意，因为这个一次函数和 ,
的正半轴交点为整点，可以枚举这个一次函数和
轴以及
轴的交点，然后判断这条直线与矩阵中哪些 "
" 点相交就是答案，同时遇到树遮挡住了阳光就
掉。
:
其实转化为一次函数解析式中的 上文的第一种情况是一样的。
只是射线方向不一样？
没错，就可以仍然按照 情况处理，只需要让
,
等于其相反数，只不过在遇到树的时候不用
，只要把当前统计到的答案清空。最后剩下来的答案就是没有被树遮住的了。统计答案即可。注意一定要每次枚举之前清空答案。
总的复杂度为: O()
满分代码:
运行时间:22ms，内存占用：1MB
#include <iostream>
int n,m,Q;
char mp[1005][1005];
int gcd(int a,int b) {
if(a % b == 0) return b;
return gcd(b , a % b);
}
int main() {
std::cin >> n >> m;
for(int i = 1 ; i <= n ; i ++) std::cin >> (mp[i] + 1);
std::cin >> Q;
for(int V = 1 ; V <= Q ; V ++) {
int x , y;
std::cin >> x >> y;
if(x != 0 && y != 0) {
int G = gcd(abs(x),abs(y));
x /= G , y /= G;//这里要预处理一下。
}
int Ans = 0;
if(x == 0) {
if(y > 0) {
for(int j = 1 ; j <= m ; j ++) { //对应 Case1，枚举每一列
for(int i = n ; i >= 1 ; i --) { // 从下到上判断每一行
if(mp[i][j] == 'T') break; //遇到了树就 break
if(mp[i][j] == 'R') Ans ++;
}
}
}
else {
for(int j = 1 ; j <= m ; j ++) { // Case2
for(int i = 1 ; i <= n ; i ++) {//从上到下判断每一行
if(mp[i][j] == 'T') break;
if(mp[i][j] == 'R') Ans ++;
}
}
}
std::cout << Ans << std::endl;
continue;
}
if(y == 0) {
if(x > 0) {
for(int i = 1 ; i <= n ; i ++) { // Case3
for(int j = 1 ; j <= m ; j ++) {//从左到右判断
if(mp[i][j] == 'T') break;
if(mp[i][j] == 'R') Ans ++;
}
}
}
else {
for(int i = 1 ; i <= n ; i ++) { // Case4
for(int j = m ; j >= 1 ; j --) {//从右到左判断
if(mp[i][j] == 'T') break;
if(mp[i][j] == 'R') Ans ++;
}
}
}
std::cout << Ans << std::endl;
continue;
}
if(x > 0 && y > 0) {
for(int s = 0 ; s <= m ; s ++) { //枚举交点的横坐标，注意这里的横坐标是坐标轴的横坐标，对应的是矩阵的列的编号
int x0 = n + 1 , y0 = s;//x0,y0即交点，这里的x0表示矩阵的第 x0 行，y0 表示矩阵的第 y0 列
while(x0 > 0 && y0 < m) {
y0 += x;
x0 -= y;
if(y0 > m || x0 <= 0) break;
if(mp[x0][y0] == 'T') break;
if(mp[x0][y0] == 'R') Ans ++;
}
}
for(int s = n ; s > 0 ; s --) { //枚举交点的纵坐标，注意这里的纵坐标是坐标轴的纵坐标，对应的是矩阵的行的编号
int x0 = s , y0 = 0; //x0,y0即交点，这里的x0表示矩阵的第 x0 行，y0 表示矩阵的第 y0 列
while(x0 > 0 && y0 < m) {
y0 += x;//因为 x,y已经取了 gcd ，可以这么写，保证这么写是正确的
x0 -= y;//因为 x,y已经取了 gcd ，可以这么写, 保证这么写是正确的
if(y0 > m || x0 <= 0) break;
if(mp[x0][y0] == 'T') break;//树遮挡住了阳光，就break
if(mp[x0][y0] == 'R') Ans ++;//否则统计答案
}
}
std::cout << Ans << std::endl;
}
if(x < 0 && y < 0) { //代码其实跟上面的是一样的，只不过统计答案的地方有点不同
x = -x , y = -y;//取反
int Ans0 = 0;
for(int s = 0 ; s <= m ; s ++) {
int x0 = n + 1 , y0 = s;
Ans0 = 0;
while(x0 > 0 && y0 < m) {
y0 += x;
x0 -= y;
if(y0 > m || x0 <= 0) break;
if(mp[x0][y0] == 'T') Ans0 = 0;//这里跟上面的代码不一样，不采用 break,采用的是清零答案
if(mp[x0][y0] == 'R') Ans0 ++;//统计答案。
}
Ans += Ans0;
}
int Ans1 = 0;
for(int s = n ; s > 0 ; s --) {
int x0 = s , y0 = 0;
Ans1 = 0;
while(x0 > 0 && y0 < m) {
y0 += x;
x0 -= y;
if(y0 > m || x0 <= 0) break;
if(mp[x0][y0] == 'T') Ans1 = 0;
if(mp[x0][y0] == 'R') Ans1 ++;
}
Ans += Ans1;
}
std::cout << Ans << std::endl;
}
}
return 0;
} D: 桃花村
被疯狂踩（
考点：质因数分解，调和级数。
首先介绍一下各个部分分的设置以及用意。
前
，是给乱搞的，
，根据题意模拟即可得到。
前
, 是给时间复杂度为 O(
) 的算法的，这个比较简单，不再赘述。
前
, 是给想到了正解为分解因数，想到了使用
来进行判断，使用了 O(
*
) 的算法的选手的。
前
, 是给想到了正解为分解因数并且想到了对于起火时间距离第一间房屋为
的房屋最多有两个对应的
，采用逆向思维，去掉
的那一个
，使用复杂度为 O(
) 的算法可以得到
(注意常数优化)。
或者还有一种情况获得 pts , 也就是想到了使用 Θ(
) 调和级数预处理出每个数的因数。
时间复杂度为O( 的因数个数 *
) ，
以内因数最多的数共有
个因数，为
。常数小的话可以拿到
(以上都是理论复杂度，实际情况看评测姬的运行情况)
满分做法:
首先要对于原题的题意进行抽象，建模。
发现实际上题目给出了若干条一次函数，它们的解析式为: 然后让我们求某一
使得
的数量。
(其中 是
号村舍距离第一间着火村舍的距离)
不难看出本题实际上最难维护的是 的信息，对于
的信息就直接输出当前答案即可。
然后发现了这个解析式的每一项都是含有 的。同时给定的数据范围中
，不难想到分解因数，然后进行判断是否存在燃烧增剧度程度
的因子 的村舍，对于这些村舍进行判断即可，同时这些村舍满足
，所以我们对于每一个
的询问都要找出所有满足上面式子的村舍有哪些。
那么你就得知道那间村舍的 以及
，于是想到使用
存储，对于每一次的询问的
我们枚举其因子，假设枚举到的因子是
,判断存在村舍的
并且
的村舍数量 这样子就可以实现 O(
*
) 的查询了(分解因数的复杂度是 O(
))的，其实还可以用 unorder_map 来获得更高的分数，但是这个题目里面好像不好用 unordered_map 来存，并且 unorder_map 是可以被 126271,107897 这两个数的倍数卡的，出题人很懒，并不想卡，就或许您可以通过 unordered_map 来获得更高分。
想到这一步你就获得了 的成绩。
考虑怎么优化，不难想到实际上复杂度瓶颈在于分解因数以及每次的查询。
采用预处理的方法优化，预处理出 以内的所有数的因数。
采用反向枚举的方法，枚举每一个数以及其倍数，这样子枚举下来的时间复杂度是 Θ 的，
以内所有数的因数个数和是
级别的，大概有
个，
的内存是完全够的。
通过预处理就完成了分解因数的优化。
然后，优化查询的复杂度。
考虑到 ，也就是其着火的时间是确定的，而且最多会有两间房子是同一时间着火的（一左一右距离第一间着火的房子
的距离相等）。
于是没必要开 ，直接以
为下标存储的对应村舍的
，这个的空间复杂度是 O
的。
于是这道题的时间复杂度经过优化就达到了 O 的因数个数
，这个优秀的复杂度就能过掉这一题了！
（另外注意特判 ）的情况!
满分代码:
运行时间:816ms，内存占用：118MB
#include <iostream>
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++)
inline int read() {
int x = 0, flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
const int MAXN = 1e6 + 50;
int A[MAXN << 2],n,Q = 0,X,Ans = 0;
int start[MAXN << 2],tot = 0;
struct Edge {
int next,to;
} edge[MAXN * 25];//采用前向星的方式存储。减小常数
int mp[MAXN][3];//记录对应起火时间存在的Ai
void add(int u,int v) {
if(u > 1e6 || v > 1e6) return ;
edge[++tot].next = start[u];
edge[tot].to = v;
start[u] = tot;
return ;
}
void prepare() {
for(int i = 1 ; i <= 1e6 ; i ++)
for(int j = i ; j <= 1e6 ; j += i)
add(j,i);//预处理因子
for(int i = 1 ; i <= n ; i ++) {
A[i] = read();
if(mp[abs(i - X)][0] == 0)
mp[abs(i - X)][0] = A[i]; //如果第一个空位还没有元素就放第一个空位
else mp[abs(i - X)][1] = A[i]; //否则放第二个空位
} Ans = 0;
return ;
}
signed main() {
n = read(), Q = read(), X = read();
prepare();
for(int i = 1 ; i <= Q ; i ++) {
int op = read(), D = read();
if(op == 1) {
int t = read(), tt = t, now = 1;
if(t == 0) {//一定要注意特判！
if(D == 0) {Ans ++; continue;}
if(X + D <= n) Ans ++;
if(X - D >= 1) Ans ++;
continue;
}
for(int j = start[t] ; j ; j = edge[j].next) {
int to = edge[j].to;
int x = D - tt / to;
if(x < 0) continue;
if(mp[x][1] == to) Ans ++;//判断是否存在 Ai = ti 因数
if(mp[x][0] == to) Ans ++;//判断是否存在另外一个 Ai = ti 因数
}
}
else printf("%d\n",Ans);//对于操作二直接输出即可。
}
return 0;
} 这次比赛出了很大的锅，T3的题意真的不清楚，出题人在此给大家谢罪了.....
巨人网络公司福利 65人发布