小米安卓三道编程题AC代码分享
//1、排座位，暴力+贪心，遇到0就判断它的左右是否为0，然后放进去。输出是0/1，题目错了，坑 -------AC 100%
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
char s[maxn];
int main()
{
while(~scanf("%s",s+1))
{
int len=strlen(s+1);
s[0]='0';
s[len+1]='0';
int k;
scanf("%d",&k);
int ans=0;
for(int i=1; i<=len; i++)
{
if(s[i]=='1')
{
}
else
{
if(s[i-1]=='0'&&s[i+1]=='0')
{
ans++;
s[i]='1';
}
}
}
if(ans>=k)
{
printf("1\n");
}
else
{
printf("0\n");
}
}
return 0;
}
2、杨辉三角。不会做，以为是找规律，但是放到oeis也没有找出来。于是水了一发java大数，居然过了，应该是数据水吧，这不是正解。
我预处理把200*200的三角打出来，超过10^18就停，然后去判断。不是正解不是正解不是正解，虽然过了。-----AC 100%
import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
static BigInteger[][] a = new BigInteger[250][250];
public static void init()
{
int n=200;
BigInteger bi = new BigInteger("10000000000000000000");
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
a[i][j] = new BigInteger("0");
}
//System.out.println();
}
for(int i=1; i<=n; i++)
a[i][1] = a[i][i] = new BigInteger("1");
int limit = 10000000;
for(int i=3; i<=n; i++)
for(int j=2; j<=min(i-1,limit); j++)
{
a[i][j]=a[i-1][j-1].add(a[i-1][j]);
if(a[i][j].compareTo(bi)>0)
{
limit = j;
}
}
}
private static int min(int i, int limit)
{
// TODO Auto-generated method stub
if(i<limit) return i;
return limit;
}
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
init();
long x = cin.nextLong();
BigInteger y = BigInteger.valueOf(x);
BigInteger bi = new BigInteger("10000000000000000000");
int n=200;
int f=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=i; j++)
{
if(a[i][j].compareTo(bi)>0)
{
break;
}
if(a[i][j].equals(y))
{
f=1;
System.out.println(i);
break;
}
}
if(f==1)
{
break;
}
}
if(f==0)
{
System.out.println(x+1);
}
}
}
3、喝饮料那题，小数据暴力，大数据我直接算。我的界定线的k>=10和k<=0，其实界定线为7就ok！
k<10的时候，就是暴力放进去，看最后一天是哪天。
k>=10的时候，那就是有规律了，比如AA 10 ，那么A在第1天和第11天，即i+(num[A]-1)*k。有多种饮料的时候同理。------AC 100%
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000005
//bool f[maxn];
char s[10005];
int have[10];
bitset<maxn > f;
int cmp(int a,int b)
{
return a>b;
}
int main()
{
while(~scanf("%s",s))
{
f.reset();
memset(have,0,sizeof(have));
int k;
scanf("%d",&k);
int len=strlen(s);
for(int i=0; i<len; i++)
{
int a=s[i]-'A';
have[a]++;
}
sort(have,have+7,cmp);
int ans=0;
if(k<10)
{
for(int i=0; i<7; i++)
{
int num=have[i];
for(int j=1;; j++)
{
if(num==0)
{
break;
}
if(f[j]==false)
{
num--;
f[j]=true;
ans=max(ans,j);
j=j+k;
}
}
}
}
else
{
for(int i=0; i<7; i++)
{
int num=have[i];
ans=max(ans,i+1+(num-1)*k);
}
}
printf("%d\n",ans);
}
return 0;
}
OPPO公司福利 1202人发布