按:蓝桥和校赛很 sad….. 过几天看有题解没orz

Codeforces Round #406 (Div. 2) A (暴力?)

呃…..不暴力就是 EXGCD 吗?

C :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int a,b,c,d;
void f(){
scanf("%d%d%d%d",&a,&b,&c,&d);
if(b==d) {printf("%d\n",b);return;}
else{
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++){
if(b+i*a==d+j*c){printf("%d\n",b+i*a);return;}
}
}
printf("-1\n");
}
int main(){f();return 0;}

Codeforces Round #407 (Div. 2) A (模拟)

对于每种物品,都要取ceil(n/k)次,因此只要加起来再除以2就是答案。[1]

C++ :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cmath>
using namespace std;
const int Nmax=1e6+5;
int num[Nmax];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=(int)ceil((double)num[i]/k);
}
ans=(int)ceil((double)ans/2);
printf("%d\n",ans);
return 0;
}

Codeforces Round #367 (Div. 2) B (模拟)

这道题可以用二分搜索,可以用前缀和。

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>
int cnt[100005];
int main(){
int n,x,q;
while(scanf("%d", &n) != EOF){
memset(cnt, 0, sizeof(cnt));
for(int i=1; i<=n; i++) {
scanf("%d",&x);
cnt[x]++;
}
for(int i=1; i<100005; i++)
cnt[i] += cnt[i-1];
scanf("%d",&q);
while (q--) {
scanf("%d",&x);
if(x >= 100005) printf("%d\n", cnt[100004]);
else printf("%d\n", cnt[x]);
}
}
return 0;
}

POJ 1700 (贪心)

两种贪心策略:
1、让最快的人来回载人过去。
2、先让最快的人和次快的人过去,然后让最快的人回来,让最慢和次慢的人过去,让对面最快的人回来。整体效果是最快和次快的人让最慢和次慢的人过去。
于是两者统一,就是让最慢和次慢的人每次渡河。比较两种策略的时间。
直到剩余两个或者三个人,就稍微考虑一下即可。另外不要忘了考虑初始只有一个人的情况。[2]

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[1005];
int comp(int x,int y){
return x>y;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for (int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n,comp);

if (n<3) printf("%d\n",a[0]);
else {
int ans=0,top=0,rear=n;
while (rear-top>3){
ans+=min(a[rear-2]*2+a[rear-1]+a[top],a[top]+a[top+1]+2*a[rear-1]);
top+=2;
}
if (rear-top==2) ans+=a[rear-2];
else ans+= a[top]+a[rear-1]+a[rear-2];
printf("%d\n",ans);
}
}
return 0;
}


本文参考了:
[1] http://www.cnblogs.com/BBBob/p/6645432.html
[2] http://www.cnblogs.com/andyqsmart/p/4116342.html