2017/9/22~2017/9/23考试总结

2017-9-22
T1
排序贪心裸题。。考试时心慌。。没有认真写代码,数组开小了一半。RE了一半的点。。
T2
解方程。
选树上的每一条边,根据边两边的点,列方程,求出相对大小。再根据根节点的值解方程。解出所有的a值。
T3
卡特兰数或者打表找规律
当时没想到要找公式
写了四个DP水了45分
组合数学找规律这方面还需要加强


2017-9-23
T1
矩阵快速幂,考试的时候想到了,但觉得要T就没有写。
结果是1维矩阵快速幂,O(mod^2*m)的复杂度,可以跑过。
题目也很迷,讲了一大堆原根的内容,结果这道题跟原根有什么关系?
T2
先推一下式子,再通过带权并查集优化。
当时只推了一下式子,没有写并查集,而且题目所说的非负整数没有看到,一直以为样例是错的。。。
当然,出题人坑,本题数据是错的,标程也是错的。。
T3
水题,模拟一下就好。
读入了两次x1,光荣报零。。。

BZOJ3944 杜教筛

(被owenowl要求加上的内容)flx 教我杜教筛,虽然他没做这道题。

传送门,戳这里

Problem

Description

题目

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个 非负整数N,代表一组询问

Output

一共T行,每行两个用空格分隔的数ans1,ans2

Sample

Input
6
1
2
8
13
30
2333
Output
1 1
2 0
22 -2
58 -3
278 -3
1655470 2

Solution

杜教筛裸题。

下面是我学杜教筛的一点经验,和大家分享一下。
如果您已经精通杜教筛,请跳过下面的内容,直接看注意事项。

如果您还不会莫比乌斯反演,请先学习反演再看本文。否则,可能一头雾水。

一般求Phi函数和mu函数都用线性筛,可以在O(n)的时间内求出1~n的所有phi值和mu值。下面是线性筛的代码,主要思想就是筛质数,然后根据phi和mu的积性函数性质筛后面的数。

#include<bits/stdc++.h>
const int MAXN = 5000000;
int prime[MAXN+10];
ll mu[MAXN+10],phi[MAXN+10],cnt;
bool isprime[MAXN+10];
void init()
{
    mu[1]=1,phi[1]=1;
    for(register int i=2;i<=MAXN;i++)
    {
        if(!isprime[i]) prime[++cnt]=i,phi[i]=i-1,mu[i]=-1;
        for(register int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>MAXN) break;
            isprime[i*prime[j]]=1;
            if((i%prime[j])==0) {phi[i*prime[j]]=phi[i]*prime[j],mu[i*prime[j]]=0;break;}
            else phi[i*prime[j]]=phi[i]*phi[prime[j]],mu[i*prime[j]]=-mu[i];
        }
    }
    for(register int i=1;i<=MAXN;i++) phi[i]+=phi[i-1];
    for(register int i=1;i<=MAXN;i++) mu[i]+=mu[i-1];
    return ;
}

Markdown炸了。。没法打数学公式。。

但是对于n很大求前缀和的情况(比如本题),O(n)的复杂度就不够了。这个时候就需要一种新的方法————杜教筛。

设h = f ⊗ g,设f的前缀和为S,而h的前缀和易求,那么可以用杜教筛。经过推导,可以得到:
杜教筛公式

首先考虑对μ函数的前缀和(欧拉函数同理):
构造一个g(i)=1!那么,有:

M(x)为mu[x]的前缀和:

求phi函数的时候,如何构造g(x)留给读者自行思考。

杜教筛关键在于构造g函数与f函数进行卷积,再通过杜教筛的公式递归求值。(可以是另一个杜教筛)
有几个注意事项:

1、首先,在用杜教筛之前,先用线性筛把开始较小的一些数(1~n^(2/3))的phi和mu给筛出来,再调用杜教筛,这样可以优化一下复杂度。

2、在用杜教筛枚举i求phi(x/i)时,分段枚举,对于一段x/i相同的i的区间只枚举一次,再乘以这一段的大小即可。否则可能会T掉

3、对于线性筛筛出来的值,要用数组存,不要用map,否则会多一个log,很可能T掉;

Code bzoj 3944

附上AC代码,前几十行写了读入优化,可以跳过。
本题AC需要靠运气,或者您去学洲阁筛吧。

/*********************************************
    Problem: 3944
    User: dxymaster
    Language: C++
    Result: Accepted
    Time:11032 ms
    Memory:103976 kb
**********************************************/

#pragma comment(linker, "/STACK:1024000000,1024000000")//防止爆栈
#include<bits/stdc++.h>
using namespace std;
#ifdef __attribute__
#define fast __attribute__((optimize(3), target("no-ieee-fp,arch=corei7")))
#else
#define fast
#endif
#define inline fast inline
namespace io
{
    // #define USE_FREAD_IO
#ifdef USE_FREAD_IO
#define BUF_SIZE 5000010
    char buf[BUF_SIZE]; int cur = BUF_SIZE; FILE *in = stdin;
    inline char gnc()
    {
        if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
        return buf[cur++];
    }
#else
    inline char gnc()
    {
        return (char)getchar();
    }
#endif
    template<typename T>
    inline void gi(T &dx)
    {
        dx = 0;
        int yc = gnc();
        bool nega = false;
        while (yc < '0' || yc > '9') { nega = (yc == '-' ? true : nega); yc = gnc(); }
        while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); }
        if (nega) { dx = -dx; }
    }
    void gc(char &a)
    {
        do a = gnc(); while (!isgraph(a));
    }
    void gss(char *c)
    {
        *c = gnc();
        while (!isgraph(*c)) *c = gnc();
        while (isgraph(*c)) *++c = gnc();
        *c = 0;
    }
#if __cplusplus >= 201103l || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103l)
    template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
    { gi(a); gi(args...); }
#else
    template<typename t1, typename t2> inline void gi(t1 &a, t2 &b) { gi(a); gi(b); }
    template<typename t1, typename t2, typename t3> inline void gi(t1 &a, t2 &b, t3 &c) { gi(a); gi(b); gi(c); }
    template<typename t1, typename t2, typename t3, typename t4> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d) { gi(a); gi(b); gi(c); gi(d); }
    template<typename t1, typename t2, typename t3, typename t4, typename t5> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d, t5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
}
using namespace io;
typedef long long ll;
int T,n;
map <ll,ll>m,p;
const int MAXN = 5000000;
int prime[MAXN+10];
ll mu[MAXN+10],phi[MAXN+10],cnt;
bool isprime[MAXN+10];
inline ll get_mu(ll x)
{
    if(x<MAXN) return mu[x];
    if(m[x])return m[x];
    ll res=1;
    for(register ll i=2,j=0;i<=x;i=j+1)
    {
        j=x/(x/i);
        res-=get_mu(x/i)*((ll)j-i+1);
        if(j==x)break;
    }
    m[x]=res;
    return res;
}
inline ll get_phi(ll x)
{   
        if(x<MAXN) return phi[x];
        if(p[x]) return p[x];
        ll res=0;
        if(x&1) res=(x+1)/2*x;
        else res=(x/2)*(x+1);
        for(register ll i=2,j=0;i<=x;i=j+1)
        {
            j=x/(x/i);
            res-=get_phi(x/i)*((ll)j-i+1);
            if(j==x)break;
        }
        p[x]=res;
        return res; 
}
inline void init()
{
    mu[1]=1,phi[1]=1;
    for(register int i=2;i<=MAXN;i++)
    {
        if(!isprime[i]) prime[++cnt]=i,phi[i]=i-1,mu[i]=-1;
        for(register int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>MAXN) break;
            isprime[i*prime[j]]=1;
            if((i%prime[j])==0) {phi[i*prime[j]]=phi[i]*prime[j],mu[i*prime[j]]=0;break;}
            else phi[i*prime[j]]=phi[i]*phi[prime[j]],mu[i*prime[j]]=-mu[i];
        }
    }
    for(register int i=1;i<=MAXN;i++) phi[i]+=phi[i-1];
    for(register int i=1;i<=MAXN;i++) mu[i]+=mu[i-1];
    return ;
}
int main()
{
    init();
    gi(T);
    while(T--)
    {
        gi(n);
        printf("%lld %lld\n",get_phi(n),get_mu(n));
    }
    return 0;
}

IObuff fread读入优化模板

话不多说,直接上代码吧(自带O3优化)

#ifdef __attribute__
#define fast __attribute__((optimize(3), target("no-ieee-fp,arch=corei7")))
#else
#define fast
#endif
#define inline fast inline
namespace io
{
    // #define USE_FREAD_IO
#ifdef USE_FREAD_IO
#define BUF_SIZE 5000010
    char buf[BUF_SIZE]; int cur = BUF_SIZE; FILE *in = stdin;
    inline char gnc()
    {
        if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; }
        return buf[cur++];
    }
#else
    inline char gnc()
    {
        return (char)getchar();
    }
#endif
    template<typename T>
    inline void gi(T &dx)
    {
        dx = 0;
        int yc = gnc();
        bool nega = false;
        while (yc < '0' || yc > '9') { nega = (yc == '-' ? true : nega); yc = gnc(); }
        while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); }
        if (nega) { dx = -dx; }
    }
    void gc(char &a)
    {
        do a = gnc(); while (!isgraph(a));
    }
    void gss(char *c)
    {
        *c = gnc();
        while (!isgraph(*c)) *c = gnc();
        while (isgraph(*c)) *++c = gnc();
        *c = 0;
    }
#if __cplusplus >= 201103l || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103l)
    template<typename T, typename ...Args> inline void gi(T &a, Args &...args)
    { gi(a); gi(args...); }
#else
    template<typename t1, typename t2> inline void gi(t1 &a, t2 &b) { gi(a); gi(b); }
    template<typename t1, typename t2, typename t3> inline void gi(t1 &a, t2 &b, t3 &c) { gi(a); gi(b); gi(c); }
    template<typename t1, typename t2, typename t3, typename t4> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d) { gi(a); gi(b); gi(c); gi(d); }
    template<typename t1, typename t2, typename t3, typename t4, typename t5> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d, t5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); }
#endif
}
using namespace io;

调用的时候gi(x)就是读入x;可以读long long

2017/9/17 总结

A:这是什么地方?
DXY:或许是我的总结
A:这周有什么大新闻?
DXY:大新闻没有,全是一些琐事
A:这周考试怎么样?
DXY:水题写挂了很不爽
A:怎么写挂了呀?
DXY:忘了开longlong,特判没写return,dfs爆栈!
A:这周有没有比赛啊?
DXY:有啊,青岛ACM
A:结果怎么样?
DXY:滚粗,rank1000,几何题精度不够,O(n)Tle,dp转移炸。
A:不要伤心嘛,至少您贡献了许多罚时。
DXY:。。。
A:这周学了什么好东西?
DXY:数论操作(原根、循环群,反演、杜教筛),建模、网络流
A:还有呢?
DXY:一些奇奇怪怪没法证明的结论
A:这周bzoj做了多少啊?
DXY:做了几十道吧,莫队水了不少,数论做了不少。
A:一共多少了?
DXY: 60道,在这里打个卡吧。
A:rank?
DXY: rank2509
A:那您下周加油吧。要进rank2000啊,认真做题啊
DXY:嗯。
A:所以,这里到底是什么地方
DXY: 不过是茫茫寰宇中的一粒尘埃。

奇袭

©党星宇

Problem

Description:

由于各种原因,桐人现在被困在Under World(以下简称UW)中,而UW马上
要迎来最终的压力测试——魔界入侵。 唯一一个神一般存在的Administrator被消灭了,靠原本的整合骑士的力量
是远远不够的。所以爱丽丝动员了UW全体人民,与整合骑士一起抗击魔族。 在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前
发动一次奇袭,袭击魔族大本营! 为了降低风险,爱丽丝找到了你,一名优秀斥候,希望你能在奇袭前对魔族
大本营进行侦查,并计算出袭击的难度。 经过侦查,你绘制出了魔族大本营的地图,然后发现,魔族大本营是一个N
×N的网格图,一共有N支军队驻扎在一些网格中(不会有两只军队驻扎在一起)。 在大本营中,每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队,我们袭
击的难度就会增加1点。 现在请你根据绘制出的地图,告诉爱丽丝这次的袭击行动难度有多大。

Input

第一行,一个正整数N,表示网格图的大小以及军队数量。
接下来N行,每行两个整数,Xi,Yi,表示第i支军队的坐标。 保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样
的。

Output

一行,一个整数表示袭击的难度。

Solution

显然,题目可化简为:给定N个数的一个排列,问这个序列中有多少个子区间的数恰好是连续的。
进一步可以化为:有多少种情况使得,相邻的k个数中最大值和最小值的差小于等于k-1。
大致有两种解法,一种是分治,一种是线段树。
这里主要讲一下分治的解法。
考虑分治,对于当前分治区间[L,R],记区间中点为mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数,然后就分为两种情况了:
1.最小值和最大值在同侧。
2.最小值和最大值在异侧。
下面只考虑最值同在左,和最小值在左,最大值在右的情况。其余两种是对称的。
对于最值同在左侧的情况,我们枚举左边界在哪,然后可以计算出右边界的位置,在判断是否合法,统计答案。时间复杂度:O(N).
对于最小值在左侧,最大值在右侧的情况,如果一个区间满足我们所要求的关系的话,就一定有:
移项可得
然后可以用单调栈+桶来完成这个任务。时间复杂度:O(N).
如果加一些黑科技可以大大减少代码量,但是复杂度会多一个log
总的时间复杂度:O(NlogN)/O(NlogN^2)
简单提一下,线段树解法的思路大致也是维护一个单调栈,然后进行区间修改和查询,统计答案。
时间复杂度:O(NlogN).

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+10;
const int inf = 0x7f7f7f7f;
ll S,E,n;
int root=1;
struct Edge{
    int to,w,nxt;
}e[MAXN];
int last[MAXN],cnt;
ll ans=inf;
struct tree{
    int fa;
}tr[MAXN];
inline ll read()
{
    ll x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x;
}
inline void adde(ll u,ll v,ll w)
{
    e[++cnt].to=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;
    return ;
}
inline void insert(ll u,ll v,ll w)
{
    adde(u,v,w);adde(v,u,w);
    return ;
}
inline void dfs(ll cur,ll fa)
{
    for(register int i=last[cur];i;i=e[i].nxt)
    {
        if(e[i].to==fa) continue;
        else tr[e[i].to].fa=cur,dfs(e[i].to,cur);
    }
    return;
}
inline bool judge(ll dis)
{
    return (dis<=E&&dis>=S);
}
inline void get_ans(ll cur,ll fa,ll dis)
{
    for(register int i=last[cur];i;i=e[i].nxt)
    {
        if(e[i].to==fa) continue;
        if(judge((ll)dis+e[i].w)) ans=min((ll)ans,dis+e[i].w);
        if(((ll)dis+e[i].w)!=0) get_ans(e[i].to,cur,(ll)dis+e[i].w);
    }
    return;
}
int main()
{
    n=read(),S=read(),E=read();
    if(n==1)
    {
        if(judge(0))return puts("0"),0;
        return puts("-1"),0;
    }
    register ll minn = inf; 
    for(register int i=1;i<n;++i)
    {
        ll u=read(),v=read(),w=read();
        insert(u,v,w);minn=min(minn,w);
    }
    if(E<minn) return puts("-1"),0;
    else if(E==minn) return cout<<(ll)minn,0;
//  dfs(root,0);tr[root].fa=0;
    for(register int i=1;i<=n;++i)
        get_ans(i,0,0);
    if(ans==inf) return puts("-1"),0;
    cout<<ans;
    return 0;
}