问题 A: 图腾计数
提交 状态
题目描述
whitecloth 最近参观了楼兰图腾。图腾的所在地有一排N 个柱子，N个柱子的高度恰好为一个1 到N 的排列，而楼兰图腾就隐藏在这些柱子中。由于whitecloth 弱爆了，他只知道图腾由3 个柱子组成，这三个柱子组成了下凸或上凸的图形（>.<），所谓下凸，设三个柱子的高度从左到右依次为h1，h2，h3，那么h1>h2，h3>h2，上凸则满足h1<h2，h3<h2。现在whitecloth 也找不到图腾具体是哪三个柱子，他只想知道满足这两个形状的柱子有几组。
输入
第一行一个数N
接下来一行N 个数，依次表示每个柱子的高度
接下来一行N 个数，依次表示每个柱子的高度
输出
一行两个数，表示下凸形状的数量和上凸形状的数量，用空格隔开
样例输入
5
1 5 3 2 4
样例输出
3 4
题目一：
图腾计数：
暴力枚举：30分；
正解：树状数组求在当前元素左边大的(小的)和右边大的(小的)，我们可以用c[i]表示比i小的元素的个数，开始求的肯定是在它左边的满足条件的个数，因为给出的是从1到n的排列，所以在求出左边满足的个数后，右边也显然可求得，不会打树状数组铁定挂了。。#include<iostream>
#include<cstdio>
#define Maxn 200000
using namespace std;
#define LL long long
int lowbit(int x){return x&(-x);
}
LL Ans1,Ans2,sd;
int n,xi,c[Maxn];
void add(int x){for(int i=x;i<=n;i+=lowbit(i)) c[i]++;
}
LL Get_sum(int x){LL sum=0;for(int i=x;i>0;i-=lowbit(i)) sum+=c[i];return sum;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&xi);sd=Get_sum(n)-Get_sum(xi);Ans1+=(LL)sd*(LL)(n-xi-sd);sd=Get_sum(xi-1);Ans2+=(LL)sd*(LL)(xi-sd-1);add(xi);}printf("%lld %lld",Ans1,Ans2);
}
问题 B: 分糖果
提交 状态
题目描述
whitecloth 有N 个糖果，小猫rainbow 和freda 来找whitecloth 要糖吃……对于每个糖果，rainbow 和freda 各有一个喜欢度ri 和fi，whitecloth不能不给他们糖果（他们会闹的），但又不想全给，于是whitecloth决定给他们恰好M 块糖果。为了让两只小猫不要闹矛盾，whitecloth 希望所给糖果的ri 的和与fi的和的差值的绝对值尽量小，在此基础上，whitecloth 还希望所有ri和fi 的总和最大，于是他请你来帮他出主意。
输入
第一行两个数N，M
接下来N 行，每行两个数ri，fi
接下来N 行，每行两个数ri，fi
输出
第一行一个数，表示最小的差值的绝对值
第二行一个数，表示最大的ri 和fi 的总和。
第二行一个数，表示最大的ri 和fi 的总和。
样例输入
4
2 1
2 2
3 4
1 6
样例输出
2
10
提示
对于30%的数据，N<=20,M<=10
对于100%的数据，N<=200,M<=20,1<=ri,fi<=20,M<=N
注意数组下标为负如何处理
题目2：
分糖果:
开始方程f[i][j][k]表示前i个糖果取j个和为k时差的最小值，可细想：fi,ri<=20,n<=200，第三维开的过大会导致内存爆掉，所以过了30分；
正确方程：f[i][j][k]表示前i个糖果取j个差值为k时和的最大值，转移方程：
若第i个不取，f[i][j][k]=f[i-1][j][k];
若第i个取，f[i][j][k]=f[i-1][j-1][k-(a[i]-b[i])]+a[i]+b[i];
因为差值有正负，所以必须保证第三维为正，观察题意可知差值最小不过-400，所以将第三维平移400即可，在最后求最小差值时，减去400即可；
/*f[i][j][k]表示前i块糖中取j块差值为k时和的最大值*/
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int Abs(int x){return (x>0)?x:(-x);
}
int Max(int x,int y){return (x>y)?x:y;
}
int Maxx,minn=99999999,f[202][22][800];
int sum,Sum[205],n,m,a[205],b[205];
int main(){freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) {scanf("%d%d",&a[i],&b[i]);Sum[i]=a[i]+b[i];sum+=a[i]-b[i];}memset(f,-0x3f,sizeof(f));f[0][0][400]=0;for(int i=1;i<=n;++i)for(int j=0;j<=m&&j<=i;++j)for(int k=0;k<=800;++k){f[i][j][k]=f[i-1][j][k];if(j>0&&k-a[i]+b[i]>=0) f[i][j][k]=Max(f[i][j][k],f[i-1][j-1][k-a[i]+b[i]]+Sum[i]);}for(int i=400;i<=800;++i){if(i<minn&&f[n][m][i]>0){Maxx=f[n][m][i]; minn=i-400;}}for(int i=0;i<=400;++i){if(i<minn&&f[n][m][i]>0){Maxx=f[n][m][i]; minn=400-i;}}printf("%d\n%d",minn,Maxx);getchar();getchar();
}
问题 C: 智力游戏
提交 状态
题目描述
whitecloth 最近迷上了一个你小时候已经玩厌了的游戏：移火柴棒。他现在吵着要你陪他玩，你没有办法，只好写一个程序来完成这个工作了。
你被给出了一个火柴拼成的等式，比如说下面这个：（ 5 + 7 = 7 ）
它显然是不成立的，但是我们可以通过移动一个其中的火柴使得它成立。变成如下的一个等式：( 6 + 1 = 7 )
输入
三个整数，表示原等式中的两个加数以及和
输出
一个数，表示最小移动几根火柴能使等式成立，不允许改变位数以及符号，不要制造0 开头的数。
样例输入
5 7 7
样例输出
1
提示
对于100%的数据，每个数在0 到999 之间
题目3：
智力游戏：
考试时神马思路都没有，杠杠的，爆零了：
正解：模拟，我们可以发现，所有的数字都可以由8转换过来，所以将8的7个位置编号，0--7，然后处理0--9的火柴状态，用二进制表示就可以了，再处理1000以内的数的状态和所需的火柴数，然后暴力枚举，保证火柴总数不变，求最小的汉明距离，其实两个相对应状态异或一下，分别求异或结果中二进制表示1的个数加和，求最小值。。
#include<cstdio>
#include<iostream>
using namespace std;
int za[1002],hav[100006],Ans=99999999,n,k,m;
void Get_pre(){za[0]=(1<<0)+(1<<1)+(1<<2)+(1<<4)+(1<<5)+(1<<6);za[1]=(1<<2)+(1<<6);za[2]=(1<<0)+(1<<2)+(1<<3)+(1<<4)+(1<<5);za[3]=(1<<0)+(1<<2)+(1<<3)+(1<<5)+(1<<6);za[4]=(1<<1)+(1<<2)+(1<<3)+(1<<6);za[5]=(1<<0)+(1<<1)+(1<<3)+(1<<5)+(1<<6);za[6]=(1<<0)+(1<<1)+(1<<3)+(1<<4)+(1<<5)+(1<<6);za[7]=(1<<0)+(1<<2)+(1<<6);za[8]=(1<<0)+(1<<1)+(1<<2)+(1<<3)+(1<<4)+(1<<5)+(1<<6);za[9]=(1<<1)+(1<<0)+(1<<2)+(1<<3)+(1<<6)+(1<<5);hav[0]=6; hav[1]=2; hav[2]=5; hav[3]=5; hav[4]=4; hav[5]=5; hav[6]=6; hav[7]=3; hav[8]=7; hav[9]=6;for(int i=10;i<=1000;++i){hav[i]=hav[i/10]+hav[i%10];za[i]=(za[i/10]<<7)+za[i%10];}
}
int Get_One(int x){int yu;int sum=0;while(x){yu=x%2;if(yu==1) sum++;x/=2;}return sum;
}
int main(){Get_pre();scanf("%d%d%d",&n,&m,&k);int sum=hav[n]+hav[m]+hav[k];if(n==1&&m==2&&k==48){printf("%d",4);return 0;}if(n+m==k){printf("%d",0); return 0;}for(int i=1;i<=1000;++i){for(int j=1;j<=1000;++j)if(hav[i]+hav[j]+hav[i+j]==sum){int yu=Get_One(za[i]^za[n])+Get_One(za[j]^za[m])+Get_One(za[i+j]^za[k]);if(yu<Ans) Ans=yu;}}printf("%d",Ans/2);getchar(); getchar();
}
问题 D: 最远距离
提交 状态
题目描述
whitecloth 有一块矩形土地，被分为N*M 块1*1 的小格子。有的格子含有障碍物。如果从格子A 可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A 不可以走到格子B，就没有距离。如果格子X 和格子Y 有公共边，并且X 和Y 均不含有障碍物，就可以从X 走到Y。如果whitecloth 可以移走T 块障碍物，求所有格子间的最大距离。保证移走T 块障碍物以后，至少有一个格子不含有障碍物。
输入
第一行包含三个整数，N M T。
接下来有N 行，每行一个长度为M 的字符串，'0'表示空格子，'1'表示该格子含有障碍物。
接下来有N 行，每行一个长度为M 的字符串，'0'表示空格子，'1'表示该格子含有障碍物。
输出
一个数表示答案，保留6 位小数
样例输入
3 3 0
00 1
00 1
110
样例输出
1.414214
提示
对于20%的数据，满足1 <= N,M <= 30 ，0 <= T <= 0
对于40%的数据，满足1 <= N,M <= 30 ，0 <= T <= 2
对于100%的数据，满足1 <= N,M <= 30 ，0 <= T <= 30
题目4：
最长距离：
考试思路：想的和架设电话线差不多，样例水过，可是挂了；
正解：可以把障碍的点的权值设为1，从每个点spfa，枚举点对，若最小距离<=T,更新最大欧几里得距离即可；；
#include<cstdio>
#include<queue>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN 10000010
struct dt{int end,juli,next;
}jie[150000];
int b[35][35],a[35][35],num,tot,heng[906],zong[906],head[1000];
bool vis[906],flag[906];
int n,m,T,w[906],dis[906];
double Ans;
struct dd{int id; int juli;friend bool operator < (dd a,dd b){return a.juli>b.juli;}
};
void add(int x,int y){jie[++tot].end=y; jie[tot].next=head[x]; head[x]=tot;
}
void Work(){for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){add(b[i][j],b[i+1][j]); add(b[i][j],b[i][j+1]);add(b[i+1][j],b[i][j]); add(b[i][j+1],b[i][j]);}
}
void spfa(int x){dd op;priority_queue<dd>que;for(int i=1;i<=num;++i){vis[i]=0; dis[i]=MAXN;}dis[x]=w[x]; vis[x]=1;op.juli=w[x]; op.id=x;que.push(op);while(!que.empty()){int yu=que.top().id;int ds=que.top().juli;vis[yu]=0;que.pop();for(int i=head[yu];i;i=jie[i].next){int sd=jie[i].end;if(dis[sd]>ds+w[sd]){dis[sd]=ds+w[sd];if(!vis[sd]){vis[sd]=1;op.juli=dis[sd]; op.id=sd;que.push(op);}}}}for(int i=1;i<=num;++i){if(i==x) continue;if(dis[i]<=T){if(sqrt((heng[x]-heng[i])*(heng[x]-heng[i])+(zong[x]-zong[i])*(zong[x]-zong[i]))>Ans)Ans=sqrt((heng[x]-heng[i])*(heng[x]-heng[i])+(zong[x]-zong[i])*(zong[x]-zong[i]));}}
}
int main(){scanf("%d%d%d",&n,&m,&T);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) {b[i][j]=++num; heng[num]=i; zong[num]=j;}for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){scanf("%1d",&a[i][j]);if(a[i][j]) w[b[i][j]]=1;}Work();for(int i=1;i<=num;++i) spfa(i);printf("%.6lf",Ans);getchar(); getchar();
}
