9.9算法

区间数的和能被7整除（前缀和）

给你n个数，分别是a[1],a[2],...,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

输入格式

The first line of input contains?�N?(1≤�≤50,0001≤N≤50,000). The next?�N

lines each contain the?�N?integer IDs of the cows (all are in the range

0…1,000,0000…1,000,000).

输出格式

Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7. If no such group exists, output 0.

//int dp[50005],a[50005];
//int sum=0, ans=0,n;
//void fdp(int i) {
//    if ((sum + a[i]) % 7 == 0) {
//        sum += a[i];
//        dp[i] = dp[i - 1] + 1;
//        ans = max(ans, dp[i]);
//    }
//    else {
//        sum = 0;
//    }
//}
//cin >> n;
//for (int i = 1; i <= n; i++) {
//    cin >> a[i];
//}
//for (int i = 1; i <= n; i++) {
//    fdp(i);
//}
//cout << ans;
//
//dp记录以这个数字为结尾的最长
//不一定要数组内每个连续都是7的倍数，只要数组总和
//所以改用前缀和思想
//pre[i]-pre[j]即这个区间段上的和
// 若直接遍历，为n^2的复杂读
//若记录mod7下的前缀和
//那么目的就改为让pre[i]-pre[j]=0
//即pre[i]=pre[j]时,ij的max
//即pre记录的是0~6，7个数，为求和%7的余数情况
const int maxn = 50010;
int pre[maxn], first[7], last[7];
int n, len, mx = -1,l[7],r[7],ans,a;
int s = 0;
cin >> n;
//for (int i = 1; i <= n; i++) {
//    cin >> pre[i];//输入后进行更新
//    pre[i] = (pre[i] + pre[i - 1]) % 7;
//}
//for (int i = 1; i <= n; i++) {//正着扫一遍
//    //pre[i]在0~6不断更新，则last[pre[i]]不断被覆盖，那么到i=n时，这个数组记录的就是最后一次pre[i]出现时的i下标
//    last[pre[i]] = i;
//}
//for (int i = n; i >= 1; i--) {
//    first[pre[i]] = i;
//    //从后往前遍历，不断更新数组，那么最后一次更新就是pre[i]第一次出现时的位置
//}
//first[0] = 0;
//for (int i = 0; i <= 6; i++) {
//    mx = max(mx, last[i] - first[i]);
//}
//cout << mx << endl;

//也可以用滚动数组
for (int i = 1; i <= n; i++) {
    cin >> a;
    s = (s + a) % 7;
    if (l[s] = -1) {
        l[s] = i;//第一次遇到，只有第一次更新
    }
    r[s] = i;//不断更新最后遇到的位置
}
for (int i = 0; i <= 6; i++) {
    if (l[i] != -1) {//只有说遇到了这个数，才进入答案的参考
        ans = max(ans, r[i] - l[i]);
    }
}
cout << ans;
//照这个思路，dp数组的外层遍历也是这个思想，从小到大，不断更新dp数组
//从而使数组的每个位置都存储的是这个下标（为实际意义下）的最大值，而与物品范围无关
//当然这个范围是逐渐扩大的，每扩大一次更新一次，到最后就是最新的最终结果
//这就是滚动数组，将二维化为一维

因为是整体，而非连续的，所以递推，看前一项就不好用了?

还有就是first[0]必须=0，即第一次求和为0，为什么都没有，从头开始加，不然，first[i]!=0,会丢失情况，别的都是遇到两次才能开始构成区间，0时，遇到一次就能构成了

STL集合

数列去重并排序

//STL中set,每个元素只出现一次，而且还从小到大排好了
// 
// 输入，输出
//
int n;
int a[1000000];
cin >> n;
set<int>s;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s.insert(a[i]);
}
cout << s.size() << endl;
while (!s.empty()) {
    cout << *s.begin() << " ";
    s.erase(s.begin());
}

集合中元素没有重复，而且还排好序了?

猜拳进阶版（周期，最小公约数，输赢得分记录）

第一行包含三个整数：�,��,��N,NA?,NB?,分别表示共进行?�N?次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含?��NA??个整数,表示小 A 出拳的规律,第三行包含?��NB??个整数,表示小 B 出拳的规律。其中，00?表示“剪刀”，11?表示“石头”，22?表示“布”，33?表示“蜥蜴人”，44表示“斯波克”。数与数之间以一个空格分隔。

//找周期的最小公倍数，然后为大周期
//计出每个大周期内的得分情况
//最后计出剩余轮次内的得分情况
//加和
//
//模拟思路
//用二维数组记录判别表
//用两个数组记录两人出拳情况(一个周期）
//用n%ta,n%tb做轮回
const int MAXN = 200 + 10;
int vs[5][5] = { {0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0} };
//这个表是赢家的表，只记录了怎么赢，因为如果有-1，就说不清了，就不能加到一个人上
//所以需要让两人轮流当赢家，赢了加分，输了或平不加分不扣分
int n, na, nb, a[MAXN], b[MAXN], cnta, cntb;
cin >> n >> na >> nb;
for (int i = 0; i < na; i++) {
    cin >> a[i];
}
for (int i = 0; i < nb; i++) {
    cin >> b[i];
}
for (int i = 0; i < n; i++) {
    cnta += vs[a[i % na]][b[i % nb]];
    cntb += vs[b[i % nb]][a[i % na]];
}
cout << cnta << " " << cntb;

这个表是甲对乙的结果得分表，即甲乙怎么出，甲的得分怎么变，注意，赢了加分，输了或平不扣分；i是甲（是要加分的目标），j是乙

当甲赢了，乙就输了；甲输了，乙就赢了；即对称位置不同时为1

所以只需考虑甲的情况，记录甲的得分，然后让乙加上对称位置的得分情况，即最终情况

加上对称位置就是说，甲赢则乙输，不加分；甲输则乙赢，乙加分；

输出最大正方形边长（二维dp打表）

在一个?�×�n×m?的只包含?00?和?11?的矩阵里找出一个不包含?00?的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数?�,�(1≤�,�≤100)n,m(1≤n,m≤100)，接下来?�n?行，每行?�m?个数字，用空格隔开，00?或?11。

输出格式

一个整数，最大正方形的边长。

//将每个位置的遍历赋值改为循序渐进的递推
//打表从右下开始，如果记录以该点为左上顶点的最大正方形边长
//？dp[][]记录，记录什么？
//？怎么判别是不是正方形？
//？怎么判断正方形大小？怎么渐进？

//打表从左上开始，
//dp记录该点为右下顶点的最大正方形的边长
//由于是递推，所以每个点不需要管距离自己远的点，不用检测2格以上的位置是不是1
//因为是递推，所以只需要管周围最邻近的点就行
//由于dp是右下角，所以递推需要看左边和上边（子问题）
//右下角多出来一格是其的延申，需要取左边和上边的最小值
//如果取最大值，就要扩展一个大的正方形，这时会囊括左边和上边的正方形，还会有延申，
//而最小的不够，即如果选大的，新正方形里一定有0，所以要取最小的
if (a[i][j] == 1) {
    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
    ans = max(ans, dp[i][j]);
}

铺地毯（覆盖思想）

//铺地毯，返回指定点上的第一张地毯
//1.暴力，输入左下角和长宽后，让地毯所盖区域为当前地毯编号
//如果之前有值，会直接覆盖，所以每个点的值就是最上面的地毯编号
//然后直接查找返回就行
//2.不用二维数组记录，只记录地毯信息
//然后输入坐标后，再次遍历全部地毯信息
//检测每张地毯是否涵盖目标点
//如果涵盖则更新信息
//这样，最后目标坐标就记录的就是最后一张覆盖着的地毯
for (int i = 0; i < n; i++) {
    if (x >= a[i] && y >= b[i] && x <= a[i] + g[i] && y <= b[i] + k[i]) {
        ans = i + 1;
    }
}