欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020ACM俱乐部后备营个人训练赛第七、八、九场

程序员文章站 2022-03-15 11:58:05
第七场B代码#includeint n,a[60][60],pos[60];char s[60][60];int main( ){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) { for(int j=1;j<=n-i+1;j++) {...

第七场

问题 B: 数字塔

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

简单的递推
例如:

a1 a2
a3

( a1 + a2 ) % 10 = a3
如果我们已知 a3 , a2 求 a1 怎么求
因为数字都是 0 - 9 的,所以 0 <=( a1 + a2 )<= 18
1、如果 a1 + a2 < 10 -> ( a1 + a2 ) % 10 = a1 + a2 = a3 -> a1 = a3 - a2
2、如果 a1 + a2 > 10 -> ( a1 + a2 ) % 10 = a1 + a2 - 10 = a3 -> a1 = 10 + a3 - a2
情况 1 里 a3 - a2 > 0, 情况 2 里 a3 - a2 < 0 ,所以我们根据这个特点可以推出 a1
同理可以推出整个金字塔( 从金字塔尖往上推 )

代码

#include<stdio.h>
int n,a[60][60],pos[60];
char s[60][60];
int main( )
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n-i+1;j++)
        {
            if(s[i][j]=='?') a[i][j]=-1;
            else
            {
                a[i][j]=s[i][j]-'0';
                pos[i]=j;
            }
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=pos[i]+1;j<=n-i+1;j++)
        {
            a[i][j]=a[i+1][j-1]-a[i][j-1];
            if(a[i][j]<0) a[i][j]=a[i][j]+10; 
        }
        for(int j=pos[i]-1;j>=1;j--)
        {
            a[i][j]=a[i+1][j]-a[i][j+1];
            if(a[i][j]<0) a[i][j]=a[i][j]+10; 
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n-i+1;j++)
            printf("%d",a[i][j]);
        puts("");
    }
    return 0;
}

问题 C: 路程

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

直接模拟整个走路的过程,记录整个路程和( sum )
假设一个点( x , y ) , 我们从这个点分别朝四个方向( 东南西北 - 右下左上 )走 m 步 , 那么走后的坐标为:
向东(右): ( x , y+m )
向南(下): ( x+m , y )
向西(左): ( x , y-m )
向北(上): ( x-m , y )
根据这个我们可以模拟求出超市的坐标( x2 , y2 ),将超市坐标与家的坐标(设置一个家的初始坐标,假设为 ( x1 , y1 ) )求直线距离:
2020ACM俱乐部后备营个人训练赛第七、八、九场
最后的答案就是 sum + |AB|

这个题有一个坑点就是字符输入的问题;
如果用 c++ 的 cin 那么没有啥,但是你要是用 c 的 scanf ( " %c " ) ,那么你需要在 %c 前面加空格,因为要是不加空格,那么它会将你上一步的输入结束的回车当成你这次要输入的字符

代码:

#include<stdio.h>
#include<math.h>
int main( )
{
    int m,Y,xx=0,yy=0;
    char X;
    double ans=0;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf(" %c %d",&X,&Y);//空格代替 回车\n  cin代替也可以
        if(X=='N') xx-=Y;
        else if(X=='S') xx+=Y;
        else if(X=='W') yy-=Y;
        else if(X=='E') yy+=Y;
        ans+=Y;
    } 
    ans+=sqrt((xx*xx+yy*yy));
    printf("%.6lf",ans);
    return 0;
}

问题 D: 整点

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

区间移动,我们固定一个区间长度,然后让他从序列的左边跑到右边。
区间长度为 d+1 , 两个端点就是两个点,第三个点可以在区间中(除去两个端点)之外随便选。
区间从序列左边跑到右边共 ( n - d + 1 ) 种情况;
第三个点的选取共 ( d - 1 ) 种情况;
再考虑到全排列,最终的答案就是 ( n - d + 1 ) * ( d - 1 ) * 6 ;
给的数据会爆 int 所以开 long long

代码

#include<stdio.h>
#include<math.h>
int main( )
{
    int n,d;
    scanf("%d%d",&n,&d);
    long long ans=(long long)(n-d+1)*(d-1);//int 会爆
    printf("%lld",ans*6);
    return 0;
}

问题 F: 面积2016

2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

在矩形面积相同的情况下周长:长方形>正方形
在矩形面积相同的情况下,长和宽的绝对值差越小,矩形的周长越小。
所以我们可以先看这个矩形面积可不可以是正方形,是正方形就直接输出周长;
否则我们就找构成矩形面积的长宽中相差最小的

代码:

#include<stdio.h>
#include<math.h>
int main( )
{
//面积相等,周长:长方形>正方形>圆
    int n,ans;
    scanf("%d",&n);
    int tmp=(int)sqrt(n);
    if(tmp*tmp==n) printf("%d",tmp*4);
    else
    {
        for(int i=tmp;i<=n;i++)
        {
            if(n%i==0)
            {
                ans=i+i+n/i+n/i;
                break;
            }
        }
        printf("%d",ans);
    }
    return 0;
}

问题 I: 方案数

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

我们可以将这k个计时器全排列后构成的数都记录下来,然后去重,之后剩下来的数的数量就是答案
去重可以用 stl 里面的 set(内部有序,不含重复元素)

快速幂:点击学习

typedef long long ll;
ll qpow(ll a, ll b)//a^b
{
    ll res=1;
    while(b)
    {
        if(b&1)//判断 b 的最后一位是 1 还是 0
		 	res*=a;
        a=(a*a);//将a平方,即把a^(2^i)变为a^(2^(i + 1))
        b >>= 1;// b 右移一位,舍去 b 的最后一位
    }
    return res;
}

set集合

    s.clear() //清空集合
    s.insert(1);//插入
	s.insert(1);
	s.insert(3);
	cout<<s.size()<<endl;
	set<int>::iterator it;//迭代器访问集合元素
	for(it=s.begin();it!=s.end();it++)
	{
		cout<<"!!"<<(*it)<<endl;
	}

代码

#include<stdio.h>
#include<math.h>
#include<set>
#include<iostream> 
using namespace std;
set<long long>s;
int k,a[5];
bool vis[5];
int check(int x)
{
    int sum=0;
    while(x)
    {
        x=x/10;
        sum++;
    }
    return sum;
}
int qpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1) res=res*x;
		y>>=1;
		x=x*x;
	}
	return res;
}
void dfs(long long num,int t)
{
    if(t==0) 
    {
        s.insert(num);
        return ;
    }
    for(int i=1;i<=k;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            long long tmp=num*qpow(10,check(a[i]))+a[i];
            dfs(tmp,t-1);
            vis[i]=0;
        }
    }
} 
int main( )
{
    scanf("%d",&k);
    for(int i=1;i<=k;i++) scanf("%d",&a[i]);
    dfs(0,k);
    printf("%d",s.size());
    return 0;
}

问题 J: 位置2016

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

就是序列区间翻转+判断回文数
我们有两种方法:
1、splay例题(略做了解)
2、暴力翻转:每次操作都翻转一遍区间,不过正常的应该过不去,但是卡一下、吸下氧就过去了(

卡常小技巧 / 吸氧

1.定义常量const int

给定mod用const int,mod用的多的话时间至少减半

2.寄存器register的使用

一般用在循环中用register int,不要滥用,不然可能会出现玄学错误!

register int 亲测在for循环中时间为直接int1/5,减少了4/53.inline

在函数定义的类型前面加inline

例如:
    inline int add(int a,int b) {return a+b>mod?a+b-mod:a+b;}
    
inline 一般用于比较短的,使用频率高的函数,它快的原因是把函数封装起来了,

4.位运算

比如 x<<=1 代替 x*=2 , x>>=1 代替 x/=2 啊 ,x&1代替x%2之类的,灵活运用就行。
(如果 x 是奇数, x&1 等于 1 ,否则等于 05.变量类型的选择

long long类型比int类型计算慢很多,

不过除非万不得已还是不要卡这个常了(不开longlong见祖宗)

还有,听说intbool 快一些,所以flag 就用int 定义吧!

6.for循环

 ++i 比 i++ 快一点

7.快读


inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9')
	{
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
	{
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    if(flag)
        x=-x;
    return x;
}


8.吸氧

#pragma GCC optimize(2)

代码1-splay版(略做了解即可)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int a[maxn],cnt;
struct Node
{
    int ch[2];//ch[0] 左节点 ch[1] 右结点
    int father,v;//v是结点值,father是父亲结点
    int size;//包含自己下面有多少元素(非结点)
    int mark;//该结点元素出现次数(非结点)
    void init(int x,int fa)
    {
        father=ch[0]=ch[1]=0;
        size=1;v=x;father=fa;
    }
}t[maxn];
int n,root,m,tot;
void pushup(int p)
{
    t[p].size=t[t[p].ch[0]].size+t[t[p].ch[1]].size+1;
}
void pushdown(int p)
{
    if(t[p].mark)
    {
        t[t[p].ch[0]].mark^=1;
        t[t[p].ch[1]].mark^=1;
        t[p].mark=0;
        swap(t[p].ch[0],t[p].ch[1]);
    }
}
void rotate(int x)//X是要旋转的节点
{
    int y=t[x].father;//X的父亲
    int z=t[y].father;//X的祖父
    int k=t[y].ch[1]==x;//X是Y的哪一个儿子 0是左儿子 1是右儿子
    t[z].ch[t[z].ch[1]==y]=x;//Z的原来的Y的位置变为X
    t[x].father=z;//X的父亲变成Z
    t[y].ch[k]=t[x].ch[k^1];//X的与X原来在Y的相对的那个儿子变成Y的儿子
    t[t[x].ch[k^1]].father=y;//更新父节点
    t[x].ch[k^1]=y;//X的 与X原来相对位置的儿子变成 Y
    t[y].father=x;//更新父节点
    pushup(y);pushup(x);
}
void splay(int x,int goal)//将x旋转为goal的儿子,如果goal是0则旋转到根
{
    while(t[x].father!=goal)//一直旋转到x成为goal的儿子
    {
        int y=t[x].father,z=t[y].father;//父节点祖父节点
        if(z!=goal)//如果Y不是根节点,则分为上面两类来旋转
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
            //这就是之前对于x和y是哪个儿子的讨论
        rotate(x);//无论怎么样最后的一个操作都是旋转x
    }
    if(goal==0)root=x;//如果goal是0,则将根节点更新为x
} 
inline void insert(int x)
{
    int u=root,father=0;//当前位置u,u的父节点father
    while(u) 
    {
        father=u;//向下u的儿子,父节点变为u
        u=t[u].ch[x>t[u].v];//大于当前位置则向右找,否则向左找
    }
    //不存在这个数字,要新建一个节点来存放
    u=++tot;//新节点的位置
    if(father) t[father].ch[x>t[father].v]=u;//如果父节点非根
    t[u].init(x,father);//不存在儿子
    splay(u,0);
    //把当前位置移到根,保证结构的平衡。注意前面因为更改了子树大小,所以这里必须Splay上去进行pushup保证size的正确。
}
inline int Kth(int k)
{
    int u=root;
    while(1)
    {
        pushdown(u);
        if(t[t[u].ch[0]].size>=k) u=t[u].ch[0];
        else if(t[t[u].ch[0]].size+1==k) return u;
        else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1];
    }
}
void print(int u)
{
    pushdown(u);
    if(t[u].ch[0]) print(t[u].ch[0]);
    if(t[u].v>1&&t[u].v<n+2) a[++cnt]=t[u].v-1;
    if(t[u].ch[1]) print(t[u].ch[1]);
}
void Work(int l,int r)
{
    l=Kth(l);
    r=Kth(r+2);
    splay(l,0);
    splay(r,l);
    t[t[t[root].ch[1]].ch[0]].mark^=1;
}
bool check(int x)
{
    int num=0,k=x;
    while(k)
    {
        num=num*10+k%10;
        k=k/10;
    }
    if(num==x) return 1;
    else return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n+2;++i) insert(i);
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        Work(l,r);
    }
    print(root);
    for(int i=1;i<=cnt;i++) 
    {
        if(check(a[i]))
            printf("%d ",i);
    }
    return 0;
}

代码2-卡常吸氧版

#pragma GCC optimize(2)
#include<stdio.h>
#include<math.h>
int n,m,a[1000010];
void change(int l,int r)
{
    int mid=(l+r)/2;
    for(int i=l;i<=mid;i++)
    {
        int tmp=a[i];
        a[i]=a[r-i+l];
        a[r-i+l]=tmp;
    }
    return ;
}
bool check(int x)
{
    int num=0,k=x;
    while(k)
    {
        num=num*10+k%10;
        k=k/10;
    }
    if(num==x) return 1;
    else return 0;
}
int main( )
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
        a[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        change(x,y);
    }
    for(int i=1;i<=n;i++) 
    {
        if(check(a[i]))
            printf("%d ",i);
    }
    return 0;
}

第八场

问题 C: 青蛙跳

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

1、第二只青蛙的起点在第一只青蛙右边,且每次都比第一只青蛙跳的多,它们一定不会相遇
2、第一只青蛙的起点在第二只青蛙右边,且每次都比第二只青蛙跳的多,它们一定不会相遇
3、两只青蛙存在一个赶超另一个青蛙的情况,他们之间的相对距离每次变化 | x2 - y2 |,但是若想相遇,那么最初的相遇距离应当能够整除相对距离的变化,否则就不能相遇,就会错过

代码:

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node
{
    ll x1;
    ll x2;
    ll yy1;
    ll y2;
}a[15];
int main( )
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld%lld",&a[i].x1,&a[i].x2,&a[i].yy1,&a[i].y2);
    for(int i=1;i<=n;i++)
    {
        if((a[i].x1>a[i].x2&&a[i].yy1>=a[i].y2)||(a[i].x2>a[i].x1&&a[i].y2>=a[i].yy1))
            printf("NO\n");
        else
        {
            if((abs(a[i].x1-a[i].x2)%abs(a[i].yy1-a[i].y2))==0)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
} 

问题 D: 结合律

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

我们直接枚举 x ,y ,z 的取值,看看( x * y )* z 跟 x *( y * z )是不是所有的表达式的值都相等,要是都相等那就是符合结合律,否则不符合

代码

#include<cstdio>
using namespace std;
int p[20][20],a,b,c,d,flag;
int main()
{
    scanf("%d%d%d%d",&a,&b,&c,&d);
    p[0][0]=a,p[0][1]=b,p[1][0]=c,p[1][1]=d;
    for(int x=0;x<2;x++)
    {
        for(int y=0;y<2;y++)
        {
            for(int z=0;z<2;z++)
            {
                if(p[p[x][y]][z]!=p[x][p[y][z]])
                    flag=1;
            }
        }
    }
    if(!flag) printf("Yes\n");
    else printf("No\n");
    return 0;
}

问题 E: 石子游戏

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

这是个博弈问题(Ferguson游戏)

假设当前状态( a , b ), 并且 a 为偶数( b 为偶数同理 )。那么先手取 a 这一堆,我们总可以把它分成( a - 1 , 1 )这种情况。后手下一步只能分 a - 1 ,并且必定只能分成一堆奇数和一堆偶数。那么先手又可以只对偶数进行操作,以此类推,先手必胜。对于 a , b 均为奇数的情况。同理,先手无论取哪一堆,都只能分成一堆奇数和偶数,根据上面的结论,后手必胜。

结论:若是a,b都是奇数,那么后手必胜,否则先手必胜

代码

#include<cstdio>//Ferguson游戏 
using namespace std;
int t,a,b;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        if(a&1&&b&1) printf("Bob\n");
        else printf("Alice\n"); 
    }
    return 0;
}

问题 F: 吉利的数字

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

递归,贪心

从高位到低位贪心,记录一个 ifsame 表示是否目前构造的每一位都与 n 的对应每一位一样,如果从某一位开始生成的数字小于 n 上对应的那一位的数字,那么构造的后面的数全部用可以填的最大值填充即可。

递归调用过程 dfs( ifsame , pos , flag)表示当前正在尝试填充第 pos 位(从高位到低位填充),ifsame 表示是否目前构造过的每一位都与 n 的对应每一位一样,flag 表示是否已经出现了非零位(用于控制前导零)

从高到低枚举当前这一位要填的数字,状态会转移到 ( ifsame’ , flag’ ) ,调用 dfs( ifsame’ , pos - 1 , flag’)检查是否可行,可行的话记录下来,不可行接着枚举下一位可以填充的数。

代码

//#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
char s[maxn];
int a[maxn],ans[maxn],vis[10],n,cnt,m,x;
int dfs(int ifsame,int pos,int flag)
{
    if(!pos) return flag;
    int l=ifsame?a[pos]:9;
    for(int i=l;i>=0;i--)
    {
        if(vis[i]||(!i&&!flag))
        {
            if(dfs(ifsame&&(i==l),pos-1,flag||i))
            {
                ans[++cnt]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main( )
{
    scanf("%s %d",s+1,&m);
    for(int i=1;i<=m;i++) 
    {
        scanf("%d",&x);
        vis[x]=1;
    }
    int len=strlen(s+1);
    for(int i=1;i<=len;i++)
        a[len-i+1]=s[i]-'0';
    if(dfs(1,len,0))
    {
        int flag=1;
        for(int i=cnt;i>=1;i--)
        {
            if(!flag||ans[i])
            {
                printf("%d",ans[i]);
                flag=0;
            }
        }
    }
    else printf("-1");
    return 0;
}

问题 K: 美丽的大树

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

标记被砍掉的树木编号,枚举两侧所有的树木,“ 打擂台 ” 找最长的连续长度(可以加哨兵节点避免少统计最后一次的连续长度)

代码

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream> 
using namespace std; 
int n,x,pos,maxx; 
bool vis[110];
int main() 
{ 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        vis[x]=1;
    }
    vis[101]=vis[102]=1;
    int cnt=0;
    for(int i=1;i<=101;i+=2)
    {
        if(vis[i])
        {
            if(maxx<cnt)
            {
                maxx=cnt;
                pos=i-cnt*2;
            }
            cnt=0;
        }
        else cnt++;
    }
    cnt=0;
    for(int i=2;i<=102;i+=2)
    {
        if(vis[i])
        {
            if(maxx<cnt)
            {
                maxx=cnt;
                pos=i-cnt*2;
            }
            cnt=0;
        }
        else cnt++;
    }
    printf("%d %d",pos,maxx);
    return 0; 
}

第九场

问题 A: 小 X 与机器人I

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

区分出两个点是在邻边,还是在对边,还是在同一条边上。剩下的就是取两个距离中的最小值就可以了

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int x1,x2,yy1,y2,sx,sy;
int main()
{
    scanf("%d%d%d%d",&x1,&yy1,&x2,&y2);
    if(abs(x1-x2)==18)//左右对边
    {
        sx=18+yy1-1+y2-1;
        sy=18+19-yy1+19-y2;
    }
    if(abs(yy1-y2)==18)//上下对边
    {
        sx=18+x1-1+x2-1;
        sy=18+19-x1+19-x2;  
    }
    if(x1==x2) sx=abs(yy1-y2);//左右同边
    if(yy1==y2) sx=abs(x1-x2);//上下同边
    if(sx+sy==0) sx=abs(x1-x2)+abs(yy1-y2);//邻边
    if(sx>sy&&sy)
        printf("%d",sy);
    else printf("%d",sx);
    return 0;
}

问题 B: 小 X 与机器人 2

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

2020ACM俱乐部后备营个人训练赛第七、八、九场
若四个棋子都在一条直线上那么就是直四;
若四个棋子围成一个正方形那就是方四;
若四个棋子有三个在一条直线上,第四个棋子在这三个棋子中间的是丁四,在两边的是曲四;
若四个棋子两两分布在两条直线上就是弯四

sort函数

sort函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序。
sort函数进行排序的时间复杂度为n*log2n,比冒泡之类的排序算法效率要高,
sort函数包含在头文件为#include<algorithm>的c++标准库中。
语法
sort(start,end,cmp)
参数
(1)start表示要排序数组的起始地址;
(2)end表示数组结束地址的下一位;
(3)cmp用于规定排序的方法,可不填,默认升序。

代码

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
int x[100],y[100],s1,s2,t;
int main()
{
    for(int i=1;i<=4;i++)
        scanf("%d%d",&x[i],&y[i]);
    sort(x+1,x+4+1);
    sort(y+1,y+4+1);
    t=1;
    if((x[1]==x[2])&&(x[3]==x[2])&&(x[3]==x[4])||(y[1]==y[2])&&(y[3]==y[2])&&(y[3]==y[4]))
    {
        printf("zhisi");
        return 0;
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=i+1;j<=4;j++)
        {
            if(x[i]==x[j]) s1+=1;
            if(y[i]==y[j]) s2+=1;
        }
    }
    if((s1==2)&&(s2==2))
    {
        printf("fangsi");
        return 0;
    }
    if(s1==3)
    {
        for(int i=1;i<=3;i++)
        {
            if(y[i]==y[i+1])
            {
                if(i==2)
                {
                    printf("dingsi");
                    return 0;
                }
                else
                {
                    printf("qusi");
                    return 0;
                }
            }
        }
    }
    if(s2==3)
    {
        for(int i=1;i<=3;i++)
        {
            if(x[i]==x[i+1])
            {
                if(i==2)
                {
                    printf("dingsi");
                    return 0;
                }
                else
                {
                    printf("qusi");
                    return 0; 
                }
            }
        }
    }
    if((s1==1&&s2==2)||(s1==2&&s2==1))
        printf("wansi");
    return 0;
}

问题 D: 小 X 与位运算

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

先看两个字符串是否相等,不相等补齐(在短的前面加前导零)
补齐之后模拟运算即可

<<string.h>>

strlen求字符串长度
strcmp比较2个字符串是否一样(大于1,小于-1,等于0)
strcat字符串连接操作
strcpy字符串拷贝操作
--------------------------------------以上为常用
strncat字符串连接操作(前n个字符)
strncpy字符串拷贝操作(前n个字符)
strchr查询字串
strstr 查询子串

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
char a[maxn],b[maxn],c[5],d[maxn],e[maxn];
int l1,l2,len,flag;
int main( )
{
    scanf("%s",a);
    scanf("%s",b);
    scanf("%s",c);
    l1=strlen(a),l2=strlen(b);
    len=max(l1,l2);
    if(l1>l2)
    {
        for(int i=0;i<l1-l2;i++) e[i]='0';
        strcat(e,b);
        flag=1;
    }
    else
    {
        for(int i=0;i<l2-l1;i++) e[i]='0';
        strcat(e,a);
        flag=2;
    }
    if(c[0]=='a')
    {
        for(int i=0;i<len;i++)
        {
            if(flag==1)
            {
                if(a[i]=='1'&&e[i]=='1') d[i]='1';
                else d[i]='0';
            }
            else
            {
                if(b[i]=='1'&&e[i]=='1') d[i]='1';
                else d[i]='0';
            }
        }
    }
    else if(c[0]=='o')
    {
        for(int i=0;i<len;i++)
        {
            if(flag==1)
            {
                if(a[i]=='0'&&e[i]=='0') d[i]='0';
                else d[i]='1';
            }
            else
            {
                if(b[i]=='0'&&e[i]=='0') d[i]='0';
                else d[i]='1';
            }
        }
    }
    else if(c[0]=='x')
    {
        for(int i=0;i<len;i++)
        {
            if(flag==1)
            {
                if(a[i]=='0'&&e[i]=='0'||a[i]=='1'&&e[i]=='1') d[i]='0';
                else d[i]='1';
            }
            else
            {
                if(b[i]=='0'&&e[i]=='0'||b[i]=='1'&&e[i]=='1') d[i]='0';
                else d[i]='1';
            }
        }
    }
    int flag=1;
    for(int i=0;i<len;i++)
    {
        if(flag==0||d[i]=='1')
        {
            printf("%c",d[i]);
            flag=0;
        }
    }
    return 0;
} 
 

问题 F: 小 X 玩游戏

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

将电脑的牌分为两部分(前n张,后n张),然后各自从小到大排序(只要区分前部分后部分就行,前后各自部分内排序不影响结果),在对我自己的牌从小到大进行排序,排完序之后我自己的前n张对应电脑的前n张,后n张对应电脑的后n张(因为前半部分是小的得分,所以我牌越小越好,后半部分是大的得分,所以我的牌越大越好);然后就是各部分贪心分配了,对于前半部分我们枚举电脑的牌,从我的牌里选小的安排上;对于后半部分枚举我的牌,从电脑的牌里选小的安排上;最后总的安排的牌数就是答案。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[2010],b[2010],ans,cnt=1;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n*2;i++)
        scanf("%d",&b[i]);
    sort(b+1,b+n+1);
    sort(b+n+1,b+n*2+1);
    sort(a+1,a+1+n*2);
    for(int i=1;i<=n;i++)
        if(a[cnt]<b[i]) ans++,cnt++;
    cnt=n+1;
    for(int i=n+1;i<=n*2;i++)
        if(b[cnt]<a[i]) ans++,cnt++;
    printf("%d",ans);
    return 0;
}

问题 H: 小 X 学游泳

2020ACM俱乐部后备营个人训练赛第七、八、九场
2020ACM俱乐部后备营个人训练赛第七、八、九场

思路

递归求最小距离
先给每个点赋一个极大值,然后从1,1开始递归,每次枚举当前点的四个方向,如果这个点可以更新那个方向,那么就朝那个方向递归,如果不能更新那个方向,就枚举下一个方向

代码

//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int d[4][2]={1,0,-1,0,0,1,0,-1};
int a[50][50],dp[50][50],n,m,ans=INF,cnt;
bool vis[50][50];
void dfs(int x,int y,int v)
{
    if(v>=dp[x][y]) return ;
    else dp[x][y]=v;
    for(int i=0;i<4;i++)
    {
        int xx=x+d[i][0];
        int yy=y+d[i][1];
        if(xx<=0||yy<=0||xx>n||yy>m) continue;
        if(vis[xx][yy]) continue;
        vis[xx][yy]=1;
        dfs(xx,yy,v+a[xx][yy]);
        vis[xx][yy]=0;
    }
}
int main( )
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            dp[i][j]=INF;
    vis[1][1]=1;
    dfs(1,1,a[1][1]);
    printf("%d",dp[n][m]);
    return 0;
}

本文地址:https://blog.csdn.net/Cosmic_Tree/article/details/110123148

相关标签: upc