2018 CCPC 女生赛题解
题目要求：
包含 T 组测试用例，
每个测试用例提供一个长度为n的序列a[i]并伴随m次查询。
每次查询会指定l、r和d三个数值，
并询问该序列在区间[l, r]内的乘积是否能被d整除。
数据范围如下：
T的取值范围是从1到10之间。
n和m的最大值均不超过一百万。
ai的取值范围是从一到十万。
l和r满足条件：一≤l≤r≤n。
d的取值范围是从一到十万。
输入样例：
1
5 4
6 4 7 2 5
1 2 24
1 3 18
2 5 17
3 5 35输出样例：
Yes
No
No
Yes思路：采用质因数分解的方式（单纯依赖gcd反复判断每次的结果会导致超时）。具体而言：
将vector[j]（j为质因子）用于存储a[i]可被分解出的质因子及其对应的下标i：通过vector[j].push_back(i);来记录。
例如，在处理a[i]=12时，在j=2的情况下将两次推入v[2].push_back(1)，此时经过两次除以2后得到a[i]=3；接着在j=3的情况下再推入v[3].push_back(1)，此时经过除以3后得到a[i]=1。（此时有a[i]=2×2×3）
这样就能完成整个序列的质因数分解并存储到对应的vector中。
ac代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
vector<int> v[maxn];
bool d_judge(int l, int r, int d)
{
int cnt, tmp;
for(int i = 2; i * i <= d; i++)
{
cnt = 0;
while(d % i == 0)
{
cnt++;
d /= i;
}
if(cnt > 0)
{
tmp = upper_bound(v[i].begin(), v[i].end(), r) - lower_bound(v[i].begin(), v[i].end(), l);
if(tmp < cnt) return false;
}
}
if(d > 1){//
tmp = upper_bound(v[d].begin(), v[d].end(), r) - lower_bound(v[d].begin(), v[d].end(), l);
if(tmp < 1) return false;
}
return true;
}
int main()
{
int t, n, m, x, l, r, d;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < maxn; i++)
v[i].clear();//注意这一步
for(int i = 1; i <= n; i++)
{
cin>>x;
for(int j = 2; j * j <= x; j++)
{
while(x % j == 0)
{
v[j].push_back(i);
x /= j;
}
}
if(x > 1) v[x].push_back(i); //注意 x可能本身为一个质因子
}
for(int i = 1; i <= m; i++)
{
cin>>l>>r>>d;
if(d_judge(l, r, d))
printf("Yes\n");
else printf("No\n");
}
}
return 0;
}题目大意：
有T组样例，每次会输入一组评测记录，然后要求将它改为符合要求的格式输出，从左至右依次是排名rank(3像素),队名S(16像素),题号prob(4像素),评测情况(12像素)，相邻两个部分之间由1像素的分隔线“ | ”分开。其中，排名右对齐显示，队名左对齐显示，长度不足时用空格补齐。题号一定是4位正整数，因此恰好占据4像素。评测情况则比较复杂，它由两侧的括号 [ ] 以及中间10像素组成。
数据范围：1 <=T <= 1000 1 <= rank <= 400
1<= S <= 16 1001 <= prob <= 1013 1 <= p <= 9
输入样例：
5
19 qqqqq_University 1001 Running 3
125 quailty_U_2 1002 WA
4 quailty_U_3 1003 TLE
1 quailty_U_4 1003 FB
2 qqqqq 1001 AC输出样例：
19|qqqqq_University|1001|[XXX ]
125|quailty_U_2 |1002|[ WA ]
4|quailty_U_3 |1003|[ TLE ]
1|quailty_U_4 |1003|[ AC* ]
2|qqqqq |1001|[ AC ]这道题需要注意的点：
① 如果该条评测记录的状态是"Running"，需要再输入一个正整数p表示它通过了多少个测试点，输出的评测情况标为p个"X"，例如样例1：p = 3，输出为：19|qqqqq_University|1001|[XXX ]
② 注意"Running"的判断条件，因为评测情况里还包含一个"RTE"，不能只判断第一个字符"R"。
思路采用模拟的方式；较为便捷的方式是利用C++语言的输出控制语句；同时还可以通过手动的方式进行模拟；只要遵循相应的格式规范即可。
ac代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <string>//学习<strng.h>与<string>两个头文件的区别
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
//学习使用C++输出的格式控制
int main()
{
int T, rank, prob, p;
string sname, status;
cin>>T;
while(T--)
{
cin>>rank>>sname>>prob>>status;
if(status[0] == 'R' && status[1] == 'u')
{
status = "";
cin>>p;
for(int i = 1; i <= p; i++)
status += 'X';
}
else if(status[0] == 'F')
status = "AC*";
cout<<right<<setw(3)<<rank<<"|";
cout<<left<<setw(16)<<sname<<"|";
cout<<prob<<"|[";
if(status[0] == 'X')
cout<<left<<setw(10)<<status<<"]"<<endl;
else cout<<" "<<left<<setw(6)<<status<<"]"<<endl;
}
return 0;
}