2017 Multi-University Training Contest - Team 4

第四场前刚补完以前的博客和题目，觉得状态一般吧，有点浮躁，尤其碰到难题和简单题自己做了很久的时候，心态很容易炸，很着急更加忙中出错。好在最后做出03还是把排名拉回了前300。水题的出题速度和1A成功率都有待加强。

1003. Counting Divisors

设 $n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$ ，则 $d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)$ 。

枚举不超过 $\sqrt{r}$ 的所有质数 $p$ ，再枚举区间 $[l, r]$ 中所有 $p$ 的倍数，将其分解质因数，最后剩下的部分就是超过 $\sqrt{r}$ 的质数，只可能是 $0$ 个或 $1$ 个。

时间复杂度 $O(\sqrt{r}+(r-l+1)\log\log(r-l+1))$

$ + (r - l + 1) lo g lo g (r - l + 1))$ 。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6 + 7;
ll top, n, i, j;
int p[N + 10];
int f[N + 10];

inline void init() {
top = 0;
memset(f, 0, sizeof(f));
for (i = 2; i <= N; ++i) {
if (!f[i]) {
p[++top] = i;
}
for (j = 1; j <= top && i * p[j] <= N; ++j) {
f[i * p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
return;
}

ll now[1000010];
ll tm[1000010];
int ft, T;
ll l, r, k;

int main() {
init();
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld", &l, &r, &k);
ll ans = 0;
for (i = l; i <= r; ++i) {
now[i-l] = i;
tm[i-l] = 1;
}
for (i = 1; i <= top; ++i) {
j = (l + p[i] - 1) / p[i] * p[i];
while (j <= r) {
ll tmp = 0;
while (now[j-l] % p[i] == 0) {
++tmp;
now[j-l] /= p[i];
}
tm[j-l] *= (tmp * k + 1);
if (tm[j-l] >= mod)
tm[j-l] %= mod;
j += p[i];
}
}
for (i = l; i <= r; ++i) {
if (now[i-l] != 1)
tm[i-l] = tm[i-l] * (k + 1) % mod;
ans += tm[i-l];
if (ans >= mod)
ans %= mod;
}
ans = (ans + mod) % mod;
printf("%lld\n", ans);
}
return 0;
}

1009. Questionnaire

奇数多，输出2,1。同理，偶数多，输出2,0。

#include<cstdio>

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
long long n,x;
long long a=0,b=0;
scanf("%lld",&n);
for (long long i=1;i<=n;i++)
{
scanf("%lld",&x);
if (x%2==0) a++;
else b++;
}
if (a>=b) printf("%d %d\n",2,0);
else printf("%d %d\n",2,1);
}
return 0;
}

1011. Time To Get Up

按题意模拟即可。

#include<cstdio>
#include<string>
#include<map>
using namespace std;
int Case,i,j;char a[7][21];
string num[10][7],t,A,B,C,D;
map<string,int>T;
int main(){
num[0][0]=".XX.";
num[0][1]="X..X";
num[0][2]="X..X";
num[0][3]="....";
num[0][4]="X..X";
num[0][5]="X..X";
num[0][6]=".XX.";

num[1][0]="....";
num[1][1]="...X";
num[1][2]="...X";
num[1][3]="....";
num[1][4]="...X";
num[1][5]="...X";
num[1][6]="....";

num[2][0]=".XX.";
num[2][1]="...X";
num[2][2]="...X";
num[2][3]=".XX.";
num[2][4]="X...";
num[2][5]="X...";
num[2][6]=".XX.";

num[3][0]=".XX.";
num[3][1]="...X";
num[3][2]="...X";
num[3][3]=".XX.";
num[3][4]="...X";
num[3][5]="...X";
num[3][6]=".XX.";

num[4][0]="....";
num[4][1]="X..X";
num[4][2]="X..X";
num[4][3]=".XX.";
num[4][4]="...X";
num[4][5]="...X";
num[4][6]="....";

num[5][0]=".XX.";
num[5][1]="X...";
num[5][2]="X...";
num[5][3]=".XX.";
num[5][4]="...X";
num[5][5]="...X";
num[5][6]=".XX.";

num[6][0]=".XX.";
num[6][1]="X...";
num[6][2]="X...";
num[6][3]=".XX.";
num[6][4]="X..X";
num[6][5]="X..X";
num[6][6]=".XX.";

num[7][0]=".XX.";
num[7][1]="...X";
num[7][2]="...X";
num[7][3]="....";
num[7][4]="...X";
num[7][5]="...X";
num[7][6]="....";

num[8][0]=".XX.";
num[8][1]="X..X";
num[8][2]="X..X";
num[8][3]=".XX.";
num[8][4]="X..X";
num[8][5]="X..X";
num[8][6]=".XX.";

num[9][0]=".XX.";
num[9][1]="X..X";
num[9][2]="X..X";
num[9][3]=".XX.";
num[9][4]="...X";
num[9][5]="...X";
num[9][6]=".XX.";
for(i=0;i<=9;i++){
t="";
for(j=0;j<7;j++)t+=num[i][j];
T[t]=i;
}
scanf("%d",&Case);
while(Case--){
for(i=0;i<7;i++)scanf("%s",a[i]);
A=B=C=D="";
for(i=0;i<7;i++)for(j=0;j<4;j++){
A.push_back(a[i][j]);
B.push_back(a[i][j+5]);
C.push_back(a[i][j+12]);
D.push_back(a[i][j+17]);
}
printf("%d%d:%d%d\n",T[A],T[B],T[C],T[D]);
}
return 0;
}

秒客网

2017 Multi-University Training Contest - Team 4

1003. Counting Divisors

1009. Questionnaire

1011. Time To Get Up

相关文章