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 閱讀(296)
評論(0) 編輯 收藏 引用 所屬分類:
acm 、
比賽總結