T1 输出全排列
很典的一道题（在某哈算法一书里作为dfs的例题）
代码如下：
#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 山
我写的很懒，主要是感觉会重复标记所以一直在想怎么优化。（但其实并不会重复标记）
#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 跳跃
非常像奇怪的电梯那道题，但是因为没有确认下标的问题，一直卡在这道题。
#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 最长光路
看到输入就不太想做了。）
但是想了想某书上有一道水管工的题，要定义四个朝向和四个状态，感觉还是做一做还是蛮有用的。
（其实做了半天没做出来还是看了题解）
#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;
}是我第一次周赛做三道好耶（好锤子哦）