CF-192-diy-2 - c++编程基础 - C语言编程开发

#include
#include
#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] 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;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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] 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]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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];
vectorrow[120];
vectorcol[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",c

CF-192-diy-2 (二)