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}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)d(n​k​​)=(kc​1​​+1)(kc​2​​+1)...(kc​m​​+1)。

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

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

​​+(r−l+1)loglog(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; }