http://codeforces.com/contest/1260/problem/C

B. Obtain Two Zeroes

 

题意：两个整数 a,b,(a,b≥0)a,b,(a,b\geq 0)，每次 a−=xa-=x 且 b−=2xb-=2x 或 a−=2xa-=2x 且 b−=xb-=x，xx 为正整数。问任意次操作后能否使 a，b都等于0.

把所有对a减x的操作合并为减x，所有对b减x的操作合并为减y。

则 a=x+2y,b=2x+ya=x+2y,b=2x+y。

a+b=3⋅(x+y)a+b=3\cdot (x+y)。即 a+ba+b 为 3 的倍数。

但由于有 a=1，b=8这样的情况，还要一步。

x=3⋅(2b−a)≥0x=3\cdot (2b-a)\geq 0，所以 2b−a≥02b-a\geq 0。同理，2a−b≥02a-b\geq 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n;
int T;
int main(){
    scanf("%d",&T);
    while(T--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==0&&b==0)puts("Yes\n");
        else if(2*b>=a&&2*a>=b&&b>0&&(a+b)%3==0)puts("Yes\n");
        else puts("No\n");
    }
    return 0;
}

 

C. Infinite Fence

 

题意：有无数个篱笆，给出两个正整数 r 和 b ，若是 r 的倍数则可以涂red，若是 b 的倍数则可以涂blue，若是公倍数则随便选一种，其它数字不能涂色。现在把所有涂了色的篱笆拿出来，若有连续 k 个是同一种颜色，则失败。

假设 r>b，就是要判断两个 r 之间是否会有 k 个 b。

要在两个r之间放下尽可能多的b，就要使第一个b距离第一个r尽可能近。

则 r⋅x+b⋅y=cr\cdot x+b\cdot y=c，要让 c 尽可能小，由于x，y有整数解，则c最小等于gcd(r,b)。

两个 r 之间相隔 r-1 ，而r+c是第一个b，所以剩下的长度是 (r-c-1) ，判断是否有 k-1个b即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n;
int T;
int gcd(int a, int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    scanf("%d",&T);
    while(T--){
        int a,b,k;
        scanf("%d%d%d",&a,&b,&k);
        if(a>b)swap(a,b);
        int c=gcd(b,a);
        if((b-c-1)/a+1>=k)puts("REBEL");
        else puts("OBEY");
    }
    return 0;
}

 

D. A Game with Traps

 

感觉比前两题简单多了啊。。

二分+贪心

只有在前面是过不去的陷阱的时候才会来回一次把它除掉。

二分最低的能力值。

区间合并，交叉的区间合成大区间更划算。我用的是stack，也有用前缀和的。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int maxn=1e6 + 10;
int m, n, k, t;
int a[maxn];
int l[maxn], r[maxn], d[maxn];
stack<pii>st;
struct X{
    int l,r,d;
}b[maxn];
bool cmp(const X& a,const X& b){
    return a.l==b.l?a.r<b.r:a.l<b.l;
}
bool check(int mid){
    while(!st.empty())st.pop();
    for(int i=0;i<k;i++){
        if(b[i].d<=mid)continue;
        if(st.empty()){
            st.push(pii(b[i].l,b[i].r));
            continue;
        }
        pii tp=st.top();
        if(tp.second>=b[i].l){
            st.pop();
            st.push(pii(tp.first,max(tp.second,b[i].r)));
        }
        else{
            st.push(pii(b[i].l,b[i].r));
        }
    }
    ll res=n+1;
    while(!st.empty()){
        pii tp=st.top();st.pop();
        res+=2*(tp.second-tp.first+1);
    }
    return res<=t;
}
int main(){
    scanf("%d%d%d%d",&m, &n, &k, &t);
    for(int i = 0;i < m;i++){
        scanf("%d", &a[i]);
    }
    for(int i = 0;i < k;i++){
        scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].d);
    }
    sort(b,b+k,cmp);
    int L=0,R=2e5;
    while(L<R){
        int mid=(L+R)/2;
        if(check(mid))R=mid;
        else L=mid+1;
    }
    int ans=0;
    for(int i=0;i<m;i++){
        if(a[i]>=L)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

 

E. Tournament

 

题意：有 n 个人，能力值分别为 1到 n，要收买 i 需要对应的 cost[i]，每轮一对一比赛，n 个人中有 1 个是你的朋友，问最少花费多少使朋友夺冠。

决赛只会面对所有人中最强的那个，半决赛只会面对后一半的某人或前一半最强的那个，1/4决赛只会面对后3/4的人或前1/4最强的那个人。

以此类推，发现从后往前遍历，每当遇到2的幂次时，就要进行一次比赛了，可以从所有遍历过的人中挑一个人比赛（收买）。

则优先队列，从后往前遍历时，遇到2的幂次就pop一次，找到花费最小的那个人收买他。注意要先把2的幂次那个人push进去，原因如上。

学到一个新技巧，i&(i−1)i\&(i-1) 可以把最低位的 1 变为 0 ，若 i 是 2的幂次，则返回0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e7 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[maxn];
priority_queue<int,vector<int>,greater<int> >que;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	ll ans = 0;
	for (int i = n; i >= 1 && a[i] != -1; i--) {
		que.push(a[i]);
		if (!(i&(i - 1)))ans += que.top(), que.pop();
	}
	cout << ans << endl;
	return 0;
}