B今天你升级了吗
这道题比赛的时候是甘甜做的，比赛后我才看了题，当时对着它发了好长时间呆，没想法，那么多人错，还有一堆堆的人在叫错，又说连sort都不能用，后面经甘甜提醒用hash存吗，对的呀，无穷大的就都存入一个online[200001],这样就免了sort
在处理的时候就简单了呀，处理下online 数组，是它存储的当前数目之和。来一个询问，做一次相减就可以了，但是在处理级别7的时候要特别处理下，其实有些边界还是想的不是很好，可能数据不强，没测出错误
以下是我的代码
#include<iostream>
#define Max 100000
#define MaxN 200001
int online[MaxN+1];
int N,M;
int begin[]={0,101,501,2001,10001,50001,200001};
void solve(int time,int rank)
{
int ans=0;
int low,high;
if(rank==7){
if(begin[6]>time)low=begin[6]-time;
else low=0;
if(low==0)ans=N;
else ans=N-online[low];
}
else{
low=begin[rank-1]-time;
high=begin[rank]-time;
if(low==0)ans=online[high];
else if(low<0){
if(high<0)ans=0;
else ans=online[high];
}
else ans=online[high]-online[low];
}
printf("%d\n",ans);
}
int main()
{
int i,time,rank,tmp1,tmp2;
while(scanf("%d",&N)!=EOF){
memset(online,0,sizeof(online));
for(i=0;i<N;i++){
scanf("%d",&tmp1);
if(tmp1<MaxN)online[tmp1]++;
else online[MaxN]++;
}
tmp1=online[0];
online[0]=0;
for(i=1;i<=MaxN;i++){
tmp2=online[i];
online[i]=online[i-1]+tmp1;
tmp1=tmp2;
}
scanf("%d",&M);
while(M--){
scanf("%d%d",&time,&rank);
solve(time,rank);
}
}
return 0;
}这道题我是按照以前做fary序列的一个性质做的，其实还慢庆幸的，当时刚好是我将这道题，所以还特地了解了下far有序列，具体证明在组合数学数论章是有的。
主要是指：(n，是指分母最大值)
p/q,p1/q1,p2/q2
p2 = (q + n) / q1 * p1 - p;
q2 = (q + n) / q1 * q1 - q;
这个性质很利于我们顺序构造fary序列，以下是我的代码：
#include<iostream>
int solve(int n)
{
int i=0;
int p,q,p1,q1,p2,q2;
p1=1,q1=n;
p=0;q=1;
while(p1!=q1){
p2 = (q + n) / q1 * p1 - p;
q2 = (q + n) / q1 * q1 - q;
p = p1; q = q1;
p1 = p2; q1 = q2;
i++;
}
return 2*i+1;
}
int main()
{
int N;
int num;
while(scanf("%d",&N)!=EOF){
num=solve(N);
printf("%d\n",num);
}
return 0;
}
物理与生活这道题是很值得我总结的一题，开始自己研究阶段可以说我完全是个白的，连最基本的公式都不知道，好了很长时间，因为看大家都过了，以为大家和我一样白，结果我错了，于是乎，我开始问人，首先问了卢亚德，经他一点拨，我更发现了我的白
首先做这题要有两个基本概念：
1．混合物体的质心的求法，我们假设有两个物体，第一个物体的质心是h,质量是m,第二个物体的质心是H,质量是M，那么混合物体的质心有杠杆定理得 (h*m+H*M)/(m+M)。
2．第二个基础知识是均匀圆锥体的质心据底面高度是圆锥高的1/4。
好，有了基础知识，我以为我就能轻松拿下了，再加上一听说个什么二分答案就可以了，我就兴高彩烈的开敲了，别人还告诉我不会花我多少时间，当天晚上我挺到2点，放弃，睡觉去，但此时我还是坚信这题没什么。
第二天，我继续，还是一路错到底，我开始怀疑这题能不能用二分作，后来我发现这果然不是单调的，但是具体的物理过程我还是不想去想，我只是坚信可能会有好多个波峰波谷，我把求导公式也搞出来了，结果，太复杂
第三天，也就是今天，pc用公式easy AC，来我们来分析下物理过程，液体上涨，整体质心应该是下降的，但是当液体质心和整体质心重合的时候，此时整体质心应该是最低的，但是如果继续倒入液体，而此时整体质心就会往上了，所以应该说只有一个波谷，所以按我当初的思路，记录当前整体质心的最小值，然后每次把mid计算出的整体质心和当前的比较来判断该往上该往下，这样是不对的，而他们之所以二分可以判断条件是看整体质心和液体质心是否相等，如果用之前的作其实应该三分作，虽然我之前发现问题后有尝试多分，但是我尝试的是四分，和二分没区别。
以下是我的代码：
#include<iostream>
#define pie acos(-1.0)
#define eps 1e-8
int M,R,P;
double low,high;
double compute(double i)
{
double h,m;
h=0.75*i;
m=(pie*i*i*i*P)/3.0;
return ((h*m)+(R*M/2.0))/(m+M);
}
bool check(double i)
{
double lh,rh,mh;
mh=compute(i);
if(mh<i)
return true;
else return false;
}
int main()
{
double mid,tmp;
while(scanf("%d%d%d",&M,&R,&P)!=EOF){
low=0;high=R;
while(1){
if(high-low<eps)break;
mid=(high+low)/2.0;
if(check(mid))high=mid;
else low=mid;
}
printf("%.3lf\n",low);
}
return 0;
}
H:ECNU-LAB-qwynick这道题，是自己的问题，作比赛的时候我是最先做这道题的，我上手就使用搜索作，但是判断错误呀，我从最大的数开始搜，我当时认为这样会得到最小的字典序序列，但是后面和甘甜商量下，才发现应该从最小的开始搜，于是乎我就改，才发现改了之后，问题更大了，答案都出不来，后面我一步一步的调试才发现正面搜和反面搜不一样的呀，正面搜回溯的时候我可能把成对的数字覆盖掉，这时候我已经不想做了，完全不想做了，而且还搞不清是不是这样做，这时候已经有几个人过了，我突然意识到他们的时间是四位数的，原来给的时间是10秒，我看成了1秒，虽然我还是耐着性子改下去，而且还是拿着人家的标准代码去对答案的，我出了无数组数据死活没错的呀。我崩溃了，眼看时间划过了6点
后面我发现是非负数，我没考虑0呀，在每次遇到这种问题的时候，应该去返回去看题，虽然我们也懂，我和甘甜也意识到问题不会大，但是一个是改了一下午失去了耐性，一个是改别的题改的头大，根本看不进别的题。俩个人都放弃了，比赛的时候结果也许就是差那么一点点。
以下是我的代码，我没做什么剪枝，实在不想看到它了
#include<iostream>
#include<algorithm>
using namespace std;
#define MaxN 25
#define Max 25
int num[Max]={0};
int ans[Max];
int data[MaxN];
int tmp[Max];
int hash[MaxN];
int n,k;
void init()
{
int i=0;
memset(num,0,sizeof(num));
for(i=0;i<Max;i++)
num[i]=2+i;
}
void print()
{
int i;
for(i=1;i<2*n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[i]);
}
void solve(int i,int rest)
{
if(rest==0){
k=1;
print();
return;
}
if(ans[i]!=-1)solve(i+1,rest);
int j;
for(j=1;j<=n;j++){
if(tmp[i]==2)return;
if(hash[data[j]])continue;
if(i+num[data[j]]-1>2*n)return;
if(ans[i+num[data[j]]-1]!=-1)continue;
ans[i]=data[j];
ans[i+num[data[j]]-1]=data[j];
tmp[i]=1;
tmp[i+num[data[j]]-1]=2;
hash[data[j]]=1;
solve(i+1,rest-2);
if(k)return;
ans[i]=ans[i+num[data[j]]-1]=-1;
tmp[i]=tmp[i+num[data[j]]-1]=0;
hash[data[j]]=0;
}
}
int main()
{
int i;
init();
while(scanf("%d",&n)!=EOF&&n){
k=0;
memset(data,0,sizeof(data));
memset(hash,0,sizeof(hash));
memset(ans,-1,sizeof(ans));
memset(tmp,0,sizeof(tmp));
for(i=1;i<=n;i++)
scanf("%d",&data[i]);
for(i=1;i<=n;i++)
if(num[data[i]]>2*n){
printf("NO ANSWER!\n");
break;
}
if(i>n){
sort(data+1,data+n+1);
solve(1,2*n);
if(!k) printf("NO ANSWER!\n");
}
}
return 0;
}
posted on 2008-04-16 19:48
zoyi 阅读(260)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
比赛总结