Frost_Delay 的博客

Frost_Delay 的博客

day12

posted on 2019-08-12 14:21:43 | under 未分类 |

自闭了,今天真傻逼

11:28写的

wdnmd本来今天看到题就觉得难,写完两题居然还手残格式化D盘,心态崩了,10:30重写前两题,11:00写完,发现第二题题意理解错了,又马上改,
11:25改完,发现还有漏洞,时间已经不够改了,于是写下这段文字,纪念今天自闭的我,警示自己以后不要随便乱点东西,我真是傻逼

今天得分 0/50;

T1没理解到精髓,一道贪心被我写成这样我也是醉了;

主要判断能否分割,能分直接分

AC

#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玄学做法

语出某些大佬

T3:把所有的数放进一个数组排序,输出中间两个即可,证明参见绝对值不等式...刚学完不到半年就忘,是我zz了...
T3:排序取中间值,证明略

lzc大佬的证明

T3: 这题随便你怎么二分三分…… 不过有一个更优美的结论。 我们设取到的其中一个极值点在 ,再设两个值 。 其中 成立时值为 1 ,否则为 0 。 我们显然要让 的值尽量小,函数值才会小。 所以我们把所有的左右边界丢在一起排个序,取中间两个就是答案了。

#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;
}