日度归档：11 8 月, 2018

洛谷 P1378 油滴扩展

发表评论

成功达成成就：很有困意的情况下写完了一道搜索题，而且不是一遍写对，是后来又查了错。。
困的情况下也能写出这种稍微有些麻烦的搜索题足见我功力之高（逃
需要注意一下输出时会出现的精度问题，否则WA两个点。
参考：https://www.luogu.org/blog/2002102430204070yl/solution-p1378

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int x01,y01,x02,y02;
struct point{
    int x,y;
    double r;
    bool occupied;
}points[10];
int arr[10];
double dis[10][10];
inline double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double checkR(int p){
    if(points[p].occupied)return 0;
    double r=min(min(abs(y01-points[p].y),abs(y02-points[p].y)),min(abs(x01-points[p].x),abs(x02-points[p].x)));
    for(int i=1;i<=n;i++){
        if(i==p||!points[i].occupied)continue;
        r=min(r,dis[p][i]-points[i].r);
    }
    if(r<0)r=0;
    points[p].r=r;
    points[p].occupied=true;
    for(int i=1;i<=n;i++){
        if(points[i].occupied)continue;
        if(r>=dis[p][i])points[i].occupied=true;
    }
    return r*r*3.1415926;
}
inline double dfs(int pos,double area){
    if(pos==n+1)return area;
    return dfs(pos+1,area+checkR(arr[pos]));
}
int main(){
    cin>>n;
    cin>>x01>>y01>>x02>>y02;
    for(int i=1;i<=n;i++)cin>>points[i].x>>points[i].y;
    for(int i=1;i<=n;i++)arr[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            double v=dist(points[i].x,points[i].y,points[j].x,points[j].y);
            dis[i][j]=dis[j][i]=v;
        }
    }
    double maxV=0;
    do{
        for(int i=1;i<=n;i++){
            points[i].r=0;
            points[i].occupied=false;
        }
        double v=dfs(1,0);
        maxV=max(maxV,v);
    }while(next_permutation(arr+1,arr+n+1));
    long long v=(long long)(abs(x01-x02)*abs(y01-y02)-maxV+0.5);
    cout<<v;
}

洛谷 P1144 最短路计数

发表评论

自己一开始写了个，才60分，效率不高，后来看了题解。
参考题解：https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
            }
        }
    }
}
void DFS(int node,int dist){
    if(dist!=dis[node])return;
    cnter[node]++;
    cnter[node]%=MOD;
    for(int e=fst[node];e!=-1;e=nxt[e]){
        if(visited[e])continue;
        visited[e]=true;
        DFS(v[e],dist+1);
        visited[e]=false;
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    memset(visited,false,sizeof(visited));
    DFS(1,0);
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

100分的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    cnter[1]=1;
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }else if(dis[v[e]]==dis[node]+1){
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }
        }
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}