=================================================================
【Problem A. Area and Circumference】
題目大意，平面上n個矩形币他，且矩形的邊和坐標(biāo)軸平行斥难。找到面積與周長比最大的矩形驼壶，輸出比率水慨，精確4位，設(shè)有spj棵里。矩形個數(shù)不超過1w垮兑，坐標(biāo)限定在[-100,100][-100,100]。
=================================================================
【題解】暴力枚舉即可川队。
=================================================================
double ans=-1;
for(int i=1;i<=n;i++) {
double x1,y1,x2,y2; scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
double s=(x2-x1)(y1-y2), l=(x2-x1)2+(y1-y2)2;
ans=max(ans,s/l);
}
cout<<ans;
=================================================================
【Problem C. Canonical Binary Tree】
題目大意力细，現(xiàn)有n個節(jié)點，構(gòu)建一棵二叉樹固额，規(guī)則如下：1.用當(dāng)前剩余的孤立節(jié)點構(gòu)建盡可能大的完全二叉樹艳汽，從編號為0開始向編號增大方向構(gòu)建。例如n=13就構(gòu)成（8）+（4）+（1）三棵完全二叉樹对雪。2.將二叉樹的根節(jié)點從大到小按構(gòu)建順序的逆序依次連接河狐。即（4）和（1）有父親節(jié)點，再和（8）連接有父親節(jié)點瑟捣。
現(xiàn)在給定查詢馋艺，兩種查詢，為A d或B s迈套，其中A,B為字符捐祠，d為數(shù)字，s為字符串桑李。A d類查詢輸出d節(jié)點在二叉樹中的位置踱蛀，輸出方式為'LRLR'表示從根節(jié)點如何走到節(jié)點d。B s類查詢輸出按照s字符串的‘LRLR’走法會訪問到哪個節(jié)點贵白。n<=2e31率拒，詢問Q<=1w
=================================================================
【題解】先將n按二進制分解，并將其存入p[1...i]中禁荒，如13=8+4+1猬膨，p[1]=8,p[2]=4,p[3]=1.讀取查詢，對于A類查詢呛伴，判斷d在哪一棵完全二叉樹中勃痴。將d和p數(shù)組中數(shù)據(jù)比較谒所，大于則減去并輸出R，小于則說明就在這個子樹中沛申。此時問題轉(zhuǎn)換為在一棵完全二叉樹中找一個節(jié)點劣领，輸出LR，很明顯將此時的d轉(zhuǎn)換為齊位二進制铁材，0則為L剖踊，1則為R。對于B類查詢衫贬，找到s字符串前綴的連續(xù)R子串德澈，個數(shù)代表在哪一棵完全二叉樹上，統(tǒng)計前面節(jié)點個數(shù)固惯。后續(xù)處理和前者互逆梆造，L則2,R則2+1，最后結(jié)果與節(jié)點個數(shù)相加即為答案葬毫。
=================================================================
int n,q;scanf("%d %d",&n,&q);
while(n!=0){
if(n>=l){
p[++p[0]]=l;
n-=l;
}
l>>=1;
}
char c;
while(q--){
while(1){scanf("%c",&c);if(c=='A' || c=='B') break;}
if(c=='A'){
int d,i;scanf("%d",&d);d++;
for(i=1;i
if(d<=p[i]) {printf("L");break;}
else {d-=p[i];printf("R");}
}
d--;
if(p[i]>1) {
int t[50]={0};l=1;
while(1<<l < p[i]) l++;
while(d>0){t[++t[0]]=d%2;d>>=1;}
while(l){
if(t[l]==0) printf("L");
else printf("R");
l--;
}
}
printf("\n");
}
else{
char s[50];scanf("%s",s+1);
// cout<<s+1<<endl;
int len=strlen(s+1),i=1;
int ans=0;
while(s[i]=='R'&&i<=len&&i
ans+=p[i];i++;
}
int num=0,pp=p[i];
if(i<=p[0])
{
if(s[i]=='L') i++;
while(i<=len){
if(s[i]=='L') num=num*2;
else num=num*2+1;
i++;
}
ans+=num;
}
cout<<ans<<endl;
}
}
=================================================================
【Problem E. Express Lines】
題目大意镇辉，一個環(huán)形線路上有n個車站，現(xiàn)在選取若干車站組建新的快車線路贴捡，要求1：新線路至少有2個車站忽肛。要求2：新線路上的車站在原環(huán)形線路上兩兩不相鄰。問能組成多少種不同的新線路烂斋，答案mod k屹逛。例如n=4，可以有兩條汛骂，為（1,3）或（2,4）罕模。
=================================================================
【題解】當(dāng)n<=3必然為0.將環(huán)拆分成鏈，設(shè)f[1..n],g[1..n]. f[i]表示從1i且選擇了第i個車站的方案數(shù)帘瞭，g[i]表示從1i且不選擇第i個車站的方案數(shù)淑掌，明顯有f[i]=g[i-1],第i個車站選擇則第i-1個必然不選.g[i]=g[i-1]+f[i-1]，第i個車站不選則方案數(shù)為i-1的方案數(shù)蝶念。輸出f抛腕，g數(shù)組發(fā)現(xiàn)f，g呈相差一位的斐波那契數(shù)列媒殉，猜想通項公式和斐波那契有關(guān)担敌。設(shè)（n , ans）,有（3,0）（4,2）（5,5）（6,11）（7,21）,設(shè)此時ans=f(n),(注意不是數(shù)組f[n]) ,考慮g(n)=f(n-1)+f(n-2) 的關(guān)系，設(shè)（n , g(n) ) ,有（4,0）（5,2）（6,7）（7,16）令 δ(n)=f(n)-g(n)适袜，設(shè)(n,δ(n))有 ( 4,2 ) , ( 5,3 ) , ( 6,4 ) , ( 7,5 )發(fā)現(xiàn)規(guī)律即δ(n)=n-2,帶回柄错，有f(n)=f(n-1)+f(n-2)+n-2
=================================================================
cin>>n>>k;
for(long long i=4;i<=n;i++){
f[i]=f[i-1]+f[i-2]+i-2;
f[i]%=k;
}
cout<<f[n];
=================================================================
Problem I. "Injurious" Triples
題目大意：有n個元素的序列a1,a2...an,找是否有元素ai,aj,ak構(gòu)成等差數(shù)列舷夺，其中i
=================================================================
【題解】由于元素很小苦酱，可以開桶售貌。設(shè)v[2ai]=i,枚舉i,k,若v[ai+ak] 存在且這個值介于i,k之間說明找到了解。
=================================================================
int n,i,j,k;bk=false;
scanf("%d",&n);
memset(v,-1,sizeof(v));
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
v[2a[i]]=i;
}
for (i=1;i<=n;i++)
{
for (k=i+2;k<=n;k++)
if (v[a[i]+a[k]]!=-1 && iv[a[i]+a[k]])
{
j=v[a[i]+a[k]];bk=true;break;
}
if (bk) break;
}
if (!bk) printf("No\n");
else printf("Yes\n%d %d %d\n",i,j,k);
=================================================================
反思：我tm實在是太菜
