2017_SDNU_ACM-ICPC_Provincial_Team_Selection_Round_1【--完结--】

发表于 | 更新于 | 分类于

山东省第八届acm大学程序设计竞赛山师选拔赛第一场

(声明：标题是自己取的，如果有语法错误的话与他人无关)

—————————————————————–分割线—————————————————————–

Problem_A(大数判定2幂数)

题意：给定一个数，判断它是否是2的n次方(0 < n < $2 ^ {1000}$)

按二进制考虑的话，如果n&(n-1)==0，则这个数就是2的n次方,等于1就不是。

AC代码(JAVA版)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.math.BigInteger;
import java.util.*;
public class Main {
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int T;
		BigInteger N;
		BigInteger ZERO = new BigInteger("0");
		BigInteger ONE = new BigInteger("1");
		
		T = scanner.nextInt();
		for(int i = 0; i < T; ++i)
		{
			N = scanner.nextBigInteger();
			BigInteger M = N.subtract(ONE);
			if(N.and(M).compareTo(ZERO) == 0) 
				System.out.println("Yes");
			else 
				System.out.println("No");
		}
	}
}

Problem_B(离散化裸题)

有些数据本身很大，自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性时，那么就可以对其进行离散化。所谓离散化就是指当数据只与它们之间的相对大小有关，而与具体是多少无关时可以用到的一种方法(？

举个例子来说，假设有4个数：1234567、123456789、12345678、123456排序后是123456＜1234567＜12345678＜123456789（只考虑他们相对大小可以想为1＜2＜3＜4），那么这四个数可以表示成：2、4、3、1。

对数据进行离散化如果用上STL会很棒棒哦（思路：先排序，再去重，然后索引元素离散化后对应的值，详见代码）。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2002;
bool flag[N][N];
long long x[N], y[N];
long long xx[N], yy[N];
int main()
{
    int n;
    scanf("%d",&n);
    memset(flag, false, sizeof(flag));
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld%lld%lld%lld",&xx[i],&yy[i],&xx[i+n],&yy[i+n]);
        //输入的同时对数据进行离散化
        x[2*i] = xx[i+n];
        y[2*i] = yy[i+n];
        x[2*i-1] = xx[i];
        y[2*i-1] = yy[i];
    }
    //排序去重
    sort(x+1, x+1+2*n);
    sort(y+1, y+1+2*n);
    unique(x+1, x+1+2*n);
    unique(y+1, y+1+2*n);

    //索引元素离散化后对应的值
    for(int i = 1; i <= 2*n; ++i)
    {
        xx[i] = upper_bound(x+1, x+1+2*n, xx[i]) - (x+1);
        yy[i] = upper_bound(y+1, y+1+2*n, yy[i]) - (y+1);
    }

    for(int k = 1; k <= n; ++k)
        for(int i = xx[k]+1; i <= xx[k+n]; ++i)    //从xx[k]+1开始
            for(int j = yy[k]+1; j <= yy[k+n]; ++j)//从yy[k]+1开始
                flag[i][j] = true;

    long long ans = 0;
    for(int i = 2; i <= 2*n; ++i)
        for(int j = 2; j <= 2*n; ++j)
            if(flag[i][j])
                ans += (x[i]-x[i-1])*(y[j]-y[j-1]);//是y[j]-y[j-1]

    cout << ans << endl;
    return 0;
}

Problem_C(最长回文子串)

题意：给定一序列，输出其最长回文子序列的长度。

思路：没有思路，Manacher模板一套带走。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e6+5;
char MA[MAX*2];
int MP[MAX*2];
void Manacher(char s[], int len)
{
    int l = 0;
    MA[l++] = '$';
    MA[l++] = '#';
    for(int i = 0; i < len; ++i)
    {
        MA[l++] = s[i];
        MA[l++] = '#';
    }
    MA[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0; i < l; ++i)
    {
        MP[i] = mx > i ? min(MP[2*id-i], mx-i) : 1;
        while(MA[i+MP[i]] == MA[i-MP[i]]) MP[i]++;
        if(i+MP[i]>mx)
        {
            mx = i + MP[i];
            id = i;
        }
    }
}
char s[MAX];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        int len = strlen(s);
        Manacher(s, len);
        int ans = 0;
        for(int i = 0; i < 2*len+2; ++i)
            ans = max(ans, MP[i]-1);
        cout << ans << endl;
    }
    return 0;
}

Problem_D(多重背包)

题意：有n个面值为A1,A2,..An,数量为C1,C2,..Cn的n个硬币，问他们之间互相组合能凑出多少种总面额小于m的面值

(可参照POJ的男人八题之Coins

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 100000 + 5;
int A[105], C[105];
int DP[MAX];  //面额为A[i]的硬币在DP[i]位置用过的个数
bool vis[MAX];//能凑成的面额
int main()
{
    int N, M;
    while(scanf("%d%d",&N,&M) && (N||M))
    {
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= N; ++i)
            scanf("%d",&A[i]);
        for(int i = 1; i <= N; ++i)
            scanf("%d",&C[i]);
        vis[0] = true;
        for(int i = 1; i <= N; ++i)
        {
            memset(DP, 0, sizeof(DP));
            for(int j = 1; j <= M; ++j)
            {
                //没有凑成过并且现在硬币的面额比要凑的面额大
                if(vis[j] || j < A[i]) continue;
                if(vis[j-A[i]] && DP[j-A[i]]<C[i])
                {
                    vis[j] = true;
                    //cout << j << "  ";
                    DP[j] = DP[j-A[i]] + 1;
                }
            }
        }
        //cout << endl;
        int ans = 0;
        for(int i = 1; i <= M; ++i)
            if(vis[i]) ans++;
        cout << ans << endl;
    }
    return 0;
}

Problem_E（思维 签到）

题意：给定n个数，从中抽取3个，将它们分成4组，问能否使每组的和相同。能的话输出抽取的三个数的位置，不能就输出I am done.

思路：设置i,j,k三个指针，一开始放在2,4,6这三个位置，然后不断判断分成的四组数据和是否相同，不同就找出其中最小的那一组，让他后面的指针往后移动。还有些小细节，比如k指针到头了，四组的值都相同了等等，自己处理一下就好了。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1005;
int a[MAX];
int MIN(int a, int b, int c, int d)
{
    if(a <= b && a <= c && a <= d) return 1;
    if(b <= a && b <= c && b <= d) return 2;
    if(c <= a && c <= b && c <= d) return 3;
    if(d <= a && d <= b && d <= c) return 4;
    return 0;
}
int main()
{
    int n;
    int x, y, z;
    int ans1, ans2, ans3, ans4;
    while(~scanf("%d",&n))
    {
        for(int i = 0; i < n; ++i)
            scanf("%d",&a[i]);
        bool flag = 1;
        if(n < 7) flag = 0;
        if(flag)
        {
            ans1 = ans2 = ans3 = ans4 = 0;
            x = 1; y = 3; z = 5;
            ans1 = a[0]; ans2 = a[2]; ans3 = a[4];
            for(int i = 6; i < n; ++i)
                ans4 += a[i];
            while(flag)
            {
                if(ans1 == ans2 && ans1 == ans3 && ans1 == ans4) break;
                int ans = MIN(ans1, ans2, ans3, ans4);
                switch(ans)
                {
                    case 0:
                    case 4: flag = 0; break;
                    case 1: x++;
                    case 2: y++;
                    case 3: z++; break;
                }
                ans1 = ans2 = ans3 = ans4 = 0;
                for(int i = 0; i < x; ++i) ans1 += a[i];
                for(int i = x+1; i < y; ++i) ans2 += a[i];
                for(int i = y+1; i < z; ++i) ans3 += a[i];
                for(int i = z+1; i < n; ++i) ans4 += a[i];
            }
        }
        if(flag) cout << x+1 << " " << y+1 << " " << z+1 << endl;
        else cout << "I am done." << endl;
    }
    return 0;
}

Problem_F(八进制减法)

题意：八进制减法

AC代码(C++–模拟)

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*************
Author:E6ther
*************/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        getchar();
        for(int j=0;j<t;++j)
        {

            char a[105],b[105];
            int len1=0,len2=0;
            bool flag=1;
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            char c;
            while((c=getchar())!=' '&&c!='\n')
            {
                a[len1]=c-'0';
                len1++;
            }
            a[len1]=0;
            while((c=getchar())!=' '&&c!='\n')
            {
                b[len2]=c-'0';
                len2++;
            }
            b[len2]=0;

            /*for(int i=0;i<len1;++i)
            {
                printf("%d",a[i]);
            }cout<<endl;
            for(int i=0;i<len2;++i)
            {
                printf("%d",b[i]);
            }cout<<endl;*/

            //printf("%s %s\n",a,b);
            if(len1>len2)
            {
                flag=1;
            }
            else if(len1<len2)
            {
                flag=0;
            }
            else
            {
                for(int i=0;i<len1;++i)
                {
                    if(a[i]>b[i])
                    {
                        flag=1;
                        break;
                    }
                    else if(a[i]<b[i])
                    {
                        flag=0;
                        break;
                    }
                }
            }
            if(flag)
            {
                for(int i=len2-1,j=len1-1;i>=0;--i,--j)
                {
                    if(a[j]>=b[i])
                    {
                        a[j]=a[j]-b[i];
                    }
                    else
                    {
                        a[j]=a[j]+8-b[i];
                        if(a[j-1])
                            a[j-1]--;
                        else
                        {
                            int flag2=0;
                            for(int x=j-2;x>=0;--x)
                            {
                                if(a[x])
                                {
                                    a[x]--;
                                    flag2=1;
                                }
                                a[x+1]=7;
                                if(flag2) break;
                            }
                        }
                    }
                }
            }
            else
            {
                for(int i=len1-1,j=len2-1;i>=0;--i,--j)
                {
                    if(a[i]<=b[j])
                    {
                        b[j]=b[j]-a[i];
                    }
                    else
                    {
                        b[j]=b[j]+8-a[i];
                        if(b[j-1])
                        b[j-1]--;
                        else
                        {
                            int flag2=0;
                            for(int x=j-2;x>=0;--x)
                            {
                                if(b[x])
                                {
                                    b[x]--;
                                    flag2=1;
                                }
                                b[x+1]=7;
                                if(flag2) break;
                            }
                        }
                    }
                }
            }
            bool flag1=0;
            if(flag)
            {
                for(int i=0;i<len1;++i)
                {
                    if(a[i]) flag1=1;
                    if(flag1)
                    printf("%d",a[i]);
                }
                if(!flag1) cout<<"0";
            }
            else
            {
                cout<<"-";
                for(int i=0;i<len2;++i)
                {
                    if(b[i]) flag1=1;
                    if(flag1)
                    printf("%d",b[i]);
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

AC代码(JAVA):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.math.BigInteger;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int T;
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		BigInteger N, M, X, Y;
		
		for(int i = 0; i < T; ++i)
		{
			N = scanner.nextBigInteger();
			M = scanner.nextBigInteger();
			X = new BigInteger(N.toString(),8);
			Y = new BigInteger(M.toString(),8);
			X = X.subtract(Y);
			System.out.println(X.toString(8));
		}
	}
}

Problem_G(模拟)

题意：给你n个数，输出对他们进行第一次快速排序后的结果。不知道快速排序的话，自己去搜(其实不知道也没关系，题目里已经给出了排序的方式了，按照它的来就是了)。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 10005;
int a[MAX];
void solve(int n)
{
    int tem = a[0];
    int l = 0, r = n;
    while(l <= r)
    {
        for(--r; l <= r; --r)
        {
            if(a[r] < tem)
            {
                a[l] = a[r];
                break;
            }
        }
        for(++l; l <= r; ++l)
        {
            if(a[l] > tem)
            {
                a[r] = a[l];
                break;
            }
        }
    }
    a[--l] = tem;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; ++i)
            scanf("%d",&a[i]);
        solve(n);
        for(int i = 0; i < n; ++i)
        {
            if(i) cout << " ";
            cout << a[i];
        }
        cout << endl;
    }
    return 0;
}

Problem_H(大素数判定)

题意：给你n个数，输出他们中素数的个数。要用到Miller-rabin算法，套个模板就好了。

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
98
99
100
101
102
103
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
const int S = 8;//随机算法判定次数，一般8~10次就够了

//计算ret = (a*b)%c  a, b, c < 2^63
long long mult_mod(long long a, long long b, long long c)
{
    a %= c;
    b %= c;
    long long ret = 0;
    long long tem = a;
    while(b)
    {
        if(b & 1)
        {
            ret += tem;
            if(ret > c) ret -= c;//直接取模慢很多
        }
        tem <<= 1;
        if(tem > c) tem -= c;
        b >>= 1;
    }
    return ret;
}

//计算 ret = (a^n) % mod
long long pow_mod(long long a, long long n, long long mod)
{
    long long ret = 1;
    long long tem = a % mod;
    while(n)
    {
        if(n & 1) ret = mult_mod(ret, tem, mod);
        tem = mult_mod(tem, tem, mod);
        n >>= 1;
    }
    return ret;
}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x * 2^t 中间使用二次判断
// 是合数返回true，不一定是合数返回false
bool check(long long a, long long n, long long x, long long t)
{
    long long ret = pow_mod(a, x, n);//a^x % n
    long long last = ret;
    for(int i = 1; i <= t; ++i)//进行t次(a^x % n)^2 % n
    {
        ret = mult_mod(ret, ret, n);
        if(ret == 1 && last != 1 && last != n - 1) return true;//合数
        last = ret;
    }
    if(ret != 1) return true;
    return false;//不一定是合数
}

//**************************************************
// Miller_Rabin算法
// 是素数返回true,(可能是伪素数)
// 不是素数返回false
//**************************************************
bool Miller_Rabin(long long n)
{
    if(n < 2) return false;
    if(n == 2) return true;
    if( (n&1) == 0) return false;//偶数
    long long x = n - 1;
    long long t = 0;
    while( (x&1) == 0) //将n分解为x*2^t;
    {
        x >>= 1;
        t++;
    }

    srand( time(NULL));

    for(int i = 0; i < S; ++i)
    {
        long long a = rand()%(n-1) + 1;//产生随机数a(并控制其范围在1 ~ n-1之间)
        if(check(a, n, x, t))//是合数
            return false;
    }
    return true;
}
int main()
{
    int t, ans;
    long long tem;
    scanf("%d",&t);
    ans = 0;
    while(t--)
    {
        scanf("%lld",&tem);
        if(Miller_Rabin(tem)) ans++;
    }
    cout << ans << endl;
    return 0;
}

Donate comment here
0%