宜春学院水题赛题解

比赛入口

有一点尴尬，第一题出锅，比赛时改不了也通知不了，输出样例有问题，不能直接复制输出样例上的。

夯夯的祝福

做法：照顾新手的水题系列1，直接输出“Hello，World！”即可。

代码：

#include<stdio.h> int main() { printf("Hello, World!\n"); return 0; }

AC自动机fail指针上建可持久化线段树

做法：照顾新手的水题系列2，判断一个数是否是奇数。要看清哦，这个题目有两个坑点哦。

所有的字母‘O’都改成了数字’0’哦数据范围很大哦，必须要用字符串形式哦 判断一个数n是不是奇数：n%2==1 或者 n & 1 （二进制与运算，不知道的可以百度看看，很简单）

代码：

#include<stdio.h> #include<string.h> int main() { char s[103]; scanf("%s", s); int len = strlen(s); if((s[len-1]-'0') & 1) printf("B0B0 ZHEN SHUAI!\n"); else printf("N0\n"); return 0; }

后缀自动机的next指针DAG图上求SG函数

做法：照顾新手的水题系列3，求出a数组中的最大值和次大值。用一个res1标记一下最大值，循环的每一次以res1为限制更新res2。

代码：

#include<stdio.h> const int INF = 1e9+7; int main() { int res1 = -INF, res2 = -INF; int n, a; scanf("%d", &n); for(int i = 0; i < n; ++i) { scanf("%d", &a); if(res1 < a) { res2 = res1; res1 = a; } else if(res1 != a && res2 < a) res2 = a; } if(res1 != -INF && res2 != -INF) printf("%d %d\n", res1, res2); else printf("No answer\n"); return 0; }

夯夯和朱朱的异世界之旅

做法：照顾新手的水题系列4，一个数用二的次方和形式表示，求最少需要多少个二次方数以及最多需要多少个二次方数。最多的需求就是n本身，最少的需求就有多种解法了，详情请点击这里

代码：

#include<stdio.h> int main() { long long n, nn; while(~(scanf("%lld", &n))) { nn = n; int res = 0; while(nn) { if(nn % 2 == 1) res++; nn /= 2; } printf("%d %lld\n", res, n); } return 0; }

朱朱的数论

做法：照顾新手的水题系列5，找一段序列循环节的最后一个数字，证明过程很繁杂，但是规律很好推出来，有公式 (p-a)%p，要注意a可能比p更大，要把答案变成正数，所以再加个p，再模一次p。

证明：

若a与p不互质，那么显然，循环节一定是以开头的，那么前一个即是上一个循环的最后一个，也就是我们要求的答案，即（0-a) % p, 考虑到模数一定是正数，那么再加p 模 p即可。若a与p互质，那么显然，他的循环节的开头也一定是0， 假设 a*x%p==0， 那么x的最小值就是p（a，p互质），所以答案还是((0-a)%p+p)%p。即答案为 (-a %p + p) % p。

代码：

#include<stdio.h> int main() { int a, p; while(~scanf("%d%d", &a, &p)) { printf("%d\n", ((-a % p) + p) % p); } return 0; }

夯夯的棍棍

做法：dfs经典题目，若干长度不一样的木棒，将其拼成若干长度相等的木棒，求长度最小是多少。恩…可选棍子的长度应该在最长木棒与所有木棒长度之和之间，并且一定是总长的因数。然后再依次进行搜索即可。

代码：

#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r using namespace std; typedef long long ll; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int N = 70; int n, sum, len, num, a[N], vis[N]; // n - n根棍子，sum - n根棍子的总长，len - 每根棍子的长度 //num - 一共有多少根len长度的棍子，a数组记录切割后棍子的长度，vis用于搜索 bool cmp(int x, int y) { return x > y; } int dfs(int mid_num, int mid_len, int pos) { if(mid_num == num) return 1; //如果棍子数量对上了 if(mid_len == len) return dfs(mid_num+1, 0, 1); //如果长度够了，再拼接下一根棍子 for(int i = pos; i <= n; ++i) { if(!vis[i] && mid_len + a[i] <= len) { vis[i] = 1; if(dfs(mid_num, mid_len + a[i], i + 1)) return 1; vis[i] = 0; if(mid_len == 0) return 0; while(i + 1 <= n && a[i+1] == a[i]) i++; } } return 0; } int main() { read(n); sum = 0; for(int i = 1; i <= n; ++i) { read(a[i]); sum += a[i]; } sort(a+1, a+n+1, cmp); //从大至小排序，方便搜索 int res = -1; for(int i = a[1]; i <= sum; ++i) { if(sum % i == 0) { memset(vis, 0, sizeof vis); len = i; num = sum / len; if(dfs(0, 0, 1)) { res = len; break; } } } printf("%d\n", res); return 0; }

朱朱的图论

做法：给出起点和终点，问是否能找一条偶数路径。要知道，如果两点间能够到达，那么以这两个点组成的矩形中的数字必定是偶数。所以我们只需要判断这个矩形中的数字即可。其中还有一个很方便的操作，就是把这个数字模2。再根据 奇数+奇数 = 偶数 和 偶数+偶数 = 偶数，若这个矩形是全偶数矩形那么他在对应范围r，c范围内的和要么是0，要么全是1，前缀和处理一下即可。

代码：

#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r using namespace std; typedef long long ll; typedef pair<ll, int> pli; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int N = 1e5+5; int sumr[N], sumc[N]; int main() { int n, q; read(n); read(q); int r, c; for(int i = 1; i <= n; ++i) { read(r); r %= 2; sumr[i] = sumr[i-1] + r; } for(int i = 1; i <= n; ++i) { read(c); c %= 2; sumc[i] = sumc[i-1] + c; } int sx, sy, ex, ey, fx, fy; while(q--) { read(sx); read(sy); read(ex); read(ey); if(sx > ex) swap(sx, ex); if(sy > ey) swap(sy, ey); fx = sumr[ex] - sumr[sx-1]; fy = sumc[ey] - sumc[sy-1]; if((fx == 0 && fy == 0) || (fx == ex - sx + 1 && fy == ey - sy + 1)) puts("YES"); else puts("NO"); } }

夯夯的水题

做法：直接矩阵快速幂即可，题目具有迷惑性，想让你推出一个公式。

代码：

#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r using namespace std; typedef long long ll; typedef pair<ll, int> pli; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int Mod = 1000000007; struct xx { ll m[3][3]; xx() { for(int i = 0; i < 3; ++i) memset(m[i], 0, sizeof m[i]); } }; xx mul(xx a, xx b) { xx c; for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) { c.m[i][j] = 0; for(int k = 0; k < 2; ++k) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % Mod; } return c; } ll Pow(xx a, ll n) { xx res; res.m[0][0] = 1; res.m[1][1] = 1; while(n) { if(n & 1) res = mul(res, a); a = mul(a, a); n >>= 1; } return res.m[0][0]; } int main() { ll n; read(n); xx a; a.m[0][0] = 1; a.m[0][1] = 1; a.m[1][0] = 1; ll f1 = Pow(a, n+2), f2 = Pow(a, n-2); printf("%lld\n", (f1 * f1 % Mod - f2 * f2 % Mod + Mod) % Mod); return 0; }