天梯选拔赛赛后补题
目录
7-7 Captain-G's “Die Hard”
7-10 偶数个数字3
7-11 螺旋加密
7-12 旅行
7-14 算式幂
7-15 Emiya 家今天的饭
太久不打比赛天梯选拔赛做的题也是少的要死了，然后就浅浅的补一下题吧，把赛时剩下的题都写出来
7-7 Captain-G's “Die Hard”
思路：我们在纸上写写画画一下其实就会发现，只有是当前两个数的最大公因数的倍数的时候才能满足，能用有限次数量出来，否则就是不能的
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int k;
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
signed main()
{
cin>>n>>m;
int d=gcd(n,m);
cin>>k;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
if(x%d==0)
cout<<"1 ";
else
cout<<"0 ";
}
return 0;
}
7-10 偶数个数字3
PS：注意最终结果需要取模12345
思路：我们这题其实也是一个思维题找到相邻位递推的规律即可解决这个问题，我们仔细思考，我们要找的是n位数里面有偶数个3的所有情况，那么我们可以考虑在n-1位数中符合的数的前面加一位，加的一位不能是0也不能是3，我们假设n-1位符合的情况有sum种，那么我们可以用总情况-sum，然后再在前面加一位3，即可
所以可以通过这两部分去递推，最终写出答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1005];
int n;
signed main()
{
cin>>n;
dp[1]=9;
int sum=9;
int z=10;
for(int i=2;i<=n;i++)
{
dp[i]=(8*sum+(z-sum))%12345;
sum=sum+dp[i];
z=(10*z)%12345;
}
cout<<dp[n];
return 0;
}7-11 螺旋加密
思路：其实这题没那么难，主要的考点其实就三个（整行的读入，位运算，蛇形方阵）
我们先来解决第一个问题，如何进行整行的读入，其实直接用getline(cin,s)即可，然后再这个上面应该加一个getchar去吸收矩阵大小与字符串中间的空格
然后我们来解决第二个问题，如何去判断每一位都是哪个数，我们直接用位运算操作即可，从4到0，存储在一个队列里面即可，从后面进队列，等到赋值的时候从前面弹出
我们来解决这题里面最难的一个问题，如何进行蛇形矩阵，我们知道这题的蛇形矩阵的方向其实就是右->下->左->上 。那么我们是否能写一个状态数组去表示呢？那么显而易见是可以的，我们用dx，dy数组去表示方向,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}
我们的初始方向状态为0，然后我们只要碰到边界或者说碰到访问过的数组就要重新变换方向，然后继续去赋值，标记为已访问即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
string s;
deque<int> e;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int a[25][25];
int vis[25][25];
signed main()
{
cin>>n>>m;
getchar();
getline(cin,s);
for (char c : s) {
int x;
if (c != ' ') {
x = c - 'A' + 1;
} else {
x = 0;
}
for (int i = 4; i >= 0; i--) {
e.push_back((x >> i) & 1);
}
}
int cnt=e.size();
int x=1,y=1;
int d=0;
for(int i=1;i<=cnt&&i<=n*m;i++)
{
a[x][y]=e.front();
vis[x][y]=1;
e.pop_front();
int tx=x+dx[d],ty=y+dy[d];
if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty])
{
d=(d+1)%4;
}
x=x+dx[d],y=y+dy[d];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<a[i][j];
}
}
return 0;
}7-12 旅行
思路：这题是一个比较板的二分吧，但是不知道为什么赛时的时候犯迷糊一直在搞第7个浪费了不少时间。
我们可以先跑两边二分，找到左边能去的最大坐标和右边能去的最大坐标，然后，在这个区间内去遍历每个点，如果当前这个点是负值，就去看如果走到这个点剩下的时间的一半，能在右边走多少个景点，如果这个点是正值，那就看走到这个点剩下的时间的一半，能在左边走多少个景点，然后不断去更新最大景点数
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n;
int a[200005];
signed main()
{
cin>>t>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
int posl=lower_bound(a+1,a+1+n,-t)-a;
int posr=upper_bound(a+1,a+1+n,t)-a;
int pos0=upper_bound(a+1,a+1+n,0)-a;
posr--;
int ans=0;
for(int i=posl;i<=posr;i++)
{
int flagt=t;
if(a[i]<0)
{
flagt-=-a[i];
int pos=upper_bound(a+1,a+1+n,flagt/2)-a;
pos--;
ans=max(ans,pos-i+1);
}
else
{
flagt-=a[i];
int pos=lower_bound(a+1,a+1+n,-flagt/2)-a;
ans=max(ans,i-pos+1);
}
}
cout<<ans;
return 0;
}7-14 算式幂
思路：其实我们发现这个一个周期性的函数，周期为C，我们只需要找到每个位置上有多少个数，然后乘以当前i的b次方取模c后的数累加取模即可，记得拿快速幂优化一下哦
#include<bits/stdc++.h>
using namespace std;
#define int long long
int x,y,z;
int fast(int a,int b)
{
int ans=1;
a%=z;
while(b>0)
{
if(b%2==1)
ans=(ans*a)%z;
a=(a*a)%z;
b/=2;
}
return ans%z;
}
signed main()
{
cin>>x>>y>>z;
int cnt=x/z;
int mod=x%z;
int sum=0;
for(int i=1;i<=z;i++)
{
if(i<=mod)
{
sum=(sum+(fast(i,y)*(cnt+1))%z)%z;
}
else
{
sum=(sum+(fast(i,y)*(cnt))%z)%z;
}
}
cout<<sum;
return 0;
}
7-15 Emiya 家今天的饭
为了防止某些和我一样的蒟蒻，因为题目太长没有读懂，我这个给大家再讲解一下，题目的意思是有n种烹饪方法，m种烹饪主食材，我们对于第i种烹饪方法，第j种烹饪主食材有a[i][j]种菜肴可以做。
然后呢，有三个要求需要满足
1.至少做一个菜品
2.每个菜品的烹饪方法都不能一样
3.烹饪的菜品，不能用同一个主食材超过菜品的一半
思路：我们做这题的时候可以先想一下，如果要是暴力做这道题，那么该怎么做呢？
这问题的大致思路还是用容斥原理，用总的情况减去不满足条件的情况即可
我们先来考虑如何去求总的情况
我们题目上要求了，每个烹饪手法只能用一次，也就是说明了每一行只能选择一个菜或者说直接选择不做，因此我们总的情况=（每一行的菜品总数+1）相乘，然后最后在减去1（因为不能一道菜也不做）
先来讲一下暴力做法吧：
dp[i][j][k]，dp含义为当用第i个烹饪手法时，当前主食材用了j次，其余主食材用了k次，只要j>k，那么就说明当前的已经是不满足题意的情况了,如果再算上最外层的遍历所有主食材，其时间复杂度为O(n^3*m)
然后用总的情况去减去这个所有不满足的情况，就是最后的满足的情况
但是这样的时间复杂度太高了，我们考虑优化，其实我们只需要优化掉一层n就可以跑过整个程序，我们来仔细思考一下上面的暴力做法
优化做法，时间复杂度为O(n^2*m)
应该已经注意到了上面的最重要的信息，只要j>k即可，我们并不需要在乎j是多大，k是多大，那么我们就可以将dp方程优化为dp[i][j]表示用第i个烹饪手法的时候，当前列的菜比其他列的菜多j，只要j是大于1的，那么就是不满足题意的情况，然后直接计算不满足的情况即可
dp[i][j]=(dp[i-1][j](不做选择的)+dp[i-1][j-1]*a[i][j](选择用col这个主食材的)+dp[i-1][j+1]*(pre[i]-a[i][j])(选择用别的主食材的））%mod通过这三种然后取模mod就是所有情况都枚举出来了
那么我们上面说了只要不满足题意，也就是j>0
我们之间去循环j从1到n即可，然后去把所有累加取模
这里有个细节dp[i][j]应当用dp[i][n]去表示原点，因为有负数要平移n
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[105][2005];
int pre[105];
int dp[105][2005*2];//表示在选取前i行，当前列比其他列多j 道菜
int mod=998244353;
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int sum=1;//总方案数
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pre[i]=(pre[i]+a[i][j])%mod;
}
sum=(sum*(pre[i]+1))%mod;
}
sum=(sum-1+mod)%mod;
int ans=0;
for(int col = 1; col<=m; col++)
{
memset(dp,0,sizeof(dp));
dp[0][n] = 1;
for(int i = 1; i<=n; i++)
{
for(int j = n-i; j<=n+i; j++)
{
dp[i][j] = (dp[i-1][j]+dp[i-1][j-1]*a[i][col]%mod+dp[i-1][j+1]*(pre[i]-a[i][col])%mod)%mod;
}
}
for(int j = 1; j<=n; j++)
{
ans= (ans+dp[n][n+j])%mod;
}
}
cout<<(sum-ans+mod)%mod;
return 0;
}