NEERC2009解题报告

发表于 更新于 分类于

B. Business Center

有 mm 个电梯，每个电梯有两个权值 a,ba,b，初始在第 00 层。你可以选择一个电梯，进行恰好 nn 次操作，每次要么升高 aa 要么下降 bb。要求最终在第一层以上且尽可能低。

对于每个电梯 a,ba,b，考虑进行几次上几次下。由于要求在第一层以上，所以上的层数大于下的层数，即 ax>b(n−x)ax>b(n-x)。解一下不等式即可。

By Waterloo Black

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int n,m,best,u,d;
int main() {
  freopen("business.in","r",stdin);
  freopen("business.out","w",stdout);
  best=3000;
  cin >> n >> m;
  for(int i=0;i<m;i++){
    cin>>u>>d;
    best=min(best,(u*n-1)%(u+d)+1);
  }
  cout<<best<<endl;

}

D. Database

有一个表格，每个格子为一个字符串，问是否存在两个行 x,yx,y 和两个列 i,ji,j，使得 (x,i)=(y,i)(x,i)=(y,i) 且 (x,j)=(y,j)(x,j)=(y,j)。n≤10000,m≤10n\le 10000,m\le 10。

由于列数很少，显然可以枚举两个列，然后判断是否有两个行在这两列上的取值相等。可以使用字符串哈希进行比较，map 进行维护。

By dnkywin

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

ifstream fin ("database.in");
ofstream fout ("database.out");

typedef unsigned long long ull;

vector<ull> mat[10100];

int main()
{
  int n, m;
  fin >> n >> m;
  string s;
  getline(fin, s);
  for (int i = 0; i < n; i++) {
    getline(fin, s);
    ull h = 0;
    vector<ull> hashes;
    for (int j = 0; j < s.size(); j++) {
      if (s[j] == ',') {
        hashes.push_back(h);
        h = 0;
      } else {
        h = h * 137 + s[j];
      }
    }
    hashes.push_back(h);
    mat[i] = hashes;
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < i; j++) {
      map<pair<ull, ull>, int> f;
      for (int k = 0; k < n; k++) {
        auto t = make_pair(mat[k][i], mat[k][j]);
        if (f.count(t)) {
          fout << "NO" << endl;
          fout << f[t] + 1 << " " << k + 1 << "\n";
          fout << j + 1 << " " << i + 1 << "\n";
          return 0;
        }
        f[t] = k;
      }
    }
  }
  fout << "YES" << endl;
}

或者可以不哈希，直接用 string 和 pair 自带的比较函数扔进 map 里。

By DemiGuo

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

const int maxn=20000+10;
const int maxm = 15;
int n, m;
string str, word[maxn][maxm];
map<pair<string,string>, int> ha;

int main()  {
    freopen("database.in", "r", stdin);
    freopen("database.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for (int i = 1; i <= n; i ++)  {
        getline(cin, str);
        str = str + ",";
        int len = str.length();
        int c = 0;
        int last = 0;
        for (int j = 0; j < len; j ++)
            if (str[j] == ',')  {
                c ++;
                word[i][c] = str.substr(last, j - last);
                last = j + 1;
                // printf("(%d,%d)=", i,c);
                // cout << word[i][c] << endl;
            }
    }
    for (int c = 1; c <= m; c ++)
        for (int d = c + 1; d <= m; d ++) {
            ha.clear();
            for (int i = 1; i <= n; i ++)  {
                pair<string, string> cur = make_pair(word[i][c], word[i][d]);
                if (ha.count(cur))  {
                    printf("NO\n");
                    printf("%d %d\n", ha[cur], i);
                    printf("%d %d\n", c, d);
                    return 0;
                }
                ha[cur] = i;
            }
        }
    printf("YES\n");
    return 0;
}

F. Funny Language

题意：定义一个字符串能生成的字符串为，选择其中若干个字符重新排列得到的字符串。给定 mm 个字符串，构造 nn 个字符串，使得这 nn 个字符串不能与 mm 个给定的重复，且可以被这 mm 个字符串中尽量多的生成。

一个显然的结论是，若选了某个字符串，其中的每个子串被生成的次数都不会少于这个原串，所以可以先选一个字符的串，然后在逐步加字符，一步一步考虑。可以使用类似 Dijkstra 的做法来一步步扩展，每次选当前被生成次数最多的字符串拓展，直到确定完 nn 个合法的字符串。

By dnkywin

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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;
const int MAXM = 1100;

ifstream fin ("funny.in");
ofstream fout ("funny.out");

int N, M;
string s[MAXM];
int distro[MAXM][26];
int d[26];

priority_queue <pair <int, string> > pq;
vector <string> res;

void add (string x)
{
    for (int i = 0; i < 26; i++)
        d[i] = 0;
    for (int i = 0; i < x.length(); i++)
        d[x[i]-'A']++;

    int tot = 0;
    for (int i = 0; i < M; i++)
    {
        bool bad = false;
        for (int j = 0; j < 26; j++)
        {
            if (distro[i][j] < d[j])
            {
                bad = true;
                break;
            }
        }
        if (!bad)
            tot++;
    }

    pq.push (make_pair (tot, x));
}

int main()
{
    fin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        fin >> s[i];

        for (int j = 0; j < 26; j++)
            distro[i][j] = 0;
        for (int j = 0; j < s[i].length(); j++)
            distro[i][s[i][j]-'A']++;
    }

    for (int i = 0; i < 26; i++)
    {
        string S = "";
        S += (char) ('A' + i);
        add (S);
    }

    while (res.size() < N)
    {
        string tval = pq.top().second;
        //cout << pq.top().first << " " << tval << endl;
        pq.pop();


        for (int i = 0; i < 26; i++)
            add (tval + (char) ('A' + i));

        bool bad = false;
        for (int i = 0; i < M; i++)
            if (tval == s[i])
                bad = true;
        if (bad)
            continue;

        res.push_back (tval);
    }

    for (int i = 0; i < N; i++)
        fout << res[i] << "\n";
}

H. Headshot

题意：一个环形排列的 01 串，有一个指针随机指到了一个位置，已知目前在 00，你可以选择移到下一个位置，也可以选择随机一个位置，问哪个方案选到 11 的概率更高/相等。

考虑分别计算概率：往后移一位取到 11 的概率，其为 0101 的个数与 00 的个数之比；随机去选一位的概率为 11 的个数与串长的比。分数的比较可以移项转换为乘法比较。

By UH Counting Stars

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

#define int long long

using namespace std;



int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("headshot.in", "r", stdin);
    freopen("headshot.out", "w", stdout);

    string cad;
    cin >> cad;

    int N = cad.size();

    int p1 = 0;
    int t1 = 0;

    int p2 = 0;
    int t2 = N;

    for(int i = 0 ; i < N ; i++)
    {
    	if(cad[i] == '0')
    	{
    		t1++;
    		if(cad[(i+1)%N] == '1')p1++;
    	}
    	else
    	{
    		p2++;
    	}
    }

    if(p1*t2 < p2*t1)
    {
    	cout << "SHOOT" << '\n';
    }
    if(p1*t2 == p2*t1)
    {
    	cout << "EQUAL" << '\n';
    }
    if(p1*t2 > p2*t1)
    {
    	cout << "ROTATE" << '\n';
    }

    return 0;
}

J. Java Certification

题意：有一个考试，一共 nn 道题，分为 mm 个板块，你一共答对了 kk 道题。给定每个板块你答对的题目的占比（百分比，取整方式为，小于 0.50.5 舍弃，大于 0.50.5 进一，等于 0.50.5 取相邻两个整数中偶数的那个），求每个板块的题数和你答错的题数。如果有多解，求每个板块题目数量极差最小的解。

显然是一个 DP 题。

做法一

令 f[i][j][k][l]f[i][j][k][l] 表示考虑前 ii 个板块，用了 jj 道题，答错了 kk 道题，板块题数的最小值为 ll 时，最大值最小为多少。可以使用刷表法进行转移。一个必需的优化为，预处理每个百分比可能的题数-错误题数二元组，转移时只需要枚举二元组而不需要现计算。

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
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
int a[15],f[11][105][105][105];
struct node {
    int j,k,l;
} pre[11][105][105][105];
int calc(int a,int b) {
    double tmp=a*100.0/b;
    int x=floor(tmp+eps);
    if(tmp-eps>=x+0.5) return ceil(tmp);
    else if(abs(tmp-(x+0.5))<=eps) {
        if(x%2==0) return floor(tmp);
        else return ceil(tmp);
    }
    else return floor(tmp);
}
void print(int i,int j,int k,int l) {
    if(i==0) return;
    print(i-1,pre[i][j][k][l].j,pre[i][j][k][l].k,pre[i][j][k][l].l);
    cout<<k-pre[i][j][k][l].k<<" "<<j-pre[i][j][k][l].j<<endl;
}
int main() {
    freopen("javacert.in","r",stdin);
    freopen("javacert.out","w",stdout);
    int w,n,m;
    cin>>w>>n>>m;
    w=n-w;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    memset(f,0x3f,sizeof(f));
    f[0][0][0][n]=0;
    for(int i=0;i<m;i++) {
        vector<pair<int,int> > ok;
        for(int j=1;j<=n;j++)
            for(int k=0;k<=min(j,w);k++)
                if(calc(j-k,j)==a[i+1])
                    ok.push_back({j,k});
        for(int j=i;j<n;j++)
            for(int k=0;k<=min(j,w);k++)
                for(int l=0;l<=n;l++) {
                    if(f[i][j][k][l]>1e9) continue;
                    for(auto [jj,kk]:ok) {
                        if(j+jj>n||k+kk>w) continue;
                        int tmp=max(f[i][j][k][l],jj);
                        if(tmp<f[i+1][j+jj][k+kk][min(l,jj)]) {
                            f[i+1][j+jj][k+kk][min(l,jj)]=tmp;
                            pre[i+1][j+jj][k+kk][min(l,jj)]={j,k,l};
                        }
                    }
                }
    }
    int ans=1e9,minl=0;
    for(int l=1;l<=n;l++)
        if(f[m][n][w][l]-l<ans)
            minl=l,ans=f[m][n][w][l]-l;
    print(m,n,w,minl);
    return 0;
}

做法二

考虑钦定下界，DP 最小的上界，此时 DP 可以减少一维，重复 nn 次即可。具体地，f[i][j][k]f[i][j][k] 表示前 ii 个板块，jj 道题，kk 道正确，板块题数最大值最小是多少。转移时钦定板块题数大于等于某个值即可，总复杂度相同，但由于 DP 状态减少，实现上更清爽，空间也更优。

By dnkywin

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
using namespace std;
typedef long long ll;
const int MAXN = 102;
const int MAXM = 11;

ifstream fin ("javacert.in");
ofstream fout ("javacert.out");

int K, N, M;
int dp[MAXN][MAXN][MAXM]; // [i] questions correct out of [j], [k]-th prob, smallest max
int prev[MAXN][MAXN][MAXM];
vector <pair <int, int> > pposs[MAXM];

int res;
pair <int, int> answer[MAXM];

int getp (int num, int den)
{
    int t = (100 * num + den / 2) / den;
    if (2 * t * den == 200 * num + den && t % 2 == 1)
        --t;
    return t;
}

int solve (int lo)
{
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            for (int k = 0; k < MAXM; k++)
                dp[i][j][k] = 1000;

    dp[0][0][0] = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j <= K; j++)
            for (int k = 0; k <= N; k++)
            {
                for (int l = 0; l < pposs[i].size(); l++)
                {
                    if (pposs[i][l].second < lo) continue;
                    int x = pposs[i][l].first, y = pposs[i][l].second;

                    if (j + x > K || k + y > N)
                        break;

                    if (dp[j+x][k+y][i+1] > max (y, dp[j][k][i]))
                    {
                        dp[j+x][k+y][i+1] = max (y, dp[j][k][i]);
                        prev[j+x][k+y][i+1] = l;
                    }
                }
            }
    }

    //cout << lo << " " << dp[K][N][M] << "\n";
    if (dp[K][N][M] < 1000)
        return dp[K][N][M] - lo;
    return -1;
}

int main()
{
    fin >> K >> N >> M;
    for (int i = 0; i < M; i++)
    {
        pposs[i].clear();
        int x; fin >> x;

        for (int j = 1; j <= 100; j++)
            for (int k = 0; k <= j; k++)
            {
                if (getp (k, j) == x)
                {
                    //cout << i << " " << k << " " << j << "\n";
                    pposs[i].push_back (make_pair (k, j));
                }
            }
    }

    res = 100;
    for (int i = N / M; i >= 1; i--)
    {
        int t = solve (i);
        if (t < res && t != -1)
        {
            res = t;

            int ck = K, cn = N, cm = M;
            while (cm)
            {
                --cm;
                int x = pposs[cm][prev[ck][cn][cm+1]].first;
                int y = pposs[cm][prev[ck][cn][cm+1]].second;
                answer[cm] = make_pair (x, y);
                ck -= x;
                cn -= y;
            }
        }
    }

    for (int i = 0; i < M; i++)
        fout << answer[i].second - answer[i].first << " " << answer[i].second << "\n";
    return 0;
}