挑战程序设计竞赛1
1.抽签
你的朋友提议玩一个游戏:将写有数字的 n 个纸片放入口袋中,你可以从口袋中抽取 4 次纸
片,每次记下纸片上的数字后都将其放回口袋中.如果这 4 个数字的和是 m,就是你赢，否
则就是你的朋友赢.请你编写一个程序，判断当纸片上所写的数字是 k1,
k2,...., kn时，是否存在抽取 4 次和为 m 的方案。如果存在,输出 Yes;否则,输出 No.
1 ≤ m ≤ 10^8
1 ≤ ki ≤ 10^8
输入
n=3
m=10
k={1,3,5}
输出
No
1 ≤ n ≤ 50 (n^4)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
for (l=1; l<=n; l++)
if (a[i]+a[j]+a[k]+a[l]==m){
f=1;
break;
}
if (f==1)
printf("Yes\n");
else
printf("No\n");
1 ≤ n ≤ 50 (n^4)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
for (l=1; l<=n; l++)
if (a[i]+a[j]+a[k]+a[l]==m){
f=1;
break;
}
if (f==1)
printf("Yes\n");
else
printf("No\n");
sort(a+1,a+n+1);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
for (k=1; k<=n; k++){
l=a[i]+a[j]+a[k];
if (binary_search(a+1,a+n+1,l)){
f=1;
break;
}
}
1 ≤ n ≤ 1000 (n^2logn)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
b[i*n+j]=a[i]+a[j];
sort(b+1,b+1+n*n);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
l=a[i]+a[j];
if (binary_search(b+1,b+n*n+1,l)){
f=1;
break;
}
}
2.
有n根棍子,棍子i的长度为ai.想要从中选出 3 根棍子组成周长尽可能长的三角形。请输
出最大的周长,若无法组成三角形则输出 0.
3 ≤n ≤100
1 ≤ai ≤10^6
输入
n=5
a={2,3,4,5,10}
输出
12
for (i=1; i<=n; i++)
for (j=i+1; j<=n; j++)
for (k=j+1; k<=n; k++)
{
l=a[i]+a[j]+a[k];
max1=max(a[i],max(a[j],a[k]));
k=l-max1;
if (k>max1)
ans=max(ans,l);
}
printf("%\n",ans); 3.
poj1852
Ants
n只蚂蚁以每秒1cm的速度在长为L cm的竿子上爬行.当蚂蚁爬到竿子的端点时就会掉落.
由于竿子太细,两只蚂蚁相遇时,它们不能交错通过,只能各自反向爬回去。对于每只蚂蚁,
我们知道它距离竿子左端的距离 xi,但不知道它当前的朝向,请计算所有蚂蚁落下竿子所需
的最短时间和最长时间.
1 ≤ L ≤ 10^6
1 ≤ n ≤ 10^6
0 ≤ xi ≤ L
输入
L=10
n=3
x={2,6,7}
输出
min=4
max=8
首先对于最短时间，看起来所有蚂蚁都朝向较近的端点走会比较好。
事实上，这种情况下不会发生两只蚂蚁相遇的情况，
而且也不可能在比此更短的时间内走到竿子的端点。
接下来，为了思考最长时间的情况，让我们看看蚂蚁相遇时会发生什么
事实上，可以知道两只蚂蚁相遇后，当它们保持原样交错而过继续前进也不会有任何问题。
这样看来，可以认为每只蚂蚁都是独立运动的,所以要求最长时间，
只要求蚂蚁到竿子端点的最大距离就好了。
这样，不论最长时间还是最短时间，都只要对每只蚂蚁检查一次就好了，
这是O(n)时间的算法。对于限制条件n ≤ 10^6，这个算法是够用的，于是问题得解。
for (i=1; i<=n; i++)
minT=max(minT,min(a[i],L-a[i]));
for (i=1; i<=n; i++)
maxT=max(maxT,max(a[i],L-a[i]));4.
n!=n*(n-1)*(n-2)....*1
int fact(int x){
if (x==0) return 1;
return x*fact(x-1);
}
5.
fib[i]=fib[i-1]+fib[i-2]
int fib(int x){
if (x==1) return 1;
if (x==2) return 2;
if (f[x]) return f[x];
return fib[x-1]+fib[x-2];
}
6.部分和问题
给定整数 a1,a2....an，判断是否可以从中选出若干数，使它们的和恰好为 k
输入
n
1 ≤ n ≤ 20
-10^8 ≤ ai ≤ 10^8
-10^8 ≤ k ≤ 10^8
输入
n=4
a={1,2,4,7}
k=13
输出
Yes
bool dfs(int i,int sum){
if (i==n) return sum==k;
if (dfs(i+1,sum)) return 1;
if (dfs(i+1,sum+a[i])) return 1;
return 0;
}
if (dfs(0, 0)) printf("Yes\n");
else printf("No\n");
7.
poj2386
Lake Counting
有一个大小为 N*M 的园子,雨后积起了水.八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼？(八连通指的是下图中相对 W 的*的部分)
***
*W*
***
N, M ≤100输入
N=10, M=12
园子如下图（'W'表示积水，'.'表示没有积水）
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出
3
void dfs(int x,int y)
{
c[i][j]='.';
for (int i=-1; i<=1; i++)
for (int j=-1; j<=1; j++)
{
int xx=x+i,yy=y+j;
if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&c[xx][yy]=='W')
dfs(xx,yy);
}
}
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (c[i][j]=='W')
{
ans++;
dfs(i,j);
}8.
迷宫的最短路径
给定一个大小为 N×M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右
四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定
可以移动到终点。
N,M<=100
输入
N=10, M=10（迷宫如下图所示。'#'，'.'，'S'，'G'分别表示墙壁、通道、起点和终点）
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
输出
22
const int INF=10000000000;
typedef pair<int,int> P;
d[4][2]= {1,0,0,1,-1,0,0,-1}
int bfs()
{
queue<P>q;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
d[i][j]=INF;
q.push(P(sx,sy));
while (q.size())
{
P p=q.front();
q.pop();
if (p.first==gx&&p.second)
break;
}
for (int i=0; i<4; i++)
{
int nx=p.first+d[i][0],ny=p.secon+d[i][1];
if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&c[nx][ny]=='#'d[nx][ny]==INF)
{
q.push(P(nx,ny));
d[nx][ny]=d[p.first][p.second]+1;
}
}
return d[gx][gy];
}
printf("%d\n",bfs());9.
特殊状态的枚举
虽然生成可行解空间多数采用深度优先搜索，但在状态空间比较特殊时其实可以很简短
地实现.比如，C++的标准库中提供了next_permutation这一函数，可以把n个元素共n!种不同的排列生
成出来.又或者,通过使用位运算,可以枚举从n个元素中取出k个的共C(n,k)种状态或是某个集合
中的全部子集等。next_permutation(a,a+n)这一函数，可以把n个元素共n!种不同的排列生成出来
// 生成{0,1,2,3,4,...,n-1}的n!种排列
void permutation(int x,int n)
{
if (x== n)
{
return ;
}
for (int i = 0; i < n; i++)
{
if (!used[i])
{
perm[x] = i;
used[i] =1;
permutation(pos + 1, n);
used[i] =0;
}
}
}
// 即使有重复的元素也会生成所有的排列
// next_permutation是按照字典序来生成下一个排列的
for (i=1; i<=n; i++)
a[i]=i;
do
{
}
while (next_permutation(a+1,a+1+n));
// 所有的排列都生成后，next_permutation会返回falsefor (i=5; i>=1; i--)
{
int t=min(A/v[i],c[i]);//v[i] 面值 c[i] 个数
A=A-t*c[i];
ans+=t;
}
pair<int,int>a[1000010];
for (i=1;i<n;i++){
a[i].first=t[i];
a[i].second=s[i];
}
sort(a+1,a+n+1);
for (i=1;i<=n;i++)
if (a[i].second>k){
ans++;
k=a[i].first;
}
a=0;
b=len-1;
while (a<=b)
{
l=0;
for (i=0; a+i<=b; i++)
if (c[a+i]<c[b-i])
{
l=1;
break;
}
else
{
l=0;
break;
}
if (l)
putchar(c[a++]);
else
putchar(c[b--]);
}
sort(a+1,a+n+1);
i=1;
while (i<=n)
{
s=a[i];
i++;
while (i<=n&&a[i]<=s+r)
i++;
p=a[i-1];
while (i<=n&&a[i]<=p+r)
i++;
ans++;
}
priority_queue<int>q;
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%d",&a);
q.push(a);
}
while(q.size())
{
int k1=q.top();
q.pop();
k1=q.top()+k1;
q.pop();
ans+=k1;
q.push(k1);
}
int rec(int i,int j,int sum)
{
if (i==n)
return sum;
if (j<w[i])
return rec(i+1,j,sum);
else
return max(rec(i+1,j,sum),rec(i+1,j-w[i],sum+v[i]));
}
记忆化搜索
int rec(int i,int j)
{
int res;
if (dp[i][j]>=0)
return dp[i][j];
if (i==n)
return 0;
if (j<w[i])
res=rec(i+1,j);
else
res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
return dp[i][j]=res;
}
memset(dp,-1,sizeof(dp));
rec(0,w);
for (i=1; i<=n; i++)
for (j=m; j>=0; j--)
if (j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
for (i=1; i<=n; i++)
for (j=m; j>=w[i]; j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for (i=0; i<n; i++)
for (j=0; j<m; j++)
if (a[i]==b[i])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i-1][j],dp[i][j-1]);
ans=dp[n][m]
for (i=1;i<=n;i++)
for (j=w[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for (i=1; i<=n; i++)
for (j=maxn*maxv; j>=v[i]; j--)
dp[i][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
for (i=0; i<=maxn*maxv; i++)
if (dp[i]<=m)
ans=i;
memset(dp,-1,sizeof(dp));
dp[0]=0;
for (i=1; i<=n; i++)
for (j=0; j<=k; j++)
if (dp[j]>=0)
dp[j]=m[i];
else if (j<a[i]||dp[j-a[i]]<=0)
dp[j]=-1;
else
dp[j]=dp[j-a[i]]-1;
if (dp[k]>=0)
printf("Yes\n");
else
printf("No\n");
for (i=1; i<=n; i++)
dp[i]=1;
for (i=2; i<=n; i++)
for (j=1; j<i; j++)
if (a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
b[0]=a[0];
l=1;
for (i=1; i<n; i++)
if (a[i]>b[l])
b[l++]=a[i];
else
{
k=lower_bound(b,b+l,a[i])-b;
b[k]=a[i];
}
ans=l+1;
dp[0][0]=1;
for (i=1; i<=m; i++)
for (j=0; j<=n; j++)
if (j-i>=0)
dp[i][j]=(dp[i-1][j]+dp[i][j-i])%M;
else
dp[i][j]=dp[i-1][j];
for (i=0; i<=n; i++)
dp[i][0]=1;
for (i=0; i<n; i++)
for (j=1; j<=m; j++)
if (j-1-a[i]>=0)
dp[i+1][j]=(dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+M)%M;
else
dp[i+1][j]=(dp[i-1][j]+dp[i][j]+M)%M;
ans=dp[n][m];
priority_queue<int>q;
tank=p;
A[n+1]=L;
B[n+1]=0;
for (i=1; i<=n+1; i++)
{
int d=a[i]-pos;
while (tank<d)
{
if (q.empty)
{
printf("-1\n");
return 0;
}
tank+=q.top();
q.pop();
ans++;
}
tank-=d;
pos=a[i];
q.push(b[i]);
}
for (i=1; i<=k; i++)
{
scanf("%d%d%d",&z,&x,&y);
int x_eat=n+x,x_emeny=n*2+x,y_eat=n+y,y_emeny=n*2+y;
if ((z==2&&x==y)||x>n||y>n)
{
ans++;
continue;
}
if (z==1)
{
if (find(x)==find(y_eat)||find(x_eat)==find(y))
ans++;
else
{
f[find(x_eat)]=find(y_eat);
f[find(x)]=find(y);
f[find(x_emeny)]=find(y_emeny);
}
}
else
{
if (find(x)==find(y)||find(x_emeny)==find(y))
ans++;
else
{
f[find(x_eat)]=find(y);
f[find(y_emeny)]=find(x);
f[find(x_emeny)]=find(y_eat);
}
}
}