Dylan's Blog
0%

Posted on Edited on In

8月11日 Codeforces Round #503 题目链接：http://codeforces.com/contest/1020

A - New Building for SIS & B - Badge

过水，不说。。

C - Elections

思路： 算是一个比较简单的模拟（但是好像有大佬有$O(nlogn)$的做法）。。。枚举要得到多少选票，设为$x$，如果有其他党的选票大于x，就直接花钱买直到那个党选票小于x，如果这样最后选票不够x的话，就随便买选票直到有x张。这里买选票当然是尽可能买便宜的，然后总复杂度是$O(n^3)$的。

比赛时T了一发，然后大力卡了一下常数过了pretest。结果就很愉快地的因为TLE FST了….后面把最外层循环从1-n改为1-n/2+1就A了，想想自己真TM傻，卡常时这个都没有注意到。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#define LL long long
#define MAXN 3005
#define INF 1e18
using namespace std;

int n, m, p[MAXN], num[MAXN];
LL c[MAXN], ans=INF;

struct A {int p, tag; LL c;} a[MAXN];

void read1(LL &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

void read2(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

bool CMP1(A x, A y)
{
    if(x.p!=y.p) return x.p<y.p;
    else return x.c<y.c;
}

bool CMP2(A x, A y)
{
    return x.c<y.c;
}

int main()
{
    read2(n); read2(m);
    for(register int i=1; i<=n; ++i) read2(a[i].p), read1(a[i].c), num[a[i].p]++;
    for(register int i=1; i<=n/2+1; ++i)
    {
        sort(a+1, a+n+1, CMP1);
        for(register int j=1; j<=n; ++j) a[j].tag=0;
        LL cost=0; int res=0, pnt=1;
        for(register int j=1; j<=m; ++j)
        {
            if(j==1)
            {
                pnt+=num[j];
                res+=num[j];
                continue;
            }
            for(register int k=pnt; k<=pnt+num[j]-i; ++k)
            {
                cost+=a[k].c; a[k].tag=1;
                res++;
            }
            pnt+=num[j];
        }
        sort(a+1, a+n+1, CMP2);
        for(register int j=1; res<i; ++j)
        {
            if(a[j].tag || a[j].p==1) continue;
            res++;
            cost+=a[j].c;
        }
        ans=min(ans, cost);
    }
    printf("%lld\n", ans);
}

D - The hat

思路： 交互题，比赛时少看到一个条件连题目都没有弄懂。菜死了QWQ

相邻的同学手上数字不会相差超过1，这是一个很神奇的条件。我们设数组$b[i]=a[i]-a[i+n/2]$，根据上面的条件可以发现$b[i]-b[i+1]$只能为$\lbrace -2, 0, 2 \rbrace$，在某种意义下我们可以把数组$b$的取值视为是连续的，这个性质也很有意思。

显然有$b[i]=-b[i+n/2]$，答案也就是求一点$i$使得$b[i]=0$。因为上面的性质，我们就可以使用二分求解。有一点要注意的是如果$b$中有一个元素为奇数时，那么$b$中的所有元素都是奇数，这样就直接输出-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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, ans, a[MAXN], b[MAXN];

int main()
{
    scanf("%d", &n);
    printf("? %d\n", 1); fflush(stdout);
    scanf("%d", &a[0]);
    printf("? %d\n", n/2+1); fflush(stdout);
    scanf("%d", &a[n/2]);
    b[0]=a[0]-a[n/2]; b[n/2]=a[n/2]-a[0];
    if(b[0]%2) {printf("! -1\n"); fflush(stdout); return 0;};
    int l=0, r=n/2;
    while(1)
    {
        int mid=(l+r)/2;
        printf("? %d\n", mid+1); fflush(stdout);
        scanf("%d", &a[mid]);
        printf("? %d\n", n/2+mid+1); fflush(stdout);
        scanf("%d", &a[n/2+mid]);
        b[mid]=a[mid]-a[n/2+mid];
        if(b[mid]==0) {ans=mid; break;}
        if(b[mid]*b[l]<0) r=mid;
        else l=mid;
    }
    printf("! %d", ans+1);
}

E - Sergey’s problem

思路： 神题啊。。。首先有一个很简单的思路，假设一个确定了$1~i-1$号节点的集合，那么对于$i$号节点，如果集合中的点不与节点$i$相邻，那么就把$i$号节点加入集合中。

那么这样就会有一个问题，就是可能会有节点无法加入集合，并且集合中的点无法到达它（CF上第三个点就能够HACK掉）。于是我们先从小到大扫一遍确定出一个集合，集合内编号小的点不会向编号大的点连边。然后从大到小扫一遍这个集合，如果编号大的点有一条边连向了集合内编号小的点，那就把编号小的点移除集合。这样就可以保证满足题目的条件，因为第二遍移出集合的点一定能一步内到达，第一遍移出集合的点一定能两步内到达。

代码：

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 <cstring>
#include <cstdio>
#define MAXN 1000005
using namespace std;

int n, m, cnt, top, head[MAXN], ans[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i]) for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to>i) vis[edge[j].to]=1;
    for(int i=n; i>=1; i--)
        if(!vis[i])
        {
            ans[++top]=i;
            for(int j=head[i]; j; j=edge[j].next) vis[edge[j].to]=1;
        }
    printf("%d\n", top);
    for(int i=1; i<=top; i++) printf("%d ", ans[i]);
}

Posted on Edited on In

问题描述：

给定整数$N$，求$1<=x,y<=N$且$gcd(x, y)$为素数的数对$(x, y)$有多少对

输入：

一个数$N$（$1<=N<=10^7$）

输出：

满足条件的对数

思路：

这题有莫比乌斯反演的做法。。。其实不用反演的做法感觉更好想。

看完数据范围，做法应该就是在$O(n)$左右的。我们可以先筛出范围内的素数，然后可以暴力对每个素数$pri[i]$计算范围内$gcd(x, y)=pri[i]$的对数。

范围内$gcd(x, y)=pri[i]$的对数也就相当于在$1<=x,y<= N/pri[i]$范围内互素的个数。在某个范围内互素的个数就是欧拉函数的前缀和*2+1，因此这个我们可以$O(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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 10000007
#define LL long long
using namespace std;

int n, cnt, pri[MAXN];
LL ans, phi[MAXN];
bool vis[MAXN];

int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        if(!vis[i]) pri[++cnt]=i, phi[i]=i-1;
        for(int j=1; j<=cnt && i*pri[j]<=n; j++)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0) {phi[i*pri[j]]=pri[j]*phi[i]; break;}
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
    for(int i=2; i<=n; i++) phi[i]+=phi[i-1];
    for(int i=1; i<=cnt; i++) ans+=phi[n/pri[i]]*2+1;
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述：

给你一个$n*n$的矩阵$A$和一个整数$k$，需要你求出矩阵$S=A+A^2+A^3+···+A^K$

输入：

第一行三个整数$n(n<=30), k(k<=10^9), m(m<=10000)$

输出：

输出模$m$意义下的矩阵$S$

思路：

一道矩阵的好题。我们一般都是将矩阵用于加速递推上，这道题却是让你求一个矩阵。

虽然要你求一个矩阵，然而一样可以使用矩阵加速递推的思路。我们可以将式子$A+A^2+A^3+···+A^K$看作是由$A+A^2+A^3+···+A^{k-1}$乘上$A$再加$A$递推而来，递推的初始值就是$A$。

代码：

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 <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n, k, m, a[100][100], b[100][100];

void mul(int a[100][100], int b[100][100])
{
    int c[100][100];
    memset(c, 0, sizeof(c));
    for(int i=1; i<=n*2; i++)
        for(int j=1; j<=n*2; j++)
            for(int k=1; k<=n*2; k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;
    memcpy(a, c, sizeof(c));
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
        a[i][i+n]=a[i+n][i+n]=1;
    }
    memcpy(b, a, sizeof(b));
    while(k)
    {
        if(k&1) mul(b, a);
        k>>=1; mul(a, a);
    }
    for(int i=1; i<=n; i++) b[i][i+n]=(b[i][i+n]-1+m)%m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) printf("%d ", b[i][j+n]);
        printf("\n");
    }
}

Posted on Edited on In

8月11日 2018百度之星初赛 (A) 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=825

1001 - 度度熊拼三角

思路： 我们将木棒长度排序之后，可以发现我们要选的三根木棒一定是连续的，因为连续了才最优嘛。于是我们扫一遍，碰到符合要求的就记录下答案。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define MAXN 1005
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n, a[MAXN], ans;

vector<int> vec;

bool check(int x)
{
    if(a[x]>=a[x-1]+a[x-2]) return false;
    return true;
}

int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        ans=-1;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        sort(a+1, a+n+1);
        for(int i=n; i>=3; i--)
            if(check(i))
            {
                ans=a[i]+a[i-1]+a[i-2];
                break;
            }
        printf("%d\n", ans);
    }
}

1002 - 度度熊学队列

思路： 神TM，我以为区间翻转要splay。。。像我这么菜不会splay，于是比赛是就弃掉这题了。。

看题解说用双向链表模拟，突然醒悟过来，于是码了一发。其中有很多细节要注意，特别是指针什么的。但码完后发现区间翻转并不是O(1)的，复杂度也并没有保证，数据强一点就会卡掉，O(1)的区间翻转我不知道到底怎么写QWQ，哪位大佬教一下啊。。

虽然复杂度没有保证，但还是A了，可能是数据水吧。。

代码：

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1500005
using namespace std;

void read(int &x)
{
    char ch = getchar(); x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int n, Q;

struct Link
{
    int val;
    Link *nxt, *pre;
} *head[MAXN], *tail[MAXN];

int main()
{
    while(scanf("%d%d", &n, &Q)!=EOF)
    {
        for(int i=1; i<=n; i++) tail[i]=head[i]=NULL;
        for(int i=1; i<=Q; i++)
        {
            int op, u, v, w, val;
            read(op);
            if(op==1)
            {
                read(u); read(w); read(val);
                Link *temp=new Link;
                temp->val=val;
                if(w==0)
                {
                    if(!head[u])
                    {
                        temp->pre=temp->nxt=NULL;
                        head[u]=tail[u]=temp;
                    }
                    else
                    {
                        temp->nxt=head[u];
                        temp->pre=NULL;
                        head[u]->pre=temp;
                        head[u]=temp;
                    }
                }
                else
                {
                    if(!tail[u])
                    {
                        temp->pre=temp->nxt=NULL;
                        head[u]=tail[u]=temp;
                    }
                    else
                    {
                        temp->nxt=NULL;
                        temp->pre=tail[u];
                        tail[u]->nxt=temp;
                        tail[u]=temp;
                    }
                }
            }
            if(op==2)
            {
                read(u); read(w);
                if(w==0)
                {
                    if(!head[u]) printf("-1\n");
                    else
                    {
                        printf("%d\n", head[u]->val);
                        if(head[u]!=tail[u])
                        {
                            head[u]=head[u]->nxt;
                            free(head[u]->pre);
                            head[u]->pre=NULL;
                        }
                        else free(head[u]), tail[u]=head[u]=NULL;
                    }
                }
                else
                {
                    if(!tail[u]) printf("-1\n");
                    else
                    {
                        printf("%d\n", tail[u]->val);
                        if(head[u]!=tail[u])
                        {
                            tail[u]=tail[u]->pre;
                            free(tail[u]->nxt);
                            tail[u]->nxt=NULL;
                        }
                        else free(tail[u]), tail[u]=head[u]=NULL;
                    }
                }
            }
            if(op==3)
            {
                read(u); read(v); read(w);
                if(!tail[v]) continue;
                if(w)
                {
                    Link *temp=head[v];
                    while(temp)
                    {
                        swap(temp->pre, temp->nxt);
                        temp=temp->pre;
                    }
                    swap(head[v], tail[v]);
                }
                if(tail[u])
                {
                    head[v]->pre=tail[u];
                    tail[u]->nxt=head[v];
                }
                else head[u]=head[v];
                tail[u]=tail[v];
                head[v]=tail[v]=NULL;
            }
        }
    }
}

1003 - 度度熊剪纸条

思路： 首先头和尾的两段1（如果存在的话）把他们剪出来只需要一刀。中间部分的一段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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 1000005
using namespace std;

int n, k, a[MAXN], f[MAXN];

struct B {int val, cost;} b[MAXN];

int main()
{
    while(scanf("%d%d", &n, &k)!=EOF)
    {
        int head, tail, cnt=0, tot=0;
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++) scanf("%1d", &a[i]);
        for(head=1; a[head]; head++) ;
        if(head!=1) b[++tot].val=head-1, b[tot].cost=1;
        for(tail=n; a[tail]; tail--) ;
        if(tail!=n && tail!=0) b[++tot].val=n-tail, b[tot].cost=1;
        for(int i=head; i<=tail; i++)
        {
            if(a[i]==0 && cnt)
            {
                b[++tot].val=cnt;
                b[tot].cost=2;
                cnt=0;
            }
            if(a[i]==1) cnt++;
        }
        if(k==0) {printf("%d\n", head-1); continue;}
        for(int i=1; i<=tot; i++)
            for(int j=k+1; j>=b[i].cost; j--) f[j]=max(f[j], f[j-b[i].cost]+b[i].val);
        printf("%d\n", f[k+1]);
    }
}

Posted on Edited on In

8月12日 2018百度之星初赛 (B) 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=826

1001 - degree

思路： 一道比较简单的结论题吧。。。我们贪心地找出一个度数最多的点，当不考虑K时，我们可以将其他的联通块都接在这个点上。当我们考虑K时，我们就可以从联通块上拆下K个点，再接到度数最多的点上，注意一下有没有K个点够拆就好了。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int maxd=0;
        memset(deg, 0, sizeof(deg));
        scanf("%d%d%d", &n, &m, &k);
        for(int i=1; i<=m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            deg[x]++, deg[y]++;
            maxd=max(maxd, max(deg[x], deg[y]));
        }
        if(k>m-maxd) printf("%d\n", n-1);
        else printf("%d\n", n-m+maxd+k-1);
    }
}

1003 - odds

思路： 特别好的一道题吧。。。

我们可以把每个叶子节点到根的路径提出来，这样问题可以简化为：一个路径上有K条边，分别有权值$x_1, y_1, x_2, y_2····x_k,y_k$，其中$y_i>=x_i$的。你需要从中选$x$条边取$y_i$，其余边取$x_i$，使这些的乘积最大。根据题目要求，求这个的复杂度应该要在$O(nlogn)$以内的。

于是我们可以想到一个贪心的方法，对于这$K$条边，我们选其中$y_i*x_i$最大的x条边取$y_i$，其余的取$x_i$。证明也很简单：假如已经处理出了前$i-1$条边（$i$是应该大于$x$的，否则直接取$y_i$）乘积为$w$。我们考虑第$i$条边：如果第$i$条边取$x_i$，那么乘积为$w*x_i$；如果取$y_i$，那么我们就需要从前$x$条取$y$边中，选出一条边$j$，让它值变为$x_j$，这样乘积就为$w_i*y_i*(x_j/y_j)$。不难看出我们希望乘积尽可能大，那么就需要选$y_i*x_i$尽可能大的边。

有了这个贪心策略后，实现就不难了。用一个multiset动态维护路径上$y_i*x_i$前$x$大的边，同时计算出答案，回溯时要将答案和multiset复原。注意，千万不能对于每一个叶子节点都重新算一遍答案，我比赛时就是这样SB的都算一遍，然后T飞了，比完赛才反应过来。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#define MAXN 200005
#define p 1000000007
#define LL long long
using namespace std;

int T, n, k, cnt, head[MAXN];
LL ans[MAXN], inv[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];
struct Node
{
    LL x, y;
    bool friend operator < (Node a, Node b)
    {
        return a.y*b.x<b.y*a.x;
    }
} node[MAXN];

multiset<Node> st;
multiset<Node>::iterator it;

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void dfs(int x, LL val)
{
    int maxd=-1;
    for(int i=head[x]; i; i=edge[i].next) maxd=max(maxd, edge[i].dis);
    if(maxd==-1) ans[x]=val;
    for(int i=head[x]; i; i=edge[i].next)
    {
        node[i].x=edge[i].dis;
        node[i].y=maxd;
        Node top= *st.begin();
        LL tag=0, temp=val;
        if(st.size()<k)
        {
            tag=1;
            st.insert(node[i]);
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else if(top<node[i])
        {
            tag=2;
            st.erase(st.begin());
            st.insert(node[i]);
            temp=temp*inv[top.y]%p*top.x%p;
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else temp=temp*inv[200000]%p*node[i].x%p;
        dfs(edge[i].to, temp);
        if(tag==1)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
        }
        if(tag==2)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
            st.insert(top);
        }
    }
}

int main()
{
    inv[0]=inv[1]=1;
    for(int i=2; i<=200000; i++) inv[i]=inv[p%i]*(p-p/i)%p;
    scanf("%d", &T);
    while(T--)
    {
        cnt=0;
        memset(head, 0, sizeof(head));
        memset(ans, -1, sizeof(ans));
        scanf("%d%d", &n, &k);
        for(int i=1; i<n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            x++, y++;
            addedge(x, y, z);
        }
        dfs(1, 1);
        for(int i=1; i<=n; i++) if(ans[i]!=-1) printf("%lld\n", ans[i]);
    }
}

1004 - p1m2

思路： 二分应该能够很容易的看出来，对于二分值大的就计算一下正的贡献，小于二分值的计算负的贡献，判断正负贡献是否大于0。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, x[300005], y[300005];

bool check(int mid)
{
    LL res=0;
    memcpy(y, x, sizeof(x));
    for(int i=1; i<=n; i++)
    {
        if(y[i]>mid+1) res+=(y[i]-mid)/2;
        if(y[i]<mid) res-=(mid-y[i]);
    }
    return res>=0;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int ans=0;
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &x[i]);
        int l=0, r=1e8;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid)) ans=mid, l=mid+1;
            else r=mid-1;
        }
        printf("%d\n", ans);
    }
}

1006 - rect

思路： 题目有一句比较重要的话就是$x_i,y_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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int w, h, x, y;
        LL ans=0;
        scanf("%d%d%d", &w, &h, &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &x, &y);
            ans+=min(min(x, y), min(w-x, h-y));
        }
        printf("%lld\n", ans);
    }
}