【190801】计蒜客-Hong-Kong_2017

2019-08-01

目录

D题

最短路。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=1000+100;
struct Qnode
{
    int v;
    int c;
    Qnode(int _v=0, int _c=0):v(_v),c(_c){}
    bool operator<(const Qnode &r) const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}

};
vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];
int n,a,b,c,st,ed;
void Dijkstra(int n,int start)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=n;++i) dist[i]=INF;
    priority_queue<Qnode> que;
    while(!que.empty()) que.pop();
    dist[start]=0;
    que.push(Qnode(start,0));
    Qnode tmp;
    int u,v,cost;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        u=tmp.v;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=0; i<E[u].size(); ++i)
        {
            v=E[tmp.v][i].v;
            cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(Qnode(v,dist[v]));
            }
        }
    }
}
void addEdge(int u, int v, int w)
{
    E[u].push_back(Edge(v,w));
}

void init()
{
    for(int i=0;i<=n;++i) E[i].clear();
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        scanf("%d%d",&st,&ed);
        while(~scanf("%d",&a)&&a)
        {
            scanf("%d%d",&b,&c);
            addEdge(a,b,c);
            addEdge(b,a,c);
        }
        Dijkstra(n,st);
        printf("%d\n",dist[ed]);
    }
    return 0;
}

F题

暴力。

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
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int maxm = 1e3+10;
const double eps = 1e-12;
struct point
{
    double x,y;
};
point bi[maxm],user[maxn];//每个人的坐标不用存
double s[maxn];
char ss[maxn*10];//读取字符串
int n,m;
double get_dis(point a,point b)
{
    double t1 = a.x-b.x;
    double t2 = a.y-b.y;
    double res = sqrt(t1*t1 + t2*t2);
    return res;
}
void solve(int number )
{
    int ans = 0;
    double dis=0;
    for(int i=1;i<=m;i++)
    {
        dis = get_dis(user[number],bi[i]);
        if(dis - s[number] <=eps)
        {
            ans++;
        }

    }
    if(number==n)
    {
        printf("%d\n",ans);
    }
    else
    {
        printf("%d ",ans);
    }
    return ;
}

int main()
{


    while(~scanf("%d%d",&m,&n))
    {
        if(m==0&&n==0)
            break;
        for(int i=1;i<=m;i++)
            {
                scanf("%s",ss);
                sscanf(ss,"(%lf,%lf)",&bi[i].x,&bi[i].y);
            }
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ss);
            sscanf(ss,"(%lf,%lf)",&user[i].x,&user[i].y);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&s[i]);
        }
        for(int i=1;i<=n;i++)
            solve(i);
    }
    return 0;
}

G题

背包

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
//只要用的尽量少的硬币就好了,总数量尽量少
//因为题目保证升序，所以我正常顺序写就可以保证低额度的用的多
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;//这个可以用mem
const int maxn = 20+10;//最多10种硬币
const int maxv = 20000+10;//最多这么多。。但是考虑面值问题
int dp[maxv];
int ans[maxv][maxn];//达到V的时候每一个的最小花销
int money[maxn];
int n,v;
int main()
{
    while(~(scanf("%d%d",&v,&n)))
    {
        memset(dp,inf,sizeof(dp));
        memset(ans,0,sizeof(ans));
        dp[0] = 0;
        //一个完全背包,而且必须用完
        for(int i=1;i<=n;i++)
            scanf("%d",&money[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=v;j++)
            {
                if(j+money[i]>v)
                    break;
                else
                {
                    if(dp[j+money[i]] >= dp[j] +1)//尽量用面值小的
                    {
                        dp[j+money[i]] = dp[j] +1;
                        //维护最小花销,传递闭包
                        for(int k=1;k<=n;k++)
                            ans[j+money[i]][k] = ans[j][k];
                        ++ans[j+money[i]][i];
                    }
                }
            }
        }
        if(dp[v]==inf)
            printf("-1\n");
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(i==n)
                    printf("%d\n",ans[v][i]);
                else
                    printf("%d ",ans[v][i]);
            }
        }
    }
    return 0;
}

E题

二分答案。

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
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100000 + 10;
int a[N];
int L, S;

bool check(int mid)
{
    int l = 1;
    int num = L - 1;
    for (int i = 2; i <= S; ++i)
    {
        if (a[i] - a[l] >= mid)
        {
            l = i;
            --num;
            if (num == 0)
                return true;
        }
    }
    return false;
}

int main()
{
    while (scanf("%d%d", &S, &L) == 2 && L && S)
    {
        for (int i = 1; i <= S; i++)
            scanf("%d", &a[i]);
        sort(a + 1, a + 1 + S);
        int l = 0, r = a[S];
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", r);
    }
}

I题

打表找规律，偶数在杨辉三角中构成分形图，递归计算。

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
import java.lang.*;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    static BigInteger a[] = new BigInteger[201];
    static BigInteger p[] = new BigInteger[201];
    static BigInteger TWO = new BigInteger("2");
    static BigInteger TRI = new BigInteger("3");

    public static BigInteger f(BigInteger n) {
        int x = 0;
        for (int i = 0; i < 201; i++) {
            if (n.compareTo(p[i]) < 0) {
                x = i - 1;
                break;
            }
        }
        BigInteger t = n.subtract(p[x]);
        if (t.compareTo(BigInteger.ZERO) == 0)
            return a[x];
        BigInteger res = t.multiply(p[x].add(p[x]).subtract(BigInteger.ONE).subtract(t)).divide(TWO);
        return a[x].add(f(t).multiply(TWO)).add(res);
    }

    public static void main(String[] args) {
        p[0] = BigInteger.ONE;
        for (int i = 1; i < 200; i++) {
            p[i] = p[i - 1].multiply(TWO);
        }
        a[0] = a[1] = BigInteger.ZERO;
        for (int i = 2; i < 200; i++) {
            BigInteger t = p[i - 1].multiply(p[i - 1].subtract(BigInteger.ONE)).divide(TWO);
            a[i] = a[i - 1].multiply(TRI).add(t);
        }
        Scanner sc = new Scanner(System.in);
        BigInteger n;
        while (sc.hasNext()) {
            n = sc.nextBigInteger();
            System.out.println(f(n.add(BigInteger.ONE)));
        }
    }
}

A题

枚举y二分x。

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
67
import java.util.*;
import java.math.BigInteger;

public class Main {
    static BigInteger pow[][] = new BigInteger[100005][11];

    public static void main(String[] args) {

        for (int i = 1; i <= 100000; i++) {
            pow[i][0] = BigInteger.ONE;
            for (int j = 1; j <= 10; j++) {
                pow[i][j] = pow[i][j - 1].multiply(BigInteger.valueOf(i));
            }
        }
        String INF = "1";
        for (int i = 1; i <= 60; i++)
            INF = INF + "0";
        Scanner sc = new Scanner(System.in);
        int ca = sc.nextInt();

        while (ca-- != 0) {
            int n = sc.nextInt(), z = sc.nextInt();
            int X = 0, Y = 0;
            BigInteger ans = new BigInteger(INF);
            for (int i = 2; i < z; i++) {
                BigInteger num = pow[1][n].add(pow[i][n]).subtract(pow[z][n]);
                if (num.compareTo(BigInteger.ZERO) >= 0) {
                    if (num.compareTo(ans) == -1) {
                        ans = num;
                        X = 1;
                        Y = i;
                    }
                    continue;
                }
                int l = 1, r = i - 1;
                while (l < r) {
                    int mid = (l + r + 1 >> 1);
                    num = pow[mid][n].add(pow[i][n]).subtract(pow[z][n]);
                    if (num.compareTo(BigInteger.ZERO) == -1) {
                        l = mid;
                    } else
                        r = mid - 1;
                }
                num = pow[l][n].add(pow[i][n]).subtract(pow[z][n]);
                num = num.multiply(BigInteger.valueOf(-1));

                if (num.compareTo(ans) == -1) {
                    ans = num;
                    X = l;
                    Y = i;
                }
                if (l < i - 1) {
                    l++;
                    num = pow[l][n].add(pow[i][n]).subtract(pow[z][n]);
                    if (num.compareTo(ans) == -1) {
                        ans = num;
                        X = l;
                        Y = i;
                    }
                }
            }
            System.out.printf("%d %d ", X, Y);
            System.out.println(ans);
        }
        sc.close();
    }
}

B题

线段树，扫描线。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define lson l,mid,ls(root)
#define rson mid+1,r,rs(root)
const int maxn = 1e4+100;
int tree[maxn<<2];//求和
int tag[maxn<<2];//标记
void rev(int l,int r,int root)
{
    tag[root] ^= 1;//区间反转
    tree[root] = (r-l+1) - tree[root];//其实只有0 和(r-l+1)这两种情况。。
}
void push_down(int l,int r,int root)
{
    if(tag[root]==0)//没有被标记
    {
        return ;
    }
    else
    {
        int mid = l + ((r-l)>>1);
        rev(lson);
        rev(rson);
        tag[root] = 0;
        return ;
    }
}
void push_up(int root)
{
    tree[root] = tree[ls(root)]+tree[rs(root)];
}
void update(int x,int y,int number, int l,int r,int root)
{
    if(x<=l&&y>=r)
    {

        rev(l,r,root);
        return ;
    }
    push_down(l,r,root);//标记下传
    int mid = l + ((r-l)>>1);
    if(x<=mid) update(x,y,number,lson);
    if(y>mid) update(x,y,number,rson);
    push_up(root);
}
struct Node
{
    int x1,x2,y,flag;
    Node()
    {

    }
    Node(int x1,int x2,int y,int flag)
    {
        this->x1 = x1;
        this->x2 = x2;
        this->y = y;
        this->flag = flag;
    }
}node[maxn<<2];
bool cmp(Node a,Node b)//保证有序
{
    if(a.y==b.y)
        return a.flag>b.flag;
    else
        return a.y<b.y;
}
int main()
{
    int cnt = 0;
    int ans = 0;
    int j = 1;
    int x1,y1,x2,y2;
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(tree,0,sizeof(tree));
        memset(tag,0,sizeof(tag));
        cnt = 0;
        ans =0;
        for(int i=1;i<=m;i++)
        {

            scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
            node[++cnt] = Node(x1,x2,y1,1);//下位线
            node[++cnt] = Node(x1,x2,y2,-1);//上位线
        }
        sort(node+1,node+cnt+1,cmp);
        j = 1;//上位线本身算一个所以上位线本身不恢复
        for(int i=1 ; i<=n;i++)
        {
            while(node[j].y<=i&&node[j].flag==1&&j<=cnt)
            {
                update(node[j].x1,node[j].x2,1,1,n,1);
                j++;
            }
            ans += tree[1];
            while(node[j].y<=i&&j<=cnt)
            {
                update(node[j].x1,node[j].x2,1,1,n,1);
                j++;
            }
        }
        printf("%d\n",ans);
    }
}

H题

找规律。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1005;
const int M = 10005;
const int J = 10000000;

int n, m;
LL k[M];
char ch[N];

void print(LL a[])
{
    printf("%lld", a[a[0]]);
    for (int i = a[0] - 1; i; i--)
        printf("%07lld", a[i]);
    printf("\n");
}
int compare(LL a[], LL b[]) //-1:a=b  0:a<b  1:a>b
{
    if (a[0] != b[0])
        return a[0] > b[0];
    for (int i = a[0]; i; i--)
        if (a[i] != b[i])
            return a[i] > b[i];
    return -1;
}
void toBigInt(char s[], LL a[])
{
    int i, j, l = strlen(s);
    for (i = l, a[0] = 1; i > 6; i -= 7, a[0]++)
    {
        for (j = 0; j < 7; j++)
            a[a[0]] = a[a[0]] * 10 + s[i - 7 + j] - '0';
    }
    for (j = 0; j < i; j++)
        a[a[0]] = a[a[0]] * 10 + s[j] - '0';
}
void add(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = max(a[0], b[0]);
    for (int i = 1; i <= t[0]; i++)
        t[i] = a[i] + b[i];
    for (int i = 1; i <= t[0]; i++)
        t[i + 1] += t[i] / J, t[i] %= J;
    while (t[t[0] + 1])
        t[0]++;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void sub(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = a[0];
    for (int i = 1; i <= t[0]; i++)
        t[i] = a[i] - b[i];
    for (int i = 1; i < t[0]; i++)
        if (t[i] < 0)
            t[i + 1]--, t[i] += J;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void mul(LL a[], LL b[], LL c[])
{
    LL t[M] = {0};
    t[0] = a[0] + b[0];
    for (int i = 1; i <= a[0]; i++)
        for (int j = 1; j <= b[0]; j++)
            t[i + j - 1] += a[i] * b[j];
    for (int i = 1; i <= t[0]; i++)
        t[i + 1] += t[i] / J, t[i] %= J;
    while (t[t[0] + 1])
        t[0]++;
    while (!t[t[0]] && t[0] > 1)
        t[0]--;
    memcpy(c, t, sizeof(t));
}
void qpow(LL a[], LL x)
{
    LL t[M] = {1, 2, 0};
    a[0] = a[1] = 1;
    while (x)
    {
        if (x & 1)
            mul(a, t, a);
        mul(t, t, t);
        x >>= 1;
    }
}
void sum(LL t[], LL mid, LL tt[])
{
    qpow(t, mid - 1);
    tt[1] = n - 3;
    mul(t, tt, t);
    tt[1] = mid * 3;
    add(t, tt, t);
    tt[1] = n;
    sub(t, tt, t);
}

void solve()
{
    int l = 1, r = 4000, mid;
    LL t[M] = {0}, tt[M] = {1, 0};
    while (l < r)
    {
        mid = (l + r + 1) >> 1;
        sum(t, mid, tt);
        int cmp = compare(k, t);
        if (cmp == -1)
        {
            qpow(t, mid - 2);
            tt[1] = n - 1;
            mul(t, tt, t);
            tt[1] = 1;
            add(t, tt, t);
            print(t);
            return;
        }
        if (cmp)
            l = mid;
        else
            r = mid - 1;
    }
    sum(t, r, tt);
    sub(k, t, k);
    qpow(t, r);
    tt[1] = 2;
    sub(t, tt, t);
    add(k, t, t);
    print(t);
}
int main()
{
    while (scanf("%d", &n) == 1)
    {
        memset(k, 0, sizeof(k));
        if (n < 4)
        {
            scanf("%d", &m);
            if (n == 1)
            {
                if (m == 1)
                    printf("1\n");
                else
                    printf("-1\n");
            }
            else if (n == 2)
            {
                if (m < 3)
                    printf("%d\n", m);
                else
                    printf("-1\n");
            }
            else if (n == 3)
            {
                qpow(k, (m + 2) / 3);
                if (m % 3 == 1)
                    k[1]--;
                else if (m % 3 == 0)
                    k[1]++;
                print(k);
            }
        }
        else
        {
            scanf("%s", ch);
            toBigInt(ch, k);
            if (k[0] == 1 && k[1] <= n)
                print(k);
            else
                solve();
        }
    }
    return 0;
}
© 2019 blog - Powered by Hexo - Theme Chan