2023 summer 第二周
2023.07.17 SMU Summer 2023 Contest Round 4 - Codeforces
A.Telephone Number
定义电话号码：8开头，11位
给一串数字，问能否通过删除操作改成电话号码
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
if(n >= 11) {
for(int i = 0; i < n - 10; i++)
if (s[i] == '8') {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
return;
}
signed main() {
int t;
cin >> t;
while(t--) solve();
}
~B. Lost Numbers
有六个数：mark[6]={4,8,15,16,23,42}，这六个数随机排列。程序会问你四个问题，每个问题涵盖两个下标，你要回答两个下标所代表的数的乘积。在四个问题后如果程序能猜出你的数的排列，那么输出这组数，否则输出"0".
#include<bits/stdc++.h>
using namespace std;
int mark[6]={4,8,15,16,23,42} ;
int sum[4];
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int i = 0;
printf("? 1 2\n");
fflush(stdout);
cin >> sum[i];
i++;
printf("? 2 3\n");
fflush(stdout);
cin >> sum[i];
i++;
printf("? 3 4\n");
fflush(stdout);
cin >> sum[i];
i++;
printf("? 4 5\n");
fflush(stdout);
cin >> sum[i];
i++;
int cnt = 0;
do {
if(mark[0] * mark[1] == sum[0] && mark[1] * mark[2] == sum[1] && mark[2] * mark[3] ==sum[2] && mark[3] * mark[4] == sum[3])
break;
else cnt ++;
} while (next_permutation(mark, mark + 6));
if(cnt == 720) {//如果最后一次才找到答案的话，由于上面cnt是后加的，所以cnt==719，不会出错
cout << '0';
fflush(stdout);
return 0;
}
cout << "!";
for (int j : mark) cout << ' ' << j;
fflush(stdout);
return 0;
}
~C. News Distribution
有n个用户分布在m个好友群组中。开始时，某个用户x从消息源接收到一条消息，则x所在的所有的好友群组中的所有人都将知道这个消息。
输入n和m，接下来有m行，每行描述一个好友群组，以整数k（0~n）开头，表示这个群组中用户的数量，然后k个整数表示属于该群组的用户。
输出n个整数。第i个整数表示如果用户i开始传播消息，最终会有多少用户知道这条消息。
并查集，读取一个群组的成员时把他们都合并成一个集合，两个群组中有相同的成员的时候会把两个群组也合并，最后只用输出每个成员所在的集合拥有的成员个数即可
#include "bits/stdc++.h"
#define int long long
#define endl "\n"
using namespace std;
const int MAX_N = 1e6 + 10;
int p[MAX_N], ans[MAX_N];
int n, m;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1;i <= n;i++) p[i] = i;
while(m--) {
int k, h, v;
cin >> k;
if (k) cin >> h;
for (int i = 1; i < k; i++) {
cin >> v;
if (find(v) != find(h)) p[find(v)] = find(h);
}
}
for (int i = 1;i <= n;i++) ans[find(i)]++;//遍历n个成员，find(i)可理解为i所在的集合的编号（根节点的编号），每一次遍历到这个集合的元素，这个集合映射的ans值都会增加，则遍历完成员后，这个集合所映射的ans值则代表了这个集合中元素的个数
for (int i = 1;i <= n;i++) cout << ans[find(i)] << ' ';
cout << endl;
return 0;
}
D. Bicolored RBS
将一个给定的合法括号序列（RBS）分成两个括号序列r和b，使得r和b都是合法的括号序列，并且它们的嵌套深度尽可能接近，即两个序列的最大嵌套深度的差值要最小。
为了尽可能地使两个序列的嵌套深度接近，我们希望每次选择括号的时候，都选择括号数量较少的那个序列。这样可以确保括号的嵌套深度较小的序列能够尽可能多地接受新的括号，而括号的嵌套深度较大的序列则相对较少地接受新的括号，从而尽量平衡两个序列的嵌套深度。
对于RBS字符串s中的每个字符s[i]，进行如下处理：
a. 如果s[i]是左括号'('，则判断当前red和blue的括号数量，将括号数量较少的那个栈对应的括号颜色设置为蓝色，并将ans[i]设置为字符'1'。将s[i]放入对应的栈中。
b. 如果s[i]是右括号')'，则判断当前red和blue的括号数量，将括号数量较少的那个栈对应的括号颜色设置为红色，并将ans[i]设置为字符'0'。将对应的栈中的顶部括号出栈。
#include<bits/stdc++.h>
using namespace std;
string s;
vector<char> ans(2e5+10);
int main(){
int n;
cin >> n;
cin >> s;
stack<int> red, blue;
for(int i = 0; i < n; i++) {
if(s[i] == '(') {
if(red.size() >= blue.size()) {
blue.push(s[i]);
ans[i] = '1';
} else {
red.push(s[i]);
ans[i] = '0';
}
} else {
if(red.size() >= blue.size()) {
red.pop();
ans[i] = '0';
} else {
blue.pop();
ans[i] = '1';
}
}
}
for(int i = 0; i < n; i++) cout << ans[i];
cout << endl;
return 0;
}
2023.07.19 nowcoder 23暑假友谊赛
~A. 马猴烧酒
给定一个n*m由.和*组成的网格中，通过a次行删除和b次列删除的机会把所有*删去，问能否把*全删除
针对行讨论（这题行的数据范围较小），每行删除和不删除相互组合总共有2^n种情况，抛去执行删除次数超过a的情况，在每种情况中分别检测未执行删除操作的行的每个列元素，如果有*则把这列存在set中维护，再判断列删除的机会够不够删去这些列即可
#include "bits/stdc++.h"
#define lowbit(x) x&(-x)
using namespace std;
const int N = 30, M = 100010;
char g[N][M];
int get(int x){
int res=0;
while(x) res++,x-=lowbit(x);//lowbit(x)不断返回二进制中第一个1所代表的数字，这个循环则会得出x中有多少个1
return res;
}
void solve() {
int n, m, a, b;
cin >> n >> m >> a >> b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
for (int op = 0; op < (1 << n); op++) {//2^n的意思是对于每一行都有删除和不删除两种清楚，则n行是2^n种情况，转换为2进制的01串则0和1代表了两种情况，1代表删除
int cnt = get(op);//get统计op在二进制中1的个数
if (cnt > a) continue;//如果这次枚举的需要删除的行大于a次行删除机会则跳过这次枚举
set<int> st;//维护维护哪些列存在敌人
for (int i = 0; i < n; i++) {
if (!(op >> i & 1)) {//如果第i行是0，即这行没有执行删除操作
for (int j = 0; j < m; j++) {//在这行上逐列扫描如果这列有*则存进st中
if (g[i][j] == '*')st.insert(j);
}
}
}
if (st.size() <= b) {//如果列上的*小与等于b次列删除机会，则一定可以删完
cout << "yes" << endl;
return;
}
}
cout << "no" << endl;
}
signed main() {
int T;
cin >> T;
while(T--) solve();
}
B. 阶乘
给一个正整数p，让你求一个正整数n，使得n!是p的倍数
例如p为90
p = 90 = 2^1 * 3^2 * 5^1
我们要找到n!=1*2*3*4*5*6*……，使得n！中的因子正好能把p的全部消灭掉
将n看作变量，设置为x，x！在区间上具有二段性，一开始不能把p消去，到某个值的时候突然可以并且后面的都可以，则可以二分去写
#include "bits/stdc++.h"
using namespace std;
void solve() {
int p;
cin >> p;
if (p == 1) {
cout << 1 << endl;
return;
}
//将p分解质因数
map<int, int> m;
for (int i = 2; i <= p / i; i ++ )
if (p % i == 0) {
int s = 0;
while (p % i == 0) p /= i, s ++ ;
m[i] = s;
}
if (p > 1) m[p] = 1;
//二分原理：由于x！具有单调性，我们只用找区间中第一个满足x! 是 p的倍数的 数（设这个数为x），找左值
//check判断x!是否等于p，检测x的所有个质因子，如果都完全包含p的，则true
auto check = [&](int x) {
for(auto [a, b] : m) {
int res = 0;
int n = x;
while(n) {
res += n / a;
n /= a;
}
if (res < b) return false;
}
return true;
};
int l = 0, r = 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
signed main() {
int T;
cin >> T;
while(T--) {
solve();
}
}
C. 完全图
给定一个包含 n 个顶点的完全图，你可以删掉图中的一些边，但是删掉的边不能超过 m 条，请问删去边之后的图最多能有几个连通分量？
贪心，二分
设联通分量为x(1～n)，f(x)为得到x个联通分量需要删去的边数
x f(x)
1 0
2 n-1
3 n-1 + n-1-1
4 n-1 + n-1-1 + n-1-1-1
则得到关系式f(x) = (x-1)(n-1 + n-x-1)/2 <=m
f(x)单调增，可以二分，且二分找右端点
由于数据量(1e18 * 1e18)太大，则需要__int128
#include "bits/stdc++.h"
#define int __int128
using namespace std;
int read() {
int res = 0, ch, flag = 0;
if ((ch = getchar()) == '-') flag=1;
else if (ch >= '0' && ch <= '9') res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + ch - '0';
return flag ? -res : res;
}
void write(int x){
if (x < 0) putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
int n,m;
bool check(int x) {
return 2 * n * x - 2 * n - x * x + x <= 2 * m;
}
signed main() {
int T = read();
// cin >> T;
while (T--) {
n = read();
m = read();
// cin >> n >> m;
int l = 1,r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
write(r);
cout << endl;
// cout << r << endl;
}
}
*E. A+B问题
int a, b;
cin >> a >> b;
cout << a+b;
输出c，问有多少种输入可能
样例
cin 1
cout 4294967296
#include "bits/stdc++.h"
using namespace std;
signed main() {
cout<<4294967296<<endl;
return 0;
}
G. 树上求和
给一个n个节点n-1条边的树，要你给每条边上附上权值（1~n-1且不重复）
定义树的权值为所有不同的树链的权值的代数和(即w(1~2)+w(1~3)+……w(1~n)+w(2~3)+……w(2~n)+……w(n-1~n) )
输出树的最小权值
如果要找最小的话，肯定让经过边次数最多的那条边权值最小，经过边次数最小的那条边权值最大
如何计算边的次数？找规律发现每条边的次数为 边左边的所有点的个数×右边的所有点的个数
例如下图，从1开始dfs，搜到左半所有子节点的个数为2，右半为3，则1~2边的次数为2*(n-2),1~3边的次数为3*(n-3),则可记录所有边的次数，反向排下序然后和权值1~n一次乘积求和即可
graph TD
A(1)<-->B1(2)
A<-->B2(3)
B1<-->C1(6)
B2<-->D1(4)
B2<-->D2(5)
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e5+10;
int n;
vector<int> g[N];
vector<bool> vis(N);
vector<int> res;//存每条边需要经过的次数
int dfs(int v) {
vis[v] = true;
int sum = 1;//记录以v为父节点，父节点和子节点的总数量
for (int i = 0; i < g[v].size(); i++) {
if(!vis[ g[v][i] ]) {
int s = dfs(g[v][i]);
sum += s;
res.push_back(s * (n - s));
}
}
return sum;
}
signed main() {
cin >> n;
for(int i = 1;i < n; i++) {
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
std::sort(res.begin(), res.end(), greater());
// for (int i : res) cout << i << " ";
// cout << endl;
int ans = 0;
for(int i = 1; i <= n - 1; i++) {
ans += res[i-1] * i;
// cout << ans <<endl;
}
cout << ans;
return 0;
}
~H. 奇怪的背包问题增加了
容量2^30的背包，去选择装若干件体积为2^ki(0<=ki<=30)的物品，所装的体积要正好等于背包容积。给你i个k的值，输出含i个数字的01串代表第i个物品是否被选中，如果不存在符合条件的方案输出impossible
//由二进制加法，可将背包容量拆分为2^30== 2^29+2^29 == 2^29+2^28+2^28 == 2^29+2^28+2^27+2^27
//从上面这行可以看到，2^30依次减去2^k(0<=k<=30)的数，且下一次减去的数比上一次小或相等，这样操作下去最后一定会经过0（如果供减去的数足够）
//则将物品体积从大到小排序，用2^30依次减去，直至减到0或者物品用完即可判断
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+10;
signed main(){
int T;
cin >> T;
while(T--){
int m;
cin >> m;
pair<int,int> a[MAX_N];
for(int i = 0; i < m; i++){
int t;
cin >> t;
a[i].first = 1 << t;
a[i].second = i;
}
sort(a, a + m, greater<pair<int,int>>());
int res = 1 << 30;
int ans[MAX_N];
memset(ans, 0, sizeof ans);
for (int i = 0; i < m; i++)
if (res >= a[i].first) {
res = res - a[i].first;
ans[a[i].second] = 1;
}
if(res == 0){
for (int i = 0; i < m ; i++) cout << ans[i];
} else cout << "impossible";
cout << endl;
}
return 0;
}
I. 寻找字串
找字符串中字典序最大的连续字串
先确定最大的字母作为首元素，然后循环判断找字典序大的，由于 abcde 比 abcd 字典序大 ，所以贪心的直接截取到末尾
#include <bits/stdc++.h>
using namespace std;
signed main() {
string s;
cin>>s;
char t = * max_element(s.begin(),s.end());
string ans = {};
for(int i = 0; i < s.size(); i++)
if(s[i] == t) ans = max(ans, s.substr(i));
cout << ans;
return 0;
}
*J. 最大的差
给定n个数字，请你从中选出两个数字，使得这两个数字的差尽量大，输出这个最大的差。
#include "bits/stdc++.h"
using namespace std;
signed main() {
int n;
cin >> n;
vector<int> num(n);
for(int i = 0; i < n; i++) cin >> num[i];
std::sort(num.begin(), num.end());
cout << num[n - 1] - num[0];
}
2023.07.21 SMU Summer 2023 Contest Round 5
A. Points in Segments
给n个，1～m的子集，求1～n中所有没在这些子集中出现过的数字
把子集区间合并为集合s，输出1～n中没有在s中出现过的数
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
int n, m;
vector<PII> segs;
vector<bool> mark(110);
void merge() {
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first) {
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
void solve() {
merge();
for(auto [i, j] : segs) {
// cout << i << ' ' << j << endl;
for(int pos = i; pos <= j; pos ++) {
mark[pos] = true;
}
}
int cnt = 0;
for(int i = 1; i <= m; i++) {
if(!mark[i]) cnt ++;
}
cout << cnt << endl;
if(cnt == 0) {
return;
}
for(int i = 1; i <= m; i++) {
if(!mark[i]) cout << i << " ";
}
}
signed main() {
cin >> n >> m;
while(n--) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
solve();
}
~B. Obtaining the String
给定两个长度相等的字符串，通过每次交换相邻两个字符的操作，把第一个字符串调整为第二个字符串，问最少的操作数和每次操作所交换元素的第一个元素的下标
第一次读错题以为字符串中没有相同的字母，所以这么做了：把第二个字符串的字母，映射成它的下标，则第一个字符串就可以转换为一个数字串，冒泡排序即可
#include "bits/stdc++.h"
using namespace std;
vector<int> arr(100);
vector<int> ans;
int cnt;
void bubbleSort(vector<int> &arr, int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素位置
cnt++;
ans.push_back(j + 1);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
return;
}
}
}
signed main(){
int n;
string s1, s2;
cin >> n;
cin >> s1 >> s2;
map<char, int> mp;
for(int i = 0; i < n; i++) mp[s2[i]] = i;
for(int i = 0; i < n; i++) {
if (mp.find(s1[i]) == mp.end()) {
// 如果 s1[i] 不在 s2 中出现
cout << -1;
return 0;
}
arr[i] = (mp[s1[i]]);
}
bubbleSort(arr, n);
cout << cnt << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
}
如果有相同的字符则不能这么映射了，因为后一个字符会把前一个相同的字符的映射给覆盖掉，所以把mp.first的类型改成queue来维护相同字母的序号即可
#include "bits/stdc++.h"
using namespace std;
vector<int> arr(100);
vector<int> ans;
int cnt;
void bubbleSort(vector<int> &arr, int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素位置
cnt++;
ans.push_back(j + 1);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
return;
}
}
}
signed main(){
int n;
string s1, s2;
cin >> n;
cin >> s1 >> s2;
//判断是否可以排序成一样的，只要判断两个字符串中每个字母的个数是否分别相等即可
int ok[30] = {0};
for(int i = 0;i < n;i++) {
ok[s1[i] - 96]++;
ok[s2[i] - 96]--;
}
for(int i = 1;i <= 26;i++) {
if(ok[i] != 0) {
cout<<-1;
return 0;
}
}
map<char, queue<int>> mp;
for(int i = 0; i < n; i++) mp[s2[i]].push(i);
for(int i = 0; i < n; i++) {
// if (mp.find(s1[i]) == mp.end()) {
// // 如果 s1[i] 不在 s2 中出现
// cout << -1;
// return 0;
// }//由于可能存在多个相同的字母，例如，s2中有两个a，而s1中只有一个，这么写检测不出来
arr[i] = mp[s1[i]].front();
mp[s1[i]].pop();
}
bubbleSort(arr, n);
cout << cnt << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
}
*C. Songs Compression
Ivan有n首歌,第i首歌原始大小为ai,压缩后为bi。他有一个容量为m的U盘。
他想把所有歌复制到U盘中,可以选择任意歌曲压缩,使得总大小不超过m。
求最少需要压缩的歌曲数,如果无法完成则输出-1。
#include<bits/stdc++.h>
using namespace std;
#define int long long
// 定义长长整型便于处理大数
int n, m, t1, t2;
// n:歌曲数 m:U盘容量
// t1:所有歌曲压缩后大小总和 t2:所有歌曲原始大小总和
vector<pair<int, int>> t;
// t数组存储每首歌的(原始大小,压缩后大小)
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first - a.second > b.first - b.second;
}
// cmp函数用于排序,按压缩效果从大到小排序
signed main() {
cin >> n >> m;
t.resize(n);
for(int i = 0; i < n; i++){
cin >> t[i].first >> t[i].second;
t1 += t[i].second;
t2 += t[i].first;
}
// 读入输入,计算t1和t2
if(t1 > m){
cout << -1;
return 0;
}
// 判断压缩后是否能装下,不能则输出-1
sort(t.begin(), t.end(), cmp);
// 排序
for(int i = 0; i < n; i++){
if(t2 <= m) {
cout << i;
return 0;
}
t2 -= t[i].first - t[i].second;
}
// 贪心算法,从效果最大的开始压缩,直到容量满足
cout << n;
return 0;
}