COOK50小结

很遗憾。看到第五题的通过人数就不敢做了。待日后补上。

A题

求最长的连续子序列，使得他们满足gcd为１。

如果有相邻的两个数的gcd为１，那么整个序列的gcd值也就是１，

否则就是该序列不存在。

 /*************************************************************************

     > File Name: A.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月23日 星期二 13时57分22秒

     > Propose:

  ************************************************************************/

 #include <map>

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 const int MAX_N = ;

 int N, A[MAX_N];

 #define rep(i, n) for (int i = (1); i <= (n); i++)

 int gcd(int a, int b) {

       if (!b) return a;

     return gcd(b, a % b);

 }

 int main(void) {

     ios::sync_with_stdio(false);

     int T;

     cin >> T;

     while (T--) {

         cin >> N;

         bool flag = false;

         rep (i, N) {

             cin >> A[i];

             if (i >  && gcd(A[i], A[i-]) == ) flag = true;

         }

         if (flag) cout << N << endl;

         else cout << - << endl;

     }

     return ;

 }

Ｂ题

统计一个每个位置向右和向下是否都没有障碍。

 /*************************************************************************

     > File Name: B.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月23日 星期二 14时30分39秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 char a[][];

 int N, T;

 bool col[][], row[][];

 #define rep(i, n) for (int i = (1); i <= n; i++)

 #define per(i, n) for (int i = (n); i >= 1; i--)

 int main(void) {

     ios::sync_with_stdio(false);

     cin >> T;

     while (T--) {

         cin >> N;

         rep (i, N) rep (j, N) cin >> a[i][j], row[i][j] = col[i][j] = true;

         rep (i, N) per (j, N) if ((j < N && !row[i][j+]) || (a[i][j] != '.')) row[i][j] = false;

         rep (j, N) per (i, N) if ((i < N && !col[i+][j]) || (a[i][j] != '.')) col[i][j] = false;

         int res = ;

         rep (i, N) rep (j, N) if (row[i][j] && col[i][j]) res++;

         cout << res << endl;

     }

     return ;

 }

Ｃ题

先预处理出每个数的所有的质因子。　并记录下每个质因子在序列中最后一次出现的位置即可。

 /*************************************************************************

     > File Name: C.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月23日 星期二 17时24分56秒

     > Propose:

  ************************************************************************/

 #include <set>

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 const int MAX_N = ;

 int A[MAX_N], p[MAX_N], cnt, last[MAX_N*];

 bool vis[MAX_N*];

 #define rep(i, n) for (int i = (1); i <= n; i++)

 void prime() {

     cnt = ;

     memset(vis, false, sizeof(vis));

     for (int i = ; i < ; i++) if (!vis[i]) {

         p[cnt++] = i;

         for (int j = *i; j < ; j += i) vis[j] = true;

     }

 }

 void read(int &res) {

     res = ;

     char c = ' ';

     while (c < '' || c > '') c = getchar();

     while (c >= '' && c <= '') res = res *  + c - '', c = getchar();

 }

 vector<int> factor[];

 vector<int>::iterator it;

 int main(void) {

     prime();

     rep (i, ) {

         int x = i;

         for (int j = ; p[j]*p[j] <= x; j++) {

             if (x % p[j] == ) {

                 factor[i].push_back(p[j]);

                 while (x % p[j] == ) x /= p[j];

             }

         }

         if (x > ) factor[i].push_back(x);

     }

     int T, N;

     read(T);

     while (T--) {

         read(N);

         rep (i, N) read(A[i]);

         int l = , r = , res = ;

         memset(last, , sizeof(last));

         for (it = factor[A[l]].begin(); it != factor[A[l]].end(); ++it) last[*it] = l;

         while (l <= r && r <= N) {

               int m = ;

             for (it = factor[A[r]].begin(); it != factor[A[r]].end(); ++it) {

                 if (last[*it] >= l) m = max(m, last[*it]);

                 last[*it] = r;

             }

             if ( == m) res = max(res, r - l + );

             else l = m + ;

             r++;

         }

         if (res == ) puts("-1");

         else printf("%d\n", res);

     }

     return ;

 }

Ｄ题

分奇数行和偶数行讨论，并得出递推式，即可用矩阵加速。

 /*************************************************************************

     > File Name: D.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月24日 星期三 13时20分04秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 typedef long long LL;

 const int MOD = 1e9 + ;

 #define rep(i, n) for (int i = (1); i <= (n); i++)

 struct Matrix {

      LL mat[][];

     int n, m;

     Matrix() {}

     Matrix(int n, int m):n(n), m(m) {

         memset(mat, , sizeof(mat));

     }

     Matrix operator * (const Matrix &b) const {

         Matrix c(n, b.m);

         rep (i, n) rep (k, n) rep (j, b.m) c.mat[i][j] = (c.mat[i][j] + mat[i][k] * b.mat[k][j]) % MOD;

         return c;

     }

 };

 Matrix pow_mod(Matrix a, int b) {

     Matrix res(a.n, a.m);

     rep (i, a.n) res.mat[i][i] = ;

     while (b) {

         if (b & ) res = res * a;

         a = a * a;

         b >>= ;

     }

     return res;

 }

 int main(void) {

     ios::sync_with_stdio(false);

     int T, N, M;

     cin >> T;

     while (T--) {

         cin >> N >> M;

         Matrix a(M, M), b(M, M);

         rep (i, M) {

             if (i -  >= ) a.mat[i][i-] = b.mat[i][i-] = ;

             if (i +  <= M) a.mat[i][i+] = b.mat[i][i+] = ;

             a.mat[i][i] = ;

         }

         Matrix res = pow_mod(a*b, (N% ==  ? N/- : N/));

         if (N %  == ) res = b * res;

         Matrix f1(M, );

         rep (i, M) f1.mat[i][] = ;

         res = res * f1;

         LL ans = ;

         rep (i, M) ans = (ans + res.mat[i][]) % MOD;

         cout << ans << endl;

     }

     return ;

 }

Ｅ题

巴特西

COOK50小结

最新文章

热门文章