SDNU_ACM_ICPC_2022_Weekly_Practice_1rd「个人赛」

A - A Recursive Function

题目描述：

定义一个函数f(x)

• f(0) = 1
• f(x) = x*f(x-1)

输入n,输出f(n)

思路：

诈骗题，其实就是输出n的阶乘,不过直接按照题意模拟递归也行

注意数据范围不会爆longlong，所以用int就行

//循环版
#include 
using namespace std;
int n;
int main(){cin >> n;int ans = 1;for(int i = 1; i <= n; ++i){ans *= i;}cout << ans << endl;return 0;
}

//递归版
#include 
using namespace std;
int n;
int f(int x){if(!x)return 1;else return x*f(x-1);
}
int main(){cin >> n;cout << f(n) << endl;return 0;
}

B - Broken Rounding

题目描述：

给你一个数字n，要对数字n的后k位进行k次四舍五入操作，从低位开始操作，每次四舍五入后都要用得到的结果去替换n，即保证每次四舍五入的操作都是在上一次的基础上进行的

例如：

n=2048, k = 2

对后两位数字进行四舍五入，先四舍五入第一位8，显然应该四舍五入为10，要进一位，即n=2050,再四舍五入第二位5,显然还会进位，即2100

思路：

数据范围比较小，x不会超过1e15，所以可以用longlong读入

这个题的考点是如何提取出数字n的从后数的第i位数字

我们可以利用对10的幂次方的除法和取模操作完成

比如n=1234567，我们要提取从后数的第3位，只需要计算出(n102)(\frac{n}{10^2})(102n​)后对10取模即可得到

即提取n从后数的第i位，我们可以直接用 (n/10^i-1)%10

#include 
using namespace std;
typedef long long ll;
ll n, k;
int main(){cin >> n >> k;ll mul = 1;//记录10的i-1次方for(int i = 1; i <= k; ++i){int x = (n / mul) %10;//当前第i位是x，即有x个10的i-1次方if(x >= 5){//如果大于等5，则需要进位，即n加上10-x个muln += (10-x)*mul;}else n -= x*mul;//小于等于4，则需要将第i位变成0，即n减去x个mulmul *= 10;}cout << n << endl;return 0;
}

C - (K+1)-th Largest Number

题目描述：

给定一个长度为n的数组，输出n个数字，对于第i次输出，我们需要计算出存在多少个j，满足a[1]-a[n]中严格大于a[j]的不同的数字的数量为i

思路：

题意比较晦涩难懂，多读读研究研究

我们可以统计出来对于每个a[i]存在多少个数字严格大于它，计作num，然后用一个数组ans记录每个num的数量

所以重要的是统计出数组中大于a[i]的数字的数量

一种方法是去排序然后去干一些奇怪的操作去统计

还有就是可以直接用map或者set或者去重函数去重后，从小到大遍历，用容器大小减去当前数子在去重容器中的下标，就能知道大于这个数字的不同的数字的数量，由于a[i]的范围是1e9，所以我们得用map来记录对应数字的num

然后再遍历一次数组，开一个ans数组去记录答案就行

#include 
using namespace std;#define MAX 300000 + 50int n, m, k, x;
int tr[MAX];
int ans[MAX];int main(){cin >> n;mapmp, num;for(int i = 1; i <= n; ++i){cin >> tr[i];++mp[tr[i]];//去重}int id = 0;for(auto [x, y] : mp){//用auto来遍历map++id;//记录比他小的数字的数量num[x] = (int)mp.size() - id;//容器大小-比他小的数字的数量就能计算出大于它的不同的数字的数量}for(int i = 1; i <= n; ++i){++ans[num[tr[i]]];//计算答案}for(int i = 0; i < n; ++i){cout << ans[i] << endl;}return 0;
}

D - LRUD Instructions

题目描述：

给定一个n*m的矩形，其中有k个障碍物，你的起点为(x, y)，现在给你Q次操作， 每次操作都是进行一个固定方向固定距离的移动，如果前方遇到障碍物或边界则无法往前移动，每走一次输出当前位置

思路：

防AK用的…

数据范围很大，需要进行离散化，然后大模拟，通过二分来走路

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair  pii;#define MAX 500000 + 50
ll n, m, k, x, y, p;
vectorar[MAX], br[MAX];
struct ran{ll x, y;
}tr[MAX];
bool cmp1(ran a, ran b){if(a.x != b.x)return a.x < b.x;else return a.y < b.y;
}
bool cmp2(ran a, ran b){if(a.y != b.y)return a.y < b.y;else return a.x < b.x;
}void work(){cin >> n >> m >> x >> y;cin >> k;for(int i = 1; i <= k; ++i){cin >> tr[i].x >> tr[i].y;}sort(tr + 1, tr + 1 + k, cmp1);ll h=0, l=0;maphang, lie;for(int i = 1; i <= k;){hang[tr[i].x] = ++h;while(i + 1 <= k && tr[i+1].x==tr[i].x){ar[h].push_back(tr[i].y);++i;}ar[h].push_back(tr[i].y);++i;}sort(tr+1, tr+1+k, cmp2);for(int i = 1; i <= k;){lie[tr[i].y] = ++l;while(i+1<=k&&tr[i+1].y==tr[i].y){br[l].push_back(tr[i].x);++i;}br[l].push_back(tr[i].x);++i;}cin >> p;char op;int len;while(p--){cin >> op >> len;if(op == 'L'){if(!hang.count(x)){y = max(1ll, y-len);}else{ll id = hang[x];if(ar[id].front() > y){y = max(1ll, y - len);}else{ll pos = lower_bound(ar[id].begin(), ar[id].end(), y) - ar[id].begin()-1;y = max(ar[id][pos]+1, y-len);}}cout << x << ' ' << y << endl;}else if(op == 'U'){if(!lie.count(y)){x = max(1ll, x - len);}else{ll id = lie[y];if(br[id].front() > x){x = max(1ll, x - len);}else{ll pos = lower_bound(br[id].begin(), br[id].end(), x) - br[id].begin()-1;x = max(br[id][pos]+1, x - len);}}cout << x << ' ' << y << endl;}else if(op == 'R'){if(!hang.count(x)){y = min(m, y+len);}else{ll id = hang[x];if(ar[id].back() < y){y = min(m, y + len);}else{ll pos = lower_bound(ar[id].begin(), ar[id].end(), y) - ar[id].begin();y = min(ar[id][pos]-1, y+len);}}cout << x << ' ' << y << endl;}else{if(!lie.count(y)){x = min(n, x + len);}else{ll id = lie[y];if(br[id].back() < x){x = min(n, x + len);}else{ll pos = lower_bound(br[id].begin(), br[id].end(), x) - br[id].begin();x = min(br[id][pos]-1, x+len);}}cout << x << ' ' << y << endl;}}
}int main(){io;work();return 0;
}

E - Integer Sum

题目描述：

输入n个数字，输出n个数字的和

思路：

水题

#include 
using namespace std;int n, x, sum;int main(){cin >> n;for(int i = 1; i <= n; ++i){cin >> x;sum += x;}cout << sum << endl;return 0;
}

F - Everyone is Friends

题目描述：

n个人，m场派对，第i场派对都有k[i]个人参加，并给出是哪些人参加了第i场派对，问对任意的两个人，都满足二者参加过至少一场相同的派对，则输出Yes，否则输出No

思路：

数据范围很小，我们可以直接暴力

开一个二维数组tr[x][y]，如果是1则表示x和y至少同时参加过一场派对，是0则没有

对于每场派对，我们用两个for循环去暴力枚举，然后去更新tr[x][y]就行

#include 
using namespace std;int n, m, k, x;
bool tr[105][105];int main(){cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> k;vectorv;for(int j = 1; j <= k; ++j){cin >> x;v.push_back(x);}for(int j = 0; j < v.size(); ++j){for(int p = 0; p < v.size(); ++p){tr[v[j]][v[p]] = tr[v[p]][v[j]] = 1;}}}bool ans = 1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j){if(!tr[i][j]){ans = 0;}}}if(ans)cout << "Yes\n";else cout << "No\n";return 0;
}

G - Max Even

题目描述：

给n个数字，让你任意挑两个不同的数字，使得数字之和最大，问最大可以是多少

思路：

奇偶分开，奇+奇=偶 偶+偶=偶，所以找大最大的两个奇数和最大的两个偶数求最大值就行

我们把奇数和偶数都分开存，然后排个序，取最大的俩奇数和最大的俩偶数，如果都不能取，就是-1

#include 
using namespace std;int n, m, k;
int x;int main(){cin >> n;vectorodd,even;for(int i = 1; i <= n; ++i){cin >> x;if(x % 2)odd.push_back(x);else even.push_back(x);}sort(odd.begin(), odd.end());sort(even.begin(), even.end());int ans = -1;if(odd.size() > 1)ans = max(ans, odd.back() + odd[(int)odd.size() - 2]);if(even.size() > 1)ans = max(ans, even.back() + even[(int)even.size() - 2]);cout << ans << endl;return 0;
}

H - 484558

题目描述：

给你一个十进制数字，将其转换成16进制

思路：

用printf("%02X",n)即可

具体用法可以自行百度

#include 
using namespace std;int n;int main(){scanf("%d", &n);printf("%02X\n", n);return 0;
}

I - Maintain Multiple Sequences

题目描述：

n个序列，m次询问

第i个序列的长度为k[i]，并给出每个序列的元素

m次询问，每次询问给出两个元素s, t,问第s个序列的第t个数字是什么

思路：

很显然要用vector来存，输出的时候注意vectro是从0开始放数字的，所以要输出的是v[s][t-1]

#include 
using namespace std;#define MAX 300050
int n, m, k, x;int main(){cin >> n >> m;vectorv[MAX];for(int i = 1; i <= n; ++i){cin >> k;while(k--){cin >> x;v[i].push_back(x);}}while(m--){cin >> k >> x;cout << v[k][x-1] << endl;}return 0;
}

J - Manga

题目描述：

给定一个数组，你可以对数组进行若干次操作，每次操作可以删除两个数字并添加一个数，求1 2 3… 连续自然数的最后一个值最大可以是多少

思路：

显然答案不会超过n，所以大于n的数字肯定不会成为答案

我们开一个变量num记录没被用的数字的个数

从1开始遍历到n，如果i这个数字出现过了，那说明我们不用去用两个数字去凑，num-=1就行，否则我们需要最后面的两个数字去凑，也就是num-=2，直到num=0或者需要用两个数字去凑的时候num<2就停止了，输出这个时候的i

#include 
using namespace std;#define MAX 300050
int n, x;
bool tr[MAX];int main(){cin >> n;for(int i = 1; i <= n; ++i){cin >> x;if(x<=n)tr[x] = 1;}int num = n;int ans = 0;for(int i = 1; i <= n; ++i){if(num == 0)break;if(tr[i])--num;else{if(num >= 2)num -= 2;else break;}ans = i;}cout << ans << endl;return 0;
}

K - 1-2-4 Test

题目描述：

三场考试，分数分别是1、2、4，现在知道A和B的三场总分数分别是多少，现在C只能通过A或B能通过的考试，而不能通过A和B都不能通过的考试，问C的分数

思路：

其实就是求A|B

简单的位运算

#include 
using namespace std;int n, m;int main(){cin >> n >> m;cout << (n|m) << endl;return 0;
}

L - Hammer

题目描述：

一维直线，你现在在0，目标地点为X, Y处有一个门，Z处有门的钥匙，问你到达X的最短路程是多少，如果不能到达，则输出-1

思路：

简单的分类讨论

如果x=0，直接输出0

如果x>0

• 如果门的位置y<0或者y>x，说明门不会对我们产生阻碍，直接输出x就行
• 否则
  • 如果钥匙z的位置在门y的右边，即z>y，我们想拿钥匙就得先开门，但是开不了门，所以就无法到达,输出-1
  • 如果钥匙z>0，也就是在起点和门之间，那就从起点出发拿了钥匙开了门直接到终点，输出x就行
  • 如果钥匙z<0，也就是要从起点往反方向走，先拿钥匙，在开门再到终点，那就输出-z*2+x

x<0的情况也类似，请自行讨论

#include 
using namespace std;int x, y, z;int main(){cin >> x >> y >> z;if(x == 0){cout << 0 << endl;}else if(x > 0){if(y < 0 || y > x)cout << x << endl;else {if(z > y)cout << -1 << endl;else{if(z > 0)cout << x << endl;else cout << -z*2 + x << endl;}}}else{if(y < x || y > 0)cout << -x << endl;else{if(z < y)cout << -1 << endl;else {if(z > 0)cout << 2*z - x << endl;else cout << -x << endl;}}}return 0;
}

M - Simple path

题目描述：

给你一棵树，给定起点和和终点，输出从起点到终点的路径

思路：

防AK题，用dfs或者bfs都行

#include 
using namespace std;#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair  pii;#define MAX 500000 + 50
int n, m, k, x, y;int tot;
int head[MAX];
struct ran{int to, nex;
}tr[MAX];
inline void add(int u, int v){tr[++tot].to = v;tr[tot].nex = head[u];head[u] = tot;
}int fa[MAX];
void dfs(int u, int ff){if(u == x){int p = x;while(p != y){cout << p << ' ';p = fa[p];}cout << y << endl;exit(0);}for(int i = head[u];i;i = tr[i].nex){int v = tr[i].to;if(ff == v)continue;fa[v] = u;dfs(v, u);}
}void work(){cin >> n >> x >> y;for(int i = 1; i < n; ++i){cin >> m >> k;add(m, k);add(k, m);}dfs(y, -1);}int main(){io;work();return 0;
}