- chenshixian 的博客
陈室先的总结8.24day26
-
chenshixian
LV 2
@
2024-8-24 10:31:16
这套题我没考试
题目传送门
T1填涂颜色
思路
公式min(n,k)*min(m,k)
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
long long n,m,k;
cin>>n>>m>>k;
cout<<min(n,k)*min(m,k);
return 0;
}
T2密码
思路
先把密码表给打下来，然后在处理
代码
#include<bits/stdc++.h>
using namespace std;
char a[26][26]={
'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
'B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A',
'C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B',
'D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C',
'E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D',
'F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E',
'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F',
'H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G',
'I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H',
'J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I',
'K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J',
'L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K',
'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L',
'N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M',
'O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N',
'P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
'Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
'R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q',
'S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R',
'T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S',
'U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T',
'V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U',
'W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V',
'X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W',
'Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X',
'Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y',
};
int main(){
freopen("vigenere.in","r",stdin);
freopen("vigenere.out","w",stdout);
string k,s;
cin>>k>>s;
int l=k.size();
for(int i=0;i<=s.size()-l-1;i++)k+=k[i];
for(int i=0;i<s.size();i++){
int w;
char d;
if(k[i]>='a'&&k[i]<='z')w=k[i]-'a';
else w=k[i]-'A';
if(s[i]>='a'&&s[i]<='z')d=s[i]-'a'+'A';
else d=s[i];
for(int j=0;j<26;j++){
if(a[w][j]==d){
if(s[i]>='a'&&s[i]<='z')cout<<char(j+'a');
else cout<<char(j+'A');
}
}
}
return 0;
}
T3海港
思路
用一个单调队列维护，再来个桶记录，就可以了
代码
#include<bits/stdc++.h>
using namespace std;
vector<int>v;
queue<vector<int>>q;
int st[111111],c=0;
int main(){
freopen("port.in","r",stdin);
freopen("port.out","w",stdout);
int n,x,y;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
vector<int>a;
a.push_back(x);
cin>>x;
for(int j=1;j<=x;j++){
cin>>y;
if(st[y]==0)c++;
st[y]++;
a.push_back(y);
}
q.push(a);
while(q.front()[0]<=a[0]-86400){
for(int k=1;k<q.front().size();k++){
if(st[q.front()[k]]==1)c--;
st[q.front()[k]]--;
}
q.pop();
}
v.push_back(c);
}
for(int i=0;i<v.size();i++)cout<<v[i]<<"\n";
return 0;
}
T4流星雨
思路
记录流星时用一个标记数组，还要提个防止重复走，最后套BFS模版
代码
#include<bits/stdc++.h>
using namespace std;
int st[555][555],n,c=-1;
int ss[555][555];
int dx[10]={0,1,0,-1};
int dy[10]={1,0,-1,0};
struct P{
int x,y,s;
};
void bfs(){
queue<P>q;
if(st[0][0]==0)return;
q.push({0,0,0});
while(!q.empty()){
P a=q.front();
q.pop();
if(st[a.x][a.y]==0x3f3f3f3f){
c=a.s;
break;
}
for(int i=0;i<4;i++){
int x=a.x+dx[i];
int y=a.y+dy[i];
if(x<0||x>302||y<0||y>302)continue;
if(a.s+1>=st[x][y])continue;
if(ss[x][y]==1)continue;
q.push({x,y,a.s+1});
ss[x][y]=1;
}
}
}
int main(){
freopen("meteor.in","r",stdin);
freopen("meteor.out","w",stdout);
memset(st,0x3f,sizeof st);
cin>>n;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
st[x][y]=min(z,st[x][y]);
st[x+1][y]=min(z,st[x+1][y]);
if(x!=0)st[x-1][y]=min(z,st[x-1][y]);
if(y!=0)st[x][y-1]=min(z,st[x][y-1]);
st[x][y+1]=min(z,st[x][y+1]);
}
bfs();
if(c==1000000000)cout<<-1;
else cout<<c;
return 0;
}