7.19 讲题

消防局的设立；luogu2279

定根之后，找到这棵树中深度最深的叶子节点：

1.自己 2.兄弟 3.父亲 4.爷爷

应该选择哪一种？

显然是4，因为把士兵放在1 2 3位置能覆盖的所有节点，放在4都可以被覆盖；

找出深度最深的节点，找到他的爷爷，在爷爷的位置放一个士兵，把它爷爷能覆盖到的所有节点直接从树中删掉；

重复直到没有节点；

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

inline int read(){
    int ans=0;
    char last=' ',ch=getchar();
    while(ch>'9'||ch<'0') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int n,cnt,ans;
int head[1001],deep[1001],nn[1001];
struct Edge{
    int to,nxt;
}e[2001];

void add(int from,int to){
    ++cnt;
    e[cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
bool vis[1001];
int fa[1001];

bool cmp(int a,int b){return deep[a]>deep[b];}

void dfs(int k){
    for(int i=head[k];i;i=e[i].nxt){
        int v=e[i].to;
        if(!v) continue;
        if(!vis[v]){
            deep[v]=deep[k]+1;
            fa[v]=k;
            vis[v]=1;
            dfs(v);
        }
    }
    return;
}

void Dfs(int k,int step){
    if(step>2)return ;
    deep[k]=0;
    for(int i=head[k];i;i=e[i].nxt){
        int v=e[i].to;
        if(!vis[v]) {
            vis[v]=1;
            Dfs(v,step+1);
        }
    }

}

void solve(){
    deep[1]=1;vis[1]=1;vis[0]=1;
    dfs(1);
    sort(nn+1,nn+n+1,cmp);
   
    for(int i=1;i<=n;i++){
        if(!deep[nn[i]]) continue;
        int u=fa[fa[nn[i]]]; 
        memset(vis,0,sizeof(vis));    
        vis[0]=1;
        ans++;
        vis[u]=1;
        Dfs(u,0);
    }
}

int main(){
    n=read();
    int a;
    for(int i=1;i<n;i++){
        a=read();nn[i]=i;
        add(i+1,a);add(a,i+1);
    }nn[n]=n;
    solve();
    printf("%d",ans);
    return 0;
}

View Code

BZOJ 2313

实际上算的是M^分组方案

step1：求出有多少种分组方案

求因子个数 for i=1~√n =>有k个因子

step2：求有多少种颜色数

计算M^k =>quick_pow

up：

不考虑人在分组中的顺序，但要考虑不同人分配在同一组产生的差异：（有点乱，举个例子：假设6个人，编号为1 2 3 4 5 6，那么分组的话：(123)(456)与(124)(356)是不同的，而(312)(564)与(123)(456)是相同的）

只要组内的人不完全相同，就认为是不同的两种方案；

第一组的方案数：从n个人选n/r个人出来C_n^n/r

第二组的方案数：从剩下的n-n/r个人中选出n/r个人C_n-n/r^n/r

……

第n组的方案数：从剩下n/r个人中选出n/r个人

最后因为不考虑排列方式，因此我们还要再除r！

problem 1：论如何求上面的公式

problem 2：k（也就是上述式子）应该去mod多少；

solve problem 1：、

化简上述式子：

solve problem 2：

运用欧拉定理：

因此k%φ(1e9-401)；

problem 3： n这么大，阶乘该怎么算

solve：1e9-401是一个质数，

那么φ(1e9-401)=1e9-402=2*13*5281*7283;

转化为n！%2，n！%13，n！%5281，n！%7283;

然后用中国剩余定理？？合并方程；

模的数非常小，意味着一定有循环节

开始懵逼？？？？？

求N！%13:

先要知道什么样的(x,y)是先手必胜的：

①把黑色格子到顶端的距离缩小

②把黑色格子到左端的距离缩小

③把黑色格子到低端的距离缩小

④把黑色格子到右端的距离缩小

可以看做有四堆石子的nim石子游戏，

四堆石子分别是：

①x-1个石子

②y-1个石子

③n-x个石子

④m-y个石子

显然先手必胜或必败，只需要异或一下：

对于1<=x<=n,1<=y<=m。

使得(x-1)^(y-1)^(n-x)^(m-y)=0;

优化枚举过程：

问有多少个x，y，满足(x-1)^(n-x)=(y-1)^(m-y)（异或相同为0不同为1，若两边相等，异或以后为0）

首先枚举x，求出所有可能值，放到一个数组里，然后每计算一个y，看在数组中出现了几次。排序+二分的思想（或者使用桶排思想），然后就好了。

CF 45GPrime Problem

代码最长的是判断一个数是不是质数；

哥德巴赫猜想：

任何一个大于等于4的偶数，可以被拆成两个质数之和；未证明

任何一个大于等于7的奇数，可以被拆成三个质数之和；已证明

S=n*(n+1)/2

if (S%2==0) printf("2");

if(S%2==1) S是一个质数当且仅当n=2；

当n=2时输出1；

如果S-2是质数输出2

否则输出3

啊啊啊啊啊啊啊啊啊啊啊啊太艰难了

以下是CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long

using namespace std;

ll n,sum;
ll ans[10010];
bool notp[18003001];

void prime(ll sum){
    notp[1]=1;notp[0]=1;
    for(ll i=2;i<=sum;i++){
        if(notp[i]) continue;
        for(ll j=i*i;j<=sum;j+=i)
            notp[j]=1;
    }
}

void print(){
    for(ll i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return;
}

int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) ans[i]=1;
    sum=n*(n+1)/2;

    prime(sum);
    if(!notp[sum]) {
        print();
        return 0;
    }
    ll u=-1;
    for(ll i=2;i<sum-1;i++)
        if((!notp[i])&&(!notp[sum-i]))
            u=i;
    
    if(u==-1){
        ans[3]=3;sum-=3;
        for(ll i=2;i<sum-1;i++)
            if((!notp[i])&&(!notp[sum-i]))
                u=i;
    } 
    
    for(ll i=n;i>=1;i--){
        if(i<=u&&ans[i]==1){
            u-=i;
            ans[i]=2;
        }
    }
    print();
    return 0;
}

View Code

显然对于任意两头牛的曼哈顿距离都是|x1-x2|+|y1-y2|

我们不妨假设x1>=x2；

那么就变成了x1-x2+|y1-y2|;

两种情况：

①：y1>y2：x1-x2+y1-y2=(x1+y1)-(x2+y2)

②：y1<y2:x1-x2+y2-y1=(x1-y1)-(x2-y2);

按照x+y排一遍序，按照x-y排一遍序，分别取两次的最大-最小，然后再将这两次最大-最小取max；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long

using namespace std;

int n,x,y;
int a,b,c,d;

int main(){
    scanf("%d",&n);
    a=-0x7fffffff;
    b=0x7fffffff;
    c=-0x7fffffff;
    d=0x7fffffff;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        a=max(x+y,a);
        b=min(b,x+y);
        c=max(x-y,c);
        d=min(x-y,d);
    }
    printf("%d",max(a-b,c-d));
    return 0;
}