对于小宝来说，如果一个数组的总和能够整除他的幸运数字k，就是他的幸运数组，而其他数组小宝都很讨厌。现在有一个长度为n的数组，小宝想知道这个数组的子数组中，最长的幸运子数组有多长。
对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组b获得数组a，则称数组a是数组b的子数组。（子数组包含原数组，但不包含空串）
题意：对一个数组求数组和能整除k的子数组的个数，子数组是指原数组中任意连续的数组，长度大于0即可。
思路：暴力解法是两重for循环对前缀和求差，找最长的。但会TLE。所以进行一下改进：观察题意要的是能整除k的子数组，所以可以让前缀和对k取模，这样如果模相等，则求差的时候得到的中间的数组和就可以整除k，只需要找到最大的长度即可。方法是利用两个数字分别存每个取模以后的最大和最小的位置，最后进行一次循环输出最大减最小的差即可。
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f typedef long long ll; ll tr[100005], ma[100005], mi[100005], have[100005]; ll x, t, n, k, a; int main() { cin>>t; while(t--) { a = 0;//a用来判断最终结果是否输出-1 memset(tr, 0, sizeof(tr));//初始化 memset(ma, 0, sizeof(ma));//ma数组用来存每一个余数出现的最大位置，因为是求max，则需让数组初始化为-1e9，但本题的值都大于等于0，所以没必要赋-1e9 memset(have, 0, sizeof(have));//have数组用来存每一个余数出现的次数，只有出现次数大于1，其相减才能得到能整除k的子数组 for(int i = 0; i < 100005; i++) mi[i] = inf;//mi数组用来存每一个余数出现的最小位置，因为是求min，所以赋初始值为最大的数 mi[0] = 0; /*这个和下面的那个初始化很重要，因为可能是前缀和本身就能整除k，此时余数就是0，而这个时候不需要两个的差，所以要给have[0] = 1，这样0这个位置就有资格去求了，而且mi[0] = 0,不会出现比0还小的位置，减的时候就正确*/ have[0] = 1; cin>>n>>k; for(int i = 1; i <= n; i++){ cin>>x; tr[i] = tr[i - 1] + x;//求前缀和 } for(ll i = 1; i <= n; i++){ tr[i] = tr[i] % k;//对前缀和取模 mi[tr[i]] = min(mi[tr[i]], i);//存余数出现的最小位置 ma[tr[i]] = max(ma[tr[i]], i);//存余数出现的最大位置 have[tr[i]]++; if(have[tr[i]] >= 2) a = 1; } if(a == 0) cout<<-1<<endl; else{ ll ans = 0; for(ll i = 0; i < 100005; i++){ if(have[i] >= 2) ans = max(ans, ma[i] - mi[i]); } cout<<ans<<endl; } } return 0; } C-上进的凡凡 题目描述凡凡是一个上进的人，他的人生没有下坡路，他也讨厌带有”下坡路“的东西。
所以，对于凡凡来说，只有非降序的数组才是nice的（如：1，2，2，3，4，5，5）；若数组元素个数为1，也满足非降序，也是nice的。
现在有一个长度为n的数组，凡凡想知道它的子数组中有多少个数组是nice的。
题意：让你求非降序的子数组的个数，相等也算非降序。
思路：先举个栗子：1,2,3,4,3,1,2从1开始看，子数组有[1]；再看2，它和1构成非降序，所以子数组又多了[1，2]和[2]；再看3，它和1,2构成非降序，所以子数组又多了[1,2,3]和[2,3]和[3]；再看4，它和1,2,3构成非降序，所以字数组又多了[1,2,3,4]和[2,3,4]和[3,4]和[4];再看第二个3,他和前面的不构成非降序，所以子数组又多了个[3];再看第2个1，他和前面的也不构成非降序，所以子数组又多了[1]；再看第2个2，他和前面的构成降序，所以子数组又多了[1,2]和[2]；所以子数组的数量是1 + 2 + 3 + 4 + 1 + 1 + 2。规律就是每多一个非降序的数，则加的值是上次加的值加一，而每多一个降序的数，就加1。还有一种做法是将数组分成若干个非降序的子数组，然后利用（n + 1） * n / 2的公式带入所有的子数组的长度然后相加，如果是降序的就1个1个的分开。这个公式其实也就是我上面的那个规律的等差求和公式而已，不过我个人感觉比较麻烦，你每次都得找两个端点才能套公式，而我的那个只需要一次模拟，时时更新值即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n, tr[100005]; int main() { cin>>n; for(int i = 1; i <= n; i++) cin>>tr[i]; tr[0] = 1e9; ll sum = 0, k = 1; for(int i = 1; i <= n; i++) { if(tr[i] >= tr[i - 1]) { k++; } else k = 1; sum += k; } cout<<sum<<endl; return 0； } Seek the Joker I 题目描述长达数日的春日祭终于告一段落，作为巫女的朝野芳乃在打扫完神社本决定好好享受一下久违的宁静。然而守护了神刀数百年的丛雨难耐寂寞，希望芳乃能陪她一起玩扑克消解愁闷。