首页 > 代码库 > 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的倍数