B今天你升級(jí)了嗎
這道題比賽的時(shí)候是甘甜做的，比賽后我才看了題，當(dāng)時(shí)對(duì)著它發(fā)了好長時(shí)間呆，沒想法，那么多人錯(cuò)，還有一堆堆的人在叫錯(cuò)，又說連sort都不能用，后面經(jīng)甘甜提醒用hash存嗎，對(duì)的呀，無窮大的就都存入一個(gè)online[200001],這樣就免了sort
在處理的時(shí)候就簡單了呀，處理下online 數(shù)組，是它存儲(chǔ)的當(dāng)前數(shù)目之和。來一個(gè)詢問，做一次相減就可以了，但是在處理級(jí)別7的時(shí)候要特別處理下，其實(shí)有些邊界還是想的不是很好，可能數(shù)據(jù)不強(qiáng)，沒測出錯(cuò)誤
以下是我的代碼
#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序列的一個(gè)性質(zhì)做的，其實(shí)還慢慶幸的，當(dāng)時(shí)剛好是我將這道題，所以還特地了解了下far有序列，具體證明在組合數(shù)學(xué)數(shù)論章是有的。
主要是指：(n，是指分母最大值)
p/q,p1/q1,p2/q2
p2 = (q + n) / q1 * p1 - p;
q2 = (q + n) / q1 * q1 - q;
這個(gè)性質(zhì)很利于我們順序構(gòu)造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;
}
物理與生活這道題是很值得我總結(jié)的一題，開始自己研究階段可以說我完全是個(gè)白的，連最基本的公式都不知道，好了很長時(shí)間，因?yàn)榭创蠹叶歼^了，以為大家和我一樣白，結(jié)果我錯(cuò)了，于是乎，我開始問人，首先問了盧亞德，經(jīng)他一點(diǎn)撥，我更發(fā)現(xiàn)了我的白
首先做這題要有兩個(gè)基本概念：
1．混合物體的質(zhì)心的求法，我們假設(shè)有兩個(gè)物體，第一個(gè)物體的質(zhì)心是h,質(zhì)量是m,第二個(gè)物體的質(zhì)心是H,質(zhì)量是M，那么混合物體的質(zhì)心有杠桿定理得 (h*m+H*M)/(m+M)。
2．第二個(gè)基礎(chǔ)知識(shí)是均勻圓錐體的質(zhì)心據(jù)底面高度是圓錐高的1/4。
好，有了基礎(chǔ)知識(shí)，我以為我就能輕松拿下了，再加上一聽說個(gè)什么二分答案就可以了，我就興高彩烈的開敲了，別人還告訴我不會(huì)花我多少時(shí)間，當(dāng)天晚上我挺到2點(diǎn)，放棄，睡覺去，但此時(shí)我還是堅(jiān)信這題沒什么。
第二天，我繼續(xù)，還是一路錯(cuò)到底，我開始懷疑這題能不能用二分作，后來我發(fā)現(xiàn)這果然不是單調(diào)的，但是具體的物理過程我還是不想去想，我只是堅(jiān)信可能會(huì)有好多個(gè)波峰波谷，我把求導(dǎo)公式也搞出來了，結(jié)果，太復(fù)雜
第三天，也就是今天，pc用公式easy AC，來我們來分析下物理過程，液體上漲，整體質(zhì)心應(yīng)該是下降的，但是當(dāng)液體質(zhì)心和整體質(zhì)心重合的時(shí)候，此時(shí)整體質(zhì)心應(yīng)該是最低的，但是如果繼續(xù)倒入液體，而此時(shí)整體質(zhì)心就會(huì)往上了，所以應(yīng)該說只有一個(gè)波谷，所以按我當(dāng)初的思路，記錄當(dāng)前整體質(zhì)心的最小值，然后每次把mid計(jì)算出的整體質(zhì)心和當(dāng)前的比較來判斷該往上該往下，這樣是不對(duì)的，而他們之所以二分可以判斷條件是看整體質(zhì)心和液體質(zhì)心是否相等，如果用之前的作其實(shí)應(yīng)該三分作，雖然我之前發(fā)現(xiàn)問題后有嘗試多分，但是我嘗試的是四分，和二分沒區(qū)別。
以下是我的代碼：
#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這道題，是自己的問題，作比賽的時(shí)候我是最先做這道題的，我上手就使用搜索作，但是判斷錯(cuò)誤呀，我從最大的數(shù)開始搜，我當(dāng)時(shí)認(rèn)為這樣會(huì)得到最小的字典序序列，但是后面和甘甜商量下，才發(fā)現(xiàn)應(yīng)該從最小的開始搜，于是乎我就改，才發(fā)現(xiàn)改了之后，問題更大了，答案都出不來，后面我一步一步的調(diào)試才發(fā)現(xiàn)正面搜和反面搜不一樣的呀，正面搜回溯的時(shí)候我可能把成對(duì)的數(shù)字覆蓋掉，這時(shí)候我已經(jīng)不想做了，完全不想做了，而且還搞不清是不是這樣做，這時(shí)候已經(jīng)有幾個(gè)人過了，我突然意識(shí)到他們的時(shí)間是四位數(shù)的，原來給的時(shí)間是10秒，我看成了1秒，雖然我還是耐著性子改下去，而且還是拿著人家的標(biāo)準(zhǔn)代碼去對(duì)答案的，我出了無數(shù)組數(shù)據(jù)死活沒錯(cuò)的呀。我崩潰了，眼看時(shí)間劃過了6點(diǎn)
后面我發(fā)現(xiàn)是非負(fù)數(shù)，我沒考慮0呀，在每次遇到這種問題的時(shí)候，應(yīng)該去返回去看題，雖然我們也懂，我和甘甜也意識(shí)到問題不會(huì)大，但是一個(gè)是改了一下午失去了耐性，一個(gè)是改別的題改的頭大，根本看不進(jìn)別的題。倆個(gè)人都放棄了，比賽的時(shí)候結(jié)果也許就是差那么一點(diǎn)點(diǎn)。
以下是我的代碼，我沒做什么剪枝，實(shí)在不想看到它了
#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 閱讀(283)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm 、
比賽總結(jié)