AK 了！我愿称之为信心场。

A. Rudolph and Cut the Rope

题意

有 nn 个钉子，每个钉子高度在 aia_i，并且有一根长度为 bib_i 的绳子连接着钉子和糖。

问：想要把糖放到 h=0h=0 的地方，至少要割断几根绳子？

解法

若 ai>bia_i>b_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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(){
    int n=read();
    int ans =0 ;
    for(int i=0;i<n;i++){
        int a=read(),b=read();
        if(a-b>0)ans++;
    }
    printf("%d\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

B. Rudolph and Tic-Tac-Toe

题意

有一个井字棋游戏，有三种棋子，X，O，+，以及 . 代表空白位置。
给定一个局面，判断谁获胜。（保证没有两个人同时获胜）

解法

依次检查三条横线，三条竖线，主对角线，副对角线即可。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

char s[5][5];

void solve(){
    for(int i=0;i<3;i++)scanf("%s",s[i]);


    for(int i=0;i<3;i++){ // 横线
        bool ok = 1;
        for(int j=1;j<3;j++){
            if(s[i][j]!=s[i][0]){
                ok=0;
                break;
            }
        }
        if(ok && s[i][0]!='.'){
            printf("%c\n",s[i][0]);
            return;
        }
    }

    
    for(int i=0;i<3;i++){ // 竖线
        bool ok = 1;
        for(int j=1;j<3;j++){
            if(s[j][i]!=s[0][i]){
                ok=0;
                break;
            }
        }
        if(ok && s[0][i]!='.'){
            printf("%c\n",s[0][i]);
            return;
        }
    }


    if(s[0][0]==s[1][1] && s[1][1]==s[2][2]  && s[0][0]!='.'){ // 主对角线
        printf("%c\n",s[0][0]);
        return;
    }
    if(s[0][2]==s[1][1] && s[1][1]==s[2][0] && s[0][2]!='.'){ // 副对角线
        printf("%c\n",s[0][2]);
        return;
    }
    puts("DRAW");
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

C. Rudolf and the Another Competition

题意

有 nn 个人，mm 道题目。第 ii 个人完成第 jj 个题目要花费 ai,ja_{i,j} 的时间。比赛总共有 hh 分钟。

每个人的排名先按照过题数量排序，若通过的题目数量是相同的，按照过题时刻的总和排序。（比如说花了 5 min5\,\text{min} 做了第一题，花了 5 min5\,\text{min} 做第二题，时间总和就是 5 min+(5+10) min=25 min5\,\text{min}+(5+10)\,\text{min}=25\,\text{min}）

求每个人都按照最优策略行动的情况下，第一个人的排名。

解法

不难发现，每个人的最优策略就是从时间小的题目开始做起。这是因为：① 要保证过题数量最多，先做时间短的题有优势。 ② 在过题数量相同的情况下，先做时间短的题，过题时刻的总和更小。

预处理出每个人在 hh 分钟内能做几道题，然后求出比第一个人厉害的人数量即可。

要 开 long long。

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>
using namespace std;

#define int long long

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(){
    int n=read(),m=read(),h=read();
    vector<vector<int>> a(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            a[i][j]=read();
        }
        sort(begend(a[i]));
    }

    int k = 1;

    vector<pii> res(n);
    for(int i=0;i<n;i++){
        int pts=0,tm = 0;
        int realtm=0;
        for(int j=0;j<m;j++){
            if(tm + a[i][j]>h)break;
            pts++; tm+=a[i][j];
            realtm+=tm;
        }
        res[i]={pts,realtm};
        if(i!=0){
            if(pts>res[0].first)k++;
            else if(pts==res[0].first&&realtm<res[0].second)k++;
        }
    } 

    printf("%lld\n",k);
}

signed main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

D. Rudolph and Christmas Tree

题意

有 nn 个底为 dd，高为 hh 的等腰三角形，底边与 xx 轴平行。
现在知道每个三角形底边中点的高度，求这些三角形并集形成的图形的面积。

解法

从上往下依次处理每个三角形。如果这个三角形和上一个三角形没有交集，答案直接加上三角形的面积。否则，答案加上形成的一块等腰梯形的面积。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(){
    int n=read(),d=read(),h=read();
    vector<int> y;
    for(int i=0;i<n;i++){
        y.push_back(read());
    }
    sort(begend(y),greater<int>());

    double ans = 0;
    for(int i=0;i<n;i++){
        if(i==0){ // 第一个
            ans += (double)d*h/2;
            continue;
        }

        if(y[i]+h>y[i-1]){
            int realh = y[i-1]-y[i]; // 梯形的高度
            double realup = d*1.0*(((double)h-realh)/(double)h); // 梯形的上底
            ans += (realup+d)*realh/2;
        }
        else{
            ans += (double)d*h/2;
        }
    }

    printf("%f\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

E1. Rudolf and Snowflakes (simple version)

题意

给定 n(n≤106)n (n \le 10^6)，求是否存在 k>1,q>1k>1,q>1，使得 n=∑i=0kqi\displaystyle n=\sum_{i=0}^k{q^i}。
比如说 21=42+4+121=4^2+4+1，所以 2121 是 YES。

解法

本方法和 E2 的解法没有任何关系。这个方法不能修改成 E2 的解法，你可以直接去看 E2 的题解。

考虑一下等比数列的求和公式。

n=1⋅(1−qk)1−q=qk−1q−1n=\dfrac{1\cdot (1-q^k)}{1-q}=\dfrac{q^k-1}{q-1}

(q−1)n=qk−1qn−n+1=qk(q-1)n=q^k-1 \\ qn - n + 1 =q^k

得到

n−1≡0(modq)n-1 \equiv 0 \pmod q

所以 qq 是 n−1n-1 的一个因数。可以 O(n)O(\sqrt n) 求出所有因数。注意这是一个必要条件，我们再检验 qn−n+1qn - n + 1 是否是 qq 的整数次幂即可。

复杂度 O(tn)O(t\sqrt n)。（tt 为样例数）

E2. Rudolf and Snowflakes (hard version)

题意

只改变了 nn 的范围。现在 n≤1018n \le 10^{18}。

解法

注意到最高次不能超过 6060（因为 260>10182^{60}>10^{18}）。

对于一个给定的最高次 kk，我们尝试找出一个合法的 qq。
设 f(q)=∑i=0kqi\displaystyle f(q)=\sum_{i=0}^k{q^i}。注意到 f(q)f(q) 单调递增，可以用二分查找找出是否有这样一个合法的 qq。

因此，枚举所有的最高次项次数，依次判断是否有解即可。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

// 计算 1+q+q^2+..+q^k
ll cal(ll q,int k){
    ll ans = 1;
    ll now = 1;
    for(int i=0;i<k;i++){
        now *= q;
        ans += now;
    }
    return ans;
}

void solve(){
    ll n=read<ll>();
    if(n==1){
        puts("NO");
        return;
    }   

    for(int i=2;i<=60;i++){ // 最高是 i 次项
        ll l=2,r=pow(1e18,(double)1/i);
        while(l<r){
            ll mid = (l+r+1)>>1;
            if(cal(mid,i)>n)r=mid-1;
            else l=mid;
        }

        if(cal(l,i)==n){
            puts("YES");
            return;
        }
    }   

    puts("NO");
}


int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

F. Rudolph and Mimic

题意

交互题。有 nn 个物体，每个物体由一个整数确定。还有一个模仿怪，可以模仿任意一种初始存在的物体。

现在，可以进行最多不超过 5 次删除操作。每次删除操作后，你要求删去的数（可以不删除）会被删去，模仿怪可以重新换一个模仿，也可以不更换模仿对象，但是不能连续两次不更换模仿对象。之后所有数会被重新打乱。
如果删除了模仿怪，则直接判负。

请你求出最后模仿怪所在位置的编号。

解法

考虑必胜策略。

破题关键就是模仿怪不能连续两次不更换模仿对象。前两次我们按兵不动，不删除数，这样一定能找到现在模仿怪变成的数到底是几。接下来删除所有与其不同的数。然后不删除数按兵不动两次，如果有一个数与众不同，那么他就是模仿怪。

举个例子：

  1. 一开始是 1 1 2 2 3。
  2. 第一次，按兵不动，模仿怪不动，仍然是 1 1 2 2 3。
  3. 第二次，模仿怪必须动，假设变成了 1，那么就是 1 1 1 2 3。
  4. 比较两次的数量，发现 1 多了一个。那么模仿怪一定是 1。把除了 1 的所有数删去。模仿怪在这个回合没动，那么就是 1 1 1。
  5. 现在模仿怪必须动了。哪个位置不是 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int cnt1[10],cnt2[10];
const int N = 205;
int a1[N],a2[N];

void solve(){
    mem0(cnt1);
    int n=read();

    for(int i=1;i<=n;i++){
        a1[i]=read();
        cnt1[a1[i]]++;
    }
    
    again:printf("- 0\n");fflush(stdout);
    mem0(cnt2);
    for(int i=1;i<=n;i++){
        a2[i]=read();
        cnt2[a2[i]]++;
    }
    int val = 0;
    for(int i=1;i<=9;i++){
        if(cnt2[i]==cnt1[i]+1){
            val = i;
            break;
        }
    }
    if(val==0)goto again;

    vector<int> del;
    for(int i=1;i<=n;i++){
        if(a2[i]!=val)del.push_back(i);
    }
    printf("- %d ",(int)del.size());
    for(int x:del){
        printf("%d ",x);
    }
    puts("");fflush(stdout);

    n-=del.size();
    while(true){
        for(int i=1;i<=n;i++){
            a2[i]=read();
        }
        for(int i=1;i<=n;i++){
            if(a2[i]!=val){
                printf("! %d\n",i);fflush(stdout);
                return;
            }
        }

        printf("- 0\n");fflush(stdout);
    }
} 

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

G. Rudolf and CodeVid-23

题意

有 n(n≤10)n(n\le 10) 个症状。初始你有某些症状。
有 mm 个药，每个药花费 did_i 时间服用，能消除某些症状，但是会再给予某些症状（不会给予能消除的症状）。

现在在同一时间只能吃一个药，求消除所有症状的最短用时，或 -1 不能消除所有症状。

解法

发现 nn 极小，那么拥有症状的情况最多就只有 210=10242^{10}=1024 种。对于每一个症状情况，用每一个药一定会转移到另一个确定的状态。不难发现这就是一张带权有向图，那么求出初始状态到 0 的最短路长度即可。

我们用一个二进制来代表症状。有一些好用的位运算操作：

  • x | give：将 x 中 give 有的位全部置为 1。
  • x & ~remove：将 x 中 remove 有的位全部置为 0。

复杂度 O(2nm+n2)O(2^nm+n^2)。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e3+5;
int rem[N],giv[N];
int cost[N];

int get_bin(){
    char s[15];
    scanf("%s",s);
    int val = 0;
    int l = strlen(s);
    for(int i=0;i<l;i++){
        val*=2;
        val+=s[i]-'0';
    }
    return val;
}

const int M = 1030;
int G[M][M];
int dis[M];
bool vis[M];
const int INF = 0x3f3f3f3f;

void solve(){
    int n=read(),m=read();
    int initial = get_bin();
    
    for(int i=0;i<m;i++){
        cost[i]=read();
        rem[i]=get_bin();
        giv[i]=get_bin();
    }

    memset(G,0x3f,sizeof(G));
    for(int i=0;i<1024;i++){
        for(int j=0;j<m;j++){
            int x = i;
            x |= giv[j];
            x &= ~rem[j];
            G[i][x]=min(G[i][x],cost[j]);
        }
    }

    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[initial]=0;

    for(int i=0;i<1024;i++){
        int u;int du=INF;
        for(int j=0;j<1024;j++){
            if(!vis[j] && dis[j]<du){
                u=j, du=dis[j];
            }
        }
        vis[u]=1; 
        for(int v=0;v<1024;v++){
            if(vis[v])continue;
            
            if(G[u][v]!=INF && dis[v]>dis[u]+G[u][v]){ 
                dis[v]=dis[u]+G[u][v];
            }
        }
    }

    if(dis[0]==INF)puts("-1");
    else printf("%d\n",dis[0]);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}