发表更新计算机 / 算法竞赛10 分钟读完 (大约1513个字)0次访问

2018年SCUT软件学院ACM新生杯

难度非常友好！！
就是我打炸了。奖品只有气球。。。

A#

人类的本质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
int main(){
	int t;
	scanf("%d",&t);
	for(int T=1;T<=t;T++){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			printf("\"LJJnb!!!!!!!\'\'\n");
		}
		if(T!=t)printf("\n");
	}
	return 0;
}

B#

CYC的公倍数
注意到$1 \le d_{min} \le 1000$，枚举$d_{min}$即可。

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
#include <iostream>
using namespace std;
const int N=1005;
int a[N];
int main(){
	int T;
	cin>>T;
	for(int t=1;t<=T;t++){
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		int d;
		for(d=1;d<=1000;d++){
			int count=0;
			for(int i=1;i<=n;i++){
				if(d%a[i]==0)count++;
				if(count>=k)break;
			}
			if(count>=k)break;
		}
		cout<<d<<'\n';
	}
	return 0;
}

C#

CYC的计算几何
容易推出$S=|EF| \times |AE|$

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		cout<<(a*b)%10017<<'\n';
	}
	return 0;
}

D#

时空裂隙(参考题目pdf）
这题有些不严谨，而且OJ题库里也没找到这题。就姑且自己分析一波吧。
比赛时，我以为第k大的数要去除重复的，后来才发现不用，这个可能是我理解有问题。
但，官方题解给的是暴力！！而范围内明显暴力可能会超时！
此题给出的程序不一定正确

官方题解#

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include <cmath>
using namespace std;
const int Maxn=10010;
int n,k;
int num[Maxn];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&num[i]);
	sort(num+1,num+n+1);
	for (int k=1;k<=(n+1)/2;k++)
	{
		int a=num[k],b=num[n-k+1];
		int number=b-a;
		bool bj=true;
		for (int i=2;i<=sqrt(number);i++)
		{
			if (number%i==0)
			{
				bj=false;
				break;
			}
		}
		if (bj) {printf("%d\n",k);return 0;}
	}
	printf("GG\n");
	return 0;
}

hack数据生成程序#

2147483353是范围内需要判定次数最多的合数。利用这一点可以让上面程序超时。
数据类似这样：
10
1 1 1 1 1 2147483354 2147483382 2147483382 2147483382 2147483382

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
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
//const int N=10;
int N;
int Min=1;
int Max=(1<<31)-1;
int i,j,k;
int main(){
	freopen("input.txt","w",stdout);
	//printf("%d\n",Max);return 0;
	//scanf("%d",&N);
	N=10000;
	printf("%d\n",N);
	int M=N>>1;
	for(i=1;i<=M-1;i++){
		printf("%d ",Min);
	}
	//int maxi,maxn=0;
	/*
	for(i=2147483381;i>2147483381-10000;i--){
		int j=int(sqrt(i));
		int flag=1;
		for(k=2;k<=j;k++){
			if(i%k==0){
				//printf("\ni=%d\nk=%d\n",i,k);
				if(k>maxn){
					maxn=k;
					maxi=i;
				}
				flag=0;
				break;
			}
		}
		if(flag){
			printf("get one:%d\n",i);
			break;
		}
	}*/
	//printf("\nmaxi=%d\nmaxn=%d\n",maxi,maxn);
	//maxi=2147483381
	//maxn=46271
	//2147483381=46271*46411
	//18 2147483647
	//2147483647-18=2147483629
	//get one:2147483353
	printf("%d %d ",1,2147483354);
	Max=2147483381+1;
	for(i=1;i<=M-1;i++){
		printf("%d",Max);
		if(i==M-1)printf("\n");
		else printf(" ");
	}
	return 0;
}

Miller-Rabin随机性素数测试#

貌似只有这种方法了，经测试是不会超时的，这个就先当模版。。
原理以后再学。。

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
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int A[N];
typedef long long LL;
LL muti_mod(LL a,LL b,LL c){     //return (a*b) mod c,a,b,c<2^63
    a%=c;
    b%=c;
    LL ret=0;
    while(b){
        if(b&1){
            ret+=a;
            if(ret>=c)ret-=c;
        }
        a<<=1;
        if(a>=c)a-=c;
        b>>=1;
    }
    return ret;
}
LL pow_mod(LL x,LL n,LL mod){   //return x^n mod c
    if(n==1) return x%mod;
    int bit[90],k=0;
    while(n){
        bit[k++]=n&1;
        n>>=1;
    }
    LL ret=1;
    for(k=k-1;k>=0;k--){
        ret=muti_mod(ret,ret,mod);
        if(bit[k]==1) ret=muti_mod(ret,x,mod);
    }
    return ret;
}
bool check(LL a,LL n,LL x,LL t){
    LL ret=pow_mod(a,x,n),last=ret;
    for(int i=1; i<=t; i++){
        ret=muti_mod(ret,ret,n);
        if(ret==1&&last!=1 && last!=n-1) return 1;
        last=ret;
    }
    if(ret!=1) return 1;
    return 0;
}
bool miller(LL n,int S=50){
	if(n<=1)return 0;
    LL x=n-1,t=0;
    while ((x&1)==0) x>>=1,t++;
    bool flag=1;
    if (t>=1 && (x&1)==1){
        for (int k=0; k<S; k++){
            LL a=rand()%(n-1)+1;
            if (check(a,n,x,t)){
                flag=1;
                break;
            }
            flag=0;
        }
    }
    if (!flag || n==2) return 1;
    return 0;
}
int check(int x){
	if(x<=1)return 0;
	if(x==2||x==3)return 1;
	for(int i=2;i<=int(sqrt(1.0*x)+1);i++){
		if(x%i==0)return 0;
	}
	return 1;
}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	srand((unsigned)time(NULL));
	int n;
	scanf("%d",&n);
	/*for(int i=0;i<n;i++){
		//printf("check(%d)=%d\n",i,check(i));
		//printf("miller(%d)=%d\n",i,miller(i));
		if(check(i)!=miller(i))printf("%d\n",i);
	}
	return 0;*/
	for(int i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	sort(A,A+n);
	//for(int i=0;i<n;i++)printf("A[%d]=%d\n",i,A[i]);
	//return 0;
	int flag=0;
	int tn=(n>>1)+1;
	for(int k=1;k<=tn;k++){
		if(miller(A[n-k]-A[k-1])){
		//if(check(a[n-k]-a[k-1])){
			flag=k;
			break;
		}
	}
	if(flag){
		printf("%d\n",flag);
	}else{
		printf("GG\n");
	}
	return 0;
}

E#

yang12138的快乐炉石

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main(){
	int T;
	cin>>T;
	for(int t=1;t<=T;t++){
		int n;
		cin>>n;
		int count=0;
		while(n!=1){
			if(n&1){
				n=(n-1)>>1;
			}else{
				n=n>>1;
			}
			count++;
		}
		cout<<count<<'\n';
	}
	return 0;
}


F#

yang1238的激烈炉石
注意到$\sqrt{1}=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
#include <iostream>
#include <cmath>
using namespace std;
const int N=100005;
int a[N][9];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i][0];
		for(int j=1;j<9;j++){
			a[i][j]=int(sqrt(1.0*a[i][j-1]));
		}
	}
	for(int j=1;j<=m;j++){
		if(j>=9)cout<<n<<'\n';
		else{
			int sum=0;
			for(int i=1;i<=n;i++){
				sum=sum+a[i][j-1];
			}
			cout<<sum<<'\n';
		}
	}
	return 0;
}


G#

yang12138的妹子
容易推出

$$ ans=\sum_{i=m}^nC_n^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
#include <iostream>
using namespace std;
int com(int n,int r){
	if(n-r>r)r=n-r;
	int i,j,s=1;
	for(i=0,j=1;i<r;i++){
		s*=(n-i);
		for(;j<=r&&s%j==0;j++)s/=j;
	}
	return s;
}
int main(){
	int T;
	cin>>T;
	for(int t=1;t<=T;t++){
		int n,m;
		cin>>n>>m;
		int ans=1;
		for(int i=m;i<n;i++){
			ans=ans+com(n,i);
		}
		cout<<ans<<'\n';
	}
	return 0;
}


H#

yang12138的随机炉石
简单的dp。

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
#include <cstdio>
#include <iostream>
using namespace std;
const int N=105;
int a[N],b[N];
double f[N][N];
int main(){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==0)f[i][j]=0;
			else if(j==0)f[i][j]=1.0;
			else f[i][j]=0.5*f[i-1][j]+0.5*f[i][j-1];
		}
	}
	int T;
	cin>>T;
	for(int t=1;t<=T;t++){
		int hp1,hp2,n,m;
		cin>>hp1>>hp2>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int j=1;j<=m;j++){
			cin>>b[j];
		}
		if(hp1%10==0)hp1--;
		if(hp2%10==0)hp2--;
		hp1=hp1/10+1;
		hp2=hp2/10+1;
		printf("%.5lf\n",f[hp1][hp2]);
	}
	return 0;
}

I#

HOOCCOOH的大模拟
真是大模拟，按题意处理即可。

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=200005;
char base[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int rebase[305];
char s[N];
int change(char *p){
	char a=rebase[int(*(p))],b=rebase[int(*(p+1))],c,d;
	if(*(p+2)=='=')c=0;
	else c=rebase[int(*(p+2))];
	if(*(p+3)=='=')d=0;
	else d=rebase[int(*(p+3))];
	int ta=(a<<2)+(b>>4),tb=((b&15)<<4)+(c>>2),tc=((c&3)<<6)+(d);
	//printf("\nta=%d\ntb=%d\ntc=%d\n",ta,tb,tc);
	if(ta>=32&&ta<=126)printf("%c",ta);
	if(tb>=32&&tb<=126)printf("%c",tb);
	if(tc>=32&&tc<=126)printf("%c",tc);
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	for(int i=0;i<64;i++){
		rebase[base[i]]=i;
	}
	while(~scanf("%s",s)){
		int len=strlen(s);
		/*for(int i=0;i<len;i++){
			printf("%c:%d\n",s[i],rebase[s[i]]);
		}*/
		for(int i=0;i<len;i+=4)
			change(s+i);
		printf("\n");
	}
	return 0;
}

J#

BPM的签到题
发现自己分析能力好弱。。尤其是做这种构造题。
从左往右逐个贪心选取，能选取的条件是后面能补回来。
每个位只可能出现三种情况，逐个判断即可。

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;
const int N=100005;
char a[N],b[N];
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		scanf(" %s %s",a,b);
		int len=strlen(a);
		int d=0;
		for(int i=0;i<len;i++){
			if(a[i]==b[i]){
				printf("a");
				continue;
			}
			int t[3]={a[i],b[i],'a'};
			while(t[2]==a[i]||t[2]==b[i])t[2]++;
			for(int ii=0;ii<2;ii++){
				for(int jj=ii+1;jj<3;jj++){
					if(t[ii]>t[jj])swap(t[ii],t[jj]);
				}
			}
			/*for(int ii=0;ii<3;ii++){
				printf("\ntest:t[%d]=%c\n",ii,t[ii]);
			}*/
			for(int ii=0;ii<3;ii++){
				if(t[ii]!=a[i]&&t[ii]!=b[i]&&d==0){
					printf("%c",t[ii]);
					break;
				}
				int td=d;
				if(t[ii]!=a[i])d++;
				if(t[ii]!=b[i])d--;
				int count=0;
				for(int jj=i+1;jj<len;jj++){
					if(a[jj]!=b[jj])count++;
					if(count>=abs(d))break;
				}
				//printf("\nii=%d,d=%d,count=%d\n",ii,d,count);
				if(count>=abs(d)){
					printf("%c",t[ii]);
					break;
				}else{
					d=td;
				}
			}
		}
		puts("");
	}
	return 0;
}

K#

BPM种南瓜
n个区间里面选k个，要求这k个区间的连续公共长度最大。
先对左端点排序，依次选取。

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
#include <bits/stdc++.h>
using namespace std;
struct seg{
	int l,r;
	seg(int l,int r):l(l),r(r){}
};
bool cmp1(seg a,seg b){
	return a.l<b.l;
}
struct cmp2{
	bool operator()(seg a,seg b){
		return a.r>b.r;
	}
};
vector<seg>V;
priority_queue<seg,vector<seg>,cmp2> Q;
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		V.push_back(seg(l,r));
	}
	sort(V.begin(),V.end(),cmp1);
	int ans=0;
	for(auto i:V){
		//printf("test:V=(%d,%d)\n",i.l,i.r);
		if(Q.size()<k){
			Q.push(i);
			if(Q.size()==k){
				ans=max(ans,Q.top().r-i.l);
			}
			continue;
		}
		//printf("Q.top=(%d,%d)\n",Q.top().l,Q.top().r);
		Q.push(i);
		seg temp=Q.top();
		Q.pop();
		if(temp.r!=i.r)ans=max(ans,Q.top().r-i.l);
	}
	printf("%d\n",ans);
	return 0;
}

L#

小南瓜爱旅游

2018年SCUT软件学院ACM新生杯

https://blog.tootal.xyz/posts/scutpc2018-newcup/

作者

黄智权

本文发布于

2018-11-11

本文更新于

2018-11-11

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

×