这道题本人在考场上只开了long long(华丽丽的60pts)
思路其实还是简单的,是NOIP考场上唯一看得懂的题目
以下是思考过程:
管道不会形成回路,即不会发生污水形成环流的情况
说明该图是个DAG(有向无环图)
污水只能从这些接收口流入排水系统
可看出搜索时只需从接收口开始
要求 p 与 q 互素
还要约分(STL里有__gcd
函数)
70pts
#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll long long
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
ll fz,fm;
}arr[MAXN];
node operator+(node a,node b){
node ans = (node){a.fz * b.fm + b.fz * a.fm,a.fm * b.fm};
return ans;
}
void dfs(int pos){
ll tmp = __gcd(arr[pos].fz,arr[pos].fm);
arr[pos].fz /= tmp;arr[pos].fm /= tmp;
if(s[pos])arr[pos].fm *= s[pos];
tmp = __gcd(arr[pos].fz,arr[pos].fm);
arr[pos].fz /= tmp;arr[pos].fm /= tmp;
for(re int i = h[pos];i != -1;i = nxt[i]){
if(s[e[i]] != 0)arr[e[i]] = arr[pos];
else arr[e[i]] = arr[e[i]] + arr[pos];
dfs(e[i]);
}
}
int main() {
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(re int i = 1;i <= n;i++){
scanf("%d",&s[i]);
arr[i].fm = 1;
for(re int j = 1;j <= s[i];j++){
int v;
scanf("%d",&v);
add(i,v);
}
}
for(re int i = 1;i <= m;i++){
arr[i].fz = arr[i].fm = 1;
dfs(i);
}
for(re int i = 1;i <= n;i++) {
if(s[i] == 0)printf("%lld %lld\n",arr[i].fz,arr[i].fm);
}
return 0;
}
这道题得分占了我NOIP将近二分之一的分数~
那么,为啥WA?
主要原因:数据过大,会爆LL
使用unsigned long long
会得到80分的好成绩
此处不再赘述
接下来咋办嘞?
我们发现此处:
node operator+(node a,node b){
node ans = (node){a.fz * b.fm + b.fz * a.fm,a.fm * b.fm};
return ans;
}
语句a.fm * b.fm
最容易爆
优化:取公因数约分即可
90pts:
#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll unsigned long long
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
ll fz,fm;
}arr[MAXN];
node operator+(node a,node b){
ll tmp = __gcd(a.fm,b.fm);//优化在这里!!!!!!
node ans = (node){a.fm / tmp * b.fz + b.fm / tmp * a.fz,a.fm / tmp * b.fm};
return ans;
}
void dfs(int pos){
ll tmp = __gcd(arr[pos].fz,arr[pos].fm);
arr[pos].fz /= tmp;arr[pos].fm /= tmp;
if(s[pos])arr[pos].fm *= s[pos];
tmp = __gcd(arr[pos].fz,arr[pos].fm);
arr[pos].fz /= tmp;arr[pos].fm /= tmp;
for(re int i = h[pos];i != -1;i = nxt[i]){
if(s[e[i]] != 0)arr[e[i]] = arr[pos];
else arr[e[i]] = arr[e[i]] + arr[pos];
dfs(e[i]);
}
}
int main() {
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(re int i = 1;i <= n;i++){
scanf("%d",&s[i]);
arr[i].fm = 1;
for(re int j = 1;j <= s[i];j++){
int v;
scanf("%d",&v);
add(i,v);
}
}
for(re int i = 1;i <= m;i++){
arr[i].fz = arr[i].fm = 1;
dfs(i);
}
for(re int i = 1;i <= n;i++) {
if(s[i] == 0)printf("%llu %llu\n",arr[i].fz,arr[i].fm);
}
return 0;
}
然而,数据范围还是过大~
这时候有两种选择:高精or long double
无论哪种选择,gcd都是大问题。
蒟蒻经过思考(ˇˍˇ) ~
发现:
a % b == a - a / b * b
在浮点数中,只需将a,b下取整即可。
下取整用floor函数
P.S.输出时加setprecision函数,防止答案以指数形式出现
100pts
#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll unsigned long long
#define ld long double
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
ld fz,fm;
}arr[MAXN];
ld gcd(ld a,ld b){
if(a < b)swap(a,b);
ld tmp = floor(a / b);
if(a - tmp * b <= 0.01)return b;//浮点数不能判等!!
return gcd(b,a - tmp * b);
}
node operator+(node a,node b){
ld tmp = gcd(a.fm,b.fm);
node ans = (node){a.fm / tmp * b.fz + b.fm / tmp * a.fz,a.fm / tmp * b.fm};
return ans;
}
void dfs(int pos){
ll tmp = gcd(arr[pos].fz,arr[pos].fm);
arr[pos].fz /= tmp;arr[pos].fm /= tmp;
if(s[pos]){
tmp = gcd(arr[pos].fz,(ld)s[pos]);
s[pos] /= tmp;
arr[pos].fm *= s[pos];
}
for(re int i = h[pos];i != -1;i = nxt[i]){
if(s[e[i]] != 0)arr[e[i]] = arr[pos];
else arr[e[i]] = arr[e[i]] + arr[pos];
dfs(e[i]);
}
}
int main() {
// ld a,b;
// cin >> a >> b;
// cout << gcd(a,b) << endl;//gcd写错来时用这里调试
memset(h,-1,sizeof h);
cin.tie(0);
cin >> n >> m;
for(re int i = 1;i <= n;i++){
cin >> s[i];
arr[i].fm = 1;
for(re int j = 1;j <= s[i];j++){
int v;
cin >> v;
add(i,v);
}
}
for(re int i = 1;i <= m;i++){
arr[i].fz = arr[i].fm = 1;
dfs(i);
}
for(re int i = 1;i <= n;i++) {//防止输出以诸如1e6的形式出现
if(s[i] == 0)cout << fixed << setprecision(0) << arr[i].fz << ' ' << arr[i].fm << endl;
}
return 0;
}
中考加氢!CSP2021加氢!NOIP2021加氢!
(氢的热值高于汽油)
%%%%%%%%%
当年赛场上,本来想到用高精或者unsigned long long 果断拿了90分走人