游记#2019PKUWC

muronglin
muronglin 2019年12月13日
  • 在其它设备中阅读本文章

正文从 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],e510;
long double ans,res[510],E[30010],a510;
void solve()
{
    for(int i=1;i<=n;i++)
    {
        int t;
        for(int j=1;j<=n;j++)
            if(!id[j]&&fabs(aj)>eps)t=j;
        id[t]=i;
        for(int j=1;j<=n;j++)if(j!=t)
        {
            long double BASE=aj/at;
            for(int k=1;k<=n+1;k++)aj-=at*BASE;
        }   
    }
    for(int i=1;i<=n;i++)
        res[id[i]]=ai/ai];
    for(int i=1;i<n;i++)for(int j=i+1;j<n;j++)
            if(ei)E[++cnt]=res[i]/d[i]+res[j]/d[j];
    for(int i=1;i<=n;i++)
        if(ei)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("%.3lfn",double(ans));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),
        ex=ey=1,
        d[x]++,d[y]++;
    for(int i=1;i<=n;i++)
    {
        ai=1,ai=(i==1);
        for(int j=1;j<n;j++)
            if(ej)ai-=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=1llreta%mod;
        a=1llaa%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],wN,sM;
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(sj)
        {
            int num=1llsjp(si,mod-2)%mod;
            for(int x_=A,y_=A-k;x_<=B;x_++,y_++)
                sj=(sj-1llnumsi%mod+mod)%mod;
            val[j]=(val[j]-1llnumval[i]%mod+mod)%mod;
        }
    for(int i=cnt;i>=wn;i--)
    {
        ans[i]=1llval[i]p(si,mod-2)%mod;
        for(int j=i-1,k=1;j&&k<=A;j--,k++)if(sj)
            val[j]=(val[j]-1llans[i]sj%mod+mod)%mod;
    }
    return answ[n];
}
int main()
{
    scanf("%d",&n),A=n2,B=n4;
    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))wi=++cnt;
    for(int i=0;i<=A;i++)for(int j=0;j<=A;j++)if(wi)
    {
        for(int k=0;k<4;k++)if(wx)
            sw[i]w[x-wi+A]=P[k];
        sw[i][A]=valw[i]=mod-sum;
    }
    printf("%dn",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

算法

生成函数

例题

有四种无限多的水果,要求第一种恰好拿出偶数个,第二种恰好拿出 5 的倍数个,第三种最多拿 4 个,第四种最多拿 1 个,求恰好拿出 n 个水果的方案数
可以先想到背包,那么易得 第一种的序列为 ${1,0,1,0,1,0,...}$ 第二种的序列为 ${1,0,0,0,0,1,0,...}$ 第三种的序列为 ${1,1,1,1,1,0,0,...}$ 第四种的序列为 ${1,1,0,0,0,0,0,...}$ 分别写出它们的生成函数 第一种 $\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,...}$ 所以方案数就是 $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 也算没白来,滚回去学文化课了