19年11月17号个人训练赛补题

基础算法
字数统计: 2.1k字   |   阅读时长≈ 11分钟

这次的题都是atcoder的上的原题，有几道题我做过，但是还是没能一次过。

A

题意
给你n个坐标，让你从中间任选几个，求几个点相加距远点的最远距离。
思路
先利用极角排序，将他变为一个按角度的有序序列，然后暴力求最远距即可。
(偷一波华佬的代码)

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 <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
struct node{
	ll x,y;
	 
}r[1100];
bool cmp(node a,node b){
	return atan2(a.y,a.x) < atan2(b.y,b.x);
	
}
int main(){
	ll n,x,y;
	cin >> n;
	for(ll i = 0; i < n; i++){
		cin >> r[i].x >> r[i].y;
	}
	ll ans = 0;
	sort(r,r+n,cmp);
	for(ll i = 0; i < n; i++){
		x = r[i].x ; y = r[i].y;
		ans = max(ans,x*x+y*y);
		for(ll j = (i+1)%n; j != i; j = (j+1)%n){
			x += r[j].x ; y += r[j].y;
			ans = max(ans,x*x+y*y);
		}

	}
	double ans1 = sqrt(ans);
	printf("%.13lf\n",ans1);
	return 0;
}

B

题意
从1到n中选k个连续的数 问有多少种选法
思路
答案为n-k+1

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
#include<iostream> 
using namespace std;
int n,k;
int main()
{
	cin>>n>>k;
	printf("%d\n",n-k+1);
	return 0;
}

C

题意
序列ai为1到n的有序序列，pi为1到n的任何一个序列，求ai%pi和的最大值
思路
分别用ai%（ai+1）最后n%1即为最大。为n*（n-1）/2.

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#include<iostream> 
using namespace std;
typedef long long ll;
ll n;
int main()
{
	cin>>n;
	printf("%lld\n",n*(n-1)/2);
	return 0;
}

E

题意
n个顶点，从第一个顶点到其他各个顶点的边数依次为啊ai，求最小能生成几棵不一样的树。
思路
若第一个数不为0或除除第一个数以外有的为0或给的不是一个连续的序列，都无法生成树。
除此以外，ai统计为0 1 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
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n;
int a[100000+100];
ll p(ll pp,ll qq)
{
	ll ss=1;
	for(int i=1;i<=qq;i++)
	{
		ss=ss*pp%mod;
	}
	return ss;
}
int main()
{
	int flag=0,x;
	memset(a,0,sizeof a);
	cin>>n;
	cin>>x;
	a[x]++;
	if(x!=0) flag=1;
	for(int i=1;i<n;i++)
	{
		cin>>x;
		a[x]++;
	}
	if(a[0]>1) flag=1;
	int f=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]==0&&f==0) f=1;
		if(a[i]!=0&&f==1)
		{
			flag=1;
			break;
		}
	}
	ll sum=1;
	if(flag)
	{
		printf("0\n");
	}
	else
	{
		for(int i=1;i<n-1;i++)
		{
			if(a[i]==0) break;
			sum=(sum*p(a[i],a[i+1]))%mod;
		}
		printf("%lld\n",sum%mod);
	}
	return 0;
}

F

题意
n个怪兽，第i个怪兽有ai的血，但血量为p的怪兽攻击血量为q的怪兽时，q变为q-p，为最后剩的那一个血量最少为多少。
思路
每次让其他的对血量最小的那一个取余，最后剩的那一个即为最小的。

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
#include<stdio.h>
#include<iostream>
#include<math.h> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n;
ll a[100000+100];
bool cmp(int a,int b)
{
	return a>b;
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1);
	int ss=a[1],minn=ss;
	sort(a+1,a+n+1,cmp);
	while(a[2]!=0)
	{
		ss=min(ss,minn);
		minn=0x3f3f3f3f;
		for(int i=1;i<n;i++)
		{
			if(a[i]==0)
			break;
			if(a[i]==ss&&a[i+1]==0)
			break;
			a[i]=a[i]%ss;
			if(minn>a[i]&&a[i]!=0)
			{
				minn=a[i];
			}
			
		}
		sort(a+1,a+n+1,cmp);
	}
	printf("%lld\n",a[1]);
	return 0;
}

G

每次找到最大的那个除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
#include<stdio.h>
#include<iostream>
#include<math.h> 
#include<queue>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,less<ll> >q;
ll n,m;
ll a;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		q.push(a);
	}
	while(m--)
	{
		a=q.top();
		q.pop();
		a=a/2;
		q.push(a);
	}
	ll sum=0;
	while(!q.empty())
	{
		sum=sum+q.top();
		q.pop();
	}
	printf("%lld\n",sum);
	return 0;
}

H

若问题数小于初始分数，则都能幸存。
若问题数大于等于初始分数，则给回答正确的那个人加1，最后小于等于q的人不能幸存。

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<stdio.h>
#include<iostream>
#include<math.h> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,k,q,b;
ll a[100000+100];
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		a[i]=k;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>b;
		a[b]++;
	}
	if(q<k)
	{
		for(int i=1;i<=n;i++)
		printf("Yes\n");
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(a[i]-q<=0)
			printf("No\n");
			else
			printf("Yes\n");
		}	
	}
	return 0;
}

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
36
37
38
#include<stdio.h>
#include<iostream>
#include<math.h> 
using namespace std;
typedef long long ll;
ll n;
struct stt
{
	ll a;
	ll b;
}st[100000+100];
bool cmp(stt aa,stt bb)
{
	return aa.b>bb.b;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>st[i].a;
	}
	int sum=0;
	st[n].b=0;
	for(int i=n-1;i>=1;i--)
	{
		if(st[i].a>=st[i+1].a)
		{
			st[i].b=sum+1;
			sum++;
		}
		else
		sum=0;
	}
	sort(st+1,st+n+1,cmp);
	printf("%lld\n",st[1].b);
	return 0;
}

J

题意
对一个序列复制k次，一个数后面有n个数比他小，则此数为n，求每一个数的n相加。
思路
对于同一个序列中，求出num1为每一个数的n相加。对于两个不同序列num2为每一个的n相加，一共有k个num1，k（k-1）个num2。相加即可。
数据量过大，用快速乘和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
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,k;
int a[20000+100];
ll ksc(ll a,ll b,ll c)
{
	ll ans=0;
	while(b)
	{
		if(b%2==1)
		ans=(ans+a)%c;
		b=b/2;
		a=(a+a)%c;
	}
	return ans;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	ll num1=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]>a[j]) num1++;
		}
	}
	ll num2=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i]>a[j]) num2++;
		}
	}
	printf("%lld\n",(ksc(num1,k,mod)%mod+ksc(num2,k*(k-1)/2,mod)%mod)%mod);
	return 0;
}

M

题意
给你n个字符串，你可以对他随意组合，使其形成一个新的字符串，求里边子串AB的个数。
思路
能形成AB的无非两种情况，第一个是字符串里边本来就包含AB，第二个是字符串头为B与另一个字符串的尾A组合为AB
将开头为B结尾为A的kai、仅开头为B的、仅开头为A的分别统计，先让开头为B结尾为A的自行组合，然后让仅开头为B的和仅开头为A的补上，最后加上字符串之间的AB，即为所求。

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
#include<stdio.h>
#include<iostream>
#include<math.h> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n;
int len[10000+100];
char s[10000+100][100];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		len[i]=strlen(s[i]);
	}
	ll a=0,b=0,sum=0;
	int ss=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i][0]=='B'&&s[i][len[i]-1]=='A')
		{
			ss++;
		}
		else if(s[i][0]=='B') 
		{
			b++;
		}
		else if(s[i][len[i]-1]=='A') 
		{
			a++;
		}
		for(int j=0;j<len[i]-1;j++)
		{
			if(s[i][j]=='A'&&s[i][j+1]=='B') sum++;
		}
	}
//	printf("%d %d %d %d\n",ss,sum,a,b);
	if(ss==0)
	{
		sum=sum+min(a,b);
	}
	else
	{
		if(b>0&&a>0)
		{
			sum=sum+ss+1+min(a-1,b-1);
		}
		else if((a>0&&b==0)||b>0&&a==0)
		{
			sum=sum+ss;
		}
		else if(a==0&&b==0)
		{
			sum=sum+ss-1;
		}
	}
	printf("%lld\n",sum);
	return 0;
}

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • © 2020 Super Monkey
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信