newcoder-contest2

ACM

newcoder contest2 补题


比赛的链接

G transform

题意

给一个坐标轴上若干个点，然后上面放了若干个货物。
确定一个定点，然后可以将货物移到这个点上面，花费为\( 2 \left| (x_i-x_j) \right| \),总花费不能超过T。
问最多能将多少数量的货物集中到一个点上面

题解

这种最大最小值的问题，往往一开始要想到二分答案。
然后先确定固定的点，然后递推的计算代价，若找到符合条件的组合，立刻退出，具体的过程可以看我的注释

ac code

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
#include<bits/stdc++.h>
#define gs(c) (c < '0' || c > '9')
#define gc(c) c = getchar()
#define getint() ({ int w = 0; char gc(c); while (gs(c)) gc(c); while (!gs(c)) w = w*10+c-'0', gc(c); w; })
#define d(i, j) (int64)(x[j] - x[i])
using namespace std;
const int N = 500050;
typedef long long int64;
int n, x[N], a[N];
int64 T, s[N];
int64 sum(int l, int lc, int r, int rc) {
	return l == r? rc - lc: s[r - 1] - s[l] + a[l] - lc + rc;
}
bool check(int64 need) {
	int l = 1, lc = 1, r = n + 1, rc = 1;
	//lc, rc分别表示向a[l], a[r]借用了多少的货物
	int64 cur = 0, sa = 0;
	for (int i = 1; i <= n; ++i) {//都移到坐标为x[1]的点
		if (sa + a[i] <= need) sa += a[i], cur += d(1, i) * a[i];
		else { r = i, rc = need - sa + 1, cur += d(1, i) * (rc - 1); break; }
	}
	//这里的rc表示向a[r]借了rc-1个物品
	//cout<<"haha"<<need<<" "<<cur<<endl;
	if (cur <= T) return 1;
	for (int i = 2; i <= n; ++i) {//i应该是中位点,枚举中位点
		cur += d(i - 1, i) * (sum(l, lc, i, 1) - sum(i, 1, r, rc));
		while (r <= n && d(l, i) > d(i, r)) {//拓展l, r使得i变成中位数
			int z = min(a[l] - lc + 1, a[r] - rc + 1);//最多可以移动的货物的数量
			cur += (d(i, r) - d(l, i)) * z;
			//这个每次必然会更新其中的一个数
			if (lc += z, lc > a[l]) ++l, lc = 1;//移动了左端
			if (rc += z, rc > a[r]) ++r, rc = 1;//移动了右端
		}
		if (cur <= T) return 1;
	}
	return 0;
}
int main() {
	cin>>n>>T;
	T /= 2;
	for (int i = 1; i <= n; ++i) x[i] = getint();
	for (int i = 1; i <= n; ++i) a[i] = getint(), s[i] = s[i - 1] + a[i];
	int64 ll = 0, rr = s[n];
	while (ll < rr) {
		int64 mm = (ll + rr + 1) >> 1;
		if (check(mm)) ll = mm;
		else rr = mm - 1;
	}
	cout<<ll<<endl;
}

重写了一遍的代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
ll n, T;
int x[maxn], a[maxn];
ll s[maxn];
ll dis(ll i, ll j){
    return abs(x[i]-x[j]);
}
ll cost(int l, int ul, int r, int ur){
    if(l == r) return ur-ul;
    else return s[r-1]-s[l-1]+ur-ul;
}
bool judge(ll mid){
    int l=1, r=n+1, ul=0, ur=0;
    ll cur = 0;
    ll now_cost = 0;
    for(int i=1; i<=n; i++){
        if(cur+a[i]<=mid) {
            cur += a[i];
            now_cost += dis(1, i)*a[i];
        }
        else{
            ur = mid-cur;
            now_cost += dis(1, i)*(ur);
            r = i;
            break;
        }
    }
    if(now_cost<=T) return true;
    for(int i=2; i<=n; i++){
        now_cost += dis(i-1, i)*(cost(l, ul, i, 0)-cost(i, 0, r, ur));
        while(r<=n && dis(l, i)>dis(i, r)){
            int z = min(a[l]-ul, a[r]-ur);
            now_cost += z*(-1*dis(l, i)+dis(i, r));
            ul += z;
            ur += z;
            if(ul>=a[l]) ul=0, l++;
            else ur=0, r++;
        }
        if(now_cost<=T) return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>T;
    T /= 2;
    for(int i=1; i<=n; i++) cin>>x[i];
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=0; i<=n; i++) s[i] = s[i-1]+a[i];
    ll l=0, r=s[n];
    ll mid;
    while(l<r){
        mid = 1ll*(l+r+1)/2;
        if(judge(mid)){
            l = mid;
        }
        else r = mid-1;
    }
    cout<<l<<endl;
    return 0;
}

J farm

题意

二维的格子上面有一种植物，施不同种类的肥料，如果化肥的种类和植物的种类不同的话，那么植物将死亡。
问最后死了多少个植物。

题解

比赛的时候想到的是怎么维护删除之后的信息，自然时间复杂度非常的高。
题解里面根本不需要维护删除，而是将他们的权值进行叠加，然后判断是否为倍数之类的

随机化的做法

给每一个化肥一个编号权重，使他们之间尽量不是倍数的关系。
统计每一个格子的化肥的权重和，若是原来的倍数，那么说明化肥的种类和植物的种类是一致的，不会导致死亡。否则植物死亡，统计答案
随机数大法好orz

ac code

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
typedef long long ll;
//inline ll rrand(){return (1ll*rand()<<15)+rand();}
int n, m, k;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    //srand(233);
    vector<int> fertilizer(n*m+10);
    vector<vector<ll> > a(n+2, vector<ll>(m+2));
    vector<vector<ll> > b(n+2, vector<ll>(m+2));
    for(int i=1; i<=n*m; i++) fertilizer[i] = rand();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>b[i][j];
        }
    }
    for(int i=0; i<k; i++){
        int x1, y1, x2, y2, c;
        cin>>x1>>y1>>x2>>y2>>c;
        //标记的过程还是有一些小技巧的。
        a[x1][y1] += fertilizer[c];
        a[x2+1][y2+1] += fertilizer[c];
        a[x2+1][y1] -= fertilizer[c];
        a[x1][y2+1] -= fertilizer[c];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]%fertilizer[b[i][j]]) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

二维树状数组组

题解链接

二维树状数组解释
二维树状数组其实就是扫两遍的思想

先将查询排序，然后检查每一个种类的植物，看他们的值是否为0，若为0表示同种农药的，没有死亡；否则有不同种的农药

玄学ac

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define mp(a, b) make_pair(a, b)
int n, m, k;
vector<int> bit[maxn];
vector<pii> plant[maxn];
int low_bit(int x){
    return x&(-x);
}
void add(int x, int y, int val){
    for(int i=x; i<=n; i+=low_bit(i)){
        for(int j=y; j<=m; j+=low_bit(j)){
            bit[i][j] += val;
        }
    }
    return ;
}
int query(int x, int y){
    int ans = 0;
    for(int i=x; i>0; i-=low_bit(i)){
        for(int j=y; j>0; j -= low_bit(j)){
            ans += bit[i][j];
        }
    }
    return ans;
}
struct Query{
    int x1, y1, x2, y2, k;
}q[maxn];
bool cmp(Query a, Query b){
    return a.k<b.k;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i=0; i<n+2; i++){
        bit[i].resize(m+2);
        plant[i].resize(m+2);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int kind;
            scanf("%d", &kind);
            plant[kind].pb(mp(i, j));
        }
    }
    int x1, y1, x2, y2, c;
    for(int i=1; i<=k; i++){
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        q[i].x1=x1, q[i].y1=y1, q[i].x2=x2, q[i].y2=y2, q[i].k=c;
        add(x1, y1, 1);
        add(x2+1, y2+1, 1);
        add(x1, y2+1, -1);
        add(x2+1, y1, -1);
    }
    int i, j, zz;
    sort(q+1, q+k+1, cmp);
    int ans = 0;
    for(int i=1, j=1; i<=n*m; i++){//第i种植物
        while(q[j].k<i&&j<=k) j++;//第j种农药
        if(plant[i].size() == 0) continue;
        zz = j;
        while(q[zz].k==i&&zz<=k) zz++;
        for(int ii=j; ii<zz; ii++){
            add(q[ii].x1, q[ii].y1, -1);
            add(q[ii].x2+1, q[ii].y2+1, -1);
            add(q[ii].x1, q[ii].y2+1, 1);
            add(q[ii].x2+1, q[ii].y1, 1);
        }
        for(int ii=0; ii<plant[i].size(); ii++){
            if(query(plant[i][ii].fi, plant[i][ii].se)){
                //cout<<"ha"<<endl;
                ans++;
            }
        }
        for(int ii=j; ii<zz; ii++){
            add(q[ii].x1, q[ii].y1, 1);
            add(q[ii].x2+1, q[ii].y2+1, 1);
            add(q[ii].x1, q[ii].y2+1, -1);
            add(q[ii].x2+1, q[ii].y1, -1);
        }
        j=zz;
    }
    printf("%d\n", ans);
    return 0;
}

未解决的问题

本文标题:newcoder-contest2

文章作者:Babydragon

发布时间:2018-07-22, 12:50:13

最后更新:2018-07-22, 21:39:39

原始链接:http://baolintian.github.io/2018/07/22/newcoder-contest2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. G transform
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. ac code
    4. 1.4. 重写了一遍的代码
  2. 2. J farm
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. 随机化的做法
    4. 2.4. ac code
    5. 2.5. 二维树状数组组
    6. 2.6. 玄学ac
  3. 3. 未解决的问题
{{ live2d() }}