2020ACM俱乐部后备营个人训练赛第七、八、九场
第七场
问题 B: 数字塔
思路
简单的递推
例如:
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: 路程
思路
直接模拟整个走路的过程,记录整个路程和( sum )
假设一个点( x , y ) , 我们从这个点分别朝四个方向( 东南西北 - 右下左上 )走 m 步 , 那么走后的坐标为:
向东(右): ( x , y+m )
向南(下): ( x+m , y )
向西(左): ( x , y-m )
向北(上): ( x-m , y )
根据这个我们可以模拟求出超市的坐标( x2 , y2 ),将超市坐标与家的坐标(设置一个家的初始坐标,假设为 ( x1 , y1 ) )求直线距离:
最后的答案就是 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: 整点
思路
区间移动,我们固定一个区间长度,然后让他从序列的左边跑到右边。
区间长度为 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
思路
在矩形面积相同的情况下周长:长方形>正方形
在矩形面积相同的情况下,长和宽的绝对值差越小,矩形的周长越小。
所以我们可以先看这个矩形面积可不可以是正方形,是正方形就直接输出周长;
否则我们就找构成矩形面积的长宽中相差最小的
代码:
#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: 方案数
思路
我们可以将这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
思路
就是序列区间翻转+判断回文数
我们有两种方法:
1、splay:例题(略做了解)
2、暴力翻转:每次操作都翻转一遍区间,不过正常的应该过不去,但是卡一下、吸下氧就过去了(逃
卡常小技巧 / 吸氧
1.定义常量const int
给定mod用const int,mod用的多的话时间至少减半
2.寄存器register的使用
一般用在循环中用register int,不要滥用,不然可能会出现玄学错误!
register int 亲测在for循环中时间为直接int的1/5,减少了4/5!
3.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 ,否则等于 0 )
5.变量类型的选择
long long类型比int类型计算慢很多,
不过除非万不得已还是不要卡这个常了(不开longlong见祖宗)
还有,听说int 比bool 快一些,所以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: 青蛙跳
思路
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: 结合律
思路
我们直接枚举 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: 石子游戏
思路
这是个博弈问题(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: 吉利的数字
思路
递归,贪心
从高位到低位贪心,记录一个 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: 美丽的大树
思路
标记被砍掉的树木编号,枚举两侧所有的树木,“ 打擂台 ” 找最长的连续长度(可以加哨兵节点避免少统计最后一次的连续长度)
代码
#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
思路
区分出两个点是在邻边,还是在对边,还是在同一条边上。剩下的就是取两个距离中的最小值就可以了
代码
#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
思路
若四个棋子都在一条直线上那么就是直四;
若四个棋子围成一个正方形那就是方四;
若四个棋子有三个在一条直线上,第四个棋子在这三个棋子中间的是丁四,在两边的是曲四;
若四个棋子两两分布在两条直线上就是弯四
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 与位运算
思路
先看两个字符串是否相等,不相等补齐(在短的前面加前导零)
补齐之后模拟运算即可
<<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 玩游戏
思路
将电脑的牌分为两部分(前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 学游泳
思路
递归求最小距离
先给每个点赋一个极大值,然后从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