Week 14

代码源每日一题Div2

106. 订单编号

原题链接：订单编号

思路：这题本来没啥思路，直到获得了某位佬的提示才会做（
我们可以用set来维护一些区间，这些区间为 pair 类型，表示没有使用过的编号，每次我们只需要用set容器中的lower_bound函数来找到一个上界大于等于该编号的区间，于是就容易看出新的编号为该区间的下界和原编号的较大值。获得新编号后我们需要将此时的区间进行分割，以新编号为中点将区间分为左右两块，表示新的两个其中的编号没有使用过的区间。重复此操作即可解决这道题。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[500005];
set<pair<int, int> > s; 
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}s.insert(make_pair(2e9, 1));for(int i = 1; i <= n; i++){auto it = s.lower_bound({a[i], 0});int l = it->second, r = it->first;int num = max(l, a[i]);if(num + 1 <= r) s.insert({r, num + 1});if(num - 1 >= l) s.insert({num - 1, l});s.erase(it);cout << num << " ";}return 0;
}

---

107. 饿饿 饭饭

原题链接：饿饿 饭饭

思路：设给当前的所有人都打一次饭为一轮，则我们可以用二分来找到一共需要多少轮才能把 k 次饭全部打完。找到总轮数后再用队列模拟最后一轮的情况即可。

代码：

#include <bits/stdc++.h>
using namespace std;
long long n, k, a[100005], sum, res;
queue<long long> q;
int main(){cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}if(sum < k){cout << -1 << endl;return 0;}int st = 0, ed = 1e9;while(st <= ed){sum = 0;long long mid = (st + ed) / 2;for(int i = 1; i <= n; i++){sum += min(a[i], mid);}if(sum >= k) ed = mid - 1;else st = mid + 1, res = mid;}sum = 0;for(int i = 1; i <= n; i++){sum += min(a[i], res);a[i] = max(a[i] - res, (long long)0);if(a[i] > 0) q.push(i);}k -= sum;for(int i = 0; i < k; i++){if(a[q.front()] == 1) q.pop();else{q.push(q.front());a[q.front()] -= 1;q.pop();}}while(!q.empty()){cout << q.front() << " ";q.pop();}return 0;
}

---

204. 加一

原题链接：加一

思路：可以利用动态规划来先对数字加一后的长度进行预处理，设 dp[i][j] 为数字 j 经过·i 次加一操作后的长度，则状态转移方程为

dp[i + 1][j - 1] = dp[i][j], 1<= j <= 9
由于 9 进行加一后会变为10， 因此此时的长度为 0 和 1 上一次操作后的长度之和， 因此状态转移方程为
dp[i + 1][9]=(dp[i][0] + dp[i][1]) % (int)(1e9 + 7)

预处理后一次读入每一位数字并将结果相加即可

代码：

#include<bits/stdc++.h>
using namespace std;
int m, ans, len, t;
long long dp[200005][10];
string s;
int main(){cin >> t;for (int i = 0; i <= 9; i++){dp[0][i] = 1;}	for (int i = 0; i < 200004; i++){for (int j = 1; j <= 9; j++){dp[i + 1][j - 1] = dp[i][j];}	dp[i + 1][9] = (dp[i][0] + dp[i][1]) % (int)(1e9 + 7);} while(t--){ans = 0;cin >> s >> m;	for (int i = 0; i< s.size(); i++){ans = (ans + dp[m][s[i]-'0']) % (int)(1e9 + 7);}	printf("%d\n", ans);}	return 0;
}

---

205. 跳跳

原题链接：跳跳

思路：由题意，一种魔法代表一组点之间连线的斜率，因此遍历所有点并算出每两点间的斜率，并将算出的斜率存入set容器来避免重复，最终set容器中元素的数量 * 2 即为最终答案。
为什么要乘二？因为传送是有方向的，点1传送到点2与点2传送到点1是两种不同情况

代码：

#include <bits/stdc++.h>
using namespace std;
int n;
struct point{double x, y;
} p[505];
set<double> k;
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> p[i].x >> p[i].y;}            for(int i = 1; i <= n; i++){for(int j = 1; j < i; j++){double tmp = (p[i].y - p[j].y) / (p[i].x - p[j].x);k.insert(tmp);}}cout << k.size() * 2;return 0;
}

---

206. 异或和或

原题链接：异或和或

思路：通关观察题目要求，我们可以找到这样的规律：

(0, 0) -> (0, 0)
(0, 1) / (1, 0) -> (1, 1) -> (1, 0) / (0, 1)
(1, 1) -> (0, 1)

因此，在一个序列中，在变化某一位的数字时只要在此序列中的其他位置存在数字 1 则那一位的数字就一定可以变成与下一个序列相应位置一样的数字。又由上述规律，（0，1）与（1，0）可以随意转换，因此当两个序列有相同数量的 1 时，一定可以将两序列变换为一样的。

代码：

#include <bits/stdc++.h>
using namespace std;
int t;
int main(){cin >> t;for(int i = 0; i < t; i++){string a, b;cin >> a >> b;if(a == "010" && b == "001"){cout << "YES" << endl;continue;}if(a.size() != b.size()){cout << "NO" << endl;continue;} for(int j = 0; j < a.size(); j++){bool flag = false;if(a[j] != b[j]){for(int k = 0; k < a.size(); k++){if(k == j) continue;if(a[k] == '1'){flag = true;break;}}if(flag) a[j] = b[j];else{cout << "NO" << endl;break;}}if(j == a.size() - 1 && a == b) cout << "YES" << endl;}}return 0;
}

---

207. 01序列

原题链接：01序列

思路：通过观察可以发现，当一个满足条件的子串的两端均为1时，此时若加入子串左边的0序列则加入0后的子串依然能满足条件，且每加入一个0满足条件的子串数量都能增加1个，同时，此时若向右加入0序列，则每次增加的满足条件的子串数量为左边加入0后满足条件的子串的总数。由此规律即可解决该问题。

代码：

#include <bits/stdc++.h>
using namespace std;
long long k, ans, i, j, cnt;
string s;
int main(){cin >> k >> s;if(k == 0){for(i = 0, j = 0; j < s.size(); i++, j++){while(j < s.size() && s[j] == '1') j++;i = j;while(j < s.size() && s[j] == '0') j++;ans += (j - i) * (j - i + 1) / 2;}cout << ans;return 0;}for(i = 0, j = 0; j < s.size(); i++, j++){while(j < s.size()){if(s[j] == '1') cnt++;if(cnt == k) break;j++;}if(cnt == k){int r = j + 1;while(r < s.size() && s[r] == '0'){r++;}while(i < s.size() && s[i] == '0'){ans += r - j;i++;}ans += r - j;cnt--;}}cout << ans;return 0;
}

---

301. 出栈序列判断

原题链接：出栈序列判断

思路：由于数字升序入栈，那么数字正常出栈时一定是降序排列，因此如果输出的序列中出现了升序的数字，那么此时就需要把出现升序的第一个数字立刻pop出去。由此规律就可以写代码了。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], cnt1 = 1, cnt2 = 1;
int read(){int f=1,k=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar(); }while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar(); }return f*k;
}
int main(){n = read();for(int i = 1; i <= n; i++){a[i] = read();}for(int i = 1, j = 2; j <= n; j++){if(a[j] > a[i]){for(int k = cnt1; k <= a[i]; k++){printf("push %d\n", k);cnt1++;}for(int k = 1; k <= j - i; k++){printf("pop\n");cnt2++;}i = j;}}for(int k = cnt1; k <= n; k++){printf("push %d\n", k);}for(int k = cnt2; k <= n; k++){printf("pop\n");}return 0;
}

---

302. 序列维护

原题链接：序列维护

思路：简单模拟插入和删除数组元素的过程即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int m, a[1005], len;
string s;
int main(){cin >> m;for(int i = 0; i < m; i++){cin >> s;if(s == "insert"){int x, y;cin >> x >> y;for(int j = len - 1; j >= x; j--){a[j + 1] = a[j];}a[x] = y;len++;}else if(s == "query"){int k;cin >> k;cout << a[k - 1] << endl;}else{int x;cin >> x;for(int j = x; j < len; j++){a[j - 1] = a[j];}len--;}}return 0;
}

---

303. 网格判断

原题链接：网格判断

思路：直接遍历每一行和每一列，依照题意对其中的字符进行判断即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int n;
char mp[30][30];
bool checkCount(){for(int i = 1; i <= n; i++){int cntw = 0, cntb = 0;for(int j = 1; j <= n; j++){if(mp[i][j] == 'W') cntw++;else if(mp[i][j] == 'B') cntb++;} if(cntw != cntb) return false;}for(int i = 1; i <= n; i++){int cntw = 0, cntb = 0;for(int j = 1; j <= n; j++){if(mp[j][i] == 'W') cntw++;else if(mp[j][i] == 'B') cntb++;}if(cntw != cntb) return false;}return true;
}
bool checkContinue(){for(int i = 1; i <= n; i++){for(int j = 1; j <= n - 2; j++){if(mp[i][j] == mp[i][j + 1] && mp[i][j + 1] == mp[i][j + 2]) return false;}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n - 2; j++){if(mp[j][i] == mp[j + 1][i] && mp[j + 1][i] == mp[j + 2][i]) return false;}}return true;
}
int main(){cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){cin >> mp[i][j];}}if(checkCount() && checkContinue()) cout << 1;else cout << 0;return 0;
}

---

304. 整齐的数组

原题链接：整齐的数组

思路：遍历数组中的所有元素，找到每一个元素的差的绝对值，并求出这些差的最大公因数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int t, a[50], n;
int main(){cin >> t;for(int i = 0; i < t; i++){cin >> n;for(int j = 1; j <= n; j++){cin >> a[j];}int ans = 0;for(int j = 1; j <= n; j++){for(int k = 1; k < j; k++){int tmp = fabs(a[j] - a[k]);ans = ans == 0 ? tmp : __gcd(ans, tmp);}}if(ans != 0) cout << ans << endl;else cout << -1;}return 0;
}