Week 17
代码源每日一题Div2
602. 01序列2
原题链接：01序列2
思路：用前缀和算出每一位的前面所有构造方法数量的和即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, k, dp[1000005], sum[1000005];
const int mod = 1e9 + 7;
int main(){cin >> n >> k;sum[0] = 1;for(int i = 1; i <= k + 1; i++){sum[i] = (sum[i - 1] + 1) % mod;}for(int i = k + 2; i <= n; i++){dp[i] = (dp[i] + sum[i - k - 1]) % mod;sum[i] = (dp[i] + sum[i - 1]) % mod;}cout << sum[n];return 0;
}
603. 整除光棍
原题链接：整除光棍
思路：模拟竖式除法，设被除数为全是1的数字，若不能整除则将全是1的数位数加一，直到能整除为止。
代码：
#include <bits/stdc++.h>
using namespace std;
int x, sum, tmp, num[100005], indexx;
int main(){cin >> x;while(tmp < x){tmp = tmp * 10 + 1;sum++;}while(tmp % x != 0){num[indexx++] = tmp / x;tmp %= x;tmp = tmp * 10 + 1;sum++;}num[indexx++] = tmp / x;for(int i = 0; i < indexx; i++){cout << num[i];}cout << " " << sum;return 0;
}
604. 碰撞2
原题链接：碰撞2
思路：用map储存点的位置和移动方向，y坐标作为map中的key，value为{x坐标，移动方向}类型的set容器，便于以x坐标来排序。然后对于每个y坐标，遍历其中的所有点，判断是否会碰撞即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bool flag;
struct point{int x, y;char dir;
} p[200005];
map<int, set<point> > mp;
bool operator<(point a, point b){return a.x < b.x;
}
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> p[i].x >> p[i].y;}cin >> s;for(int i = 0; i < s.size(); i++){p[i + 1].dir = s[i];}for(int i = 1; i <= n; i++){mp[p[i].y].insert(p[i]);}for(auto i : mp){bool isR = false;for(auto j : i.second){if(j.dir == 'L' && isR){flag = true;break;}else{if(j.dir == 'L') isR = false;else isR = true;}}if(flag) break;}if(flag) cout << "Yes";else cout << "No";return 0;
}
605. 优美！最长上升子序列
原题链接：优美！最长上升子序列
思路：由于子序列的下标要满足互相能整除，因此可以直接依次遍历1~n的整数倍，判断是否是上升序列即可，不会超时。
代码：
#include <bits/stdc++.h>
using namespace std;
int t, n, a[1000005], dp[1000005], maxx;
int main(){cin >> t;for(int k = 0; k < t; k++){maxx = 1;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = 1;for(int i = 1; i <= n; i++){for(int j = i * 2; j <= n; j += i){if(a[j] > a[i]) dp[j] = max(dp[j], dp[i] + 1), maxx = max(maxx, dp[j]);}}cout << maxx << endl;}return 0;
}
606. 巨大的牛棚
原题链接：巨大的牛棚
思路：动态规划，设dp[i][j]为(i, j)处能修建的最大牛棚，则状态转移方程为：
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
找出最大的dp[i][j]即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, t, dp[1005][1005], v[1005][1005], maxx;
int main(){cin >> n >> t;for(int i = 0; i < t; i++){int x, y;cin >> x >> y;v[x][y] = true;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(!v[i][j]) dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1, maxx = max(maxx, dp[i][j]);}}cout << maxx;return 0;
}
607. 高利贷
原题链接：高利贷
思路：二分查找p的值，直到二分的左右边界的差不超过1e-6即可。
代码：
#include <bits/stdc++.h>
using namespace std;
double n, m, k, mid;
bool check(double p){double sum = 0;for(int i = 1; i <= k; i++){sum += m / pow(1 + p, i);}if(sum >= n) return true;else return false;
}
int main(){cin >> n >> m >> k;double st = 0, ed = 10;while(st < ed){mid = (st + ed) / 2;if(ed - st < 1e-6) break;if(check(mid)) st = mid;else ed = mid;}cout << fixed << setprecision(6) << mid;return 0;
}
701. 背包
原题链接：背包
思路：依次遍历每一个物品，若物品体积满足题目要求则说明直接输出“YES”，若体积大于背包容积则跳过此物品，若体积小于背包容积的一半，我们可以累加这些物品的体积，如果某一次累加后能满足题意则输出“YES”，否则输出“NO”
代码：
#include <bits/stdc++.h>
using namespace std;
long long t, n, w, a[200005];
int main(){cin >> t;for(int i = 0; i < t; i++){cin >> n >> w;for(int i = 1; i <= n; i++){cin >> a[i];}long long sum = 0;bool flag = false;for(int i = 1; i <= n; i++){if(2 * a[i] >= w && a[i] <= w){cout << "YES\\n";flag = true;break;}else if(a[i] < w){sum += a[i];}if(2 * sum >= w && sum <= w){cout << "YES\\n";flag = true;break;}else if(sum > w){sum = 0;}}if(!flag) cout << "NO\\n";}return 0;
}
702. 三回文序列
原题链接：三回文序列
思路：由于ai的值范围很小，因此我们可以先记录所有ai出现的次数，然后遍历所有范围内的ai，分别让他们作为两边的k1，然后找出中间的k2的最大值（即中间部分数量最多的ai），求出此时的回文序列长度，最后比较所有求出的回文序列的长度即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int t, n, a[200005], sum[30], tmp[30], ans;
int main(){cin >> t;for(int k = 0; k < t; k++){cin >> n;ans = 0;memset(sum, 0, sizeof(sum));for(int i = 1; i <= n; i++) cin >> a[i], sum[a[i]]++;for(int i = 1; i <= 26; i++){int cnt = 0, maxlen = sum[a[i]];for(int j = 1; j <= 26; j++) tmp[j] = sum[j];int l = 1, r = n;while(l < r){while(a[l] != i && l < r){tmp[a[l]]--;l++;}while(a[r] != i && l < r){tmp[a[r]]--;r--;}cnt += min(2, tmp[i]);tmp[i] = max(0, tmp[i] - 2);for(int j = 1; j <= 26; j++) maxlen = max(maxlen, cnt + tmp[j]);l++, r--;}ans = max(ans, maxlen);}cout << ans << endl;}return 0;
}
703. 简单的异或问题
原题链接：简单的异或问题
思路：找规律。通过观察可以发现，0~2^m-1的所有二进制数的每一位的0和1的数量一定是相同的，那么当m大于1时，这个区间所有的数每一位的异或和则为m个（1 | 0）的值的异或值，即最后得出的每一位的异或值一定为0。因此，如果n为0，则最大的k即为2m，若n不等于0，则我们一定能通过单独去除某一个数来改变所有数的异或和从而得到n，因此此时的k为2m-1。特别地，当m等于1时，需要单独判断一下。
代码：
#include <bits/stdc++.h>
using namespace std;
long long n, m;
int main(){cin >> n >> m;if(m == 1 && n == 0) cout << 1;else if(m == 1 && n == 1) cout << 2;else if(n != 0) cout << (long long)pow(2, m) - 1;else cout << (long long)pow(2, m); return 0;
}
704. 子串的循环挪动
原题链接：子串的循环挪动
思路：当挪动次数k很大时，只需要计算k % (r - l + 1)即可得出子串最后的移动次数。
代码：
#include <bits/stdc++.h>
using namespace std;
string s;
int m, l, r, k;
int main(){cin >> s >> m;s = " " + s;for(int i = 0; i < m; i++){cin >> l >> r >> k;int dis = k % (r - l + 1);while(dis--){char tmp = s[r];for(int j = r; j > l; j--){s[j] = s[j - 1];}s[l] = tmp;}}s.erase(0, 1);cout << s;return 0;
}