很遗憾。看到第五题的通过人数就不敢做了。待日后补上。
A题
求最长的连续子序列，使得他们满足gcd为１。
如果有相邻的两个数的gcd为１，那么整个序列的gcd值也就是１，
否则就是该序列不存在。
1 /************************************************************************* 2 > File Name: A.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月23日 星期二 13时57分22秒 6 > Propose: 7 ************************************************************************/ 8 #include
Ｂ题
统计一个每个位置向右和向下是否都没有障碍。
1 /************************************************************************* 2 > File Name: B.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月23日 星期二 14时30分39秒 6 > Propose: 7 ************************************************************************/ 8 9 #include10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std;17 /*Let's fight!!!*/18 19 char a[1005][1005];20 int N, T;21 bool col[1005][1005], row[1005][1005];22 #define rep(i, n) for (int i = (1); i <= n; i++)23 #define per(i, n) for (int i = (n); i >= 1; i--)24 25 int main(void) {26 ios::sync_with_stdio(false);27 cin >> T;28 while (T--) {29 cin >> N;30 rep (i, N) rep (j, N) cin >> a[i][j], row[i][j] = col[i][j] = true;31 32 rep (i, N) per (j, N) if ((j < N && !row[i][j+1]) || (a[i][j] != '.')) row[i][j] = false;33 rep (j, N) per (i, N) if ((i < N && !col[i+1][j]) || (a[i][j] != '.')) col[i][j] = false;34 35 int res = 0;36 rep (i, N) rep (j, N) if (row[i][j] && col[i][j]) res++;37 cout << res << endl;38 }39 40 return 0;41 }
Ｃ题
先预处理出每个数的所有的质因子。 并记录下每个质因子在序列中最后一次出现的位置即可。
1 /************************************************************************* 2 > File Name: C.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月23日 星期二 17时24分56秒 6 > Propose: 7 ************************************************************************/ 8 #include9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std;18 /*Let's fight!!!*/19 20 const int MAX_N = 100050;21 int A[MAX_N], p[MAX_N], cnt, last[MAX_N*10];22 bool vis[MAX_N*10];23 #define rep(i, n) for (int i = (1); i <= n; i++)24 25 void prime() {26 cnt = 0;27 memset(vis, false, sizeof(vis)); 28 for (int i = 2; i < 1000005; i++) if (!vis[i]) {29 p[cnt++] = i;30 for (int j = 2*i; j < 1000005; j += i) vis[j] = true;31 }32 }33 34 void read(int &res) {35 res = 0;36 char c = ' ';37 while (c < '0' || c > '9') c = getchar();38 while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar();39 }40 41 vector factor[1000005];42 vector ::iterator it;43 int main(void) {44 prime();45 rep (i, 1000000) {46 int x = i;47 for (int j = 0; p[j]*p[j] <= x; j++) {48 if (x % p[j] == 0) {49 factor[i].push_back(p[j]);50 while (x % p[j] == 0) x /= p[j];51 }52 }53 if (x > 1) factor[i].push_back(x);54 }55 56 int T, N; 57 read(T);58 while (T--) {59 read(N);60 rep (i, N) read(A[i]);61 62 int l = 1, r = 2, res = 1;63 memset(last, 0, sizeof(last));64 for (it = factor[A[l]].begin(); it != factor[A[l]].end(); ++it) last[*it] = l;65 while (l <= r && r <= N) {66 int m = 0;67 for (it = factor[A[r]].begin(); it != factor[A[r]].end(); ++it) {68 if (last[*it] >= l) m = max(m, last[*it]);69 last[*it] = r;70 }71 if (0 == m) res = max(res, r - l + 1);72 else l = m + 1;73 r++;74 }75 76 if (res == 1) puts("-1");77 else printf("%d\n", res);78 }79 80 return 0;81 }
Ｄ题
分奇数行和偶数行讨论，并得出递推式，即可用矩阵加速。
1 /************************************************************************* 2 > File Name: D.cpp 3 > Author: Stomach_ache 4 > Mail: sudaweitong@gmail.com 5 > Created Time: 2014年09月24日 星期三 13时20分04秒 6 > Propose: 7 ************************************************************************/ 8 9 #include10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std;17 /*Let's fight!!!*/18 19 typedef long long LL;20 const int MOD = 1e9 + 7;21 #define rep(i, n) for (int i = (1); i <= (n); i++)22 23 struct Matrix {2 LL mat[32][32];25 int n, m;26 Matrix() {}27 Matrix(int n, int m):n(n), m(m) {28 memset(mat, 0, sizeof(mat));29 }30 Matrix operator * (const Matrix &b) const {31 Matrix c(n, b.m);32 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;33 return c;34 }35 };36 37 Matrix pow_mod(Matrix a, int b) {38 Matrix res(a.n, a.m);39 rep (i, a.n) res.mat[i][i] = 1;40 while (b) {41 if (b & 1) res = res * a;42 a = a * a;43 b >>= 1;44 }45 return res;46 }47 48 int main(void) {49 ios::sync_with_stdio(false);50 int T, N, M;51 cin >> T;52 while (T--) {53 cin >> N >> M;54 Matrix a(M, M), b(M, M);55 rep (i, M) {56 if (i - 1 >= 1) a.mat[i][i-1] = b.mat[i][i-1] = 1; 57 if (i + 1 <= M) a.mat[i][i+1] = b.mat[i][i+1] = 1;58 a.mat[i][i] = 1;59 }60 Matrix res = pow_mod(a*b, (N%2 == 0 ? N/2-1 : N/2));61 if (N % 2 == 0) res = b * res;62 Matrix f1(M, 1);63 rep (i, M) f1.mat[i][1] = 1;64 res = res * f1;65 66 LL ans = 0;67 rep (i, M) ans = (ans + res.mat[i][1]) % MOD;68 cout << ans << endl;69 }70 71 return 0;72 }
Ｅ题