SDNU_ACM_ICPC_2022_Weekly_Practice_1rd「个人赛」题解
admin
|
|
344
|
个人训练赛

2346 字
|
31 分钟

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 <bits/stdc++.h>
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 <bits/stdc++.h>
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位，只需要计算出后对10取模即可得到

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

#include <bits/stdc++.h>
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个mul
            n += (10-x)*mul;
        }
        else n -= x*mul;//小于等于4，则需要将第i位变成0，即n减去x个mul
        mul *= 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 <bits/stdc++.h>
using namespace std;

#define MAX 300000 + 50

int n, m, k, x;
int tr[MAX];
int ans[MAX];

int main(){
    cin >> n;
    map<int, int>mp, 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 <bits/stdc++.h>
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 <int,int> pii;

#define MAX 500000 + 50
ll n, m, k, x, y, p;
vector<ll>ar[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;
    map<ll, ll>hang, 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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
        vector<int>v;
        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 <bits/stdc++.h>
using namespace std;

int n, m, k;
int x;

int main(){
    cin >> n;
    vector<int>odd,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 <bits/stdc++.h>
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 <bits/stdc++.h>
using namespace std;

#define MAX 300050
int n, m, k, x;

int main(){
    cin >> n >> m;
    vector<int>v[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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <int,int> 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;
}

 

博客内容均系原创，未经允许严禁转载！
个人赛
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
「个人赛」SDNU_ACM_ICPC_2021_Winter_Practice_1st

							
							

							
「个人赛」SDNU_ACM_ICPC_2021_Winter_Practice_4th

							
							

							
「个人赛」SDNU_ACM_ICPC_2021_Winter_Practice_2nd

							
							

							
「个人赛」2020-2021年度第二届全国大学生算法设计与编程挑战赛（冬季赛）

							
							

							
「个人赛」SDNU_ACM_ICPC_2021_Winter_Practice_7th