达卡 2012 Game of MJ

Posted on by

有 $n$ 个显示器，第i个显示器能显示 $L_i$ 个数，每个数能显示的范围是$0$~$ b_i-1$，显然最后显示的数是一个$b_i$进制的数。一开始这些数均为 $0$，现在 $2$ 人轮流操作，每次一人选一个显示器上的一个数并将它加上 $1$（要求不能选个位数，不能进位）。如果操作后，所有显示器显示的数视为$b_i$进制后转成 $10$ 进制的和是 $3$ 的倍数，那么操作这一步的人输。如果没有合法操作算平局。问谁赢。

注意问题可以转化成有若干 $0，1，2，2$ 人轮流取要求不能是 $3$ 的倍数。这个问题的答案是显然的。

import java.io.*;
import java.util.*;
import java.math.*;

public class B
{
    static int[] a=new int[1234567];
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n,m,k;

        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();
        int dis=10000,p;
        for(int i=1;i<=n;i++) {
            p=cin.nextInt();
            int d=i-m;
            if(d<0) d=-d;
            if (p>0 && p<=k &&dis>d ) {
                dis=d;
            }

        }
        System.out.println(dis*10);

    }
}
Posted in 未分类

FWT代码-BZOJ 4589 Hard Nim

Posted on by

题目：给n个不超过m的素数，求xor和=0的方案数，FWT变换裸题。
题目

2关于F逆元的公式： $inv(2)=(F+1)>>1$
证：$ [(F+1)>>1]*2 \pmod F=F+1 \pmod F =1$

代码：


#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll F=1000000007LL;
ll iv2=F+1>>1; //Õâ¸ö¼ÆËã˼·ºÃÆÀ 
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
void fwt(int*a,int n){
    int i,j,k,x;
    for(k=2;k<=n;k<<=1){
        for(i=0;i<n;i+=k){
            for(j=i;j<i+(k>>1);j++){
                x=a[j]+a[j+(k>>1)];if(x>=F) x-=F;
                a[j]=a[j]-a[j+(k>>1)];if(a[j]<0) a[j]+=F;
                a[j+(k>>1)]=x;
            }
        }
    }
}
void twf(int*a,int n){
    int i,j,k,x;
    for(k=n;k>=2;k>>=1){
        for(i=0;i<n;i+=k){
            for(j=i;j<i+(k>>1);j++){
                x=a[j]+a[j+(k>>1)];
                a[j+(k>>1)]=(int)(1LL*(a[j+(k>>1)]-a[j]+F)*iv2%F);
                a[j]=(int)(1LL*x*iv2%F);
            }
        }
    }
}
ll pow2(ll a,ll b){
    if (!b) return 1%F;
    ll p=pow2(a,b/2);
    p=mul(p,p);
    if (b&1) p=mul(p,a);
    return p;
}
#define MAXN (50000<<3)
int b[MAXN],a[MAXN];
ll n,m;
int main()
{
//  freopen("bzoj4589.in","r",stdin);
//  freopen(".out","w",stdout);

    n=50000;
    MEM(b) b[1]=b[0]=1;
    Fork(i,2,n) if (!b[i]) {
        for(int j=2;i*j<=n;j++)
            b[i*j]=1;
    }   
    while(cin>>n>>m) {
        int len=1;
        while(len<=m) len<<=1;
        Rep(i,len) a[i]=(!b[i])&&(i<=m);
        fwt(a,len);
        Rep(i,len) a[i]=pow2(a[i],n);
        twf(a,len);
        printf("%d\n",a[0]);
    }

    return 0;
}
Posted in FWT

BZOJ 水题50乱做

Posted on by
[TOC] 1051: [HAOI2006]受欢迎的牛
显然受欢迎的牛一定在一个强连通分量里,缩点后看看有没有出度为0的点，如果有多个那么无解
4690: Never Wait for Weights
加权并查集
1269: [AHOI2006]文本编辑器editor
rope的使用方法http://blog.csdn.net/iamzky/article/details/38348653
1031: [JSOI2007]字符加密Cipher
后缀数组裸题
3238: [Ahoi2013]差异
后缀数组裸题
1041: [HAOI2008]圆上的整点
数学题，求\(a^2+b^2=c^2\)(c已知),a,b的正整数解个数
http://blog.csdn.net/csyzcyj/article/details/10044629
1014: [JSOI2008]火星人prefix
splay+hash+二分
1069: [SCOI2007]最大土地面积
平面土地上有N个点，选择其中的四个点，求围成的多边形最大面积。
n<=2000
求凸包，O(n^2)枚举对角线，两侧的点有决策单调性，用一个指针O(1)求
1090: [SCOI2003]字符串折叠
区间dp
3998: [TJOI2015]弦论
SAM

1066: [SCOI2007]蜥蜴
网络流，拆点
1015: [JSOI2008]星球大战starwar
倒着并查集
4443: [Scoi2015]小凸玩矩阵
网络流，动态加边/二分都行
1067: [SCOI2007]降雨量
线段树/RMQ都行，要分类讨论
1042: [HAOI2008]硬币购物
我们先算出不考虑限制时的方案数\(f_s\),如果一个硬币超出限制，那么至少要使用\(d_i+1\)次，此时答案为\(f_{s-c_i*(d_i+1)}\),我们可以用容斥定理解决问题
2298: [HAOI2011]problem a
考虑一个人的话：“有ai个人分数比我高，bi个人分数比我低”等价于“我的排名在\([L,R]\)区间中，这个区间中人的成绩相同“，然后就可以变成线段覆盖问题，贪心即可。
4653: [Noi2016]区间
将区间按长度排序，枚举最长区间长度，显然最短区间长度满足单调性，只需要确认“m个区间共同包含至少一个位置”，用线段树维护最大值即可。
1192: [HNOI2006]鬼谷子的钱袋
k个钱袋最多能凑出\(2^k-1\)的所有钱数
1800: [Ahoi2009]fly 飞行棋
暴力。
1856: [Scoi2010]字符串
回顾卡特兰数的推导过程，发现\(ans=C(n+m,n)-C(n+m,n+1)\)

1801: [Ahoi2009]chess 中国象棋
炮的攻击范围为，横行竖行，跳过一个棋子打一个，距离不限
故原题为求\(n*m\)的矩阵中同行同列只能放至多2个炮的方案数
\(f_{i,j,k}\)表示到第i行，j列放了一个，k列放了2个的方案数
4641: 基因改造
在允许置换的情况下kmp是可以的，hash应该也行
我觉得我应该改改KMP的模板了。。
4602: [Sdoi2016]齿轮
dfs走一遍
3926: [Zjoi2015]诸神眷顾的幻想乡
由于叶子节点不超过20个，所以可以用SAM。
注意拷贝叶子节点时只拷贝c个节点不然会TLE.
4627: [BeiJing2016]回转寿司
线段树裸题
4619: [Wf2016]Swap Space
贪心，证明看得不是很懂
http://www.cnblogs.com/gangding/p/5705400.html
1016: [JSOI2008]最小生成树计数
回忆Kruskal的建立方法，显然每个长度后图的连通性是一定的，具有相同权值的边不会超过10条，dfs就行。
1061: [Noi2008]志愿者招募
经典的问题
https://www.byvoid.com/blog/noi-2008-employee/
3295: [Cqoi2011]动态逆序对
cdq，三维偏序（白书原题）
3996: [TJOI2015]线性代数
经过一堆变形我们发现\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n} B_{i,j}a_i a_j-\sum_{i=1}^nC_ia_i\)
我们把这转化为最大权闭合子图最小割
答案=所有点正权值之和-最小割
3875: [Ahoi2014]骑士游戏
令f_i为杀死i的最小代价，那么有\(f_i=min(K_i,\sum_v{f_{v_i}})\)
状态之前的转移有环，我们考虑《SPFA算法的优化及应用》中提到的算法

3997: [TJOI2015]组合数学
安利Dilworth定理：http://blog.csdn.net/popoqqq/article/details/45171469
4448: [Scoi2015]情报传递
询问离线，树链剖分
1070: [SCOI2007]修车
费用流经典模型
http://www.cnblogs.com/Sky-Grey/p/3862019.html
4418: [Shoi2013]扇形面积并
扫描线，用树状数组+二分判断
1406: [AHOI2007]密码箱
\(x^2=1 \mod n\)等价于\(n|(x-1)(x+1)\)然后暴力枚举因子就行
1038: [ZJOI2008]瞭望塔
半平面交，把分段点（包括边界）取出来
2618: [Cqoi2006]凸多边形
拆成一堆直线半平面交
4517: [Sdoi2016]排列计数
错排公式\(D(0)=1,D(1)=0,D(i)=(i-1)(D(i-1)+D(i-2))\)
有个求一段阶乘的逆元的小技巧

for(inv[n]=pow2(fact[n],F-2,F),i=n-1;i;i--)
        inv[i]=mul(inv[i+1],i+1);

4516: [Sdoi2016]生成魔咒
1.裸sam+map
2.求出反序后字符串的SA,每次添加一个字符串，考虑其对height前后字符串的影响
4514: [Sdoi2016]数字配对
我们发现两个数能配对，则它们分解质因子后的数的个数奇偶性不同，我们可以建出二分图，费用流乱搞

2243: [SDOI2011]染色
树链刨分，把情况转成子节点到父节点的两条链会比较好讨论
3531: [Sdoi2014]旅行
树链剖分，拆成n棵树。记得动态开点减少结点数
3631: [JLOI2014]松鼠的新家
对于加法操作差分，将对链的操作转换为点始末节点的操作，避免后效性,在子节点\(s_i\)+1表示从它开始到根节点均+1，最后统计一遍就行
4034: [HAOI2015]T2
树链剖分时，可用dfs序剖分

void dfs(int x,int fa,int tp){
        top[x]=tp; id[x]=++cnt;
        if (son[x]) dfs(son[x],x,tp);
        Forp(x)
        {
            int v=edge[p];
            if (v==fa||v==son[x]) continue;
            dfs(v,x,v);
        }   
        mx[x]=cnt;
    }

3626: [LNOI2014]LCA
操作离线，然后

后加每个点的时候是把从这个点到根的路径的点权全部+1
然后查询就是查询某个点到根的路径的点权和

1191: [HNOI2006]超级英雄Hero
二分图匹配
1143: [CTSC2008]祭祀river
用floyd求传递闭包，建图，原题求最长反链=最小链覆盖
证明：http://www.bubuko.com/infodetail-664202.html
路径不能相交的最小路径覆盖可以用二分图做
路径可以相交的最小路径覆盖（也就是最小链覆盖）可以用floyd求传递闭包建图，转成前面那个用二分图做
2227: [Zjoi2011]看电影(movie)
公式题：ans=(k+1)^(n-1)*(k-n+1)/k^n
神一般的证明：http://www.cnblogs.com/devilpi/articles/3817691.html
1179: [Apio2009]Atm
tarjen缩点+跑一遍dij
4419: [Shoi2013]发微博
用户没有传递性（SB读错题），只有直接关系能看到信息
差分后得到，\(ans_i=t2-t1+t3-t4+...+t_n-t_{n-1}\)暴力维护

埃及卢克索wf游记

Posted on by

Day -1：

托渡渡鸟的福，成功获得了取luxor旅游的机会。本来应该去年就能去了，结果遇到了战争又又又推迟了，多灾多难的一天。。。。

做动车来到了广东省，看到ddd它们还在泡澡。。最后直到机场才会和。

在广州火车站到机场的路上做的ingress mission

到埃及开罗转Luxor的时候发现自己机票不是连买的，来不及取托运行李了。。结果行李·就落在开罗到Luxor的时候就剩包了。。我就不应该托运行李。。。

到了Luxor以后和xjtu的人聊天，还有2个人没到。。老师不来了。。。还在想我行李的事。之后和jc，jiangly，等等人聚会。。。午餐是华为请的。。

晚上去华为那里研究如何拿回行李。。

晚上睡过了差点没赶上晚餐。。

这里酒店晚餐很丰盛 差点错过

晚上和dls等人进行了热烈友好的交流 就icpc发展，和算法竞赛培训交换了意见。着重讨论了如何帮助选手进步，如何减小弱校强校之前的差距之类的问题。

Day 0：

今天去报到。，。。上午又来一个·人取拍照。。下午估计还要再来一个人。。

下午

ICPC训练联盟 2024.7.19

Posted on by

链接: https://pan.baidu.com/s/1TIo0Y3A1Da8w2QMK6FUY1g?pwd=f4f3 提取码: f4f3 复制这段内容后打开百度网盘手机App，操作更方便哦
--来自百度网盘超级会员v6的分享

Posted in 未分类 | Tagged

ICPC训练联盟夏令营

Posted on by

PPT：

链接: https://pan.baidu.com/s/1NsUu06tsM7Hk8_5r07GZuQ?pwd=672v 提取码: 672v 复制这段内容后打开百度网盘手机App，操作更方便哦
--来自百度网盘超级会员v6的分享

Posted in 未分类

百度之星 2024 游记

Posted on by

2023年12月29号，我去北京参加百度之星比赛，提前一天向网龙公司请假，去的路上收到航班延误的消息，更糟糕的是发现错买到了中午去上海的机票，之后赶紧在高速上买了去北京的机票并在机场退了前一张票。

到了北京以后，迅速到所在酒店下榻。酒店的位置非常偏，离以前举办的地点百度总部大楼非常远。因为之后还要去总部参观，小睡了一会儿后，打的来到了总部。感觉没睡好觉。因为参观过很多次百度大楼了，上一次没能坐上百度的自动驾驶车。这次人少坐上了。以前这会儿应该给各个hr和团队的信息挖人了，这会儿没这个环节，联想到这次百度不报销路费，初赛收费，比赛正式加入官方比赛合集的操作，感觉似乎这比赛性质变了

发现自己的室友是苏畅是以前认识的人，圈子好小。。晚上在酒店1F水了顿自助火锅，肉不大新鲜，并不好吃。。

第二天模拟赛，大家陆陆续续到了。晚上的时候去了模拟赛，还是之前新出的系统，卡着半天一直进不去，最后只来得及签个到，，希望明天正赛正常。

第二天起了个大早，在正赛开始前才发现大家都带了纸质模版，以前么这么一出。。不过已经来不及弄了，就这么着了（后面发现正赛没啥大数据结构题）

题解见我之前发csdn的那篇（博客关停好几次结果发现还是csdn好用。。12年前的记录都能找出来，同一时间的BlogBus，百度空间，网易博客全军覆没……）

老年选手做不完题。。

晚上比赛结束，终于有宣讲环节了……不过以前的组单独介绍部分没了（可能人太多）。。这次的滚版好长时间。。基本人手一个奖，最末尾都有

对没错，真的是锤子。。

晚上同学生日，半夜跑到市中心玩跨年倒数，，还去酒吧啃了汉堡，，3个人中只有我不会酒，，本来还想看日出，结果大家都醉了，，最后回宾馆睡觉了。。

新年快乐。

Posted in 未分类

运动会集训

Posted on by

最近--开始了运动会的集训--（有生之年最后一次高中运动会………………の集训）

好吧，这不是重点。。。

说一下这2天的题目：

Day 1：

Relation：