首页 > 编程语言 >2022合肥学院ACM程序设计大赛-正式赛题解

2022合肥学院ACM程序设计大赛-正式赛题解

时间:2022-12-06 20:47:11浏览次数:91  
标签:return int 题解 mid ACM long 2022 include id

A.孤独摇滚

计算下一个回文年,输出即可。

#include<stdio.h>
int check(int x)
{
    if(x/1000==x%10&&x/100%10==x%100/10)
        return 1;
    return 0;
}
int main()
{
    for(int i=2022;;i++)
        if(check(i))
        {
            printf("%d",i);
            break;
        }
    return 0;
}

B.苦痛之路

构造方式不唯一,满足题意即可,给下面给出一种构造方法。

#include<stdio.h>
long long  a,b,c;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    printf("%lld %lld %lld",a+b+c,b+c,c);
    return 0;
}

C.浅浅的下个五子棋

枚举棋盘的每个位置,检查一下是否存在4子即可。注意要判断一下是否会访问越界。

成四子的方法无非就是横着,竖着,正对角线,反对角线

#include<stdio.h>
int a[510][510], n, cnt = 0;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] == 1 && a[i + 1][j + 1] == 1 && a[i + 2][j + 2] == 1 && a[i + 3][j + 3] == 1)
            {
                cnt ++;
                break;
            }
            if (a[i][j] == 1 && a[i][j + 1] == 1 && a[i][j + 2] == 1 && a[i][j + 3] == 1)
            {
                cnt ++;
                break;
            }
            if (a[i][j] == 1 && a[i + 1][j] == 1 && a[i + 2][j] == 1 && a[i + 3][j] == 1)
            {
                cnt ++;
                break;
            }
            if (i - 3 >= 1 && a[i][j] == 1 && a[i - 1][j + 1] == 1 && a[i - 2][j + 2] == 1 && a[i - 3][j + 3] == 1)
            {
                cnt ++;
                break;
            }
        }
    if (cnt == 0)
        printf("123456");
    else
        printf("114514");
    return 0;
}

D.方格移动

题解传送门:https://zhuanlan.zhihu.com/p/585838659?utm_campaign=&utm_medium=social&utm_oi=1491769876256096256&utm_psn=1583199367946731520&utm_source=qq

E.冠军小智的宝可梦盒子

小智终于拿冠军了,太不容易了。从宝可梦动画播出到现在已经25年了,终于看到他拿了冠军了!

虽然他冠军拿的十分困难,但是这题一点都不难,你用map,用vector,用啥都可以。

我这边给一个不用标准库容器的版本,思路是将二维转一维。因为固定的二维可能会炸。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m,q;
int a[N];
int &my_get(int i,int j)
{
    return a[(i-1)*m+j];
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            cin>>my_get(i,j);
    cin>>q;
    while (q--)
    {
        int x,y;
        cin>>x>>y;
        if (my_get(x,y)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

你问函数前面为什么带一个&,这个吧,emmmmmmmm,详见C++的引用。

F.完美的数

二进制数中k + 1个连续的 1 可以由 \(2^{k} - 1\)得到

二进制数中k个连续的0可以由 \(2^{k - 1}\)得到

两者相乘即可得到二进制数中存在连续k + 1个1和连续k个0

可以得到公式$(2^{k} - 1) * 2^{k - 1} $

当然也可以暴力求解

在一个二进制数后面填1相当于对这个数乘2 再加 1

在一个二进制数后面填0相当于对这个数乘2

下面是第一种方法的代码

// c

#include <stdio.h>

int q[32]; //存 2^k
int main()
{
    //求出2^i
    q[0] = 1;
    for(int i = 1; i <= 31; i ++)
        q[i] = q[i - 1] * 2;
    
    int ans = 0;

    int n ;
    scanf("%d", &n);
    for(int k = 1; ; k ++)
    {
        if((q[k] - 1) * q[k - 1] <= n)
            ans = (q[k] - 1) * q[k - 1];
        else
            break;
    }

    printf("%d\n", ans);
}

第二种方法

// c
#include <stdio.h>
int main()
{
    int ans = 0;
    int n;
    scanf("%d", &n);
    for(int k = 0; ; k ++)
    {
        int res = 0;
        //往0后面加(k + 1)个1
        for(int i = 1; i <= k + 1; i ++)
            res = res * 2 + 1;
        
        //往(k+1)个1后面加k个0
        for(int i = 1; i <= k; i ++)
            res = res * 2;
        
        //如果得到的值小于等于n则更新答案
        if(res <= n)
            ans = res;
        else break;
    }

    printf("%d\n", ans);
}

G. 国足怎么能进世界杯?

签到题

读入上底a, 下底b, 高h

由梯形面积公式 (a + b) * h / 2

可以得到答案

代码如下

// C;
#include <stdio.h>

int main()
{
    int a, b, h;
    scanf("%d%d%d", &a, &b, &h);
    
    printf("%d\n", (a + b) * h / 2);

    return 0;
}

H.我真的不是小黑子

我真的不是小黑子,真的!

没写C++的标准程序,这里用一下新生校赛第一的代码

#include<bits/stdc++.h>
using namespace std;
int p[1000];
int main()
{
	long long a,b;
	cin>>a>>b;
	long long sum,y,cnt=0,j;
	sum=a*b;
	for(y=sum;y>0;cnt++)
        y/=10;
	long long ans,l=1;
	for(j=0;j<cnt;j++)
    {
		p[j]=sum%10;
		sum/=10;
	}
	for(int u=cnt-1;u>=0;u--)
    {
		cout<<p[u];
		if(p[u-1]==0)
            cout<<endl;
		else if(p[u]==0)
            cout<<endl;
	}
	return 0;
}

然后附加一份Python的

A, B = map(int,input().split())
S = str(A * B)
print(S.replace("0", "\n0\n").replace("0\n\n0", "0\n0").strip())

I.同行之路

观察可以发现,想让两个分式相等,最多需要2次操作,分类讨论即可。
对于\(\frac{a}{b},\frac{c}{d}\):
如果\(a*d==b*c\),需要0次操作。
如果\((a*d)\%(b*c)==0\),需要1次操作。
如果\((a*d)\%(b*c)!=0\),需要2次操作。
此外还需要特判一下\(b*c\)是否为0。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long num1 = a * d;
    long long num2 = b * c;
    if (num1 < num2)
        swap(num1, num2);
    if (num1 == num2)
        cout << "0" << endl;
    else
    {
        if (num2 == 0)
            cout << "1" << endl;
        else
        {
            if (num1 % num2 == 0)
                cout << "1" << endl;
            else
                cout << "2" << endl;
        }
    }
    return 0;
}

J.凝冰渡海真君

(转载某位大佬的题解,A题)https://zhuanlan.zhihu.com/p/561604699

K.重生之我在昨日圆车

因为数组的每个数都大于0,所以保证前缀和没有相同的值,可以用map来记录前缀和的值是否存在。因此,题目转化为,是否存在前缀和\(x\),使得\(x+p,x+p+q,x+p+q+r\)都存在。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, p, q, r;
int a[N];
ll sum[N];
map<ll, bool> mp;
void solve()
{
    mp[0] = true;
    cin >> n >> p >> q >> r;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        mp[sum[i]] = true;
    }
    for (int i = 1; i <= n; i++)
        if (sum[i] >= p)
        {
            if (mp[sum[i] - p] && mp[sum[i] + q] && mp[sum[i] + q + r])
            {
                cout << "Yes" << endl;
                return;
            }
        }
    cout << "No" << endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

L.合大校园锦标赛

首先通过二分答案求出每个校区之间的最小距离,然后对于每个提问和最小距离进行对比

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1001;
int n,k,q;
int x[N],y[N],p[N],idx = 0;
int st[N];
struct E{
    int a,b;
    double v;
    inline bool operator< (const E& e) const {
        return this->v < e.v;
    }
} e[(N+1)*N/2];

int find(int x)
{
    return (p[x]==x?p[x]:p[x]=find(p[x]));
}
//求取两点距离
double getdis(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void build(int a,int b)
{
    e[idx].a = a;
    e[idx].b = b;
    e[idx++].v = getdis(a,b);
}
int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;++i) cin>>x[i]>>y[i];
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            build(i,j);
    sort(e,e+idx);
    double l = 0,r = e[idx-1].v;
    //二分答案求出最短距离
    while (r-l>1e-6)
    {
        double mid = (l+r) / 2;
        for (int i=0;i<=n;++i) p[i] = i;
        for (int i=0;i<idx;++i)
        {
            int a = e[i].a,b = e[i].b;
            double v = e[i].v;
            if (v>mid) break;
            a = find(a),b = find(b);
            if (a!=b)
            {
                p[a] = b;
            }
        }
        memset(st,0,sizeof st);
        int cnt = 0;
        for (int i=1;i<=n;++i)
            if (!st[find(i)]) st[find(i)]=true,cnt ++;
        if (cnt >= k)
            l = mid;
        else
            r = mid;
    }
    cin>>q;
    for (int i=1;i<=q;++i)
    {
        int a,b;
        cin>>a>>b;
        if (getdis(a,b)<=l) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

M.大慈树王的树

本题涉及高级数据结构——线段树,新生看看就行()。

题意:给你一棵树,每个点都有一个权值,将询问q次,每次询问将x点的权值改为y,或询问m个点,需要输出这m个点子树中点的并集的积

分析:考虑dfs序,用dfs序的开始和结尾表示每个点代表的区间,用线段树维护每个区间的值的积,只需单修区查即可,每次询问m个点将区间记下来,跑一遍区间合并,然后将求合并后的区间的积即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10, M = 4010,mod = 1e9+7, b1 = 1037, b2 = 1111, p1 = 9999971, p2 = 9999973,inf=1<<30;
const double eps = 1e-10;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<int,ll> PIL;
struct Node{
	ll val;
} seg[8*N];
int n,q;
ll w[N];
vector<int> e[N];
int stk[N],tot;
int st[N],ed[N];
vector<PII> tmp,res;

void merge(){
	res.clear();
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	int sta=-2e9,end=-2e9;
	for(auto [i,j] : tmp){
		if(sta == -2e9){
			sta = i;
			end = j;
			continue;
		}
		if(i > end){
			res.push_back({sta,end});
			sta = i;
			end = j;
		}else{
			end = max(j,end);
		}
	}
	res.push_back({sta,end});
}

void dfs(int u,int f){
	st[u] = ++tot;
	stk[tot] = u;
	for(auto v : e[u]) {
		if(v == f) continue;
		dfs(v,u);
	}
	ed[u] = tot;
}

void pushup(int id){
	seg[id].val = seg[2*id].val*seg[2*id+1].val%mod;
}

void build(int id,int l,int r){
	if(l == r){
		seg[id].val = w[stk[l]];
		return ;
	}
	int mid = l + r >> 1;
	build(2*id,l,mid);
	build(2*id+1,mid+1,r);
	pushup(id);
}

void change(int id,int l,int r,int p,ll x){
	if(l == r && l == p){
		seg[id].val = x;
		return ;
	}
	int mid = l + r >> 1;
	if(mid>=p) change(2*id,l,mid,p,x);
	else change(2*id+1,mid+1,r,p,x);
	pushup(id);
}

ll query(int id,int l,int r,int ql,int qr){
	if(l == ql && r == qr){
		return seg[id].val;
	}
	int mid = l + r >> 1;
	if(mid>=qr) return query(2*id,l,mid,ql,qr);
	else if(mid<ql) return query(2*id+1,mid+1,r,ql,qr);
	else{
		return query(2*id,l,mid,ql,mid)*query(2*id+1,mid+1,r,mid+1,qr)%mod;
	}
}

void solve(){
	scanf("%d%d",&n,&q);
	for(int i = 1; i <= n; i ++) e[i].clear();
	tot = 0;
	for(int i = 1; i < n; i ++) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	for(int i = 1; i <= n; i ++) scanf("%lld",&w[i]);
	build(1,1,n);
	while(q --){
		ll op,x,y;
		scanf("%lld%lld",&op,&x);
		if(op == 1){
			scanf("%lld",&y);
			change(1,1,n,st[x],y);
		}else{
			tmp.clear();
			for(int i = 1; i <= x; i ++){
				int xx;
				scanf("%d",&xx);
				tmp.push_back({st[xx],ed[xx]});
			}
			merge();
			ll ans = 1;
			for(auto [i,j] : res){
				ans = ans*query(1,1,n,i,j)%mod;
			}
			printf("%lld\n",ans);
		}
	}
}

int main()
{
		solve();

    return 0;
}

标签:return,int,题解,mid,ACM,long,2022,include,id
From: https://www.cnblogs.com/Chesedss/p/16960443.html

相关文章