慕容琳的后花园
慕容琳的后花园
游记#2019PKUWC

正文从Day0开始

Day-7

算法

主元法
Band Matrix
Berlekamp-Massey

例题

HNOI2013 游走 \checkmark

#include<bits/stdc++.h>
using namespace std;
const double eps=(1e-8);
int n,m,cnt,x,y,d[510],id[510],e[510][510];
long double ans,res[510],E[30010],a[510][510];
void solve()
{
    for(int i=1;i<=n;i++)
    {
        int t;
        for(int j=1;j<=n;j++)
            if(!id[j]&&fabs(a[j][i])>eps)t=j;
        id[t]=i;
        for(int j=1;j<=n;j++)if(j!=t)
        {
            long double BASE=a[j][i]/a[t][i];
            for(int k=1;k<=n+1;k++)a[j][k]-=a[t][k]*BASE;
        }   
    }
    for(int i=1;i<=n;i++)
        res[id[i]]=a[i][n+1]/a[i][id[i]];
    for(int i=1;i<n;i++)for(int j=i+1;j<n;j++)
            if(e[i][j])E[++cnt]=res[i]/d[i]+res[j]/d[j];
    for(int i=1;i<=n;i++)
        if(e[i][n])E[++cnt]=res[i]/d[i];
    sort(E+1,E+1+cnt);
    for(int i=1;i<=cnt;i++)ans+=E[i]*(m-i+1);
    printf("%.3lf\n",double(ans));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),
        e[x][y]=e[y][x]=1,
        d[x]++,d[y]++;
    for(int i=1;i<=n;i++)
    {
        a[i][i]=1,a[i][n+1]=(i==1);
        for(int j=1;j<n;j++)
            if(e[j][i])a[i][j]-=1.0/d[j];
    }
    solve();
    return 0;
}

SDOI2012 走迷宫 \times
SCC(强连通分量)忘了
CF963E Circles of Waiting \checkmark

#include<bits/stdc++.h>
#define mod 1000000007
#define F(x) ((x)*(x))
#define N 110
#define N_ 210
#define M 8010
using namespace std;
int p(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b/=2; 
    }
    return ret;
}
#define x i+t1[k]
#define y j+t2[k]
int n,A,B,cnt,sum,P[4],f[M],val[M],ans[M],w[N][N],s[M][N_];
int t1[]={-1,0,1,0},t2[]={0,-1,0,1};
int solve()
{
    for(int i=1;i<=cnt;i++)
        for(int j=i+1,k=1;j<=cnt&&k<=A;j++,k++)if(s[j][A-k])
        {
            int num=1ll*s[j][A-k]*p(s[i][A],mod-2)%mod;
            for(int x_=A,y_=A-k;x_<=B;x_++,y_++)
                s[j][y_]=(s[j][y_]-1ll*num*s[i][x_]%mod+mod)%mod;
            val[j]=(val[j]-1ll*num*val[i]%mod+mod)%mod;
        }
    for(int i=cnt;i>=w[n][n];i--)
    {
        ans[i]=1ll*val[i]*p(s[i][A],mod-2)%mod;
        for(int j=i-1,k=1;j&&k<=A;j--,k++)if(s[j][A+k])
            val[j]=(val[j]-1ll*ans[i]*s[j][A+k]%mod+mod)%mod;
    }
    return ans[w[n][n]];
}
int main()
{
    scanf("%d",&n),A=n*2,B=n*4;
    for(int i=0;i<4;i++)
        scanf("%d",&P[i]),sum+=P[i];
    for(int i=0;i<=A;i++)
        for(int j=0;j<=A;j++)
            if(F(i-n)+F(j-n)<=F(n))w[i][j]=++cnt;
    for(int i=0;i<=A;i++)for(int j=0;j<=A;j++)if(w[i][j])
    {
        for(int k=0;k<4;k++)if(w[x][y])
            s[w[i][j]][w[x][y]-w[i][j]+A]=P[k];
        s[w[i][j]][A]=val[w[i][j]]=mod-sum;
    }
    printf("%d\n",solve());
    return 0;
} 

loj3080 国际象棋 \times 咕咕咕

Day-6

模拟赛

van游戏 \checkmark
雀魂喵喵喵 \checkmark
圣诞礼物 \checkmark

Day-5

算法

组合数学

例题

咕咕咕

Day-4

模拟赛

\times 咕咕咕
饮料 \checkmark
货币 \times 咕咕咕

Day-3

模拟赛

\times 咕咕咕
矩形 \times 咕咕咕
除法与取模 \times 咕咕咕

Day-2

模拟赛

xor on tree \times 咕咕咕
calc on lowbit \times 咕咕咕
color on board \times 咕咕咕

Day-1

算法

生成函数
https://muronglin.123yes.me/m2a24-300x161.png

例题

有四种无限多的水果,要求第一种恰好拿出偶数个,第二种恰好拿出5的倍数个,第三种最多拿4个,第四种最多拿1个,求恰好拿出n个水果的方案数
可以先想到背包,那么易得
第一种的序列为 {1,0,1,0,1,0,\dots}
第二种的序列为 {1,0,0,0,0,1,0,\dots}
第三种的序列为 {1,1,1,1,1,0,0,\dots}
第四种的序列为 {1,1,0,0,0,0,0,\dots}
分别写出它们的生成函数
第一种 \frac{1}{1-x^2}
第二种 \frac{1}{1-x^5}
第三种 1+x+x^2+x^3+x^4
第四种 1+x
最后把它们乘起来再化简,就是 \frac{1}{(1-x)^2}
把这个东西化回序列,变成 {1,2,3,4,5,\dots}
所以方案数就是 n+1

Day0

上午

7:48的高铁,去北京咯

下午

宾馆订了公寓式酒店,两个人两张大床,还是挺舒服的
不太习惯的就是北方房间里的暖气,一进门就要脱两件衣服
收拾完东西去报道,一不小心走错了门,就从未名湖一路逛过去了233
未名湖结冰了,看到有人在上面走,但我没敢下去玩
报道的地方找了好久emmm
不用交营费还白嫖了150的PKU饭卡,舒服~

Day1

上午

开营仪式好无聊,就介绍了一下PKU
中午去PKU食堂吃饭,发现比学校食堂好多了QWQ
终于知道那些冬天吃棒冰的人是什么心态了
因为冬天吃棒冰真的很舒服啊23333

下午

自闭了好吧
开了T1发现暴力都不会做,果断跑去开T2
T2搞了搞只能拿前三档分,18分滚粗
看一眼T3,送了19分,拿了跑路
我感觉凉了,想回T1看能不能拯救一下
看了会发现21分暴力可以做了
于是Day1只有 21+18+19=58
自闭选手

Day2

上午

上午的面试,竟然是面向全体营员的
分三场,每场5分钟的单人面试
问的都什么魔鬼问题

昨天考的怎么样,考了几分
为什么没考好
以后有什么打算
你的学校在你们那排第几
你的文化课怎么样

都是来自灵魂的拷问,我死了

下午

一进去就看到T3的名字叫最小割
完了,最大流忘记怎么打了
本着自闭的心态瞄了眼T1
发现是送分题???
10分钟的时候敲完一交
A了!!!???
心态忽然好起来
剩下4个多小时一直搞T2
结果也只乱搞拿了个数据随机的分
于是Day2的分数就只有 100+65+0=165
两天加起来223分,凉了

Day3

上午

没啥事,教练本来想带我们去清华玩
我懒得起来就在床上颓了一个上午233
快中午了才起来退房,去PKU食堂吃最后一顿午饭顺便把卡刷完

下午

闭营仪式了,讲题的时候一直怀疑人生
我为什么要来WC受虐emmmmm
颁奖的时候,莫名其妙的混了个三等奖
看那些一等奖大佬上去签了什么东西
以为他们有学上了,没想到是不能去其他学校的营233
也算没白来,滚回去学文化课了

赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

游记#2019PKUWC
正文从Day0开始 Day-7 算法 主元法 Band Matrix Berlekamp-Massey 例题 HNOI2013 游走 $\checkmark$ #include<bits/stdc++.h> using namespace std; const double eps=(1e-8)…
扫描二维码继续阅读
2019-12-13
功能