2020ACM俱乐部后备营个人训练赛第七、八、九场
程序员文章站
2022-06-26 17:27:16
第七场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: 数字塔
思路
简单的递推
例如：
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