Week 10
P1636 Einstein学画画
-
知识点：欧拉路
-
存在欧拉路的条件：图是连通的，有且只有2个奇点。
存在欧拉回路的条件：图是连通的，有0个奇点。
-
-
思路：统计所有点的度数：如果是奇数结果加一；
如果是偶数则是途中的点，最后结果除以二。
注意：连成一串的点所有点的度都是偶数，但是可以一笔画完。
#include<bits/stdc++.h> using namespace std; int n, m, cnt[1005], ans; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; cnt[x]++; cnt[y]++; } for (int i = 1; i <= n; i++) { if (cnt[i]%2!=0) { ans++; } } if (ans == 0) { cout << 1; } else { cout << ans / 2; } system("pause"); return 0; }
P8654 [蓝桥杯 2017 国 C] 合根植物
-
知识点：并查集问题
#include<bits/stdc++.h> using namespace std; int root[1000005],ans=0,num[1000005]; int find(int x) { if(root[x]==x) return x; return root[x]=find(root[x]); } void unite(int a,int b) { int root1=find(a); int root2=find(b); if(root1!=root2) root[root2]=root1; } int main() { int n,m,k; cin>>n>>m; cin>>k; memset(num,0,sizeof(num)); for(int i=1;i<=n*m;i++) { root[i]=i; } for(int i=1;i<=k;i++) { int a,b; cin>>a>>b; unite(a,b); } for(int i=1;i<=n*m;i++) { num[find(i)]=1; } for(int i=1;i<=n*m;i++) { if(num[i]) ans++; } cout<<ans<<endl; return 0; }
P3958 [NOIP2017 提高组] 奶酪
- 知识点：并查集
- 思路：记录每个与上表面和下表面相交或相切的球，然后把每个球进行并查集的归类。把每个与上表面和下表面相交或相切的球进行并查集查找“父亲”的判断，如果是同一个“父亲”，则答案为可行。
#include<bits/stdc++.h>
using namespace std;
unsigned long long r, n, h, jud;
unsigned long long m[1005];
struct dong {
double x, y, z;
};
dong p[1005];
bool pd(dong a, dong b) {
long long d;
d = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
if (d <= 4 * r * r) return true;
else return false;
}
void run(int x) {
if (jud == 1) return;
if (p[x].z + r >= h) {
jud = 1;
return;
}
for (int i = 1; i <= n; i++) {
if (m[i] == 1) continue;
if (pd(p[x], p[i])) {
m[i] = 1;
run(i);
}
}
}
int main() {
int T;
cin >> T;
for (int j = 1; j <= T; j++) {
cin >> n >> h >> r;
jud = 0;
for (int i = 1; i <= n; i++) {
m[i] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y >> p[i].z;
}
for (int i = 1; i <= n; i++)
if (p[i].z <= r) {
m[i] = 1;
run(i);
}
if (jud == 1) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}
P1119 灾后重建
- 知识点：Floyd思想
#include<bits/stdc++.h>
using namespace std;
int n,m,q,now=0;
int tt[205],f[205][205];
void floyd(int k)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
return;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>tt[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) f[i][i]=0;
else f[i][j]=0x3ffffff;
}
}
int x,y,d;
for(int i=0;i<m;i++)
{
cin>>x>>y>>d;
f[x][y]=f[y][x]=d;
}
cin>>q;
int a,b,t;
for(int i=0;i<q;i++)
{
cin>>a>>b>>t;
while(tt[now]<=t&&now<n)
{
floyd(now);
++now;
}
if(tt[a]>t||tt[b]>t) cout<<-1<<endl;
else
{
if(f[a][b]==0x3ffffff) cout<<-1<<endl;
else cout<<f[a][b]<<endl;
}
}
return 0;
}
P2504 [HAOI2006]聪明的猴子
- 知识点：生成树
- 思路：把每条边进行Kruskal算法，然后加入到同一个连通图，每次更新最大边。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
double num=-1.0;
int a[1000005][3],ty[1000005],root[1000005];
struct tre{
int t1,t2;
double dis;
}tree[1000005];
int cmp(tre a,tre b)
{
return a.dis<b.dis;
}
int find(int x)
{
if(root[x]==x) return x;
return root[x]=find(root[x]);
}
int main()
{
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>ty[i];
}
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
}
int k=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
k++;
tree[k].t1=i;
tree[k].t2=j;
tree[k].dis=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));//计算边的大小
}
}
}
int pos=n;
sort(tree+1,tree+k+1,cmp);
for(int i=1;i<=n;i++)
{
root[i]=i;
}
for(int i=1;i<=k;i++)
{
if(pos==1) break;
int s1=find(tree[i].t1);
int s2=find(tree[i].t2);
if(s1!=s2)
{
root[s1]=s2;
pos--;
num=tree[i].dis;
}
}
for(int i=1;i<=m;i++)
{
if(num<=ty[i]) ans++;
}
cout<<ans<<endl;
return 0;
}