题目链接:Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
题目链接:Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
这道题第一眼看去很难,其实不然,短短几行代码就搞定了。
说一下大概思路,如果是排成一排的n个人,如 1 2 3 4 5 6 7 8 我们要变成 8 7 6 5 4 3 2 1 需要交换 28次,找规律的话就是 n*(n-1)/2,但这道题是一个圈,要让他们顺序变反的话不一定1要在8的位置上去,4 3 2 1 8 7 6 5 这样也是反的,我们只要把n个人分成两部分,然后按拍成一条线的方法来出来两部分就OK了。
题目意思很容易理解,学校有n个社团,每个社团只给编号从a到b 的发传单,而且只给隔了c的人发,问最后谁收到的传单是单数,输出他的编号和收到的传单数量。
昨天做这题的时候看见很多人过了,感觉不会很难,但是打死都想不出来,看了别人的思路,一下子就想通了。这里我简要说一下,用二分,我们可以很容易求出一段区间里的总的传单数,因为保证最多有一个是单数,我们就看单数在哪边。
下面是java代码,刚开始学java,代码不是很简洁。
import java.util.Scanner; public class Main { static long[] a = new long[20005]; static long[] b = new long[20005]; static long[] c = new long[20005]; public static void main(String[] args) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int n = cin.nextInt(); for (int i = 1; i <= n; i++) { a[i] = cin.nextLong(); b[i] = cin.nextLong(); c[i] = cin.nextLong(); } long r = Integer.MAX_VALUE, l = 0; while (l < r) { long mid = (l+r)>>1; long sum = 0; for (int i = 1; i <= n; i++) { long minnum; if (mid <= b[i]) minnum = mid; else minnum = b[i]; if (minnum >= a[i]) { sum += (minnum - a[i])/c[i] + 1; } } if (sum%2 == 1) r = mid; else l = mid+1; } if (l == Integer.MAX_VALUE) { System.out.println("DC Qiang is unhappy."); continue; } long ans = 0; for (int i = 1; i <= n; i++) { if (l >= a[i] && l <= b[i]) { if ((l - a[i]) % c[i] == 0) ans += 1; } } System.out.println(l + " " + ans); } cin.close(); } }
我先解释一下汉明距离 以下来自百度百科
汉明距离在信息论、密码学等方向有很重要的应用。
这个题是让你求n个数两两之间最小的汉明距离,而且规定了每个数是长度为5的16进制数,可以想到求出最大的值为20,最小为10。 没想到什么好的算法,看了人家的解题报告,依靠RP,随机找1000000对点求最小值,不过还是过了。
#include<algorithm> #include<stdio.h> #include <stdlib.h> #define inf 1000000007 using namespace std; int M[100005]; int count(int x,int y) { int sum=0,p=x^y; while (p) sum+=p%2,p>>=1; return sum; } int main() { int T,y,n,d,i,j,x; scanf("%d",&T); while (T--) { scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%X", &M[i]); } int ans=inf; for (i=1;i<=1000000;i++) { x=rand()%n+1; y=rand()%n+1; if (x==y) continue; ans=min(ans,count(M[x],M[y])); } printf("%d\n",ans); } return 0; }
题目意思就是用a-z组成一个N,然后到z后又跳回a,输出宽从3到10的N。
#include <stdio.h> #include <string.h> char s[14][15]; int main() { int cnt = 0; for (int kase = 3; kase <= 10; kase++) { memset(s, ' ', sizeof(s)); for (int i = 1; i <= kase; i++) { for (int j = 1; j <= kase; j++) { cnt %= 26; if (i == 1 || i == kase) { cnt %= 26; s[j][i] = 'a'+cnt; cnt++; } else { if (i == j) { cnt %= 26; s[kase-j+1][i] = 'a'+cnt; cnt++; break; } } } } for (int i = 1; i <= kase; i++) { for (int j = 1; j <= kase; j++) { printf("%c", s[i][j]); } puts(""); } } return 0; }
#include <string.h> #include <stdio.h> const int maxn = 1000006; bool vis[1000006]; int pr[1000005]; int cnt = 1; int bs(int l, int r, int v) { int mid=(l+r)>>1; while(l < r) { if(pr[mid] < v) l = mid+1; else r = mid; mid= (l+r) >> 1; } return l; } void getpr() { int i,j; for(i=2;i*i<maxn;i++) if(!vis[i]) { pr[cnt++]=i; for(j=i*i;j<maxn;j+=i) vis[j]=1; } for(;i<maxn;i++)if(!vis[i]) { pr[cnt++]=i; } } int main() { memset(vis, 0, sizeof(vis)); getpr(); int n, t; scanf("%d", &t); while (t--) { scanf("%d", &n); int ans1 = 0; int ans2 = 0; for (int i = 1; i <= cnt; i++) { if (pr[i] <= n) continue; int x = bs(1, cnt-1, pr[i]-n); if (pr[i] - n == pr[x]) { ans1 = pr[i]; ans2 = pr[x]; break; } } if (ans1) printf("%d %d\n",ans1, ans2); else puts("FAIL"); } return 0; }
把输入的数加起来,输入0表示结束。
先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); BigInteger sum = BigInteger.valueOf(0); BigInteger a; a = cin.nextBigInteger(); while (true) { sum = sum.add(a); if (a.compareTo(BigInteger.valueOf(0)) == 0) break; a = cin.nextBigInteger(); } System.out.println(sum); cin.close(); } }
下面是我从网上找的C++代码,无外乎就是用数组模拟实现大数的加法。
#include<stdio.h> #include<string.h> #define N 20000 int ans[N],f,max; void hadd(char a[]) { f=0; int n=strlen(a); for(int i=n-1;i>=0;i--) { a[i]-='0'; ans[f]+=a[i]; ans[f+1]+=ans[f]/10; ans[f]%=10; f++; if(max<f) max=f; } } int main() { memset(ans,0,sizeof(ans)); while(1) { char s[N]; scanf("%s",s); if(strlen(s)==1&&s[0]=='0') break; hadd(s); } int flag=0; for(int i=N-1;i>=0;i--) { if((!flag&&ans[i]!=0)||flag||(!flag&&i==0)) {printf("%d",ans[i]);flag|=1;} } puts(""); return 0; }
有红绿蓝三种颜色的画,每种拿三朵可以组成一束花,或者各拿一朵组成花束,告诉你每种花的数目,求出可能组成最多的花束。
如果你的代码过不了,考虑一下 8 8 9这种组合。 因为数据量很大,我的思想就是局部和总体采用不同的策略。
#include <iostream> #include <algorithm> using namespace std; int main() { int r, g, b; while (cin >> r >> g >> b) { int m = min(r, g); m = min (m, b); int ans = 0; int a = 0; for (int i = 0; i <= 10000 && i <= m; i++) { a = (r-i)/3 + (g-i)/3 + (b-i)/3 + i; ans = max(a, ans); } cout << ans << endl; } return 0; }