2022-11-29 22:08 已编辑大连大学 C++ 发布于辽宁

关注

题解 | 大连大学2022年11月程序设计竞赛（同步赛）题解

地层

https://ac.nowcoder.com/acm/contest/45599/A

难度预测

check-in: A J B

easy: N C

medium-easy: H I

medium: D E

medium-hard: F

hard: G K

very-hard: L M

Problem A 地层

签到题

按照题面输出即可，注意double型数据和int型数据的比较以及换行字符。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f

int main() {
    int m,n;
    cin>>m>>n;
    int h;
    if(m==1) h=1200;
    else if(m==2) h=1800;
    else h=2400;
    while(n--){
        int a;
        cin>>a;
        if(a<h/10) cout<<"underworld"<<endl;
        else if(a<h/10*7) cout<<"cavern"<<endl;
        else if(a<h/10*8) cout<<"underground"<<endl;
        else if(a<h/10*9) cout<<"surface"<<endl;
        else  cout<<"space"<<endl;
	}
	return 0;
}

Problem B v我50

签到题

按照题意输出即可。

#include <iostream>
#define ll long long
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        string t="kfccrazythursdayvme50";
        int j=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==t[j]||s[i]==t[j]-32){
                j++;
            }
            if(j==t.size()) break;
        }
        if(j==t.size()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
	}
	return 0;
}

Problem C 2048

暴力题

暴力搜索，不过注意判断边界条件。

#include<bits/stdc++.h>
using namespace std ;
int a[1005][1005] ;
void solve()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;j++) 
            scanf("%d",&a[i][j]) ;
    bool flag=0 ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;j++)
            flag|=(i>1&&a[i-1][j]==a[i][j])|(j>1&&a[i][j-1]==a[i][j]) ;
    flag?puts("YES"):puts("NO") ;
}
int main()
{
    int T ; scanf("%d",&T) ;
    while(T--) solve() ;
    return 0 ;
}

Problem D 循环数组

从右往左找到第一个小于前一个数且大于等于后一个数的数字，并记录下标。再从该下标开始依次判断每个数是否小于等于它的后面一个数即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    a[n]=INT_MAX;
    int p=0;
    for(int i=n-1;i>0;--i){
        if(a[i]<=a[i+1]&&a[i]<a[i-1])
            p=i;
    }
    for(int i=1;i<n;++i){
        if(a[(p+i-1)%n]>a[(p+i)%n]){
            cout<<-1<<endl;
            return ;
        }
    }
    for(int i=0;i<n;++i)cout<<a[(p+i)%n]<<' ';cout<<endl;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
        solve();
}

Problem E 买瓜

数学题

按照题意要求计算即可，注意为0的情况

ll a[N];
int main()
{
    ll n;
    scanf("%lld",&n);
    ll ans=0;
    bool bl=1;
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        if(100-x>=50) ans+=(100-x)-x,bl=0;
    }
    if(bl) printf("What's up\n");
    else printf("%lld\n",ans);
    return 0;
}

Problem F 我心落花一样飘落下来

思维题

根据题意，排序后，遍历一遍即可。本题没卡掉冒泡排序，所以可以不用快排过。

#include <bits/stdc++.h>
using namespace std;
#define N 1005000
#define ll long long
ll a[N];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll h,n;
        scanf("%lld%lld",&h,&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        ll ans=0;
        ll times=0;
        for(int i=1;i<=n;i++)
        {
            if(h<=a[i]-times)
            {
                ans++;
                times++;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Problem G 二维码

模拟题

模拟四种(其实只有三种)情况的旋转即可

int a[1005][1005];
struct node
{
    int x,y;
}s[4];
bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        int qr=0;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]==0) s[cnt++]={i,j};
            }
        }
        int x_max=-1,y_max=-1,x_max_cnt=0,y_max_cnt=0;
        int x_min=999999,y_min=999999,x_min_cnt=0,y_min_cnt=0;
        for(int i=0;i<3;i++)
        {
            x_max=max(x_max,s[i].x);
            x_min=min(x_min,s[i].x);
            y_max=max(y_max,s[i].y);
            y_min=min(y_min,s[i].y);
        }
        for(int i=0;i<3;i++)
        {
            if(s[i].x==x_max) x_max_cnt++;
            else x_min_cnt++;
            if(s[i].y==y_max) y_max_cnt++;
            else y_min_cnt++;
        }
        int op=0;
        if(x_max_cnt==1) op+=2;
        if(y_max_cnt==1) op+=1;
        if(op==0)
        {
            for(int i=x_max;i>=x_min;i--)
            {
                for(int j=y_max;j>=y_min;j--)
                {
                    printf("%d ",a[i][j]);
                }printf("\n");
            }
        }
        else if(op==1)
        {
            for(int i=y_min;i<=y_max;i++)
            {
                for(int j=x_max;j>=x_min;j--)
                {
                    printf("%d ",a[j][i]);
                }printf("\n");
            }
        }
        else if(op==2)
        {
            for(int i=y_max;i>=y_min;i--)
            {
                for(int j=x_min;j<=x_max;j++)
                {
                    printf("%d ",a[j][i]);
                }printf("\n");
            }
        }
        else
        {
            for(int i=x_min;i<=x_max;i++)
            {
                for(int j=y_min;j<=y_max;j++)
                {
                    printf("%d ",a[i][j]);
                }printf("\n");
            }
        }
    }
    return 0;
}

另一种解法

#include<bits/stdc++.h>
using namespace std ;
const int N = 1005 ;
int n ;
int x[3],y[3] ;
int a[N][N],b[N][N] ;
bool check()
{
	int cnt=0 ;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;j++)
			if(a[i][j]==0) x[cnt]=i,y[cnt]=j,cnt++ ;
	if(x[0]==x[1]&&y[0]==y[2]) return 1 ;
	return 0 ;
}
void rotate()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;j++)
			b[j][n-i+1]=a[i][j] ;
	memcpy(a,b,sizeof(a)) ;
}
void solve()
{
	scanf("%d",&n) ;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]) ;
	while(!check()) rotate() ;
	for(int i=x[0];i<=x[2];++i)
	{
		for(int j=y[0];j<=y[1];j++)
			printf("%d ",a[i][j]) ;
		printf("\n") ;
	}
}
int main()
{
	int T ; scanf("%d",&T) ;
	while(T--) solve() ;	
	return 0 ;
}

Problem H Win or lose

根据题意可知，我们只要找到最右边的子串"shu"的's'的下标和最左边的子串"ying"的'g'的下标，然后比较两个下标即可。注意，题中需要特判"ying"或"shu"没有出现的情况。

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int len=s.size();
        int gind=0;
        int sind=len-1;
        for(int i=0;i<len;++i){
            if(i+3<len&&s[i]=='y'&&s[i+1]=='i'&&s[i+2]=='n'&&s[i+3]=='g'){
                gind=i+3;
            }
        }
        for(int i=len-3;i>=0;--i){
            if(i+2<len&&s[i]=='s'&&s[i+1]=='h'&&s[i+2]=='u'){
                sind=i;
            }
        }
        if(gind<sind&&gind!=0&&sind!=len-1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}

Problem I 质数矩阵

通过观察发现，除了2之外的任意两个质数相加都为大于2的偶数，即合数。所以需要使用2与某些质数（例如3）解出该题。

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
void init(){
    for(int i=1;i<=1000;++i){
        if(i%2){
            for(int j=1;j<=1000;++j){
                if(j%2) a[i][j]=2;
                else a[i][j]=3;
            }
        }
        else{
            for(int j=1;j<=1000;++j){
                if(j%2) a[i][j]=3;
                else a[i][j]=2;
            }
        }
    }
}
int main()
{
    init();
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

Problem J 比邻

由题意可知，只需要从左往右依次判断前一个与后一个字符是否相等计数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        int re=0;
        for(int i=1;i<s.size();i++){
            if(s[i]==s[i-1]) re++;
        }
        cout<<re<<endl;
    }
    return 0;
}

Problem K 分数合一

数学题

由题意可知，我们需要先约分，用gcd函数求最大公因数约分后，再用两层循环暴力判断相加是否为1即可。注意本题数字过大，不能采用交叉相乘的方法。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
typedef long long ll;
ll a[N];
ll b[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>b[i];
    for(int i=1;i<=n;++i){
        ll gcd=__gcd(a[i],b[i]);
        a[i]/=gcd;
        b[i]/=gcd;
    }
    ll ans=0;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(b[i]==b[j]&&a[i]+a[j]==b[i])
                ans++;
        }
    }
    cout<<ans<<endl;
}

另一份代码

ll a[N],b[N];
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
    {
        ll g=gcd(a[i],b[i]);
        a[i]/=g;
        b[i]/=g;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(b[i]==b[j]&&b[i]-a[i]==a[j]) ans++;
        }
    }
    printf("%lld\n",ans/2);
    return 0;
}

Problem L 钩锁

几何题

讨论好各种情况即可

int main()
{
    int t; cin>>t;
    while(t --)
    {
        int L1, L2, x1, y1, x2, y2, x3; cin>>L1>>L2>>x1>>y1>>x2>>y2>>x3;
        if(L1 < x3 - x1 || L2 < x3 - x2) cout<<"No"<<endl;
        else
        {
            double d = sqrt(L1 * L1 - (x3 - x1) * (x3 - x1));
            double u1 = d + y1, d1 = -d + y1;
            d = sqrt(L2 * L2 - (x3 - x2) * (x3 - x2));
            double u2 = d + y2, d2 = -d + y2;
            if(d1 > u2 || d2 > u1) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
    return 0;
}

Problem M XOR

模拟题

注意模拟这个过程就行，在有限情况下变不出奇数，说明为-1

ll a[N];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n,p;
        scanf("%lld%lld",&n,&p);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        ll l=p-1,r=p+1;
        if(l==0) l=n;
        if(r==n+1) r=1;
        if(a[p]==1)
        {
            printf("0\n");
            continue;
        }
        ll cnt=0;
        bool flag=0;
        while(1)
        {
            cnt++;
            if(a[l]^a[r])
            {
                break;
            }
            l--,r++;
            if(l==0) l=n;
            if(r==n+1) r=1;
            if(l==r)
            {
                flag=1;
                break;
            }
        }
        if(flag) printf("-1\n");
        else printf("%lld\n",cnt);
    }
    return 0;
}

Problem N 呼啸山庄

分类讨论。

当只有一个衣架时，无论如何都不能使所有的衣架都为稳定的。

当有除1之外的奇数个衣架时，除了最后的3个衣架需要2根线捆住，其余的n-3个衣架必定能拆成两两一对的衣架，每对衣架只消耗1根线。故总共消耗(n-3)/2+2=(n+1)/2根线。

当有偶数个衣架时，每两个衣架消耗一根线，故总共消耗n/2根线。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        if(n==1)cout<<-1<<endl;
        else cout<<(n+1)/2<<endl;
    }
    return 0;
}

//UPD 2022.11.29 M题题解有误，已修改