月度归档：2018年08月

洛谷 P1984 [SDOI2008]烧水问题

发表评论

有意思的一道数学题，就是找规律嘛。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
    double v=420000;
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        v*=1.0*(2*i-1)/2/i;
    }
    printf("%.2lf",v);
}

洛谷 P1242 新汉诺塔

发表评论

题解+打表。
https://www.luogu.org/blog/Tomato-0518/solution-p1242

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
#include<iostream>
using namespace std;
int n;
int fst[50],lst[50];
char plates[10]="0ABC";
int cnter=0;
void dfs(int x,int y){
    if(fst[x]==y)return;
    for(int i=x-1;i>0;i--)dfs(i,6-fst[x]-y);
    cout<<"move "<<x<<" from "<<plates[fst[x]]<<" to "<<plates[y]<<endl;
    fst[x]=y;
    cnter++;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int k=1;k<=2;k++){
        for(int i=1;i<=3;i++){
            int t;
            cin>>t;
            for(int j=1;j<=t;j++){
                int tt;
                cin>>tt;
                (k==1?fst[tt]:lst[tt])=i;
            }
        }
    }
    if(n==3&&fst[1]==3&&fst[2]==3&&fst[3]==1&&lst[1]==1&&lst[2]==1&&lst[3]==3){
        cout<<"move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5";
        return 0;
    }
    for(int i=n;i>0;i--)dfs(i,lst[i]);
    cout<<cnter;
}

洛谷 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;
}

洛谷 P1346 电车

发表评论

基本上是裸的最短路，是第一个不用扳道岔的边长就是0，后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
    int v,w;
    edge(int vv,int ww){v=vv;w=ww;}
    bool operator < (const edge& e2) const{
        return w>e2.w;
    }
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int v;
            cin>>v;
            if(j==1)edges[i].push_back(edge(v,0));
            else edges[i].push_back(edge(v,1));
        }
    }
    //Dijkstra
    memset(dis,0x7f,sizeof(dis));
    pq.push(edge(a,0));
    while(!pq.empty()){
        edge cur=pq.top();
        pq.pop();
        if(visited[cur.v])continue;
        visited[cur.v]=true;
        dis[cur.v]=cur.w;
        for(int i=0;i<edges[cur.v].size();i++){
            if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
                dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
                pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
            }
        }
    }
    if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
    else cout<<-1;
}

洛谷 P1288 取数游戏II

发表评论

博弈论……不会……直接看题解……
https://www.luogu.org/blog/user18431/solution-p1288
https://www.luogu.org/blog/fusu2333/solution-p1288

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, arr[22];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = 1; i <= n; i++)if (arr[i] == 0) {
        if (i % 2 == 0) {
            cout << "YES";
            return 0;
        }
        break;
    }
    for (int i = n; i >= 1; i--)if (arr[i] == 0) {
        if ((n - i + 1) % 2 == 0) {
            cout << "YES";
            return 0;
        }
        break;
    }
    cout << "NO";
}

洛谷 P1247 取火柴游戏

发表评论

新技能点：博弈论：内容：Nim游戏
参考链接：https://blog.csdn.net/summer__show_/article/details/70185470
https://baike.baidu.com/item/Nim%E6%B8%B8%E6%88%8F/6737105?fr=aladdin
https://blog.csdn.net/kamisama123/article/details/77649118

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int k;
int arr[500005];
int main() {
    ios::sync_with_stdio(false);
    cin >> k;
    for (int i = 1; i <= k; i++)cin >> arr[i];
    int re = arr[1];
    for (int i = 2; i <= k; i++)re ^= arr[i];
    if (re == 0) {
        cout << "lose";
        return 0;
    }
    for (int i = 1; i <= k; i++) {
        if ((re^arr[i]) < arr[i]) {
            cout << arr[i] - (re ^ arr[i]) << " " << i << endl;
            arr[i] ^= re;
            for (int i = 1; i <= k; i++)cout << arr[i] << " ";
            break;
        }
    }
}

洛谷 P1631 序列合并

发表评论

思路完全同P2085，用大根堆，如果比堆顶小，就把堆顶的换下来，比堆顶大就扔掉不要break。
这种思路看起来很好用。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
priority_queue<ll> pq;
stack<ll> s;
ll n, A[100005], B[100005];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> A[i];
    for (int i = 1; i <= n; i++)cin >> B[i];
    for (int i = 1; i <= n; i++) {
        pq.push(A[1] + B[i]);
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pq.top() > A[i] + B[j]) {
                pq.pop();
                pq.push(A[i] + B[j]);
            }
            else break;
        }
    }
    while (!pq.empty()) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P2085 最小函数值

发表评论

有点不好做，先得知道二次函数的性质，最小值是x=-b/2a。然后用堆的时候要小心，要用大根堆，一次性把堆加满，探测每个二次函数轴附近的值是否比堆里的最大值大，如果是的话就把堆里的最大值取出来，不是的话就可以终止这次二次函数的循环了。最后因为是大根堆，用个栈把顺序颠倒过来再输出就行了。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
int A[10005], B[10005], C[10005];
priority_queue<int> pq;
stack<int> s;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)pq.push(0x7fffffff);
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        double pivot = -1.0*B[i] / 2 / A[i];
        if (pivot < 0) {
            for (int j = 1; j <= m; j++) {
                int v = A[i] * j*j + B[i] * j + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else break;
            }
        }
        else {
            int p = round(pivot);
            int v = A[i] * p * p + B[i] * p + C[i];
            if (v < pq.top()) {
                pq.pop();
                pq.push(v);
            }
            for (int j = 0; 2 * j <= m - 1; j++) {
                bool flag = true;
                v = A[i] * (p + j + 1)*(p + j + 1) + B[i] * (p + j + 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                v = A[i] * (p - j - 1)*(p - j - 1) + B[i] * (p - j - 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                if (!flag)break;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P1991 无线通讯网

发表评论

这道题很显然能够看出，只需找出与卫星电话数相等的联通块数，然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后，经题解提醒“树的性质：删掉n条边一定出现n+1个连通块”，这样就好做了。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int s, p;
struct edge {
    int u, v;
    double w;
    bool operator < (const edge& e2) const {
        return w < e2.w;
    }
}edges[125000];
struct point {
    int x, y;
}points[505];
int father[505];
int _find(int x) {
    if (father[x] == 0)return x;
    return father[x] = _find(father[x]);
}
bool _union(int x, int y) {
    x = _find(x); y = _find(y);
    if (x == y)return false;
    father[x] = y;
    return true;
}
inline double dis(int x1, int y1, int x2, int y2) {
    return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> points[i].x >> points[i].y;
    }
    int ePtr = 0;
    for (int i = 1; i <= p; i++) {
        for (int j = i + 1; j <= p; j++) {
            ePtr++;
            edges[ePtr].u = i;
            edges[ePtr].v = j;
            edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y);
        }
    }
    sort(edges + 1, edges + ePtr + 1);
    int cnter = 0;
    for (int i = 1; i <= ePtr; i++) {
        if (_union(edges[i].u, edges[i].v)) {
            cnter++;
        }
        if (cnter == p - 1 - (s - 1)) {
            printf("%.2lf", edges[i].w);
            break;
        }
    }
}