ACGO挑战赛7题解
2024-08-21 07:26:33
发布于:上海
T1、小灵的奇妙上学之旅
一个比较基本的动态规划,寻找不同路径的数量,由于终点只能够由起点到达,因此终点方案数就是所有起点的方案数加在一起(就是数据一言难尽)
#include<iostream>
using namespace std;
const int N=1001,MOD=114514;
long long dp[N];//一个比较基本的动态规划,就是“不同的路径”这种题目升级版
//dp[i]表示从1走到i的方案数
//使用标数法轻松解决
int n,k,e;
int main(){
dp[1]=1;//起始点只有一种走法(不走)能够到达,所以赋值为1
cin>>n;
for(int i=1;i<=n;i++){
cin>>k;
for(int j=1;j<=k;j++){
cin>>e;
dp[e]=(dp[i]+dp[e])%MOD;//这个终点能够通过现在的起点到达
//所以是由起点的方案数加上现在该终点已有的方案数得到
}
}
cout<<dp[n];
return 0;
}
T2、完美矩阵
本题难点在于找到旋转对称点。当n=4时,(0,0)的对称点为(0,3),(3,0),(3,3),(0,1)的对称点为(1,3),(2,0),(3,2),……,由此可知,(i,j)的对称点为(j,n-i-1),(n-j-1,i),(n-i-1,n-j-1)这三个点
#include<iostream>
using namespace std;
const int N=1e3;
int t,n,s;
char rec[N][N];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++)cin>>rec[i];//输入数据
s=0;
for(int i=0;i<(n+1)/2;i++){
for(int j=0;j<(n+1)/2;j++){
/*
这里我们用递推可以得知,
一个原来坐标为(i,j)的点,
顺时针旋转90°变成了(j,n-i-1)的点,
逆时针旋转90°变成了(n-j-1,i)的点,
旋转180°后变成了(n-i-1,n-j-1)的点。
也就是说,我们可以将整个二维数组划分为四个部分:左上、右上、左下、右下,
最终我们只需要判断左上部分即可同时顾虑到其他三个部分。
*/
char max_ch=max(max(rec[i][j],rec[n-i-1][n-j-1]),
max(rec[j][n-i-1],rec[n-j-1][i]));
//获取四个对称点中最大的那个字符的值
s+=(max_ch-rec[i][j])+(max_ch-rec[n-i-1][n-j-1])+
(max_ch-rec[j][n-i-1])+(max_ch-rec[n-j-1][i]);
//更新最终的结果,如果此处遇到有和最大字符相同的字符,则+0,对结果无影响
}
}
cout<<s<<endl;
}
return 0;
}
T3、So Easy
这道题第一眼是暴力枚举,时间复杂度 O(n2) ,带入最大数据n=2e5,超时。
那么我们可以换一个思路,由于题目要求找到aj-ai=j-i,那么我们作移项处理,有aj-j=ai-i,那么我们只需要判断有多少个这样的差值相等即可,因此我们可以用桶来装差值。
但是,这样会有一个问题:当我们得到的差值<0怎么办,这样会导致 RE ,那么我们就给得到的差加上一个极大的数且确保最后的结果不会超过桶的大小。
#include<iostream>
using namespace std;
int n;
const int N=2e5+25;
const int LARGE=2e7+14;
int num[N],bucket[LARGE],s;//由于双循环找索引对容易超时TLE,所以用桶来存储差值
//因为aj-ai=j-i,所以由等式的性质知只要判断aj-j=ai-i即可
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
num[i]=num[i]-i+N;//这里考虑到减出来会有负数的情况,故加上一个很大的数,变成正的
s+=bucket[num[i]]++;//先取出桶内的数量,再存入桶中
}
cout<<s;
return 0;
}
T4、棋盘对象
这道题目想不到时间复杂度 O(1) 的(或者像我一样 O(1) 做错的),建议直接广搜处理。根据象的走法,我们可以写出方向数组:int dir[4][2] = {{2, 2}, {2, -2}, {-2, 2}, {-2, -2}};
#include<iostream>
#include<queue>
using namespace std;
struct node{
int x,y;
};
queue<node>q;
bool vis[500][500];
int dir[4][2]={2,2,2,-2,-2,2,-2,-2};//这里根据象的走法写出方向数组
int n,a,b,c,d;
int main(){
cin>>n>>a>>b>>c>>d;
a--,b--,c--,d--;
q.push({a,b});
vis[a][b]=1;
while(q.size()){//基本是搜索了所有可以走的地方
node f=q.front();
q.pop();
if(f.x==c&&f.y==d){
cout<<"YES";
return 0;//碰到两人,直接cout<<"YES"并结束程序
}
for(int i=0;i<4;i++){
int nx=f.x+dir[i][0],ny=f.y+dir[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis[nx][ny]){//判断是否在棋盘上且未到达过
q.push({nx,ny});
vis[nx][ny]=1;
}
}
}
cout<<"NO";//搜不到说明两人不在象的落脚点上,cout<<"NO"即可
return 0;
}
T5、左右互搏
这道题目直接深搜即可,时间复杂度 O(2n) ,这样带入最大数据n=10,计算出来为1024,不会超时,放心写代码吧
#include<limits>
#include<utility>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull,ull>ulp;
ulp hands[10];//pair类型数组,*.first表示左手,*.second表示右手
ull n,l,r,d=numeric_limits<ull>::max();//给d(差值)赋予 unsigned long long 上限
void dfs(int steps=0,ull l=1,ull r=0){//直接深搜,l和r分别表示左手和右手
//由于左手是乘积,所以需要从1开始乘
//由于右手是总和,所以需要从0开始加
if(steps==n){//这里是递归走到底的情况
if(l-1&&r)d=min(d,l>r?l-r:r-l);//判断是否是都有战力值了,否则不能算进去
return;
}
dfs(steps+1,l*(hands[steps].first),r+(hands[steps].second));//递归 选择这组战力值的情况
dfs(steps+1,l,r);//递归 不选择这组战力值的情况,也因此到底时需要判断是否为空
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>hands[i].first>>hands[i].second;//读入数据
dfs();//dfs开始搜索
cout<<d<<endl;
return 0;
}
T6、拉丁方格
由于题目明确说明由A、B、C组成的方格且每行每列不重复(有点像数独或幻方),那么可以知道:
· 三行每行一个字母,共三个字母,即在方格中A、B、C各出现三次
· 题目输入数据只会缺少一个字母,即只有一个字母出现次数为3-1=2次,其它均为3次
所以,我们只要找到出现次数最少得字母即可,因为它就是缺少的字母
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int b[3]={};
char d;
for(int i=0;i<9;i++){
cin>>d;
if(d>64&&d<68)b[d-65]++;
}
cout<<(char)((min_element(b,b+3)-b)+65);
//最小值就是没满3的那个字母,找到它就是找到了缺少的字母
return 0;
}
感兴趣的话就加入团队吧!
这里空空如也
有帮助,赞一个