Hebuter Daily Training 201810
Hebuter Daily Training 201810
有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,W已经投掷了.求D获胜的概率.输出.0/1表示不可能获胜 1/1表示一定获胜.
题解:
根据题意的Note可知.假设$a = \max(Y, W);如果D >= a$.是$D$获胜.所以只要求 $(6-(a-1))/6$.分子分母约分.假设$x = 6 - a + 1. y = 6. z = gcd(x, y); ans = (x/z)/(y/z). $可以知道不可能有$0/1$的情况
`
#include <bits/stdc++.h>
using namespace std;
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
int Y,W;
cin >> Y >> W;
int a = max(Y, W);
int x = 6 - a + 1, y = 6, z = __gcd(x, y);
cout << x/z << "/" << y/z << endl;
return 0;
}B Interestring graph and Apples.
题目大意:
一个无向图被称作interesting.当且仅当它的顶点只属于一个 funny ring.funny ring的定义就是一个环可以遍历所有顶点 只有一次.一个圈也是一个funny ring.最少添加多少条边使得 当前图成为interesting.输出字典序最小的添加顺序.
题解:
可以肯定的是interesting graph就是一个funny ring.它有n个顶点 n条边.因为n个顶点n-1条边是树.多一条边就有一个环.如果再多一条边 就是多余两个环了.不满足定义.
一个图是一个funny ring当且仅当满足下面两个条件 A1. 每个点的度数是2. A2. 图是连通的
现在我们找到当一个图不是funny ring.但是通过添加边.可以转换成funny ring B1. m < n. 边的数量少于点的数量. B2. 没有环 B3. 每个点的度数都不超过2
我们需要添加一些边使得这些条件都满足.并且这个添加序列是字典序最小的. 所以我们按照如下规则添加边(i,j).
- i,j两个点的度数都小于2.(打破条件B3)
- i,j属于两个不同的连通分量(打破条件B2)
- (i,j)字典序最小
我们什么时候不能再添加边.当没有环的时候.每个连通分量是一颗树.因此至少 有一个点的度数小于2(根).如果有两个连通分量.连接的话就可以打破条件B1-B3 所以图连通,没有环,每个点的度数不超过2.意味着获得的图知识一条链.我们可以 连接它的结束的点获得一个funny ring.
通过上面的描述.算法:
- 检查是否满足条件A1,A2.如果满足.输出”YES” 和 0
- 检查是否满足B1.B2.不满足.输出”NO”
- 输出”YES” 和 n-m.(加入n-m条边)
- 按照描述添加边i,j.当(i,j)添加成功.输出”i j”
- 找到点i,j度数不超过2(i和j可以相等.如果n = 1). 输出 “i j”
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 55
int n,m;
int fa[MAX_N];
int in[MAX_N];
vector<int> G[MAX_N];
bool has[MAX_N];
struct P{
int u,v;
};
void init(){for(int i = 0; i < n; ++i) fa[i] = i;}
int findd(int x) {return x == fa[x] ? x : fa[x] = findd(fa[x]);}
void unite(int x, int y) {x = findd(x); y = findd(y); fa[x] = y;}
bool same(int x, int y) {return findd(x) == findd(y);}
bool dfs(int u, int fa){
int sz = G[u].size();
has[u] = true;
for(int i = 0; i < sz; ++i){
int v = G[u][i];
if(v == fa) continue;
if(has[v] || dfs(v, u)) return true;
}
return false;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
int u,v;
while(cin >> n >> m){
init();
memset(has, false, sizeof(has));
memset(in, 0, sizeof(in));
for(int i = 0; i < n; ++i) G[i].clear();
for(int i = 0; i < m; ++i){
cin >> u >> v;
++in[--u]; ++in[--v];
unite(u, v);
G[u].push_back(v);
G[v].push_back(u);
}
bool flag = false;
bool two = true; // 是不是都是2
int i;
for(i = 0; i < n; ++i) {
two &= (in[i] == 2 && same(0, i));
if(in[i] > 2) {flag = true; break;}
}
if(two){ // 满足所有点在一个联通快并且是一个环
puts("YES\n0"); continue;
}
if(flag || m >= n) {puts("NO"); continue;}
// 判断是不是有环
for(int i = 0; i < n; ++i){
if(!has[i]) {
if(dfs(i, -1)) {flag = true; break;}
}
}
if(flag) {puts("NO"); continue;}
puts("YES");
printf("%d\n", n - m);
vector<P> vp;
for(int i = 0; i < n; ++i){
if(in[i] >= 2) continue;
for(int j = 0; j < i; ++j){
if(in[j] < 2 && !same(i, j)) {
unite(i, j); // 连接i,j
++in[i]; ++in[j];
vp.push_back((P){i, j});
}
}
}
// 最后都在一个联通块.只剩下两个或者一个度数<2的
u = v = -1;
for(int i = 0; i < n; ++i){
if(in[i] < 2) {
if(u == -1) u = i;
else {v = i; break;}
}
}
// 只有一个结点的时候
if(v == -1) v = u;
vp.push_back((P){u, v});
for(int i = 0; i < n-m; ++i){
if(vp[i].u > vp[i].v) swap(vp[i].u, vp[i].v);
printf("%d %d\n", vp[i].u+1, vp[i].v+1);
}
}
return 0;
}emmm.第二天.
C.三角形
题目大意:
在$n*m$边长的网格中选择三个点可以组成的三角形个数。
题解
$n*m$边长的网格有
$(n+1)(m+1)$ 个点
我们要选择三个来组成三角形.
方案数就是$total=C_{(n+1)(m+1)}^3$.
但是这是所有情况.有些三个点是共线的.所以我们只要找出三个点共线的方案数$other$.
答案$ans=total-other$
在属于$other$的有下面三种情况:
- 横着的线有$m+1$条(横轴是$n$.纵轴是$m$).$other_1=(m+1)C_{n+1}^3$
- 竖着的先有$n+1$条.$other_2=(n+1)C_{m+1}^3$
- 斜着的.有斜率是正的斜着的.也有斜率是负的.但是我们只要算出斜率是正的.乘$2$即可.
解释一下第三种情况的计算：
斜线可以画一画图.
我们以$(0,0)$ 到 $(x,y)$ 的线$l_1$作为标准.$l_1$这样的线有$(n+1-x)(m+1-y)$条.
(emmm.这里也可以画一画).
这条线上的点是格点的有$x=gcd(x,y)-1$个
(emmm.这个结论详见《挑战程序设计竞赛》2.6章:数学问题的解题窍门).
所以只要$x>=1$.那么两端的点就可以和这$x$个点中任意一个组成一种方案.
$l1$这种线的方案数就是$2x(n+1-x)(m+1-y)$
所有$1<=x<=n.1<=y<=m$计算出来$other_3$.
最后$ans=total-(other_1+other_2+other_3)$.
时间复杂度$O(n*m)$
emm.顺便提一下.注意结果溢出.orz
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m;
LL C3(LL n) {
return n*(n-1)*(n-2)*1LL/6LL;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
++n; ++m;
LL ans = C3(n*m) - m*C3(n) - n*C3(m);
for(int i = 1; i < n; ++i){
for(int j = 1; j < m; ++j){
int x = __gcd(i, j) - 1; // (0, 0) 到 (i, j)中格子数目.不包含两端
if(x >= 1) { // 多于一个
ans -= (n - i) * (m - j) * x * 2LL;
}
}
}
cout << ans << endl;
return 0;
}