T1 输出全排列
是暑假就做过的题！
代码如下。
#include <iostream>
using namespace std;
int n;
int a[11],vis[11];
void dfs(int step){
if(step==n+1){
for(int i=1;i<=n;i++){
cout<<a[i];
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(vis[i]==0){
a[step]=i;
vis[i]=1;
dfs(step+1);
vis[i]=0;
}
}
return;
}
int main(){
cin>>n;
dfs(1);
return 0;
}T2 山
是一道非常经典的搜索题，题中的山可以换成：细胞，海岛（bushi）。
不过我的实现方式比较复杂了！
代码如下。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
queue<int> x1;
queue<int> y1;
queue<int> tx;
queue<int> ty;
int world[2005][2005];
int color[2005][2005];
int vis[2005][2005];
int n,m;
int ans;
int movex[5]={0,0,0,1,-1};
int movey[5]={0,1,-1,0,0};
int main(){
memset(world,0x3f,sizeof(world));
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
cin>>world[i][l];
if(world[i][l]==1){
x1.push(i);
y1.push(l);
}
}
}
while(!x1.empty()){
int xx=x1.front();
int yy=y1.front();
if(vis[xx][yy]==1){
x1.pop();
y1.pop();
continue;
}
vis[xx][yy]=1;
tx.push(xx);
ty.push(yy);
while(!tx.empty()){
int x2=tx.front();
int y2=ty.front();
for(int i=1;i<=4;i++){
int x3=x2+movex[i];
int y3=y2+movey[i];
if(x3>=1&&x3<=n&&y3>=1&&y3<=m&&world[x3][y3]==1&&vis[x3][y3]==0){
tx.push(x3);
ty.push(y3);
vis[x3][y3]=1;
}
}
tx.pop();
ty.pop();
}
ans++;
x1.pop();
y1.pop();
}
cout<<ans;
}T3 跳跃
和奇怪的电梯差不多，但是这道题是要找到元素值为0的下标位置。
不用输出步数所以bfs或者dfs都可。（不过我bfs调了超久诶诶诶）
代码如下。
#include <iostream>
#include <queue>
using namespace std;
const int N=5e5+5;
int start,n;
int num[N];
int step[N];
int vis[N];
queue<int> x;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
cin>>start;
if(num[start]==0){
cout<<"True";
return 0;
}
vis[start]=1;
x.push(start);
while(!x.empty()){
int x1=x.front();
if(num[x1]==0){
cout<<"True";
return 0;
}
int s=num[x1];
int l=x1-s;
int r=x1+s;
if(l>=0){
if(vis[l]==0){
vis[l]=1;
x.push(l);
}
}
if(r<n){
if(vis[r]==0){
vis[r]=1;
x.push(r);
}
}
x.pop();
}
cout<<"False";
return 0;
}T4 回文数回文
草，这道题败在了不会估计时间复杂度上面。
从起始数到极限数据回文数并不多，可以枚举。
代码如下。
#include <iostream>
using namespace std;
int ans;
int getnum(int n){
int temp=n;
int a[6];
n/=10;
for(int i=1;i<=4;i++){
a[i]=n%10;
n/=10;
}
for(int i=1;i<=4;i++){
temp*=10;
temp+=a[i];
}
return temp;
}
int main(){
int a;
cin>>a;
for(int i=10000;i<=99999;i++){
if(getnum(i)<=a){
ans++;
}
}
cout<<ans;
}
T5 最长光路
这道题怎么一股oi味。（指题面和样例）
代码非常蠢呢 还有一个点过不去www。
#include <iostream>
#include <cstring>
using namespace std;
const int INF=0x3f3f;
//1为上，2为右，3为下，4为左。
// \可以用\\来表示。
// \ 1->4 2->3 3->2 4->1
// / 1->2 2->1 3->4 4->3
char world[505][505];
int vis[505][505][6];
int n,m;
int sx,sy;
int nx,ny;
long long int ans;
char ansdir;
long long int len;
bool check(int x,int y){
if(x<1||y<1) return 0;
if(x>n||y>m) return 0;
if(world[x][y]=='C') return 0;
return 1;
}
void go(int x,int y,int status){
if(status==1){
nx=x-1, ny=y;
}
else if(status==2){
nx=x, ny=y+1;
}
else if(status==3){
nx=x+1, ny=y;
}
else if(status==4){
nx=x, ny=y-1;
}
}
void dfs(int x,int y,int status){
++len;
if(vis[x][y][status]){
len=INF;
return;
}
else vis[x][y][status]=1;
if(world[x][y]=='/'){
if (status==1) status=2;
else if(status==2) status=1;
else if(status==3) status=4;
else if(status==4) status=3;
}
if(world[x][y]=='\\'){
if (status==1) status=4;
else if(status==2) status=3;
else if(status==3) status=2;
else if(status==4) status=1;
}
go(x,y,status);//更新x和y的值。
if(!check(nx,ny)) return;
dfs(nx,ny,status);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
cin>>world[i][l];
}
}
cin>>sx>>sy;
memset(vis,0,sizeof(vis));
len=0;
dfs(sx,sy,1);
if(len>ans) ansdir='U',ans=len;
memset(vis,0,sizeof(vis));
len=0;
dfs(sx,sy,2);
if(len>ans) ansdir='R',ans=len;
memset(vis,0,sizeof(vis));
len=0;
dfs(sx,sy,3);
if(len>ans) ansdir='D',ans=len;
memset(vis,0,sizeof(vis));
len=0;
dfs(sx,sy,4);
if(len>ans) ansdir='L',ans=len;
cout<<ansdir<<endl;
if(ans!=INF){
cout<<ans;
}
else cout<<"COOL"<<endl;
return 0;
}