day12

自闭了，今天真傻逼 11：28写的 ```cpp wdnmd本来今天看到题就觉得难，写完两题居然还手残格式化D盘，心态崩了，10:30重写前两题，11:00写完，发现第二题题意理解错了，又马上改， 11:25改完，发现还有漏洞，时间已经不够改了，于是写下这段文字，纪念今天自闭的我，警示自己以后不要随便乱点东西，我真是傻逼 ``` 今天得分 0/50； T1没理解到精髓，一道贪心被我写成这样我也是醉了； 主要判断能否分割，能分直接分 AC ```cpp #include<iostream> #include<cstdio> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,t,k; long long s[100000+5][2]; long long zb,zw,ans; char c,lastc; bool judge(long long x,long long y) { return zb*y==zw*x; } long long need(long long y) { if(y*zb%zw!=0)return-1; return zb*y/zw; } long long need1(long long x) { if(x*zw%zb!=0)return -1; return zw*x/zb; } int main() { freopen("silly.in","r",stdin);freopen("silly.out","w",stdout); t=read(); while(t--) { for(int i=1;i<=n;i++) s[i][0]=s[i][1]=0; zb=zw=0;lastc=0;ans=0; n=read(); for(int i=1;i<=n;i++) { k=read();cin>>c; if(c==lastc) { n--;i--; } lastc=c; if(c=='B') { s[i][0]+=k; zb+=k; } if(c=='W') { s[i][1]+=k; zw+=k; } } if(!zb||!zw) { cout<<zb+zw<<endl; continue; } long long pb=0,pw=0; for(int i=1;i<=n;i++) { if(s[i][0]) { long long z=need(pw); if(z>pb&&z<=s[i][0]+pb) { ans++; } pb+=s[i][0]; } if(s[i][1]) { long long z=need1(pb); if(z>pw&&z<=s[i][1]+pw) { ans++; } pw+=s[i][1]; } } printf("%lld\n",ans); } return 0; } ``` T3玄学做法 语出某些大佬 ```cpp T3：把所有的数放进一个数组排序，输出中间两个即可，证明参见绝对值不等式...刚学完不到半年就忘，是我zz了... T3：排序取中间值，证明略 ``` lzc大佬的证明 T3： 这题随便你怎么二分三分…… 不过有一个更优美的结论。 我们设取到的其中一个极值点在 ，再设两个值  。 其中  当  成立时值为 1 ，否则为 0 。 我们显然要让  的值尽量小，函数值才会小。 所以我们把所有的左右边界丢在一起排个序，取中间两个就是答案了。 ```cpp #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int f[200100]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int main() { freopen("linear.in","r",stdin);freopen("linear.out","w",stdout); int n=read(); for(int i=1;i<=n*2;i++) f[i]=read(); sort(f+1,f+2*n+1); cout<<f[n]<<" "<<f[n+1]<<endl; return 0; } ```