首页 > 代码库 > 老司机的奇怪noip模拟T1-guanyu
老司机的奇怪noip模拟T1-guanyu
1. 关羽
（guanyu.cpp/c/pas ）
【问题描述】
xpp 每天研究天文学研究哲学，对于人生又有一些我们完全无法理解的思考。
在某天无聊学术之后， xpp 打开了 http://web.sanguosha.com， 准备用他心爱的关羽虐
人。进入了八人身份局，作为一位主公，xpp 果断选了关羽，用关羽挑 7 人。
xpp 为什么喜欢关羽这个武将呢？因为武圣是个很牛逼的技能。
武圣——你可以将你的任意一张红桃或方片牌当杀使用或打出。
可见武圣这个技能如果用得好那么是可以轻松杀死别人的。 于是 xpp 把 7 个人全都轻松
干掉。
虽然 xpp 的武圣永远会横扫千军， 但是他想到了这样一个问题： 他应该先杀死谁后杀死
谁呢？
玩三国杀的人都是坐成一圈的， 每个人到牌堆的距离相等， 也就是说存在一个所有人都
在边界上的圆。作为主公，xpp 想怒杀 4 个反贼。根据他的推理，这一盘的情况应该是这样
的：4 个反贼所在的位置肯定构成一个矩形。现在，xpp 想知道，这一局可能有多少种反贼
的组合。
xpp 智商过于强大，不屑于想此等低端问题，然后你就要把这道题做出来。
【输入】
输入文件名为 guanyu.in。
第一行包含一个整数 n，表示除 xpp 外的游戏人数（不包括 xpp，他是主公）。
第二行包括 n 个整数，表示玩家之间的间隔弧长。
【输出】
输出文件名为 guanyu.out。
输出共 t 行，每行包括一个实数，表示所求的期望值。
【输入输出样例】
guanyu.in guanyu.out
8
1 2 2 3 1 1 3 3
3
【数据范围】
对于 30%的数据，n≤20。
对于 100%的数据，4≤n≤2000。
——————————————题解
我一个魏粉做蜀题真是不爽……这道题写的是奇怪n^2logn，就是枚举一条边，算它邻边，再算它对边，但是数组开小然后gg了，后来改大就过了
实际上答案是一个圆嘛……枚举两个点是否是直径然后等差数列算一算，n^2的
【数组开小毁一生】
【正确题解】
1 #include <iostream> 2 #include <string.h> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstring> 7 #include <vector> 8 #include <ctime> 9 #define ivorysi10 #define mo 1000711 #define siji(i,x,y) for(int i=(x);i<=(y);i++)12 #define gongzi(j,x,y) for(int j=(x);j>=(y);j--)13 #define xiaosiji(i,x,y) for(int i=(x);i<(y);i++)14 #define sigongzi(j,x,y) for(int j=(x);j>(y);j--)15 #define ivory(i,x) for(int i=head[x];i;i=edge[i].next)16 #define pii pair<int,int>17 #define fi first18 #define se second19 #define inf 1000000020 using namespace std;21 typedef long long ll;22 int a[4005],sum[4005],n,ans,po;23 bool binary(int il,int ir,int val) {24 int q=il-1;25 while(il<ir) {26 int mid=(il+ir+1)>>1;27 if(sum[mid]-sum[q]<=val) il=mid;28 else ir=mid-1;29 }30 if(sum[il]-sum[q]==val) {po=il;return true;}31 else return false;32 }33 int main() {34 #ifdef ivorysi35 freopen("guanyu.in","r",stdin);36 freopen("guanyu.out","w",stdout);37 #else 38 freopen("f1.in","r",stdin);39 #endif40 scanf("%d",&n);41 siji(i,1,n) {42 scanf("%d",&a[i]);43 sum[i]=sum[i-1]+a[i];44 }45 siji(i,1,n) {46 a[n+i]=a[i];47 sum[n+i]=sum[n+i-1]+a[n+i];48 }49 siji(i,1,n) {50 xiaosiji(j,0,n) {51 int tmp=sum[j+i]-sum[i-1];52 if(tmp*2>=sum[n]) continue;53 int tmp2=(sum[n]-tmp*2)/2;54 if(!binary(i+j+1,i+n-1,tmp2)) continue;55 if(!binary(po+1,i+n-1,tmp)) continue;56 ++ans;57 58 }59 }60 printf("%d\n",ans/4);61 }
老司机的奇怪noip模拟T1-guanyu