NEERC2002解题报告

发表于 分类于

比赛传送门

A. Amusing Numbers

题意：定义 nn 以内 kk 的排名为，数字大小在 1∼n1\sim n 的数字中，字典序小于等于 kk 的数字个数。给定 k,mk,m，求最小的 nn，使得 nn 以内 kk 的排名为 mm。m,k≤109m,k\le 10^9。无解输出 00。

直接找 nn 可能不是很好找，于是可以考虑二分答案。对于一个 midmid，比较 midmid 以内 kk 的排名与 mm 的大小关系即可。问题转换为如何找排名。

查找 nn 以内字典序小于等于 kk 的数字个数显然可以使用数位 DP，每次假设前面的若干位都与 kk 相等，这一位比 kk 小，通过记录前面是否已经比 nn 小，找在 nn 以内的数字个数即可。

By FutureGazer

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

using namespace std;

// 1 .. n, K
long long gao(long long n, long long K) {
    long long ret = 0;
    long long b = 1;
    for (; K / b >= 10; b *= 10);
    for (long long i = K, j = b; i != 0; i /= 10, j /= 10) {
        if (n >= j) {
            ret += min(n, i) - j + 1;
        }
    }
    for (long long i = K * 10, j = b * 10; ; ) {
        if (j > n) {
            break;
        }
        ret += min(i - 1, n) - j + 1;
        if (i >= n || n / j < 10) {
            break;
        }
        if (n / i >= 10) {
            i *= 10;
            j *= 10;
        } else {
            i = n + 1;
            j *= 10;
        }
    }
    return ret;
}

int main() {
    freopen("amusing.in", "r", stdin);
    freopen("amusing.out", "w", stdout);
    long long K, m;
    scanf("%I64d%I64d", &K, &m);
    if (gao(K, K) > m) {
        puts("0");
        return 0;
    }
    long long pl = K - 1, pr = 0x3f3f3f3f3f3f3f3fLL;
    while (pl + 1 < pr) {
        long long pm = pl + (pr - pl) / 2;
        if (gao(pm, K) >= m) {
            pr = pm;
        } else {
            pl = pm;
        }
    }
    if (gao(pr, K) != m) {
        puts("0");
    } else {
        printf("%I64d\n", pr);
    }
    return 0;
}

C. Cricket Field

题意：在 (0,0)−(H,W)(0,0)-(H,W) 的矩形区域中有若干个障碍，找出最大的没有障碍的正方形区域（必须在大矩形区域内）。

做法一

显然左界和下界必须有障碍，所以可以枚举左界和下界的障碍，然后考虑往外扩展正方形。可以枚举每个障碍来找正方形大小最强的限制，也可以二分答案。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
int x[110],y[110];
signed main() {
    freopen("cricket.in","r",stdin);
    freopen("cricket.out","w",stdout);
    int n,w,h;
    cin>>n>>w>>h;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    int ansx,ansy,ans=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            if(x[i]>x[j]||y[i]<y[j]) continue;
            int xx=x[i],yy=y[j];
            int l=0,r=10000;
            while(l<r) {
                int mid=(l+r+1)/2;
                if(xx+mid>w||yy+mid>h) r=mid-1;
                else {
                    bool flag=1;
                    for(int k=1;k<=n;k++)
                        if(x[k]>xx&&y[k]>yy&&x[k]<xx+mid&&y[k]<yy+mid)
                            flag=0;
                    if(!flag) r=mid-1;
                    else l=mid;
                }
            }
            if(l>ans) ans=l,ansx=xx,ansy=yy;
        }
    for(int i=0;i<=w;i++) {
        int xx=i,yy=0;
        int l=0,r=10000;
        while(l<r) {
            int mid=(l+r+1)/2;
            if(xx+mid>w||yy+mid>h) r=mid-1;
            else {
                bool flag=1;
                for(int k=1;k<=n;k++)
                    if(x[k]>xx&&y[k]>yy&&x[k]<xx+mid&&y[k]<yy+mid)
                        flag=0;
                if(!flag) r=mid-1;
                else l=mid;
            }
        }
        if(l>ans) ans=l,ansx=xx,ansy=yy;
    }
    for(int i=0;i<=h;i++) {
        int xx=0,yy=i;
        int l=0,r=10000;
        while(l<r) {
            int mid=(l+r+1)/2;
            if(xx+mid>w||yy+mid>h) r=mid-1;
            else {
                bool flag=1;
                for(int k=1;k<=n;k++)
                    if(x[k]>xx&&y[k]>yy&&x[k]<xx+mid&&y[k]<yy+mid)
                        flag=0;
                if(!flag) r=mid-1;
                else l=mid;
            }
        }
        if(l>ans) ans=l,ansx=xx,ansy=yy;
    }
    cout<<ansx<<" "<<ansy<<" "<<ans<<endl;
    return 0;
}

做法二

枚举上下界的障碍（非强制上下界），将在这个上下界之间的障碍从左到右排序，用相邻两个障碍的距离和上下界距离的 min 来更新答案。

By Ycat

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
int main(){
#ifdef ONLINE_JUDGE
    freopen(INPUT, "r", stdin);
    freopen(OUTPUT, "w", stdout);
#endif
    int n,w,h;
    pair<int, int> trees[105];
    scanf("%d%d%d",&n,&w,&h);
    for (int i=1; i<=n; i++) {
        scanf("%d%d",&trees[i].first,&trees[i].second);
    }
    int P,Q,L=-1;
    trees[++n]=make_pair(0, 0);
    trees[++n]=make_pair(w, h);
    sort(trees+1, trees+1+n);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
//			printf("%d %d\n",i,j);
            int pos[105],cnt=0,width=trees[j].first-trees[i].first;
            pos[cnt++]=0;
            for(int k=i+1;k<j;k++)
                pos[cnt++]=trees[k].second;
            pos[cnt++]=h;
            sort(pos, pos+cnt);
            for(int k=1;k<cnt;k++){
                if(L<min(pos[k]-pos[k-1],width)){
                    L=min(pos[k]-pos[k-1],width);
                    P=trees[i].first;
                    Q=pos[k-1];
//					cout<<L << ' '<<P<<' '<<Q<<' '<<i<<' '<<j<<endl;
                }
            }
        }
    printf("%d %d %d\n",P,Q,L);
    return 0;
}

D. Decoding Task

题意：有一个加密机器，其有一个密钥串。一个串的加密方式为将它和密钥的对应位异或起来。给你两个字符串，分别表示某个文本的加密结果和这个文本加一个前导空格后的加密结果。求密钥。（文本和密钥均为 2 位 16 进制形式）

可以通过空格加密的结果推出密钥的第一位，进而推出文本的第一位；继续根据文本的第一位与密钥的第二位的加密结果推出密钥的第二位，从而得到文本的第二位。以此类推即可。

By cxm1024

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<bits/stdc++.h>
using namespace std;
int to10(char a,char b) {
    int x,y;
    if(isdigit(a)) x=a-'0';
    else x=a-'A'+10;
    if(isdigit(b)) y=b-'0';
    else y=b-'A'+10;
    return x*16+y;
}
string to16(int x) {
    int a=x/16,b=x%16;
    string s;
    if(a>9) s=s+char(a-10+'A');
    else s=s+char(a+'0');
    if(b>9) s=s+char(b-10+'A');
    else s=s+char(b+'0');
    return s;
}
signed main() {
    freopen("decode.in","r",stdin);
    freopen("decode.out","w",stdout);
    string s,t;
    cin>>s>>t;
    vector<int> vs,vt;
    for(int i=0;i<s.size();i+=2)
        vs.push_back(to10(s[i],s[i+1]));
    for(int i=0;i<t.size();i+=2)
        vt.push_back(to10(t[i],t[i+1]));
    int now=vt[0]^32;
    cout<<to16(now);
    for(int i=0;i<vs.size();i++) {
        vs[i]=now^vs[i];
        now=vs[i]^vt[i+1];
        cout<<to16(now);
    }
    cout<<endl;
    return 0;
}

F. Folding

题意：给你一个字符串，可以将若干个连续重复的字符串替换为 重复次数+(+重复内容+)，例如 ABCABCABC 可以替换为 3(ABC)。求最短的替换方式。

显然可以区间 DP。令 f[l][r]f[l][r] 表示 [l,r][l,r] 的最小替换长度，则 f[l][r]=min⁡{f[l][k]+f[k+1][r]}f[l][r]=\min\{f[l][k]+f[k+1][r]\}。替换时需要特殊处理，可以采用刷表法，当计算出一段的结果后，可以通过复制来更新后面的 DP 值。具体地，设当前处理的区间的长度为 lenlen，则往后跳长度为 lenlen 的区间，如果相同则进行复制替换贡献。

By Ycat

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
int f[110][110],d[110][110],n,i,j,k,len,fold;
string s,t;

int calc(int x)
{
    return x<10?1:(x<100?2:3);
}

void print(int l,int r)
{
    int i,k=d[l][r];
    if(!k) cout<<s.substr(l,r-l+1);
    else if(k>0) print(l,k),print(k+1,r);
    else k=-k,cout<<(r-l+1)/(k-l+1)<<"(",print(l,k),cout<<")";
}

int main()
{
    freopen("folding.in","r",stdin);
    freopen("folding.out","w",stdout);
    cin>>s;
    n=s.length();
    s=" "+s;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f[i][j]=j-i+1;
    for(len=1;len<=n;len++)
        for(i=1;i<=n-len+1;i++)
        {
            j=i+len-1;
            t=s.substr(i,len);
            for(k=i;k<=j-1;k++)
                if(f[i][j]>f[i][k]+f[k+1][j])
                    f[i][j]=f[i][k]+f[k+1][j],d[i][j]=k;
            k=j+1; fold=0;
            while(k<=n-len+1)
                if(t==s.substr(k,len))
                {
                    fold++,k+=len;
                    if(f[i][k-1]>f[i][j]+calc(fold)+2)
                        f[i][k-1]=f[i][j]+calc(fold)+2,d[i][k-1]=-j;
                }
                else break;
        }
    print(1,n);
    //system("pause");
    return 0;
}

还可以使用记忆化搜索，每次可以先处理如何由复制组成，然后再考虑分裂成哪两半递归。有了记忆化的加持，无论重复调用多少次，复杂度都会保持 n2n^2，大大减小实现压力。对于复制的处理可以使用一次循环，判断每一位是否都和它前面 lenlen 位相同。

By KrK

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 <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int Maxn = 105;

int best[Maxn][Maxn], p[Maxn][Maxn], mn[Maxn][Maxn];
string s;

bool canFold(int l, int r, int len)
{
     for (int i = l + len; i <= r; i++) if (s[i] != s[i - len]) return false;
     return true;
}

int Dig(int x)
{
    int res = 0;
    while (x) { res++; x /= 10; }
    return res;
}

int Fold(int l, int r)
{
    if (l > r) return 0;
    if (!best[l][r]) {
                     int len = r - l + 1;
                     best[l][r] = mn[l][r] = len; p[l][r] = -1;
                     for (int i = 1; i * i <= len; i++)
                         if (len % i == 0) {
                                 if (canFold(l, r, i)) {
                                                int cand = Dig(len / i) + 2 + Fold(l, l + i - 1);
                                                if (cand < best[l][r]) {
                                                         best[l][r] = cand;
                                                         mn[l][r] = i;
                                                }
                                 }
                                 int j = len / i;
                                 if (i != j && j < len && canFold(l, r, j)) {
                                       int cand = Dig(len / j) + 2 + Fold(l, l + j - 1);
                                       if (cand < best[l][r]) {
                                                best[l][r] = cand;
                                                mn[l][r] = j;
                                       }
                                 }
                         }
                     for (int i = l; i < r; i++) {
                         int cand = Fold(l, i) + Fold(i + 1, r);
                         if (cand < best[l][r]) {
                                  best[l][r] = cand; p[l][r] = i;
                         }
                     }
    }
    return best[l][r];
}

void Print(int l, int r)
{
     if (l > r) return;
     int len = r - l + 1;
     if (len == best[l][r])
        for (int i = l; i <= r; i++) printf("%c", s[i]);
     else if (p[l][r] < 0) {
             printf("%d(", len / mn[l][r]);
             Print(l, l + mn[l][r] - 1);
             printf(")");
     } else { Print(l, p[l][r]); Print(p[l][r] + 1, r); }
}

int main()
{
    freopen("folding.in", "r", stdin);
    freopen("folding.out", "w", stdout);
    getline(cin, s);
    Fold(0, s.length() - 1);
    Print(0, s.length() - 1); printf("\n");
    return 0;
}

H. Heroes Of Might And Magic

题意：有 n+1n+1 个格子，编号从 0∼n+10\sim n+1。英雄在 00，若干只怪物初始在 nn，初始血量相同。每个格子有一个权值 cc。每回合英雄先操作，可以选择攻击、回血和传送之一。如果攻击，则第一只怪物的血量减去所在格子的权值。如果死掉则剩余伤害顺延到第二只，以此类推。如果传送，可以将所有怪物同时传送到某位置（除了 00）。如果回血则血量回复 dHdH（回满停止）。操作完后怪物操作，所有怪物同时向左移动 vv 格，到 11 则停止。如果到了 11 则对英雄造成当前怪物数量的伤害。要求在 mm 次操作内杀掉所有怪物。输出方案或判断无解。

首先注意到，由于所有怪物的行动都是统一的，状态并不是很复杂，可以想到记忆化搜索。搜索时记录当前英雄血量、怪物总血量（可以反推出怪物个数）、剩余操作次数。每次选择操作转移即可。

By FutureGazer

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

struct TPL{
    int hp,mp,eh,p;
    char c;
    TPL(){}
    TPL(int hp, int mp, int eh, int p, char c):hp(hp),mp(mp),eh(eh),p(p),c(c){}
};

int n,ht,mt,et,m,v,dh,l[11];
int dp[101][51][101][11];
TPL pt[101][51][101][11];

int gao(int hp, int mp, int eh, int p){
    if(~dp[hp][mp][eh][p]) return dp[hp][mp][eh][p];
    if(!eh) return dp[hp][mp][eh][p]=2;
    if(!hp) return dp[hp][mp][eh][p]=0;
    if(!mp) return dp[hp][mp][eh][p]=0;
    int HP,MP,EH,P;
    EH=max(eh-l[p],0);
    P=p-min(v,p-1);
    HP=max(hp-(P==1?(EH+et-1)/et:0),0);
    MP=mp-1;
    if(gao(HP,MP,EH,P)){
        pt[hp][mp][eh][p]=TPL(HP,MP,EH,P,'L');
        return dp[hp][mp][eh][p]=1;
    }
    for(int i=1;i<=n;i++){
        EH=eh;
        P=i-min(v,i-1);
        HP=max(hp-(P==1?(EH+et-1)/et:0),0);
        MP=mp-1;
        if(gao(HP,MP,EH,P)){
            pt[hp][mp][eh][p]=TPL(HP,MP,EH,P,i+'a');
            return dp[hp][mp][eh][p]=1;
        }
    }
    EH=eh;
    P=p-min(v,p-1);
    HP=max(min(hp+dh,ht)-(P==1?(EH+et-1)/et:0),0);
    MP=mp-1;
    if(gao(HP,MP,EH,P)){
        pt[hp][mp][eh][p]=TPL(HP,MP,EH,P,'H');
        return dp[hp][mp][eh][p]=1;
    }
    return dp[hp][mp][eh][p]=0;
}

int main(){
    freopen("heroes.in","r",stdin);
    freopen("heroes.out","w",stdout);
    scanf("%d%d%d%d%d%d%d",&n,&ht,&mt,&et,&m,&v,&dh);
    for(int i=1;i<=n;i++) scanf("%d",l+i);
    memset(dp,-1,sizeof(dp));
    if(!gao(ht,mt,et*m,n)) return puts("DEFEATED")&0;
    puts("VICTORIOUS");
    int hp=ht,mp=mt,eh=et*m,p=n;
    while(dp[hp][mp][eh][p]!=2){
        TPL c=pt[hp][mp][eh][p];
        if(c.c>='a') printf("T %d\n",c.c-'a'); else printf("%c\n",c.c);
        hp=c.hp;
        mp=c.mp;
        eh=c.eh;
        p=c.p;
    }
}