@Scarlet 2017-03-27T19:09:01.000000Z 字数 7572 阅读 2805

傻逼题范鏼

直播不看题解鏼题

BZOJ

傻逼题范鏼

随机数开题法，拒绝USACO
加了奇奇怪怪的形容词意为不能眼秒
打钩貌似可做，做了会写题解（大概）

2973：较难博弈
2370：较难DP
1153：较难搜索+计算几何
2925：较难DP
3990：奇妙结论+搜索
3337：高超数据结构拼盘（块状链表？）
3489：较难数据结构
4724：较难数论
3158：mdzz
2992：较难数位DP
3629：较难dfs
4227：图论好题【雾】
1479：置换群【不可做】
1246：高超的背包（搜索）
4335：高超图论（费用流？）
1560：DP优化
4310：二分答案
4358：莫队+线段树
4080：没看懂
4243：题目太长
3510：没看懂
2127：输入好长

4750【PJ好题】

从后往前找看到一堆1A中的一道15人A的题。
点开一看，啊好难，多组数据。

观察了一下发现 $\sum_{所有区间}区间最大值\times 区间JB玩意儿$ ，这种形式好像是套路题。先把最大值区间罗出来，问题转化相当于一个表格中对应 $a_i\oplus b_i$ 之和。发现按位分解以后就是傻逼玩意儿了。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
#define mod 1000000061
#define INF 2000000000
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int l[maxn],r[maxn],q[maxn],p[maxn];
LL aa[2][32],a[maxn][32],s[maxn];
int bin[32];
int main()
{
    bin[0]=1;
    for(int i=1;i<32;i++)
        bin[i]=bin[i-1]<<1;
    int T=read();
    q[0]=INF;
    while(T--)
    {
        int n=read();
        for(int i=1;i<=n;i++)
            s[i]=read();
        p[0]=0;
        for(int top=0,i=1;i<=n;i++)
        {
            for(;s[i]>=q[top];)top--;
            l[i]=p[top]+1;q[++top]=s[i];p[top]=i;
        }
        p[0]=n+1;
        for(int top=0,i=n;i>=1;i--)
        {
            for(;s[i]>q[top];)top--;
            r[i]=p[top]-1;q[++top]=s[i];p[top]=i;
        }
        for(int i=1;i<=n;i++)
            s[i]^=s[i-1];
        for(int i=1;i<=n;i++)
            for(int x=s[i],j=0;x;x>>=1,j++)
                a[i][j]=x&1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<32;j++)
                a[i][j]+=a[i-1][j];
        for(int i=n;i>=1;i--)
            s[i]^=s[i-1];
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            LL S=0;
            for(int j=0;j<32;j++)
            {
                LL x=r[i]-i+1,y=i-l[i]+1;
                LL s=a[r[i]][j]-a[i-1][j],t=a[i-1][j]-a[l[i]-2][j];
                (S+=((x-s)*t+(y-t)*s)%mod*bin[j]%mod)%=mod;
            }
            (ans+=S*s[i]%mod)%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

2996【简单数位DP】

题意：求 $[L,R]$ 之间被第 $k$ 大的数位整除的数的个数
MD每道数位DP都要写不知多久。
十分simple，枚举第 $k$ 大的数位，dp[x][top][qd0][h][P][s][t][rem]表示前 $x$ 位，是否有可能超过原数，是否还在前导0阶段，是否含有 $P$ ，第 $k$ 大的数位 $P$ ，小于 $P$ 的数位有几个，小于等于 $P$ 的数位有几个，余数是 $rem$ 的方案数。
然后就轻松转移了。

看了前后排名的空间和效率我觉得我一定是写了假DP方程

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 20
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int dig[maxn],k,hhh;
LL f[20][2][2][2][10][20][20][10];
LL dfs(int x,bool top,bool qd0,bool h,int s,int t,int rem)
{
    if(x<=0)return h&&s<k&&k<=t&&rem==0;
    if (f[x][top][qd0][h][hhh][s][t][rem]+1)return f[x][top][qd0][h][hhh][s][t][rem];
    int w=top?dig[x]:9;LL sum=0;
    for(int i=0;i<=w;i++)
    {
        sum+=dfs(x-1,top&(i==w),qd0&(i==0),h|(i==hhh),s+((qd0&&i==0)?0:i<hhh),t+((qd0&&i==0)?0:i<=hhh),(rem*10+i)%hhh);
    }
    return f[x][top][qd0][h][hhh][s][t][rem]=sum;
}
LL solve(LL x)
{
    int cnt=0;
    memset(f,-1,sizeof(f));
    for(;x;x/=10)dig[++cnt]=x%10;
    LL ans=0;
    for(hhh=1;hhh<=9;hhh++)
        ans+=dfs(cnt,1,1,0,0,0,0);
    return ans;
}
int main()
{
    LL L=read(),R=read();k=read();
    printf("%lld",solve(R)-solve(L-1));
    return 0;
}

4247【推求和公式】

题意： $r(n,m)$ 表示把 $n$ 重复 $m$ 遍， $S(n)$ 表示把n的所有子串视作数字相加，求 $S(r(n,m))\mod P$

假设没有重复

$\begin{align*} S(s)&=\sum_{i=1}^{len}s_i\cdot (len-i+1)\cdot\sum_{j=0}^{i-1}10^j \\ &=\sum_{i=1}^{len}s_i\cdot (len-i+1)\cdot\frac{10^i-1}{9} \end{align*}$

考虑

$S(p)\equiv\frac{9S(p)\mod 9P}{9}\pmod P$

那么

$\begin{align*} 9\cdot S(r(s,k))&=\sum_{c=0}^{k-1}\left(\sum_{i=1}^{len}s_{i+c\cdot len}\left[k\cdot len-\left(i+c\cdot len\right)+1\right] \left(10^{i+c\cdot len}-1\right)\right) \\ &=\sum_{c=0}^{k-1}\left(\sum_{i=1}^{len}s_{i+c\cdot len}\left[k\cdot len-i-c\cdot len+1\right] \left(10^{i+c\cdot len}-1\right)\right)\\ &=\sum_{c=0}^{k-1}\left(\left(k\cdot len-i+1\right)10^i\sum_{c=0}^{k-1}10^{c\cdot len}-\left(k\cdot len-i+1\right)k\\+\frac{len\cdot k\cdot(k-1)}{2}-10^ilen\sum_{c=0}^{k-1}c10^{len\cdot c}\right) \end{align*}$

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
using namespace std;
char ss[maxn];
LL s[maxn],k,m,mod,len,ten[maxn];
LL mul(LL a, LL b)
{
    LL ret=0;
    for(;b;b>>=1,a=(a<<1)%mod)
        if(b&1)ret=(ret+a)%mod;
    return ret;
}
LL Pow(LL a,LL b)
{
    LL ret=1;
    for(;b;b>>=1,a=mul(a,a))
        if(b&1)ret=mul(ret,a);
    return ret;
}
LL C1(LL a, LL b)
{
    if(b==1)return 1;
    if(b&1)return(C1(a,b-1)+Pow(a, b-1))%mod;
    else return mul(C1(a,b>>1),(1+Pow(a,b>>1))%mod);
}
LL C2(LL a, LL b) 
{
    if(b==1)return 0;
    if(b&1)return(C2(a,b-1)+mul(b-1,Pow(a,b-1)))%mod;
    else return(mul(C2(a,b>>1),1+Pow(a,b>>1))+mul(mul(b>>1,Pow(a,b>>1)),C1(a,b>>1)))%mod;
}
LL solve()
{
    LL ans=0;
    ten[0]=1;
    for(int i=1;i<=len;i++)
        ten[i]=(ten[i-1]*10)%mod;
    LL t1=C1(ten[len],k);
    LL t2=C2(ten[len],k);
    LL t3=(k*(k-1)/2)%mod;
    for(int i=1;i<=len;i++)
        ans=(ans+mul(s[i],(mul(mul(t1,(k*len-i+1)%mod),ten[i])-mul((k*len-i+1)%mod,k)-mul(mul(t2,len),ten[i])+mul(len,t3)+2*mod)%mod))%mod;
    return ans;
}
int main()
{
    scanf("%s",ss);
    k=read(),m=read();
    mod=9*m;
    len=strlen(ss);
    for(int i=0;i<=len-1;i++)
        s[len-i]=ss[i]-'0';
    LL ans=solve();
    cout<<ans/9<<endl;
    return 0;
}

1091【枚举+计算几何】

$O(n!*n^2)$ ，也不需要维护半平面交，只要计算和之前直线集的交点就好了。

#include<bits/stdc++.h>
#define maxn 20
using namespace std;
typedef long long LL;
struct poi
{
    double x,y;
    void in(){scanf("%lf%lf",&x,&y);}
    poi operator+(poi a){return (poi){x+a.x,y+a.y};}
    poi operator-(poi a){return (poi){x-a.x,y-a.y};}
    poi operator*(double a){return (poi){x*a,y*a};}
    double operator*(poi a){return x*a.y-y*a.x;}
    double dot(poi a){return x*a.x+y*a.y;}
    double abs(){return sqrt(x*x+y*y);}
}ps[maxn];
double mn,mx,v1,v2,ans=1e233;
struct uuz
{
    poi a,b;
    void chk(uuz w)
    {
        double c=w.b*b;
        if(c==0)return;
        c=(a*w.b+w.b*w.a)/c;
        if(c>0.5)c<mx&&(mx=c);
        else c>mn&&(mn=c);
    }
}ls[maxn],l0[maxn];
int n,id[maxn],lp=0;
int main()
{
    scanf("%lf%lf%d",&v1,&v2,&n);
    for(int i=1;i<=n;i++)ps[i].in(),id[i]=i;
    ps[n+1]=ps[1];
    poi p1=(poi){0,0},p2=(poi){v1,0},p3=(poi){v1,v2},p4=(poi){0,v2};
    ls[lp++]=(uuz){p1,p2-p1};
    ls[lp++]=(uuz){p2,p3-p2};
    ls[lp++]=(uuz){p3,p4-p3};
    ls[lp++]=(uuz){p4,p1-p4};
    for(int i=1;i<=n;++i)l0[i]=(uuz){ps[i],ps[i+1]-ps[i]};
    do
    {
        lp=4;
        double s=0;
        for(int i=1;i<=n;++i)
        {
            int w=id[i];
            mn=-1e10,mx=1e10;
            for(int j=0;j<lp;++j)l0[w].chk(ls[j]);
            ls[lp++]=l0[w];
            s+=(mx-mn)*l0[w].b.abs();
        }
        if(s<ans)ans=s;
    }
    while(std::next_permutation(id+1,id+n+1));
    printf("%.3f",ans);
    return 0;
}

3003【SPFA+状压DP】

傻逼到没有心情写

4690【带权并查集】

大家都会

3938【线段树维护凸包】

李超线段树

4710【组合DP】

3268【倍增】

3800【暴力】

先钦点一段路程长度，然后就能做暴力计算啦
呀啦？好像不是我写的...

#include<stdio.h>
#include<string.h>
#define zero 1e-8
#define MAXD 210
#define INF 10000
struct point
{
    double x, y;
}wa[MAXD], wb[MAXD], *a, *b;
int N, na, nb;
double u[MAXD], v[MAXD], w[MAXD];
double fabs(double x)
{
    return x < 0 ? -x : x;
}
int dcmp(double x)
{
    return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1);
}
double det(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - x2 * y1;
}
void init()
{
    int i, j, k;
    for(i = 0; i < N; i ++)
        scanf("%lf%lf%lf", &v[i], &u[i], &w[i]);
}
void add(double x, double y)
{
    b[nb].x = x, b[nb].y = y;
    ++ nb;
}
void cut(double a1, double a2, double a3)
{
    int i, j, k;
    point *t;
    double x, y, t1, t2, x1, y1, x2, y2;
    nb = 0;
    if(dcmp(a2) == 0)
    {
        x1 = x2 = (-a3) / a1;
        if(dcmp(a1) < 0)
            y1 = INF, y2 = 0;
        else
            y1 = 0, y2 = INF;
    }
    else
    {
        if(dcmp(a2) < 0)
            x1 = 0, x2 = INF;
        else
            x1 = INF, x2 = 0;
        y1 = (-a3 - a1 * x1) / a2, y2 = (-a3 - a1 * x2) / a2;
    }
    for(i = 0; i < na; i ++)
    {
        t1 = det(x2 - x1, y2 - y1, a[i].x - x1, a[i].y - y1);
        t2 = det(x2 - x1, y2 - y1, a[i + 1].x - x1, a[i + 1].y - y1);
        if(dcmp(t1) >= 0)
            add(a[i].x, a[i].y);
        if(dcmp(t1) * dcmp(t2) < 0)
        {
            x = (fabs(t2) * a[i].x + fabs(t1) * a[i + 1].x) / (fabs(t1) + fabs(t2));
            y = (fabs(t2) * a[i].y + fabs(t1) * a[i + 1].y) / (fabs(t1) + fabs(t2));
            add(x, y);
        }
    }
    t = a, a = b, b = t;
    na = nb;
    a[na] = a[0];
}
int check()
{
    int i, j, k;
    double s = 0;
    for(i = 0; i < na; i ++)
        s += det(a[i].x, a[i].y, a[i + 1].x, a[i + 1].y);
    if(dcmp(s) == 0)
        return 0;
    return 1;
}
void solve()
{
    int i, j, k;
    double a1, a2, a3;
    a = wa, b = wb;
    for(i = 0; i < N; i ++)
    {
        na = 3;
        a[0].x = 0, a[0].y = 0, a[1].x = INF, a[1].y = 0, a[2].x = 0, a[2].y = INF;
        a[na] = a[0];
        for(j = 0; j < N; j ++)
        {
            if(j == i)
                continue;
            a1 = (w[i] - v[i]) / (w[i] * v[i]) - (w[j] - v[j]) / (w[j] * v[j]);
            a2 = (w[i] - u[i]) / (w[i] * u[i]) - (w[j] - u[j]) / (w[j] * u[j]);
            a3 = INF * (w[j] - w[i]) / (w[i] * w[j]);
            if(dcmp(a2) == 0 && dcmp(a1) == 0)
            {
                if(dcmp(a3) < 0)
                    continue;
                break;
            }
            cut(a1, a2, a3);
        }
        if(j != N || !check())
            printf("No\n");
        else
            printf("Yes\n");
    }
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;
}