首页 > 代码库 > 1090 3个数和为0 1091 线段的重叠 1182 完美字符串 1283 最小周长 1284 2 3 5 7的倍数
1090 3个数和为0 1091 线段的重叠 1182 完美字符串 1283 最小周长 1284 2 3 5 7的倍数
1090 3个数和为0
给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合,输出No Solution。如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则按照第二小的数排序。
Input
第1行,1个数N,N为数组的长度(0 <= N <= 1000) 第2 - N + 1行:A[i](-10^9 <= A[i] <= 10^9)
Output
如果没有符合条件的组合,输出No Solution。 如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则继续按照第二小的数排序。每行3个数,中间用空格分隔,并且这3个数按照从小到大的顺序排列。
Input示例
7 -3 -2 -1 0 1 2 3
Output示例
-3 0 3 -3 1 2 -2 -1 3 -2 0 2 -1 0 1
确定两个找第三个,1000000复杂度。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cmath> 5 #include<map> 6 #include<cstring> 7 using namespace std; 8 9 int n; 10 int a[1007]; 11 map<int,bool>p; 12 bool boo=0; 13 14 int main() 15 { 16 scanf("%d",&n); 17 for (int i=1;i<=n;i++) 18 { 19 scanf("%d",&a[i]); 20 p[a[i]]=true; 21 } 22 sort(a+1,a+n+1); 23 for (int i=1;i<=n-2;i++) 24 for (int j=i+1;j<=n-1;j++) 25 if (i!=j) 26 { 27 int x=0-a[i]-a[j]; 28 if (a[j]<x&&p[x]) 29 { 30 printf("%d %d %d\n",a[i],a[j],x); 31 boo=1; 32 } 33 } 34 if (!boo) printf("No Solution\n"); 35 }
1091 线段的重叠
X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。
给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。
Input
第1行:线段的数量N(2 <= N <= 50000)。 第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)
Output
输出最长重复区间的长度。
Input示例
5 1 5 2 4 2 8 3 7 7 9
Output示例
4
以起点为一号关键字,终点为二号关键字排序,然后发现对于x1,y1,x2,y2,只有一号线条包含二号,相交,不相交三种情况,然后求出最优解,贪心。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 using namespace std; 7 8 int n; 9 struct Node 10 { 11 int x,y; 12 }a[50007]; 13 14 bool cmp(Node a,Node b) 15 { 16 if (a.x!=b.x) return a.x<b.x; 17 return a.y<b.y; 18 } 19 int main() 20 { 21 scanf("%d",&n); 22 for (int i=1;i<=n;i++) 23 scanf("%d%d",&a[i].x,&a[i].y); 24 sort(a+1,a+n+1,cmp); 25 int st=a[1].x,ed=a[1].y,ans=0; 26 for (int i=2;i<=n;i++) 27 { 28 if (a[i].x>=ed) st=a[i].x,ed=a[i].y; 29 else if (a[i].y<=ed) ans=max(ans,a[i].y-a[i].x); 30 else 31 { 32 ans=max(ans,ed-a[i].x); 33 st=a[i].x,ed=a[i].y; 34 } 35 } 36 printf("%d\n",ans); 37 }
1182 完美字符串
约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配,不同字母的完美度不同,分别对应一个1-26之间的整数。
约翰不在乎字母大小写。(也就是说字母F和f)的完美度相同。给定一个字符串,输出它的最大可能的完美度。例如:dad,你可以将26分配给d,25分配给a,这样整个字符串完美度为77。
Input
输入一个字符串S(S的长度 <= 10000),S中没有除字母外的其他字符。
Output
由你将1-26分配给不同的字母,使得字符串S的完美度最大,输出这个完美度。
Input示例
dad
Output示例
77
注意还有大写,第一次被坑了,简单排序后贪心。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cmath> 5 #include<cstring> 6 using namespace std; 7 8 int a[37]; 9 char s[10007]; 10 11 bool cmp(int x,int y) 12 { 13 return x>y; 14 } 15 int main() 16 { 17 scanf("%s",s); 18 int len=strlen(s); 19 for (int i=0;i<len;i++) 20 { 21 if (s[i]>=‘a‘&&s[i]<=‘z‘) a[s[i]-‘a‘]++; 22 else a[s[i]-‘A‘]++; 23 } 24 sort(a+0,a+25+1,cmp); 25 int ans=0; 26 for (int i=0;i<26;i++) 27 ans+=a[i]*(26-i); 28 printf("%d\n",ans); 29 }
1283 最小周长
一个矩形的面积为S,已知该矩形的边长都是整数,求所有满足条件的矩形中,周长的最小值。例如:S = 24,那么有{1 24} {2 12} {3 8} {4 6}这4种矩形,其中{4 6}的周长最小,为20。
Input
输入1个数S(1 <= S <= 10^9)。
Output
输出最小周长。
Input示例
24
Output示例
20
发现两个数越相近,周长最小,然后从√S找第一对,贪心就可以了。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 using namespace std; 7 8 int n; 9 10 int main() 11 { 12 scanf("%d",&n); 13 int up=(int)sqrt(n); 14 for (int i=up;i>=1;i--) 15 { 16 int x=n/i; 17 if (x*i==n) 18 { 19 printf("%d\n",(x+i)*2); 20 break; 21 } 22 } 23 }
1284 2 3 5 7的倍数
给出一个数N,求1至N中,有多少个数不是2 3 5 7的倍数。 例如N = 10,只有1不是2 3 5 7的倍数。
Input
输入1个数N(1 <= N <= 10^18)。
Output
输出不是2 3 5 7的倍数的数共有多少。
Input示例
10
Output示例
1
简单的容斥原理,不要写错是关键,被坑了好久,只怪自己菜。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 8 typedef long long LL; 9 10 LL n; 11 12 int main() 13 { 14 scanf("%lld",&n); 15 LL x=n/2+n/3+n/5+n/7-n/6-n/10-n/14-n/15-n/21-n/35+n/30+n/42+n/105+n/70-n/210; 16 printf("%lld",n-x); 17 }
1090 3个数和为0 1091 线段的重叠 1182 完美字符串 1283 最小周长 1284 2 3 5 7的倍数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。