第一次 div2四道题！（可能是教育场简单一点），cf打多了就会有感觉了，真的思维题偏多，就看谁想的快敲的快，前面几题用到的算法知识几乎没有，多打可以锻炼思维。比赛的时候犯了几个傻 * 错误，导致多了几个罚时，挺不应该的，但是这次的题真的不难，包括补的E题（剩下两题一题没人做出来，一题就个位数的人，我就不奢望补了）
A. K-divisible Sum
题意
给你n， k，让你找n个数，这n个数的和可以被k整除，求这n个数中最大值的最小值。
分析
嗯，求最大值的最小值，那不就是二分答案吗？然后开始构思check函数……什么玩意，这咋check，然后开始从其他角度分析，设这n个数和为sum，要求最大值的最小值，先求一个大于等于sum且能被n整除的值x，然后x/n就是最大值的最小值。接下来去找sum，自然而然，sum肯定要尽量小，那么就找大于等于n的k的最小倍数即可。
比赛的时候犯了个弱智的错误，找上面的x值我直接用 while(x%n) x++; 然后就T掉了…其实除一下就可以O（1）内算出来的。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int main(int argc, char const *argv[]) {
LL n, k, t;
cin >> t;
while(t--) {
cin >> n >> k;
LL sum;
if(n%k != 0)
sum = (n/k+1)*k;
else sum = n;
LL temp = sum;
if(sum%n != 0)
temp = (sum/n+1)*n;
cout << temp/n << endl;
}
return 0;
}
B. Inflation
题意
给你n个数p和k,你可以随意地给 $p_i$ 加上一定的值，要求使得对于任意的 $p_i$ ,满足 $ \frac {p_i}{\sum\limits_{j=0}^{i-1} w_j} \le \frac k {100}(0 < i < n)$，求加上的值的总和最小值。
分析
由于只能把值改大不能改小，所以如果第 i 个位置不符合要求，只能改0到i-1这一段的p值，如果修改 $p_k$ 那么它对 $p_k$ 到 $p_n$ 都有贡献，所以为了每次修改后贡献最大，我们可以从后往前遍历，如果有一个位置不满足要求，则增大 $p_0$， 因为$p_0$ 可以使得其后面所有位置都更优。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
LL p[maxn], s[maxn];
int main(int argc, char const *argv[]) {
LL n, k, t;
cin >> t;
while (t--) {
cin >> n >> k;
for (int i = 1; i <= n; i++)
scanf("%lld", &p[i]), s[i] = s[i - 1] + p[i];
LL ans = 0;
for (int i = n; i >= 2; i--) {
if (p[i] * 100 > k * (s[i - 1] + ans)) {
ans += (ceil(100*p[i]*1.0/k) - (s[i-1]+ans));
}
}
cout << ans << endl;
}
return 0;
}
C. Longest Simple Cycle
题意
按照题目要求得到一张图，找到最大的一个环。
题目分析
直接从左往右来就行，维护一个当前环的大小以及最大值，如果下一个位置封死了，不能和当前环链接，就新建一个环。主要有四个坑：
1. a并不一定小于b（这点样例有），所以要用abs。
2. 第一个环的计算是 $c[i] + 1 + abs(a[i]-b[i])$。
3.下一个环链接已有的环时有两条路可以走，可以向外走和已有的环组成一个大环，也可以直接往内走，自成一个新环，要取max，这里比赛时没考虑到，导致wa3。
4. 可能超int，这里我比赛时考虑到了，但是有个地方还是漏写了long long，导致wa5。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
LL a[maxn], b[maxn], c[maxn];
int main(int argc, char const *argv[]) {
LL n, t;
cin >> t;
while (t--) {
cin >> n;
for(int i = 0; i < n; i++) scanf("%lld", &c[i]);
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
for(int i = 0; i < n; i++) scanf("%lld", &b[i]);
LL ans = -1, now = 0;
for(int i = 1; i < n; i++) {
if(a[i] == b[i]) {
now = c[i] + 1;
}
else {
if(now == 0) now = c[i] + 1 + abs(a[i]-b[i]);
else {
now = c[i] + 1 + max(now - abs(a[i] - b[i]),abs(a[i]-b[i]));
}
}
ans = max(ans, now);
}
cout << ans << endl;
}
return 0;
}
D. Journey
题意
一共有n+1座城市，编号0-n，每相邻两座城市之间有一条有向边，共n条边，给你一个仅由’L’和’R’组成的长n的字符串表示n条边的初始方向，一个游客从一座城市出发，每天必须沿着有向边向相邻的一座城市走，并且每天有向边都会变换一次方向（朝左变成朝右，朝右变成朝左），若游客不能向左也不能向右走，则结束旅行。输出从每座城市开始，可以访问的最多城市数。
分析
首先，如果一个人可以到达某个城市，那么他还可以原路返回，并且到起点时，所有路的方向和初始相同。那么我们只要考虑每座城市向左最远可以到哪里，向右可以到哪里，加起来即可。观察可知，只有形似LRLRLR的才能畅通无阻，所有我们分别从左向右和从右向左遍历一次字符串，记录以每个位置开始向左有几个“LRLRL”以及向右有几个“LRLRL”，然后遍历一下每座城市，判断初始时是否可以向左走，如果可以，则最远距离就是向左的“LRLRLR”的长度，向右同理，左右城市数相加再+1（起点城市）就是答案。
我觉得这题的主要难点就是下标的对应关系，可以举个例子看一下下标之间的关系。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
char s[maxn];
int zuo[maxn], you[maxn];
int main(int argc, char const *argv[]) {
LL n, t;
cin >> t;
while (t--) {
cin >> n;
cin >> s;
zuo[0] = 0, zuo[1] = 1;
for(int i = 1; i < n; i++) {
if(s[i] != s[i-1]) {
zuo[i+1] = zuo[i] + 1;
}
else zuo[i+1] = 1;
}
you[n] = 0, you[n-1] = 1;
for(int i = n-1; i >= 1; i--){
if(s[i] == s[i-1]) {
you[i-1] = 1;
}
else {
you[i-1] = you[i] + 1;
}
}
for(int i = 0; i <= n; i++) {
if(i == 0) {
if(s[i] == 'R') cout << you[i] + 1 << ' ';
else cout << 1 << ' ';
}
else if(i == n) {
if(s[i-1] == 'L') cout << zuo[i] + 1<< " ";
else cout << 1 << endl;
}
else {
int ans = 0;
if(s[i] == 'R') ans += you[i];
if(s[i-1] == 'L') ans += zuo[i];
cout << ans+1 << " ";
}
}
puts("");
}
return 0;
}
E. Pattern Matching（拓扑）
题意
给你n个模式串，编号1-n，模式串中可能含有‘ _ ’,表示这个位置可以放任何值。再给你m个匹配串，每个匹配串后带一个值 $m_i$ ，模式串和匹配串的大小都为k。让你找到任意一个模式串的下标的序列，满足第 i 个匹配串对应的所有模式串，在序列中第一个出现的下标为 $m_i$。
分析
每个匹配串可能对应多个模式串，对于某个匹配串，要求第mi个模式串在序列中是最先出现的，我们将所有的模式串看成一个点，对于每个匹配串，将mi和所有该匹配串可以对应的模式串对应的点连边，只要找到拓扑序，就是一种满足题目要求的解。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
unordered_map<string, int> ha;
string p[maxn];
vector<int> mp[maxn];
int in[maxn];
int n, m, k;
bool judge(string &s, string &p) {
for(int i = 0; i < k; i++) {
if(s[i] != p[i] && p[i] != '_') return false;
}
return true;
}
int main(int argc, char const *argv[]) {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
cin >> p[i];
ha[p[i]] = i;
}
for(int i = 0; i < m; i++) {
int mt;
string s;
cin >> s >> mt;
if(!judge(s, p[mt])) {
puts("NO");
return 0;
}
for(int i = 0; i < 1 << k; i++) {
string temp = s;
for(int j = 0; j < k; j++) {
if(i >> j & 1) temp[j] = '_';
}
if(ha.find(temp) == ha.end() || ha[temp] == mt) continue;
mp[mt].push_back(ha[temp]);
in[ha[temp]]++;
}
}
queue<int> q;
vector<int> ans;
for (int i = 1; i <= n; i++) {
if (in[i] == 0) {
q.push(i);
}
}
while (q.size()) {
int now = q.front();
q.pop();
ans.push_back(now);
for (int i = 0; i < mp[now].size(); i++) {
in[mp[now][i]]--;
if (in[mp[now][i]] == 0)
q.push(mp[now][i]);
}
}
if(ans.size() != n) puts("NO");
else {
puts("YES");
for(int i = 0; i < n; i++) cout << ans[i] << ' ';
}
return 0;
}
