=================================================================
【Problem A. Area and Circumference】
题目大意，平面上n个矩形，且矩形的边和坐标轴平行。找到面积与周长比最大的矩形，输出比率，精确4位，设有spj。矩形个数不超过1w，坐标限定在[-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】
题目大意，现有n个节点，构建一棵二叉树，规则如下：1.用当前剩余的孤立节点构建尽可能大的完全二叉树，从编号为0开始向编号增大方向构建。例如n=13就构成（8）+（4）+（1）三棵完全二叉树。2.将二叉树的根节点从大到小按构建顺序的逆序依次连接。即（4）和（1）有父亲节点，再和（8）连接有父亲节点。
现在给定查询，两种查询，为A d或B s，其中A,B为字符，d为数字，s为字符串。A d类查询输出d节点在二叉树中的位置，输出方式为'LRLR'表示从根节点如何走到节点d。B s类查询输出按照s字符串的‘LRLR’走法会访问到哪个节点。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数组中数据比较，大于则减去并输出R，小于则说明就在这个子树中。此时问题转换为在一棵完全二叉树中找一个节点，输出LR，很明显将此时的d转换为齐位二进制，0则为L，1则为R。对于B类查询，找到s字符串前缀的连续R子串，个数代表在哪一棵完全二叉树上，统计前面节点个数。后续处理和前者互逆，L则2,R则2+1，最后结果与节点个数相加即为答案。
=================================================================
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】
题目大意，一个环形线路上有n个车站，现在选取若干车站组建新的快车线路，要求1：新线路至少有2个车站。要求2：新线路上的车站在原环形线路上两两不相邻。问能组成多少种不同的新线路，答案mod k。例如n=4，可以有两条，为（1,3）或（2,4）。
=================================================================
【题解】当n<=3必然为0.将环拆分成链，设f[1..n],g[1..n]. f[i]表示从1i且选择了第i个车站的方案数，g[i]表示从1i且不选择第i个车站的方案数，明显有f[i]=g[i-1],第i个车站选择则第i-1个必然不选.g[i]=g[i-1]+f[i-1]，第i个车站不选则方案数为i-1的方案数。输出f，g数组发现f，g呈相差一位的斐波那契数列，猜想通项公式和斐波那契有关。设（n , ans）,有（3,0）（4,2）（5,5）（6,11）（7,21）,设此时ans=f(n),(注意不是数组f[n]) ,考虑g(n)=f(n-1)+f(n-2) 的关系，设（n , g(n) ) ,有（4,0）（5,2）（6,7）（7,16）令 δ(n)=f(n)-g(n)，设(n,δ(n))有 ( 4,2 ) , ( 5,3 ) , ( 6,4 ) , ( 7,5 )发现规律即δ(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构成等差数列，其中i
=================================================================
【题解】由于元素很小，可以开桶。设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实在是太菜
