題目意思：
給一個r*c的矩陣方格，有些位置有S，如果某一行和一列都不含標記為S的方格，則可以把該行所有方格都收掉，問最多能收多少個方格，方格可以收多次，多次收的方格計數一次。
解題思路：
暴力
代碼：
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
char save[15][15];
bool flag[15][15];
struct Point
{
int x,y;
}pp[120];
int main()
{
int r,c;
while(scanf("%d%d",&r,&c)!=EOF)
{
int cnt=0;
memset(flag,false,sizeof(flag));
for(int i=1;i<=r;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=c;j++)
{
if(save[i][j]=='S')
{
pp[++cnt].x=i;
pp[cnt].y=j;
}
}
}
for(int i=1;i<=r;i++) //掃描每一行
{
bool ff=true;
for(int j=1;j<=c;j++) //如果都沒有S，則標記這一行
if(save[i][j]=='S')
{
ff=false;
break;
}
if(ff)
memset(flag[i],true,sizeof(flag[i]));//表示能收
}
for(int i=1;i<=c;i++) //掃描每一列
{
bool ff=true;
for(int j=1;j<=r;j++)
if(save[j][i]=='S')
{
ff=false;
break;
}
if(ff)
for(int j=1;j<=r;j++) //標記這一列
flag[j][i]=true;
}
int ans=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
if(flag[i][j]) //統計計數
ans++;
printf("%d\n",ans);
}
return 0;
}
</SPAN>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
char save[15][15];
bool flag[15][15];
struct Point
{
int x,y;
}pp[120];
int main()
{
int r,c;
while(scanf("%d%d",&r,&c)!=EOF)
{
int cnt=0;
memset(flag,false,sizeof(flag));
for(int i=1;i<=r;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=c;j++)
{
if(save[i][j]=='S')
{
pp[++cnt].x=i;
pp[cnt].y=j;
}
}
}
for(int i=1;i<=r;i++) //掃描每一行
{
bool ff=true;
for(int j=1;j<=c;j++) //如果都沒有S，則標記這一行
if(save[i][j]=='S')
{
ff=false;
break;
}
if(ff)
memset(flag[i],true,sizeof(flag[i]));//表示能收
}
for(int i=1;i<=c;i++) //掃描每一列
{
bool ff=true;
for(int j=1;j<=r;j++)
if(save[j][i]=='S')
{
ff=false;
break;
}
if(ff)
for(int j=1;j<=r;j++) //標記這一列
flag[j][i]=true;
}
int ans=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
if(flag[i][j]) //統計計數
ans++;
printf("%d\n",ans);
}
return 0;
}
B. Road Construction
題目意思：
給一些不能連接的邊，讓你構造一幅圖，使任意兩點能互相到達，且經過的邊數不超過2。
解題思路：
任意兩個點之間的邊數不超過2，說明該圖一定是星圖。找到中心的那個點（沒有限制的邊連接這點），直接連線即可。
代碼：
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int num[1100];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b;
memset(num,0,sizeof(num));
for(int i=1;i<=m;i++) //num[i]表示i點的度數
{
scanf("%d%d",&a,&b);
num[a]++,num[b]++;
}
int M=0;
num[0]=INF;
for(int i=1;i<=n;i++)
if(num[i]<num[M]) //找到度數為零的點
M=i;
printf("%d\n",n-1);
for(int i=1;i<=n;i++)
{
if(i==M)
continue;
printf("%d %d\n",i,M); //連接即可
}
}
return 0;
}
</SPAN>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int num[1100];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b;
memset(num,0,sizeof(num));
for(int i=1;i<=m;i++) //num[i]表示i點的度數
{
scanf("%d%d",&a,&b);
num[a]++,num[b]++;
}
int M=0;
num[0]=INF;
for(int i=1;i<=n;i++)
if(num[i]<num[M]) //找到度數為零的點
M=i;
printf("%d\n",n-1);
for(int i=1;i<=n;i++)
{
if(i==M)
continue;
printf("%d %d\n",i,M); //連接即可
}
}
return 0;
}
C. Purification
題目意思：
給n*n的矩陣，讓你放最少數量的清洗劑，使得所有的點都能清洗到，清洗劑所放位置的那一行和那一列的所有點都能清洗，其中E點不能放清洗劑。
解題思路：
如果能放，一定為n個，因為每一行或每一列都要掃描到。
如果每一行都有可放的位置，則輸出每一行的任意一個能放的點即可，這樣每一行的點都會清洗到。
如果每一列都有可放的位置，則輸出每一列的任意一個能放得點即可，這樣每一列的都會清洗到，也就達到了要求。
代碼：
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
bool rr[120],cc[120];
char save[120][120];
vector<int>row[120];
vector<int>col[120];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(rr,false,sizeof(rr));
memset(cc,false,sizeof(cc));
for(int i=1;i<=n;i++)
{
row[i].clear();
col[i].clear();
}
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=n;j++)
{
if(save[i][j]=='.')
{
rr[i]=true,cc[j]=true; //當前行和列能掃描到
row[i].push_back(j);
col[j].push_back(i);
}
}
}
bool r=true,c=true; //是否所有的行或列能掃描到
for(int i=1;i<=n;i++)
if(!rr[i])
{
r=false;
break;
}
for(int i=1;i<=n;i++)
if(!cc[i])
{
c=false;
break;
}
if(!r&&!c) //行或列都掃描不到
{
printf("-1\n");
continue;
}
if(r) //如果行都能掃描到，直接輸出每一行的第一個可以放的位置
{
for(int i=1;i<=n;i++)
printf("%d %d\n",i,row[i][0]);
continue;
}
if(c) //對於列 同理
{
for(int i=1;i<=n;i++)
printf("%d %d\n",col[i][0],i);
continue;
}
}
return 0;
}
</SPAN>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
bool rr[120],cc[120];
char save[120][120];
vector<int>row[120];
vector<int>col[120];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(rr,false,sizeof(rr));
memset(cc,false,sizeof(cc));
for(int i=1;i<=n;i++)
{
row[i].clear();
col[i].clear();
}
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=n;j++)
{
if(save[i][j]=='.')
{
rr[i]=true,cc[j]=true; //當前行和列能掃描到
row[i].push_back(j);
col[j].push_back(i);
}
}
}
bool r=true,c=true; //是否所有的行或列能掃描到
for(int i=1;i<=n;i++)
if(!rr[i])
{
r=false;
break;
}
for(int i=1;i<=n;i++)
if(!cc[i])
{
c=false;
break;
}
if(!r&&!c) //行或列都掃描不到
{
printf("-1\n");
continue;
}
if(r) //如果行都能掃描到，直接輸出每一行的第一個可以放的位置
{
for(int i=1;i<=n;i++)
printf("%d %d\n",i,row[i][0]);
continue;
}
if(c) //對於列 同理
{
for(int i=1;i<=n;i++)
printf("%d %d\n",col[i][0],i);
continue;
}
}
return 0;
}
D. Biridian Forest
題目意思：
給一個n*m的矩陣，一個起始點和終點，矩陣中的數字表示該位置的魔鬼數量，當從起點到終點選擇一條路徑時，如果魔鬼能夠在人之前或同時到達該路徑某一位置，則人和魔鬼要打仗，選擇一條路徑，使得人與魔鬼打仗的個數最少。
解題思路：
該題主要是思維轉換。bfs+貪心
假設人當前選擇了一條路徑C->D，終點為Ｄ，某處魔鬼B 能夠和人C打仗，假設魔鬼在A位置與人打仗，則dis(B,A)<=dis(C,A) =>dis(B,A,D)<=dis(C,D) 如果選擇D終點，只需使得Min(dis(B,D))<=dis(C,D) 而dis(B,A,D)>=Min(dis(B,D)) 所以對於某一特定路徑，選擇終點D打仗比其他任何一點都好。
如果選擇從C-D的最短路，則能夠打仗的魔鬼數量就最少。
代碼：
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int dp[1100][1100],n,m;
char save[1100][1100];
bool vis[1100][1100];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct PP
{
int x,y;
};
PP s,e;
void bfs() //找到終點到任何一點的最短距離
{
queue<PP>myq;
myq.push(e);
while(!myq.empty())
{
PP f=myq.front();
myq.pop();
for(int i=0;i<4;i++)
{
int xx=f.x+dir[i][0],yy=f.y+dir[i][1];
if((save[xx][yy]=='S'||(save[xx][yy]>='0'&&save[xx][yy]<='9'))&&!vis[xx][yy])
{
//printf(":%d %d\n",xx,yy);
vis[xx][yy]=true;
dp[xx][yy]=dp[f.x][f.y]+1;
myq.push((PP){xx,yy});
} //不在方格裡的點為空的，不會掃描的
}
}
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=m;j++)
{
if(save[i][j]=='S')
s.x=i,s.y=j;
if(save[i][j]=='E')
e.x=i,e.y=j,dp[i][j]=0,vis[i][j]=true;
}
}
// printf("%d %d\n",e.x,e.y);
bfs();
int ans=0;
// printf("%d\n",dp[s.x][s.y]);
for(int i=1;i<=n;i++) //最短距離小的話，就直接加上
for(int j=1;j<=m;j++)
if(save[i][j]>'0'&&save[i][j]<='9'&&vis[i][j]&&dp[i][j]<=dp[s.x][s.y])
ans+=save[i][j]-'0';
printf("%d\n",ans);
}
return 0;
}
</SPAN>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int dp[1100][1100],n,m;
char save[1100][1100];
bool vis[1100][1100];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct PP
{
int x,y;
};
PP s,e;
void bfs() //找到終點到任何一點的最短距離
{
queue<PP>myq;
myq.push(e);
while(!myq.empty())
{
PP f=myq.front();
myq.pop();
for(int i=0;i<4;i++)
{
int xx=f.x+dir[i][0],yy=f.y+dir[i][1];
if((save[xx][yy]=='S'||(save[xx][yy]>='0'&&save[xx][yy]<='9'))&&!vis[xx][yy])
{
//printf(":%d %d\n",xx,yy);
vis[xx][yy]=true;
dp[xx][yy]=dp[f.x][f.y]+1;
myq.push((PP){xx,yy});
} //不在方格裡的點為空的，不會掃描的
}
}
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=m;j++)
{
if(save[i][j]=='S')
s.x=i,s.y=j;
if(save[i][j]=='E')
e.x=i,e.y=j,dp[i][j]=0,vis[i][j]=true;
}
}
// printf("%d %d\n",e.x,e.y);
bfs();
int ans=0;
// printf("%d\n",dp[s.x][s.y]);
for(int i=1;i<=n;i++) //最短距離小的話，就直接加上
for(int j=1;j<=m;j++)
if(save[i][j]>'0'&&save[i][j]<='9'&&vis[i][j]&&dp[i][j]<=dp[s.x][s.y])
ans+=save[i][j]-'0';
printf("%d\n",ans);
}
return 0;
}
E. Graph Reconstruction
題目意思：
給一幅圖，圖中任意結點的度數至多為2。
讓你重構一幅圖，要求:圖中節點和原來一樣，邊數數量也一樣，任意節點度數至多為2.
解題思路：
題中所說的圖的邊數最多為n.
1、隨機算法。
隨機m個點，連成m條邊，判斷每一條邊是否在給定的圖裡面，在的話，在隨機，都不在，則滿足題目要求，直接輸出就行了。
2、構造法。
當n<=7,直接暴力判斷
當n>7,一定存在一種構造滿足題意。
構造方法：
因為每個點的度數最多為2，所以每一個聯通塊要麼是一條線，要麼是一個環，首先根據聯通塊將節點分成若干部分。
然後將每一部分的節點的奇數位置節點提前。（保證相同部分的相鄰節點之間的連線不沖突）
然後選擇一個節點數量最多的那個部分，如果其節點數為偶數的話，交換頭兩個節點（防止環的情況尾和首相連有沖突），最後將其余各部分的節點從前之後依次插入。
最後按照給定的邊數，從前之後輸出相鄰的兩個節點構成一條邊，如果需要把最後一個節點和第一個節點連起來。
代碼：
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<time.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
vector<int>myv;
vector<int>vv[110000];
int n,m;
int main()
{
srand((unsigned)(time(NULL)));
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b;
myv.clear();
for(int i=1;i<=n;i++)
{
vv[i].clear();
myv.push_back(i);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
vv[a].push_back(b);
vv[b].push_back(a);
}
bool tt=false;
for(int i=1;i<=500;i++) //隨機次數
{
random_shuffle(myv.begin(),myv.end()); //隨機節點
bool flag=true;
for(int j=0;j<m&&flag;j++) //看是否滿足
{
int a=myv[j];
int b=myv[(j+1)%n];
for(int k=0;k<vv[a].size();k++)
if(b==vv[a][k])
flag=false;
}
if(flag) //滿足的話，直接輸出
{
for(int j=0;j<m;j++)
printf("%d %d\n",myv[j],myv[(j+1)%n]);
tt=true;
break;
}
}
if(!tt)
printf("-1\n");
}
return 0;
}
</SPAN>
#include<iostream>
#include<cmath>
#include<time.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
vector<int>myv;
vector<int>vv[110000];
int n,m;
int main()
{
srand((unsigned)(time(NULL)));
while(scanf("%d%d",&n,&m)!=EOF)
{
int a,b;
myv.clear();
for(int i=1;i<=n;i++)
{
vv[i].clear();
myv.push_back(i);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
vv[a].push_back(b);
vv[b].push_back(a);
}
bool tt=false;
for(int i=1;i<=500;i++) //隨機次數
{
random_shuffle(myv.begin(),myv.end()); //隨機節點
bool flag=true;
for(int j=0;j<m&&flag;j++) //看是否滿足
{
int a=myv[j];
int b=myv[(j+1)%n];
for(int k=0;k<vv[a].size();k++)
if(b==vv[a][k])
flag=false;
}
if(flag) //滿足的話，直接輸出
{
for(int j=0;j<m;j++)
printf("%d %d\n",myv[j],myv[(j+1)%n]);
tt=true;
break;
}
}
if(!tt)
printf("-1\n");
}
return 0;
}
