【codeforces #284(div 1)】ABC题解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【codeforces #284(div 1)】ABC题解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9279字，纯文字阅读大概需要14分钟。
内容图文
Crazy Town is a plane on which there are n infinite line roads. Each road is defined by the equation aix?+?biy?+?ci?=?0, where ai andbi are not both equal to the zero. The roads divide the plane into connected regions, possibly of infinite space. Let‘s call each such region a block. We define an intersection as the point where at least two different roads intersect.
Your home is located in one of the blocks. Today you need to get to the University, also located in some block. In one step you can move from one block to another, if the length of their common border is nonzero (in particular, this means that if the blocks are adjacent to one intersection, but have no shared nonzero boundary segment, then it are not allowed to move from one to another one in one step).
Determine what is the minimum number of steps you have to perform to get to the block containing the university. It is guaranteed that neither your home nor the university is located on the road.
The first line contains two space-separated integers x1, y1 (?-?106?≤?x1,?y1?≤?106) — the coordinates of your home.
The second line contains two integers separated by a space x2, y2 (?-?106?≤?x2,?y2?≤?106) — the coordinates of the university you are studying at.
The third line contains an integer n (1?≤?n?≤?300) — the number of roads in the city. The following n lines contain 3 space-separated integers (?-?106?≤?ai,?bi,?ci?≤?106; |ai|?+?|bi|?>?0) — the coefficients of the line aix?+?biy?+?ci?=?0, defining the i-th road. It is guaranteed that no two roads are the same. In addition, neither your home nor the university lie on the road (i.e. they do not belong to any one of the lines).
Output the answer to the problem.
1 1 -1 -1 2 0 1 0 1 0 0
2
1 1 -1 -1 3 1 0 0 0 1 0 1 1 -3
2
Pictures to the samples are presented below (A is the point representing the house; B is the point representing the university, different blocks are filled with different colors):
计算几何。
求有多少直线与AB的交点的横坐标在AB之间。
要注意除数为0的情况！！
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#define eps 1e-9
using namespace std;
int main()
{
double x1,x2,y1,y2;
int n;
scanf("%lf%lf",&x1,&y1);
scanf("%lf%lf",&x2,&y2);
if (fabs(x1-x2)<eps)
{
int ans=0;
cin>>n;
if (y1>y2) swap(x1,x2),swap(y1,y2);
for (int i=1;i<=n;i++)
{
double ai,bi,ci;
cin>>ai>>bi>>ci;
if (fabs(bi-0.0)<eps)
continue;
else
{
double y=-(ci+ai*x1)/bi;
if (y>y1-eps&&y<y2+eps)
ans++;
}
}
cout<<ans<<endl;
return 0;
}
if (x1>x2) swap(x1,x2),swap(y1,y2);
double k=(y1-y2)/(x1-x2);
double b=y1-k*x1;
scanf("%d",&n);
int ans=0;
for (int i=1;i<=n;i++)
{
double ai,bi,ci;
scanf("%lf%lf%lf",&ai,&bi,&ci);
double x;
if (fabs(bi-0.0)<eps)
x=(-ci)/ai;
else
{
ai/=bi,ci/=bi,bi=1.0;
if (fabs(k+ai-0.0)<eps) continue;
x=-(ci+b)/(k+ai);
}
if (x>x1-eps&&x<x2+eps)
ans++;
}
cout<<ans<<endl;
return 0;
}
It turns out that you are a great fan of rock band AC/PE. Peter learned that and started the following game: he plays the first song of the list of n songs of the group, and you have to find out the name of the song. After you tell the song name, Peter immediately plays the following song in order, and so on.
The i-th song of AC/PE has its recognizability pi. This means that if the song has not yet been recognized by you, you listen to it for exactly one more second and with probability of pi percent you recognize it and tell it‘s name. Otherwise you continue listening it. Note that you can only try to guess it only when it is integer number of seconds after the moment the song starts playing.
In all AC/PE songs the first words of chorus are the same as the title, so when you‘ve heard the first ti seconds of i-th song and its chorus starts, you immediately guess its name for sure.
For example, in the song Highway To Red the chorus sounds pretty late, but the song has high recognizability. In the song Back In Blue, on the other hand, the words from the title sound close to the beginning of the song, but it‘s hard to name it before hearing those words. You can name both of these songs during a few more first seconds.
Determine the expected number songs of you will recognize if the game lasts for exactly T seconds (i. e. you can make the last guess on the second T, after that the game stops).
If all songs are recognized faster than in T seconds, the game stops after the last song is recognized.
The first line of the input contains numbers n and T (1?≤?n?≤?5000, 1?≤?T?≤?5000), separated by a space. Next n lines contain pairs of numbers pi and ti (0?≤?pi?≤?100, 1?≤?ti?≤?T). The songs are given in the same order as in Petya‘s list.
Output a single number — the expected number of the number of songs you will recognize in T seconds. Your answer will be considered correct if its absolute or relative error does not exceed 10?-?6.
2 2 50 2 10 1
1.500000000
2 2 0 2 100 2
1.000000000
3 3 50 3 50 2 25 2
1.687500000
2 2 0 2 0 2
1.000000000
f[i][j]表示在第j秒的时候辨认出第i首歌的可能性。
而这首歌可能是第1，2，3..t[i]秒,如果依次枚举的话就O(n^3)了。
但是我们发现i秒是可以从i-1秒转移过来的！乘上(1-p[i])再加上f[i-1][j]。
但是要注意最后一秒一定可以听出来，要特殊处理。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int t[5500],n,T;
double p[5500],f[5500][5500];
int main()
{
scanf("%d%d",&n,&T);
for (int i=1;i<=n;i++)
{
scanf("%lf%d",&p[i],&t[i]);
p[i]=(double)(p[i]/100);
}
f[0][0]=1.0;
double ans=0.0;
for (int i=1;i<=n;i++)
{
double x=0.0,k=pow(1.0-p[i],t[i]-1);
for (int j=i;j<=T;j++)
{
x=x*(1.0-p[i])+f[i-1][j-1];
if (j>=t[i])
{
x-=f[i-1][j-t[i]]*k;
f[i][j]=x*p[i]+f[i-1][j-t[i]]*k;
}
else
f[i][j]=x*p[i];
ans+=f[i][j];
}
}
printf("%.9lf\n",ans);
return 0;
}
You have written on a piece of paper an array of n positive integers a[1],?a[2],?...,?a[n] and m good pairs of integers (i1,?j1),?(i2,?j2),?...,?(im,?jm). Each good pair (ik,?jk) meets the following conditions: ik?+?jk is an odd number and 1?≤?ik?<?jk?≤?n.
In one operation you can perform a sequence of actions:
- take one of the good pairs (ik,?jk) and some integer v (v?>?1), which divides both numbers a[ik] and a[jk];
-
divide both numbers by v, i. e. perform the assignments:
and 
.
Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.
The first line contains two space-separated integers n, m (2?≤?n?≤?100, 1?≤?m?≤?100).
The second line contains n space-separated integers a[1],?a[2],?...,?a[n] (1?≤?a[i]?≤?109) — the description of the array.
The following m lines contain the description of good pairs. The k-th line contains two space-separated integers ik, jk (1?≤?ik?<?jk?≤?n,ik?+?jk is an odd number).
It is guaranteed that all the good pairs are distinct.
Output the answer for the problem.
3 2 8 3 8 1 2 2 3
0
3 2 8 12 8 1 2 2 3
2
二分图最大匹配。
题目中说ik+jk是奇数，那么这些点符合二分图性质（左边是奇数右边是偶数即可）。
把每个数质数拆分，能拆成多个p[i]的话也要拆成多个点；
然后对于有边相连的数的相同质数连边。
最大匹配就是答案。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
vector<pair<int,int> > v[2];
int tot=1,u[105][105],h[100005],cnt=0;
int my[10000],check[100005],a[105],ti,p[100000],V[10000];
struct edge
{
int y,ne;
}e[100000];
void Prepare()
{
for (int i=2;i<=100000;i++)
if (!check[i])
{
p[++cnt]=i;
for (int j=i;j<=100000;j+=i)
check[j]=1;
}
}
void chai(int x)
{
for (int i=1;i<=cnt;i++)
if (a[x]!=1)
{
while (a[x]%p[i]==0)
{
a[x]/=p[i];
v[x%2].pb(mp(x,p[i]));
}
}
if (a[x]>1)
v[x%2].pb(mp(x,a[x]));
}
void Addedge(int x,int y)
{
e[++tot].y=y;
e[tot].ne=h[x];
h[x]=tot;
}
bool dfs(int x)
{
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (V[y]!=ti)
{
V[y]=ti;
if (!my[y]||dfs(my[y]))
{
my[y]=x;
return true;
}
}
}
return false;
}
int main()
{
Prepare();
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]),chai(i);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
u[x][y]=u[y][x]=1;
}
int l=v[0].size();
for (int i=0;i<v[0].size();i++)
for (int j=0;j<v[1].size();j++)
if (u[v[0][i].f][v[1][j].f]&&v[0][i].s==v[1][j].s)
Addedge(i+1,j+1+l);
int ans=0;
for (int i=1;i<=l;i++)
{
ti++;
if (dfs(i)) ans++;
}
cout<<ans<<endl;
return 0;
}
感悟：
1.计算几何要注意除数为0
2.如果满足二分图性质的想最大匹配
原文：http://blog.csdn.net/regina8023/article/details/44247059
内容总结
以上是互联网集市为您收集整理的【codeforces #284(div 1)】ABC题解全部内容，希望文章能够帮你解决【codeforces #284(div 1)】ABC题解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。