P1601 遗址

思路：

这道题的思路跟四轮车很想，枚举四个点O(n4)O(n^4)肯定超时，这时，我们可以枚举两个点，再推出另外两个点的坐标，只要用哈希判重一下就可以了（当然也可以用set），看一下这两个点的坐标存不存在。时间复杂度O(n2)O(n^2)

枚举两个点A(x1,y1),B(x2,y2)A(x1,y1),B(x2,y2)另外两个点的坐标(x3,y3),(x4,y4)(x3,y3),(x4,y4)就是

$$ \begin{cases} x3=x1+(y2-y1)\\ y3=y1-(x2-x1)\\ x4=x2+(y2-y1)\\ y4=y2-(x2-x1) \end{cases} $$

或

$$ \begin{cases} x3=x1-(y2-y1);\\ y3=y1+(x2-x1);\\ x4=x2-(y2-y1);\\ y4=y2+(x2-x1); \end{cases} $$

另外两个点如果存在，则计算它的面积：

$$S_{正方形ABCD}\\ = (\sqrt{(x1-x2)^2+(y1-y2)^2})^2\\ = (x1-x2)^2+(y1-y2)^2\\ = (x1^2+x2^2-2x1x2)+(y1^2+y2^2-2y1y2) $$

写出代码：

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int MOD=10007;
int n,sum;
struct node{int x,y;}a[3001];
vector<node> v[MOD];
bool finds(int x,int y){
    int num=(x+y+20000)%MOD;
    for(int i=0;i<v[num].size();i++)if(v[num][i].x==x&&v[num][i].y==y)return true;
    return false;
}
int S(int x1,int y1,int x2,int y2){return (x1*x1+x2*x2-2*x1*x2)+(y1*y1+y2*y2-2*y1*y2);}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        v[(a[i].x+a[i].y+20000)%MOD].push_back((node){a[i].x,a[i].y});
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
			int x1=a[i].x,y1=a[i].y,x2=a[j].x,y2=a[j].y,x3=x1+(y2-y1),y3=y1-(x2-x1),x4=x2+(y2-y1),y4=y2-(x2-x1);
			if(finds(x3,y3)&&finds(x4,y4))sum=max(sum,S(x1,y1,x2,y2));
			x3=x1-(y2-y1);
			y3=y1+(x2-x1);
			x4=x2-(y2-y1);
			y4=y2+(x2-x1);
			if(finds(x3,y3)&&finds(x4,y4))sum=max(sum,S(x1,y1,x2,y2));
        }
    }
    cout<<sum;
    return 0;
}

洛谷 P1183 多边形的面积

题目描述

给出一个没有缺口的简单多边形，它的边是垂直或者水平的，要求计算多边形的面积。

多边形被放置在一个 xOyxOy 的笛卡尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数，因此多边形的面积也为整数。

注意：可能存在连续的三个顶点在一条直线上的情况。

输入格式

第一行给出多边形的顶点数 nn 。

接下来 nn 行，每行给出多边形一个顶点的坐标值 xx 和 yy，用空格隔开。

顶点按逆时针方向逐个给出。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。

输出格式

一行，一个整数，表示多边形的面积。

输入输出样例 #1

输入 #1

10
0 0
4 0
4 1
3 1
3 3
2 3
2 2
1 2
1 3
0 3

输出 #1

9

说明/提示

对于 100%100\% 的数据，1≤n≤1001 \le n \le 100，−200≤x,y≤200-200 \le x,y \le 200。

思路：

因为多边形的边跟坐标坐标轴是平行的，所以我们可以把它拆成几个三角形（三角形的面积可以用底乘高来求）。

代码：

#include<iostream>
using namespace std;
int n,x[101],y[101],sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	y[n+1]=y[1],x[n+1]=x[1];
	for(int i=1;i<=n;i++)sum+=(x[i]*y[i+1]-x[i+1]*y[i]);
	cout<<sum/2;
}

P1309. Cow Picnic

思路：

枚举牛们所在的农场，把那里当作起点，开始遍历每经过一个农场，这个农场的计数器加一，知道走不下去为止，最后如果这个农场经过了K头牛，那么这个地方就适合做野餐地点。

代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1000+1;
int n,k,m,u,v,a[101],farm[1001],sum;
bool flag[N];
vector<int> g[N];
void dfs(int u){
	farm[u]++;
	flag[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!flag[v]){
			dfs(v);
		}
	} 
}
int main(){
	cin>>m>>n>>k;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=m;i++){
		memset(flag,false,sizeof(flag));
		dfs(a[i]);
	}
	for(int i=1;i<=n;i++){
		if(farm[i]==m)sum++;
	}
	cout<<sum;
}

P1392. 寻找道路

思路：

第一步，建一个反图，从终点开始，向四周遍历，遍历到的每一个点把它标记起来；第二步，从起点开始，遍历四周的点，如果它没被遍历过且被标记过，那么就进行下一层的遍历。这个过程用广搜最好。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=1e4+1;
int n,k,s,t;
vector<int> g[N];//原图 
vector<int> f[N];//反向图 
bool flag[N],vis[N];
struct node{int x,s;};
void bfs_t(){
	queue<int> q;
	flag[t]=true;
	q.push(t);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<f[u].size();i++){
			int v=f[u][i];
			if(!flag[v]){
				q.push(v);
				flag[v]=true;
			}
		}
	}
	return;
}
bool check_t(int u){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!flag[v])return false;
	}
	return true;
}
void bfs_s(){
	queue<node> q;
	q.push((node){s,0});
	vis[s]=true;
	while(!q.empty()){
		node f=q.front();
		q.pop();
		for(int i=0;i<g[f.x].size();i++){
			int v=g[f.x][i];
			if(v==t){
				cout<<f.s+1;
				exit(0);
			}
			if(!vis[v]&&check_t(v)&&flag[v]){
				vis[v]=true;
				q.push((node){v,f.s+1});
			}
		}
	}
	cout<<"-1";
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v); //原图 
		f[v].push_back(u); //反向图 
	}
	cin>>s>>t;
	bfs_t();
	bfs_s();
	return 0;
}

总结：

这道题考的是思维能力，代码细节较多，建议多看几次题目。

P2267

这道题貌似模板，只要知道欧拉图的性质就行了，既所有点的度数为偶数。于是就有了下面这一段代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,a[1001];
int main(){
	while(cin>>n){
		if(n==0)return 0;
		cin>>m;
		memset(a,0,sizeof(a));
		int cnt=0;
		bool flag=true;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			a[u]++,a[v]++;
		}
		for(int i=1;i<=n;i++){
			if(a[i]%2==1||a[i]==0){
				flag=false;
				break;
			}
		}
		if(flag==false)cout<<"0\n";
		else cout<<"1\n";
	}
}

然后交上去就会发现90wa。

因为题目并没有说给出的图一定是连通图。

正确思路：

先从第一个节点开始深搜遍历，遍历到的点就标记起来，如果有没标记过的点，那么这个图就是非连通图，然后判断每个点的度数是否为偶数。

代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,a[1001];
bool f[1001];
vector<int> g[1001];
void dfs(int u){
	f[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!f[v])dfs(v);
	}
}
int main(){
	while(cin>>n){
		if(n==0)return 0;
		cin>>m;
		memset(a,0,sizeof(a));
		memset(f,false,sizeof(f));
		for(int i=1;i<=1000;i++)g[i].clear();
		int cnt=0;
		bool flag=true;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
			a[u]++,a[v]++;
		}
		dfs(1);
		for(int i=1;i<=n;i++){
			if(f[i]==false){
				flag=false;
			}
		}
		for(int i=1;i<=n;i++){
			if(a[i]%2==1||a[i]==0){
				flag=false;
				break;
			}
		}
		if(flag==false)cout<<"0\n";
		else cout<<"1\n";
	}
}

P1363

思路

计算每个点的度数，若一个点的度数为奇数，那么sum++，最后输出sum/2,（因为一条边可以连两个点）。

代码

#include<iostream>
using namespace std;
int n,m,a[1000001],sum;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		a[u]++,a[v]++;
	}
	for(int i=1;i<=n;i++){
		if(a[i]&1==1){
			sum++;
		}
	}
	cout<<sum/2;
}

P2293

模板的变形

思路

用Hierholzer算法，求欧拉路径，不过破损围栏的范围并不知道，需要用l和r求出最小的编号和最大的编号。

代码

#include<iostream>
#include<stack>
using namespace std;
int m,g[501][501],l=5000,r,node[501],cnt=1;
stack<int> s;
void dfs(int u){
	for(int i=l;i<=r;i++){
		if(g[u][i]){
			g[u][i]--;
			g[i][u]--;
			dfs(i);
		}
	}
	s.push(u);
}
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		l=min(min(l,u),v);
		r=max(max(r,u),v);
		g[u][v]++,g[v][u]++;
		node[u]++,node[v]++;
	}
	for(int i=l;i<=r;i++){
		if(node[i]&1==1){
			cnt=i;
			break;
		}
	}
	dfs(cnt);
	while(!s.empty()){
		cout<<s.top()<<"\n";
		s.pop();
	}
	return 0;
}

P2266单词游戏

思路：

如果我们以盘子为节点建图，会发现这样程序很难跑。换个思路，我们可以以一个单词的首尾字母为节点，再进行建图，最后再dfs判断是否为欧拉图或半欧拉图。不过要注意的是，需要判断此图是否为连通图。另外，盘子是不能反转的，也就是说这个图本质上是一个有向图，不过为了方便判断是否为连通图，我们可以建一个无向图，再根据欧拉图的性质写出判断欧拉图的代码。

代码：

#include<iostream>
#include<cstring>
using namespace std;
int t,n,g[27][27],nodes[27],nodet[27],flag[27];
void dfs(int u){
	flag[u]=2;
	for(int i=1;i<=26;i++){
		if(flag[i]==1&&g[u][i]){
			flag[i]=2;
			dfs(i);
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		memset(nodes,0,sizeof(nodes));
		memset(nodet,0,sizeof(nodet));
		memset(g,0,sizeof(g));
		memset(flag,-1,sizeof(flag));
		int k,a=0,b=0;
		bool f=true;
		cin>>n;
		for(int i=1;i<=n;i++){
			string z;
			cin>>z;
			int u=z[0]-'a'+1,v=z[z.size()-1]-'a'+1;
			g[u][v]++;
			g[v][u]++;
			nodes[u]++;//出度 
			nodet[v]++;//入度 
			k=u;
			flag[u]=flag[v]=1;
		}
		dfs(k);
		for(int i=1;i<=26;i++){
			int node=nodet[i]-nodes[i];
			if(node==1)a++;
			if(node==-1)b++;
			if(a>1||b>1||flag[i]==1){
				f=false;
				break;
			}
			if(node!=0&&node!=1&&node!=-1){
				f=false;
				break;
			}
			
		}
		if(!f)cout<<"The door cannot be opened.\n";
		else cout<<"Ordering is possible.\n";
	}
	return 0;
}

P2338划水

思路

建最短的边，使得原图变成欧拉图。算出每个节点需要的入度和出度，与周围最近的点进行匹配，最后输出建的新边长度之和。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,sum,s[100001],node[100001];
vector<int> in,out;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>node[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		s[u]--,s[v]++;//出度--入度++ 
	}
	for(int i=1;i<=n;i++){
		if(s[i]<0)for(int j=s[i];j<0;j++)in.push_back(node[i]);//需要入度
		if(s[i]>0)for(int j=1;j<=s[i];j++)out.push_back(node[i]); 
	} 
	sort(in.begin(),in.end());
	sort(out.begin(),out.end());
	for(int i=0;i<in.size();i++){
		sum+=abs(in[i]-out[i]);
	}
	cout<<sum;
}
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. 粤ICP备2024335011号
  3. Worker 0, 37ms
  4. Powered by Hydro v4.19.1 Community