Leetcode 377. Combination Sum IV
题目链接：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.
No Comments
Tag Archiv: acm
poj 1455 Crazy tea party
这道题第一眼看去很难，其实不然，短短几行代码就搞定了。
说一下大概思路，如果是排成一排的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了。
hdoj 4768 Flyer
题目意思很容易理解，学校有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();
}
}
hdoj 4712 Hamming Distance(靠人品过的)
我先解释一下汉明距离 以下来自百度百科
在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说，它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。 例如：
* 1 与 0 之间的汉明距离是 1。
* 214 与 214 之间的汉明距离是 0。
* “abcd” 与 “aacd” 之间的汉明距离是 1。
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。
汉明距离在信息论、密码学等方向有很重要的应用。
这个题是让你求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;
}
hdoj 4706 Children’s Day
题目意思就是用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;
}
hdoj 4715 Difference Between Primes 素数筛选+二分查找
#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;
}
poj 1503 高精度加法
把输入的数加起来，输入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;
}
codeforces 322 B Ciel and Flowers
有红绿蓝三种颜色的画，每种拿三朵可以组成一束花，或者各拿一朵组成花束，告诉你每种花的数目，求出可能组成最多的花束。
如果你的代码过不了，考虑一下 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;
}