精华 京东2017实习生招聘在线笔试编程题题解
发布于 2017-04-07 21:06 23832 次浏览 13 赞 最后一次编辑是 2017-04-14 10:07 来自 试题交流  

欢迎加入京东2017实习招聘交流群:178118918

转载题解请联系京东及赛码网,版权所有违者必究。


讲师简介


纪磊



网名啊哈磊。毕业于武汉大学计算机学院;

曾在MSRA(微软亚洲研究院)机器学习组从事搜索引擎方面的研究;

发表国际会议论文一篇(IEEE);

全国青少年信息学奥林匹克金牌教练,曾培养了数名NOI/IOI选手

保送进MIT、清华、浙大、交大、复旦和华科等高校;

多次为ACM/ICPC亚洲赛区比赛命题;

出版畅销书《啊哈C!思考快你一步 》和《啊哈!算法》并被引进到港澳台;

2013年度51cto最受读者喜爱 的IT图书作者奖,当当网2014年度计算机和互联网热门作者第一名。

 


真题链接:

拍卖:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4398&konwledgeId=41


通过考试:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4396&konwledgeId=41


分堆:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4410&konwledgeId=41


站队:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4400&konwledgeId=41


异或:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4397&konwledgeId=41


终结者C:

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=4401&konwledgeId=41



拍卖:

排序以后枚举答案

示例代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 1009
int a[maxn];
int main(){
	int n, m, ans=0, a0;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++) scanf("%d", &a[i]);
	sort(a+1, a+1+m);
	for(int i=1; i<=m; i++) if (ans < a[i]*min(n,m-i+1))
		ans=a[i]*min(n,m-i+1), a0=a[i];
	printf("%d\n", a0);
	return 0;
}



通过考试:

概率dp,定义状态前i个题目对j个的概率,递推求解

示例代码:

#include <bits/stdc++.h>
#define maxn 109
using namespace std;
int n,a[maxn];
double dp[maxn][maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0]=dp[i-1][0]*(100.0-a[i])/100;
		for(int j=1;j<=i;j++)
			dp[i][j]=dp[i-1][j]*(100.0-a[i])/100+dp[i-1][j-1]*1.0*a[i]/100;
	}
	int low=(3*n+4)/5;
	double ans=0;
	for(int i=low;i<=n;i++)
		ans+=dp[n][i];
	printf("%.5f\n",ans);
	//system("pause");
	return 0;
}



分堆:

找规律,可以证明k,k+1,k,k+1...为最优序列

示例代码:

#include <cstdio>
#define maxn 109
using namespace std;
int main(){
	int n, k, ans;
	scanf("%d%d",&n, &k);
	ans = n / (2 * k + 1);
	ans *= 2;
	if(n % (2 * k + 1) >= k)
		ans++;
	printf("%d\n",ans);
	//system("pause");
	return 0;
}


站队:

找到所有警察的位置,标记被警察看到的位置

示例代码:

#include <bits/stdc++.h>
#define maxn 100009
using namespace std;
int n;
char s[maxn];
bool vis[maxn];
int main(){
    scanf("%d", &n);
    scanf("%s", s);
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n; i++){
        if(s[i] == 'X' || s[i] == '#')
            continue;
        int x = s[i] - '0';
        for(int j = 0; j <= x; j++){
            if(i - j >= 0)
                vis[i - j] = 1;
            if(i + j < n)
                vis[i + j] = 1;
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'X' && vis[i])
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}


异或:

模拟二进制运算,之后转成十进制输出

示例代码:

#include<bits/stdc++.h>
using namespace std;
char s[100];
int getnum(int n){
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans *= 2;
        ans += s[i] - '0';
    }
    return ans;
}
int main(){
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    int a = getnum(n);
    scanf("%s", s);
    int b = getnum(n);
    printf("%d\n", a ^ b);
    return 0;
}


终结者C:

运输车相对位置不变,看成运输车不动,激光炮动,枚举放激光炮的地方

示例代码:

#include<cstdio>
#include<cstring>
int a[205],b[205],c[205];
bool q(int w,int e){
	return a[e]<=a[w]&&b[e]>=a[w];
}
int n;
int s(int w,int e){
	int re=0;
	for(int i=1;i<=n;i++)
		if(q(w,i)||q(e,i))re++;
	return re;
}
void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l;
		scanf("%d %d",&a[i],&l);
		b[i]=a[i]+l;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
				int k=s(i,j);
				if(k>ans)ans=k;
			}
	printf("%d\n",ans); 
} 
int main(){ 
	work(); 
	return 0;
}


以上思路供同学们参考,也希望同学能分享自己的经验。

108 条回复

概率>60%那题....我也是两个for啊,真是可惜了 通过率30%,多写个限定条件跳过一些情况估计就AC了

2017-04-07 21:08

时间刚到我就做出来了!!气死我了

2017-04-07 21:11
1

唉,没戏了

2017-04-07 21:11

编程只有第一个40%通过率..gg ..史密达

2017-04-07 21:12

为什么我的编程题一直显示所有数据的结果均不正确,java

2017-04-07 21:13
1

考个细碎

2017-04-07 21:13

头都大了,不擅长于算法,尴尬

2017-04-07 21:13

通过率80%但没AC会酌情给分吗还是都扣掉。

2017-04-07 21:13

拍卖的代码思路和答案一模一样,但是只有 40% 的通过率? 这是为什么呀?

2017-04-07 21:13
1

哎,最不出来啊第二题。

2017-04-07 21:13

有原题链接吗,激光炮那个怎么都不对,不知道怎么回事啊

2017-04-07 21:14

gg


2017-04-07 21:14

都是泪,分堆离AC就差一个反括号。没提示好头疼……看来平常得多练练文本编辑器写代码啊

2017-04-07 21:14

选择全乱选,编程第一个90%,第二个没过。。。我天,这都是些什么题啊!转圈懵逼中。。。

2017-04-07 21:15
1
藤原拓海 回复 coder_58PJ33VQ

给80%的分数

2017-04-07 21:15
藤原拓海 回复 acmcoder57KXwaOh

今年的题比去年容易好不

2017-04-07 21:16

过了两秒钟发现if后面没写小括号的哭晕在厕所……

#include <iostream> 

#include <math.h>

#include<set>

#include<map>

#include<vector> 

#include<string>

using namespace std;

int main(){

    int n,m,i,x,j,max1,max2,q;

    long int y,z;

    std::vector<int> a;

    std::vector<long int> b; 

    while(cin>>n){

    j=0;

    max1=0;

    max2=0; 

    for(i=0;i<n;i++){

                     cin>>x>>y;

                     a.push_back(x);

                     b.push_back(y);}

     //std::vector<int>::iterator biggest1 = std::max_element(a[0],a.end());  

     //std::vector<long int>::iterator biggest2 = std::max_element(std::begin(b), std::end(b));  

     q= *max_element(a.begin(),a.end());    

     z=*max_element(b.begin(),b.end());  

    //cout<<z<<endl;

    for(long int t=0;t<z+q;t++){

    j=0;

      for(i=0;i<n;i++){

      if(a[i]-t<=0&&a[i]-t+b[i]>=0){

      j=j+1;}}

      if (j>=max2){

      if (j>=max1){

      max2=max1;

      max1=j;      }

      else{

      max2=j;}}

                }          

    cout<<max1+max2<<endl;     

    }

}


2017-04-07 21:16

分堆那道题,为什么要k,k+1,k,k+1……这样?

为什么不是k,1,k,1,k,1……这样?

这是题目要求:

1. ai≥1(1≤i≤m)

2. ai≠ai+1(1≤i<m)

3. a1+a2+...+am=n

问:a1,a2.....,am中大于等于k的数最多能有多少个?



2017-04-07 21:16
coder_5CRKJEBY 回复 acmcoderJOJfay3j

我用递归写的。。20%。。臣妾缩不下来啊。。

2017-04-07 21:17

在本地编译器上一点问题没有,在赛码网上就是通过不了,已经多次深受其苦了

2017-04-07 21:17
1
//通过率80%。。。。。不知道咋回事,道友请指教
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for (int i=0; i<n; i++) {
        cin>>a[i];
    }
    int m;
    if(n*3%5==0)
    {
        m=n*3/5;
    }
    else
    {
        m=n*3/5+1;
    }
    double k = 1;
    double z=1;
    double u=1;
    double p;
    double result;//存储结果
    for (int i=1; i<n+1;i++) {
        k=k*i;
    }
    for (int i=1; i<m+1;i++) {
        z=z*i;
    }
    for (int i=1; i<n-m+1;i++) {
        u=u*i;
    }
    p=k/(z*u)+1;
    
    //cout<<p;
    double q=1;
    for (int t=0; t<n; t++) {
        q = a[t]*q;
    }
    double x=q/pow(100, n);
    
    result = p*x;
    cout<<setiosflags(ios::fixed)<<setprecision(5)<<result<<endl;
    //cout<<m;
    return  0;
}


2017-04-07 21:17
coder_FG55CUXH 回复 藤原拓海

diyiti henrongyi haobu

2017-04-07 21:17

好悲伤,直接弱掉

2017-04-07 21:18
acmcoderyzPkohAW 回复 acmcoder8z52ohKR

比如10,2: 用1间隔答案是3,k和k+1的话答案是4

2017-04-07 21:18

这是android方向?   

2017-04-07 21:18

终结者C这道题这样的思路行不行?

每个车可以看成是线段,第一次求出这些线段最大重叠数量,然后删去这部分,再求一次剩余的最大重叠数量。两次的累和就是结果。

因为第一次和第二次,如果删去的这部分,既属于第一次也属于第二次,那么无论是用第一次删还是第二次删都是可以的,如果要么属于第一次,要么属于第二次,则怎么删都不会互相影响。

这样的思路能不能解?

2017-04-07 21:18
acmcoderaHyCw4Rm 回复 acmcoder8z52ohKR

你用 n = 4k + 2 这个数据测试一下会发现

2017-04-07 21:19
acmcoderQ08522dl 回复 coder_Z4K3SCVP

不是可以使用ide吗

2017-04-07 21:19

为啥没有前端的编程题呢

2017-04-07 21:19
acmcoder8z52ohKR 回复 acmcoderyzPkohAW

谢谢指教。谢谢

2017-04-07 21:20

为什么它给我显示的是android方向,谁能告诉我 这到底跟android对口不?

2017-04-07 21:20
藤原拓海 回复 coder_RE9RT5E6

看看那个编程说明,上面有一些限制的,按那个来,把在本地的代码稍微改改就行了

2017-04-07 21:20
acmcoder8z52ohKR 回复 acmcoderaHyCw4Rm

已经知道自己错了,但不明白为什么是这样的规律

2017-04-07 21:21

终结者这题好难啊 一个小时都没做出来

2017-04-07 21:21
2
acmcoderoVmPiPwf 回复 acmcoderWdFQdYrZ

我前端做了拍卖和通过考试的啊

2017-04-07 21:21
coder_YDA6G9C9 回复 acmcoder8z52ohKR

我也是k,1,k,1了。。

2017-04-07 21:21
n = int(raw_input())
points = []
for i in range(n):
    point = raw_input().split(" ")
    points.append([int(point[0]),int(point[0])+int(point[1])])
# sort points by end x-axis
points = sorted(points, key=lambda x: x[1])
# count items for every valid intervals
res = {}
end = -sys.maxint
for interval in points:
    if interval[0] > end:
        res[interval[1]] = 1
        end = interval[1]
    else:
        res[end] += 1
# find the largest 2 intervals
max = sorted(res.values())[-2:]
print(sum(max))


本地至少样例输入是能输出4的(欢迎复制粘贴跑一跑),然而测试一个都不过,求高人指点!

2017-04-07 21:22

public class teminater

{

public static class car

{

int x1;

int x2;

boolean hit = false;


public car(int a, int b)

{

x1 = a;

x2 = b;

};


boolean hit(int boo)

{

return (x1 <= boo) && (boo <= x2);

}


};


public static int[] sort(int[] sq, int m, int n)

{


int rtag = 2;

int ltag = 2;

int pivot = sq[m];

int low = m;

int high = n;

while (high > low)

{

while ((high > low) && (sq[high]) >= pivot)

{

high--;

switch (rtag)

{

case 0:

break;

case 1:

{

if (sq[high + 1] > sq[high + 2])

{

rtag = 0;

}

break;

}

case 2:

{

rtag = 1;

break;

}

}

}

sq[low] = sq[high];

while ((high > low) && (sq[low]) <= pivot)

{

low++;

switch (ltag)

{

case 0:

break;

case 1:

{

if (sq[low - 1] < sq[low - 2])

{

ltag = 0;

}

break;

}

case 2:

{

ltag = 1;

break;

}

}

}

sq[high] = sq[low];


}

sq[high] = pivot;

int[] r = new int[3];

r[0] = high;

r[1] = ltag;

r[2] = rtag;

return r;

}


public static void qsort(int[] sq, int m, int n)

{

int[] mid =

{ 0, 0, 0 };

if (m < n)

{

mid = sort(sq, m, n);

}

if ((mid[0] - 1 > m) && (mid[1] == 0))

{

qsort(sq, m, mid[0] - 1);


}

if ((mid[0] + 1 < n) && (mid[2] == 0))

{

qsort(sq, mid[0] + 1, n);

}


}

public static void main(String[] ags)

{

Scanner s = new Scanner(System.in);

int n = s.nextInt();

s.nextLine();

int[] cands = new int[2 * n];

car[] cars = new car[n];

for (int i = 0; i < n; i++)

{

int x = s.nextInt();

int y = s.nextInt();

s.nextLine();

cands[2 * i] = x;//临界值肯定是某个矩形的边界,所以只考虑边界

cands[2 * i + 1] = x+y;

cars[i] = new car(x, x+y);

}

qsort(cands, 0, cands.length - 1);//对2*n个边界快排

int result = 0;

int tagi = Integer.MAX_VALUE;

for (int i = 0; i < cands.length; i++)//双重遍历

{

if (cands[i] == tagi)

continue;

int count1 = 0;

for (int m = 0; m < cars.length; m++)

{

if (cars[m].hit(cands[i]))

{

count1++;

cars[m].hit = true;


}

}

int tagj = Integer.MAX_VALUE;

for (int j = i + 1; j < cands.length; j++)

{

if (cands[j] == tagj)

continue;

int count2 = 0;

for (int m = 0; m < cars.length; m++)

{

if (cars[m].hit(cands[i]))

{

if (cars[m].hit == false)

//count1++;忘记把count1改成count2.没ac过

                                                    count++;

else

{

cars[m].hit = false;

}


}

}

int temp = count1 + count2;

if (result < temp)

{

result = temp;

}


tagj = cands[j];

}

tagi = cands[i];

}

System.out.println(result);


}



}


2017-04-07 21:22
藤原拓海 回复 coder_G24YGPQA

道友别哭,站起来撸

2017-04-07 21:23
acmcoder8z52ohKR 回复 coder_YDA6G9C9

唉。1浪费多了,可以堆一起形成少量的k+1。。。这个故事告诉我们,苍蝇再小也是肉。。

2017-04-07 21:23
wiklvrain 回复 coder_2X9B7M9J

刚刚提交了一下他给的代码…能过…而且仔细想想思路其实也是可以的…只需要枚举线段的两端就可以…大概是这样

2017-04-07 21:23
藤原拓海 回复 coder_Z4K3SCVP

你似不似傻,你现在本地IDE里面写啊,然后copy上去,稍微改改就行了啊

2017-04-07 21:25
coder_2X9B7M9J 回复 wiklvrain

应该把最大重叠数量的那些线段都删了吧。如果出现一辆车被重复击穿了两次呢?是算击毁一辆车还是两辆?

2017-04-07 21:28

只AC了一题

警察小偷

public class Main

{


public static void main(String[] args)

{

// TODO Auto-generated method stub

Scanner s = new Scanner(System.in);

int n = s.nextInt();

s.nextLine();

String q = s.nextLine();

LinkedList<Integer> ls = new LinkedList<Integer>();

int re = -1;

int found = 0;

System.out.println(q);

for (int i = 0; i < q.length(); i++)

{

char w = q.charAt(i);

if (w == 'X')

{   

if (re >= i)

{

found++;

} else

{

ls.add(i);

}

} else if (w == '#')

{


} else

{   

int ab = w - '0';

while ((!ls.isEmpty()) && (ls.peekLast() + ab >=i))

{

ls.pollLast();

found++;

System.out.println("here");

}

int cre=i+ab;

if(cre>re)re=cre;

}


}

System.out.println(found);


}


}

第二题差一点点



2017-04-07 21:29
coder_6K46ASZ2 回复 wiklvrain

不行,这样只能通过百分之70.剩下百分之30的用例显示答案错误

2017-04-07 21:31

终结者C代码,AC80%,到最后一刻都木有找到哪个case通不过。


主要思想就是将所有边界点揉碎了在一起遍历,找到所有矩形的左侧坐标到右侧坐标中均包括的最多的一个点,记录下次数,之后将于这个点相关的所有矩形去除,用同样的方式遍历第二个点。


最终返回值。



#include<iostream>

#include<algorithm>

#include<set>

using namespace std;


struct P

{

long long int begin,end;

}pa[205];


int main()

{

int n, i, j;

while (cin >> n)

{

for (i = 0; i < n; ++i)

{

int l;

cin >> pa[i].begin >> l;

pa[i].end = pa[i].begin + l;

}

int maxx = 0;

long long int x1;

for (i = 0; i < n; ++i)

{

long long int x=pa[i].begin, y=pa[i].end;

int sumx = 0, sumy = 0;

for (j = 0; j < n; ++j)

{

if (pa[j].begin <= x&&pa[j].end >= x)

++sumx;

if (pa[j].begin <= y&&pa[j].end >= y)

++sumy;

}

if (sumx>maxx)

{

x1 = x;

maxx = sumx;

}

if (sumy > maxx)

{

x1 = y;

maxx = sumy;

}

}

int ans = maxx;

for (i = 0; i < n; ++i)

{

if (pa[i].begin <= x1&&pa[i].end >= x1)

pa[i].begin = pa[i].end = -1;

}

maxx = 0;

for (i = 0; i < n; ++i)

{

long long int x = pa[i].begin, y = pa[i].end;

if (x == -1)

continue;

int sumx = 0, sumy = 0;

for (j = 0; j < n; ++j)

{

if (pa[j].begin == -1)

continue;

if (pa[j].begin <= x&&pa[j].end >= x)

sumx++;

if (pa[j].begin <= y&&pa[j].end >= y)

sumy++;

}

if (sumx>maxx)

maxx = sumx;

if (sumy > maxx)

maxx = sumy;

}

ans += maxx;

cout << ans << endl;

}

return 0;

}


2017-04-07 21:31
coder_X9YSPBA9 回复 wiklvrain

我咋感觉答案不对啊

2017-04-07 21:34
coder_2X9B7M9J 回复 wiklvrain

哦,可能是我搞错了。

2017-04-07 21:34

异或比较简单,水过...


#include<iostream>
#include<cstring>
using namespace std;
#define maxN 21
char a[maxN];
char b[maxN];
int res[maxN];
int main()
{
int n,i;
while (cin >> n)
{
for (i = 0; i < n; ++i)
cin >> a[i];
for (i = 0; i < n; ++i)
cin >> b[i];
for (i = 0; i < n; ++i)
res[i] = a[i] == b[i] ? 0 : 1;
int num = 0;
int tmp = 1;
for (i = n - 1; i >= 0; --i)
{
if (res[i])
num += tmp;
tmp *= 2;
}
cout << num << endl;
}
return 0;
}


2017-04-07 21:34
coder_RE7F2QGZ 回复 acmcoderx9y4ISWf

我们的思路类似,你可以看下我的Code,在你楼下的楼下

2017-04-07 21:44
coder_Z94H8DUM 回复 wiklvrain

我是这样做的,但是并没有AC,怀疑官方解法有误。

2017-04-07 21:46
Yayanh 回复 acmcoderqje0s4it

我也是一样,不过我最后做了一个测试,在赛码oj上提供的read_line()函数取一行的字符长度是有限制的,也就是说超过40%以上的用例使用read_line()函数不能完整的取到第二行的所有所有字符

2017-04-07 21:46
acmcoderHH34flRX 回复 coder_RE7F2QGZ

感觉去除之后再遍历是不能保证两次和最大的

2017-04-07 21:47

通过考试那一题不可以先组合出所有可能,然后概率求和吗,,,,,本地运行没问题,通过10%.............

2017-04-07 21:47
1
acmcoderx9y4ISWf 回复 coder_RE7F2QGZ

感觉这样优点坑,难道就没人反应吗?

2017-04-07 21:48
魏思政 回复 coder_G24YGPQA

是终结者C吗我怎么算都不过,测试给了我

2017-04-07 21:49

断网了,代码没交怎么办啊


2017-04-07 21:50
魏思政 回复 acmcoderHH34flRX

是终结者C吗我怎么算都不过,测试给了:10 67 27 32 9 45 40 27 24 38 39 19 33 30 42 34 16 40 9 5 31 \n\r这个结果我运行是10,也是10按,为啥结果是9,能帮解释下吗

2017-04-07 21:50
acmcoderqje0s4it 回复 Yayanh

对,我发现了,给的测试用例 m 为456,即测试数据有 456 组时,一次 read_line 只能读入 150 组数据

2017-04-07 21:50

20分一道编程题,通过90%,给18分,还是给0分?

2017-04-07 21:50

import java.util.*;


public class Main {


public static Scanner in = new Scanner(System.in);


public static void main(String[] args) {

    long n = in.nextLong();

      long k = in.nextLong();

      long x = n  /  (2 * k + 1) * 2;

      long y = n % (2 * k + 1);

      if (y >= k) x++;

      System.out.println(x);

    }

}

//断网了 代码没交 怎么办

2017-04-07 21:52
acmcoderh9uKecgX 回复 藤原拓海

真的吗????

2017-04-07 21:52

站队问题中,n的范围为1<=n<=100000,而官网给出的程序中n被定义成了int型,这样对吗?当然,肯定也有问题的,n应该为long int型才对。

2017-04-07 21:53
coder_MYANK4CV 回复 acmcoderqje0s4it

我也是!!!怎么办。。。。

2017-04-07 21:53
var line;
var numflag = false;
var pri = [];
while(line = read_line()){
    line = line.split(' ');
    if(!numflag){
    	var n = parseInt(line[0]);
        var m = parseInt(line[1]);
        numflag = true;
    } else {
    	for(var i = 0; i < line.length; i++){
        	pri[i] = parseInt(line[i]);
        }
        maxBenefit(n, m, pri);
        pri = [];
        numflag = false;
    }
}
function maxBenefit(n, m, arr){
  	 var minn = Math.min(n, m);
     arr.sort(function (a, b){
     	return b - a;
     })
  	 var priMax = -1;
     var pri = 0;
     for(var i = 0; i < minn; i++){
     	if(arr[i] * (i+1) > priMax){
        	pri = arr[i];
            priMax = pri * (i + 1);
        }
     }
  	print(pri);
}

为什么n=123 m=456 的时候始终会输出两个数据?

2017-04-07 21:53
1
藤原拓海 回复 acmcoderViKCAn2V

默哀

2017-04-07 21:53
藤原拓海 回复 acmcoderh9uKecgX

18

2017-04-07 21:54
coder_Z94H8DUM 回复 acmcoderx9y4ISWf

相当坑,其实就是一个简单的贪婪算法。不能用lambda排序就算了,官方还给个错误解。

2017-04-07 21:54
acmcodersoRXGByh 回复 coder_RE7F2QGZ

局部最优不一定是全局最优。比如这组数据6 0 4 2 4 2 4 5 3 5 3 7 9

2017-04-07 21:54
acmcoderh9uKecgX 回复 藤原拓海

爱心

2017-04-07 21:56

最后一刻,没来得及把类名JD2改为Main,就自动交卷了。😭

2017-04-07 21:58
3
coder_VMTUPXK5 回复 acmcoder8z52ohKR

哎,也是k, 1, k, 1

2017-04-07 22:01
coder_JXSVA5K7 回复 acmcoderx9y4ISWf

我也觉得他错了,最后一个测试用例,我的结果是9,而答案的结果是11

2017-04-07 22:01
魏思政 回复 coder_Z94H8DUM

10 67 27 32 9 45 40 27 24 38 39 19 33 30 42 34 16 40 9 5 31 这一组测试样例我笔算10啊,为什么答案是9 能帮我解释下吗,我的代码是排序往下找有交集的区域

2017-04-07 22:02
coder_JXSVA5K7 回复 魏思政

17 54 34 46 10 10 9 22 39 23 47 7 31 14 19 1 42 63 6 11 10 25 38 49 34 96 42 3 1 92 37 75 21 97 22这个的时候是9

2017-04-07 22:04
//
10
67 27
32 9
45 40
27 24
38 39
19 33
30 42
34 16
40 9
5 31
我笔算是10 ,我的代码也是10 ,为什么是9,不明白,谁能帮我解释下啊
#include<cstdio>
#include<string>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

class node{
public :int x;
public :int y;
	public :	node(int X,int Y)
				{
					x=X;
					y=X+Y;
				}
};
bool cmp(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(int a,int b)
{
	return a>b;
}

int main()
{	

		int n;
    while(scanf("%d",&n)==1)
	{
	vector<node> a;

	int x,y;
	int i=n;
	int j;
	while(i--)
	{
		cin>>x>>y;
        a.push_back(node(x,y));
	}
	
	sort(a.begin(),a.end(),cmp);

	vector<int> ans;
	for(i=0;i<n;i++)
	{  
	
		int t=1;
			//printf("%d %d %d\n ",a[i].x,a[i].y,t);
		for(j=i+1;j<n;j++)
		{ 
			
			if(a[j].x<=a[i].y)
			{
				t++;
				//printf("%d %d %d\n ",a[j].x,a[j].y,t);
			}
			else
			{
				//printf("%d %d %d\n ",a[j].x,a[j].y,t);
				break;
			}
		}
	    ans.push_back(t);
	}
	int max=2;
		
	 	for(i=0;i<ans.size();i++)
		{
			int t=ans[i];
			if(t>max)
				max=t;
			for(j=i+1;j<ans.size();j++)
			{
				if(a[j].x>a[i].y)
				{
                      //printf("%d %d %d %d %d %d\n ",a[i].x,a[i].y,ans[i],a[j].x,a[j].y,ans[j]); 
					if(t+ans[j]>max)
						max=t+ans[j];
					
				}
			}
		}
		if(n==1)
			cout<<1<<endl;
	cout<<max<<endl;
	}
	return 0;
}


2017-04-07 22:05
魏思政 回复 魏思政

终结者C这一题

2017-04-07 22:05
coder_JXSVA5K7 回复 魏思政

你的这个结果也是9

2017-04-07 22:07
coder_RE7F2QGZ 回复 acmcodersoRXGByh

你说的对,我只是判断了两个最优,但不保证是全局最优。。。

2017-04-07 22:07
Yayanh 回复 acmcoderqje0s4it

一起反应一下使用js做编程的问题。

2017-04-07 22:08
//异或答案
#include <iostream>
using namespace std;
//计算2^(n)
int get(int n)
{
    int m=1;
    for(int i=n;i>0;i--)
    {
        m*=2;
    }
    return m;
}
int main()
{
    int n;
    cin>>n;
    char num1[n];//存储二进制字符
    char num2[n]; //存储二进制字符
    char num[n]; //存储异或结果
    cin>>num1;
    cin>>num2;
    for(int i=0;i<n;i++)
    {

        if(num1[i]==num2[i])
        {
            num[i]='0';
        }
        else
            num[i]='1';
    }
    num[n]='\0';
    cout<<num<<endl;
    int res=0;//存二进制转十进制结果
    for(int i=0;i<4;i++)
    {
        res+=(num[i]-48)*get(3-i);
    }
    cout<<res<<endl;
    system("pause");
    return 0;
}


2017-04-07 22:09
coder 回复 coder_9N6VJ63V

我的也是。。。。。。js有坑么。。。

2017-04-07 22:10
var linecount = 0;
var line;
var n = 0;
var m = 0;
var price = [];
var ans = 0;
var maxP = 0;
while (line = read_line()) {
    if (linecount == 0) {
        var inputArray = line.split(' ');
        n = parseInt(inputArray[0]);
        m = parseInt(inputArray[1]);
        linecount++;
    } else if (linecount == 1) {
        price = line.split(' ');
        for (var i = 0; i < price.length; i++) {
            var num = getBuyerNum(price, parseInt(price[i]));
            var temp = parseInt(price[i]) * num;
            if (temp >= maxP) {
                if (temp == maxP) {
                    if (ans > parseInt(price[i])) {
                        maxP = temp;
                        ans = parseInt(price[i]);
                    }
                } else {
                    maxP = temp;
                    ans = parseInt(price[i]);
                }
            }
        }
        print(ans);
        linecount = 0;
        ans = 0;
    }
}

function getBuyerNum(array, price) {
    var num = 0;
    array.forEach(function (x) {
        if (parseInt(x) >= price) {
            num++;
        }
    });
    return num;
}
//123 456 那个测试数据始终输出两行数据。真的不知道为啥



2017-04-07 22:12
1
请问对于使用javascript做为编译语言时,OJ提供的输入函数read_line()不能获取测试用例中完整的一行字符,
以后OJ系统会不会对这个问题进行修改。


2017-04-07 22:13
1
acmcodersoRXGByh 回复 coder_RE7F2QGZ

我试了枚举。。就是枚举第一炮的位置,然后第二炮统计一下剩下的里面最多能打掉多少,结果妥妥地超时了。。。

2017-04-07 22:15
魏思政 回复 coder_JXSVA5K7

可以挑出来一炮就能打9个啊,不是只要 x2<=x1+l2 就可以一起打了吗?1 42 3 1 7 31 10 11 11 10 14 19 22 39 23 57 25 38

2017-04-07 22:16
//异或Java

public class T {

public static void main(String args[]){

        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();

        String one = sc.next();

        char c1[] = one.toCharArray();

        String two = sc.next();

        char c2[] = two.toCharArray();

        int c3[] = new int[s];

        for (int i=0;i<s;i++){

        if (c1[i]==c2[i]){

        c3[i]=0;

        }else{

        c3[i]=1;

        }

        }

       int sum = 0;

for (int i= 0,j=1;i<s;i++,j++){

sum += c3[i]*Math.pow(2, s-j);

}

System.out.println(sum);

    }

}


2017-04-07 22:19
coder_Z94H8DUM 回复 魏思政

我的答案是10

2017-04-07 22:24
//抓小偷问题

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
  
using namespace std;


int main()
{
	char sticks[5000];
	bool tag[5000]={0}; 
    int i,j,n;
    int ans,sum=0;
    scanf("%d",&n);
    scanf("%s",sticks);   //输入字符串
	ans=0;
    for(i=0;i<n;i++)
    {
		if(sticks[i]>='1'&&sticks[i]<='9')
		{
			ans=sticks[i]-48;
			if(i-ans<0){
				for(j=0;j<=i+ans;j++){
					if(sticks[j]=='X'){
						tag[j]=1;
					}
				}
			}    
			else{
				for(j=i-ans;j<=i+ans;j++){
					if(sticks[j]=='X'){
						tag[j]=1;
					}
				} 
			}
        }

	}
	for(i=0;i<n;i++){
		if(tag[i]==1){
			sum++;
		}
	}
	printf("%d\n",sum);
	return 0;
}


2017-04-07 22:27
acmcodercVJqrqLU 回复 acmcoderqje0s4it

我也是40%,想不出为什么没通过诶

2017-04-07 22:41

js拍卖,循环读入是必须的吗?

2017-04-07 22:48
1
acmcoderWmCpM7OJ 回复 coder_RE7F2QGZ

我的思路和你的一样,也只通过了89%

2017-04-07 23:11
coder_RE7F2QGZ 回复 acmcoderWmCpM7OJ

问一下这个只需要在浏览器界面点了调试即可吗?两个编程题都调试了,但是没点保存按钮。。

2017-04-07 23:13
test 回复 coder

没啥坑,我找了给ac的给你!去http://exercise.acmcoder.com/online/online_judge_answer?ques_id=4398&konwledgeId=41

2017-04-07 23:48

import java.util.*;


public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] start = new int[n];

        int[] end = new int[n];

        for (int i = 0; i < n; i++) {

            start[i] = scanner.nextInt();

            end[i] = start[i] + scanner.nextInt();

        }

        int res = 0;

        for (int i = 0; i < n; i++) { // 第一炮

            for (int j = i + 1; j < n; j++) { // 第二炮

                res = Math.max(res, getCar(start, end, i, j));

            }

        }

        System.out.println(res);

    }

    public static int getCar(int[] start, int[] end, int first, int second) {

        int res = 0;

        int n = start.length;

        for (int i = 0; i < n; i++) { // 计算第i辆车可不可以被打到

            if (canShoot(start[i], end[i], start[first]) || canShoot(start[i] ,end[i], start[second])) {

                res++;

            }

        }

        return res;

    }

    public static boolean canShoot(int start, int end, int cur) {

        return start <= cur && cur <= end;

    }

}


2017-04-08 00:02
1

对于站队问题,题中n的范围是[1,100000],而题主在参考程序中将n定义为一个int,我们知道unsigned int的变量最大才到65535,int的变量更小了,在这里如果n被赋值为100000,那程序就会有问题,所以参考程序不够严谨,还是有一定问题的。n应该被定义成long int的变量才对。

2017-04-08 10:16
//异或python
import numpy as np
while(True):
   n=int(raw_input())
   x = raw_input()
   y = raw_input()
   result=np.zeros(n)
   ans=0
   for i in range(n):
      if(x[i]!=y[i]):
         result[i]=1
      ans=ans*2
      ans=(ans+result[i])
   print ('%d'%ans)


2017-04-08 11:19

//警察抓小偷      好可惜当时做题时差一点愣是没做出来,今天看了下才发现少了个-48

#include<iostream>

using namespace std;

int main()

{

int n,nums=0;

bool flag=true;

char a;

cin>>n;

char *p=new char[n];

int *pnew=new int[n];

for(int i=0;i<n;i++)

{

pnew[i]=n+1;

}

for(int i=0;i<n;i++)

{

cin>>a;

p[i]=a;

int c=p[i];

}

for(int i=0;i<n;i++)

{

if(p[i]!='#'&&p[i]!='X')

{

int j;

if(i-p[i]-48>0)

{j=i-p[i]-48;}

else

{

j=0;

}

for(j;j<=i+p[i]-48;j++)

{

if(j<n)

{

if(p[j]=='X')

{

for(int ii=0;ii<nums;ii++)

{

if(j==pnew[ii])

flag=false;

}

if(flag)

{

pnew[nums]=j;

nums++;

}

flag=true;

}

}

}


}

}

cout<<nums<<endl;

return 0;

}



2017-04-08 11:58
acmcoderu1Q0qA1H 回复 ε 路人假゛

你这样是未通过吧,有的情况没考虑到

2017-04-08 12:35
test 回复 Yayanh

能给出一个完整的代码和测试用例吗?

2017-04-08 13:24
小网 回复 coder_4AA28QKZ

你看的教材版本太旧了吧,现在没人用16位环境了,32位环境int最大值是4294967296

2017-04-08 13:27
小网 回复 wiklvrain

(0 1),(1 1),(2 1),(3 1),(2,3)最大重合是3,但是你一开始把激光炮放在x=2就gg,放在1 3可以全部干完。

2017-04-08 13:33

通过考试那题,可以用更少的空间

from __future__ import division
import math
def cal_prob(probs):
    probs = [p/100 for p in probs]
    prob_length = len(probs)
    dp = [0]*(prob_length+1)
    dp[0] = 1
    for i in range(1, prob_length+1):
        for j in range(1, i+1)[::-1]:
            dp[j] = probs[i-1]*dp[j-1]+(1-probs[i-1])*dp[j]
        dp[0] = 1 - sum(dp[1:])
    pass_length = int(math.ceil(prob_length*0.6))
    return sum(dp[pass_length:])
if __name__ == '__main__':
    n = raw_input().strip()
    n = int(n)
    probs = raw_input().strip().split()
    probs = [int(p) for p in probs]
    print "%.5f"%cal_prob(probs)


2017-04-08 16:40

给出的示例代码写得真糟糕,特指整个代码的结构和命名

2017-04-08 21:15
1

#include<iostream>

using namespace std;

bool hit(int **p,int i,int t1,int t2){

return ((p[i][0]-t1<=0 &&p[i][0]+p[i][1]-t1>=0)||(p[i][0]-t2<=0 &&p[i][0]+p[i][1]-t2>=0));

}

int find(int **p,int n,int t1,int t2){

int i,num=0;

for(i=0;i<n;i++){

if (hit(p,i,t1,t2))

num+=1;

}

return num;

}

int time(int **p,int n){

int i,index=p[0][0]+p[0][1];

for(i=1;i<n;i++){

if(p[i][0]+p[i][1]>index)

index=p[i][0]+p[i][1];

}

return index;

}

int main(){

int n,i,j,t,k;

while(!cin.eof()){

cin>>n;

int **p=new int*[n];

for(i=0;i<n;i++){

p[i]=new int[2];

}

for(i=0;i<n;i++){

for(j=0;j<2;j++){

cin>>p[i][j];

}

}

t=time(p,n);

int number=0;

for(i=1;i<=t;i++){

for (j=i+1;j<=t;j++){

k=find(p,n,i,j);

if(k>number)

number=k;

}

}

cout<<k<<endl;

for(i=0;i<n;i++){

delete p[i];

}

delete [] p;

}

return 0;

}

我的想法就是hit函数用来判断第i个车是否被击中,传入的参数t1和t2分别表示第一次和第二次发射激光的时间,find函数用来求出在两次发射激光的时间时,能够击破车的数量,time函数就是记录最久的时间,就是所有车辆的尾部坐标的最大值,然后在主函数里用两个循环,就是两次击打时间的穷举,但是不知道为啥一个测试样例都不通过,还望大神答疑解惑,是不是我的想法有问题还是我的代码有误

2017-04-08 21:44

警察小偷短短13行

import sys
r = raw_input().split()
n = int(r[0])
s = raw_input().split()
m=[]
if n>=1 and n<=100000:
    for i in range(n):
        if (s[i].isdigit()):
            a,b = i - int(s[i]),i + int(s[i])
            for j in range(a,b+1):
                if s[j] == 'X':
                    m.append(j)
print len(set(m))


2017-04-09 12:19
5
import java.util.*;

/**
 * Created by Melo on 2017/4/7.
 * 有一条很长的队伍,队伍里面一共有n个人。所有的人分为三类:警察,小偷和普通人。将队伍里面的人从前到后由1到n编号,编号为i的人与编号为j的人的距离为i与j之差的绝对值。
 每一个警察有一个能力值x,表示他能够监视与他距离不超过x的所有人,小偷被警察发现当且仅当他被一个或多个警察监视到。你知道在整条队伍中,一共有多少个小偷会被警察发现吗?
 */
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        sc.nextLine();
        String l=sc.nextLine();
        char[] line=l.toCharArray();

        Set<Integer> set=new HashSet<Integer>();//存储警察的位置
        for(int i=0;i<line.length;i++){
            if (line[i]>='1'&&line[i]<='9')
                set.add(i);
        }

        int result=0; //存储结果
        Iterator it=set.iterator();
        while(it.hasNext()){
            int locale=(int)it.next();//取出警察的位置
            int power=Integer.parseInt(line[locale]+"");//得到警察的能力值
            for(int i=1;i<=power;i++){
                if ((locale-i)>=0){//没超左界限
                    if (line[locale-i]=='X'||line[locale-i]=='x'){
                        result++;
                        line[locale-i]='#';
                    }
                }else break;//否则终止循环
            }

            for(int i=1;i<=power;i++){
                if ((locale+i)<=num-1){//没超右界限
                    if (line[locale+i]=='X'||line[locale+i]=='x'){
                        result++;
                        line[locale+i]='#';
                    }
                }else break;//否则终止循环
            }


        }

        System.out.println(result);

        
    }

    
}


2017-04-09 15:39
1
acmcoderGGhYzsaF 回复 coder_G4PTXVM8

在学python,受教了,但是求解概率时不是特别明白,求详细解释 for j in range(1,i+2)[::-1]:

2017-04-14 15:28
添加回复
回到顶部