期末考期间作死囤题的我12月乱做——囤题计划4

Posted on by

期末考期间作死囤题的我12月乱做——囤题计划4

  • [Upd 2016.12.29] 话说统一下格式会死吗……写了4份囤题用了4种格式……还好我不是处女……
  • [Upd 2016 1.6]今天CF研究了shift-and算法，居然超时我&^(^*&)
  • [Upd 2016.1.9] 居然丢失了一部分文档……已经补在后面了……
  • [Upd 2016.1.10] 过了facebookHackCup的资格赛……因为网络延时只交了1题好气啊……投诉主席！不过还好总算是过了.今天栗子考完电磁场了大家会不会轻松一点？

【BZOJ 1209:[HNOI2004]最佳包裹】3d凸包

【BZOJ 4247: 挂饰】 背包

int n;
struct arr{
    ll a[10000];
    ll &operator[](int i) {
        if (i<-n) i=-n; if (i>n) i=n;
        return a[5000+i];
    }
}f;
//这个数组写法好评

【BZOJ 1071: [SCOI2007]组队】将题意化简为平面上有一堆点，你需要用某个直角三角形（保证直角边平行坐标轴不能旋转斜边方向为\），问最多能框住几个点。
O(n^2)暴力双指针，这里注意斜边顺序入队，丨边顺序出队。

【BZOJ 4373: 算术天才⑨与等差数列】hash+线段树

【BZOJ 4589: Hard Nim】裸的FFT，见正文

【BZOJ 3670: [Noi2014]动物园】kmp

【BZOJ 2561: 最小生成树】只要看出是最小割就行了。

【BZOJ 2761: [JLOI2011]不重复数字】暴力

【BZOJ 1189: [HNOI2007]紧急疏散evacuate】BFS计算出每个人离每个出口的距离，网络流，二分+拆点，注意一个人不能路过一个出口到达另一个出口（因为出口格子有人数限制）d。

【BZOJ 4551: [Tjoi2016&Heoi2016]树】倒序，并查集

【BZOJ 4195: [Noi2015]程序自动分析】 并查集

【BZOJ 4196: [Noi2015]软件包管理器】 树链剖分

BZOJ 4197: [Noi2015]寿司晚宴】小素数状压dp，每次处理一个大素数

【BZOJ 4198: [Noi2015]荷马史诗】 哈夫曼树，如果k>2时，要通过填0使$n\mod(k-1)=1$

【BZOJ 4199: [Noi2015]品酒大会】

【BZOJ 4128: Matrix】？？？ BSGS 矩阵

【BZOJ 4180: 字符串计数】矩阵乘法+SAM//　不想写

【BZOJ 4747: [Usaco2016 Dec]Counting Haybales】set

【BZOJ 4748: [Usaco2016 Dec]Cities and States】哈希

【BZOJ 4749: [Usaco2016 Dec]Moocast】暴力建图

【BZOJ 4746: [Usaco2016 Dec]Lasers and Mirrors】直接bfs（变为权限题无法提交）

【BZOJ 2302: [HAOI2011]Problem c】组合数学

【BZOJ 4036: [HAOI2015]按位或】论文题
http://ydc.blog.uoj.ac/blog/336

【BZOJ 4766: 文艺计算姬】矩阵树定理

【BZOJ 4519: [Cqoi2016]不同的最小割】Gusfield算法

【BZOJ 4320: ShangHai2006 Homework】分段讨论

【BZOJ 2671: Calc】mobius反演
大爷题解：http://blog.csdn.net/popoqqq/article/details/45095601

【BZOJ 2661: [BeiJing wc2012]连连看】费用流

【BZOJ 2751: [HAOI2012]容易题(easy)】没修改的数用快速幂求解，修改的暴力

【BZOJ 2731: [HNOI2012]三角形覆盖问题】

【BZOJ 3224: Tyvj 1728 普通平衡树】Treap
【BZOJ 3196: Tyvj 1730 二逼平衡树】Treap
【BZOJ 2733: [HNOI2012]永无乡】Treap+启发式合并

【BZOJ 3287: Mato的刷屏计划】打表找规律
【BZOJ 1797: [Ahoi2009]Mincut 最小割】如何判断一条边在不在最小割上（残余网络跑强连通分量）
【BZOJ 1951: [Sdoi2010]古代猪文】lucas+费马小定理

【BZOJ 4776: [Usaco2017 Open]Modern Art】想法题，2维前缀和

【BZOJ 4804: 欧拉心算】mobius反演
【BZOJ 4805: 欧拉函数求和】杜教筛
【BZOJ 4809: 皇后】就是n皇后

【BZOJ 4800: [Ceoi2015]Ice Hockey World Championship】meet in the middle 搜素，数据范围提示了

【BZOJ 4807: 車】 $ans=C(max(n,m),min(n,m))$

【BZOJ 4808: 马】二分图最大独立集

【BZOJ 1801: [Ahoi2009]chess 中国象棋】dp,$f[i][j][k]$为前i行有j列有一个炮 k列有两个炮

【BZOJ 4801:[Lydsy2017年4月月赛]打牌】分类讨论

【BZOJ 4810: [Ynoi2017]由乃的玉米田】bitset+莫队

【BZOJ 4811: [Ynoi2017]由乃的OJ】树链剖分

【BZOJ 4542: [Hnoi2016]大数】如果$gcd(p,10)=1$,显然一个子串是k的倍数当且仅当它的2个后缀mod p余数相同。
当p是2，5的时候可以根据最后一位判断。
这2种情况都可以用莫队。

【BZOJ 4813: [Cqoi2017]小Q的棋盘】由于起点必须是0号点，不难发现最优决策是走最远点，此时最长链上的边代价为1，其余为2，注意考虑能访问的点不能超过点数

【BZOJ 1078: [SCOI2008]斜堆】模拟斜堆的操作，发现最后一个节点是从根往左一直走直到第一个没有右节点的节点（如果有左节点再向左走一步，那么倒推即可

【BZOJ 4806: 炮】同BZOJ 1801

【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。

【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-...-1的简单路径

BZOJ 五月胡乱补题

Posted on by

【BZOJ 4806: 炮】同BZOJ 1801
n【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
n由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。
n【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-…-1的简单路径
n【4879: [Lydsy2017年5月月赛]失控的数位板】只要把所有的点的最后一次涂色时间求出来就行了。
n【BZOJ 4894: 天赋】有向图生成树计数的基尔霍夫矩阵
n【BZOJ 3534: [Sdoi2014]重建】 变元矩阵-树定理，求所有生成树边权积的和。把度数改为连出的边权和，$A[i][j]=-$边权，$A[i][i]=$连出的边权和.
n【BZOJ 4031: [HEOI2015]小Z的房间】矩阵树定理，注意gauss消元辗转相除的写法
n【BZOJ 4837: [Lydsy2017年4月月赛]LRU算法】模拟
n【BZOJ 4596: [Shoi2016]黑暗前的幻想乡】矩阵树定理+容斥
n【BZOJ 3517: 翻硬币】

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;
}

达卡 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);

    }
}

BZOJ 五月胡乱补题

Posted on by

BZOJ 五月胡乱补题

@(ACM)

【BZOJ 4806: 炮】同BZOJ 1801
【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。
【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-...-1的简单路径
【4879: [Lydsy2017年5月月赛]失控的数位板】只要把所有的点的最后一次涂色时间求出来就行了。
【BZOJ 4894: 天赋】有向图生成树计数的基尔霍夫矩阵
【BZOJ 3534: [Sdoi2014]重建】 变元矩阵-树定理，求所有生成树边权积的和。把度数改为连出的边权和，$A[i][j]=-$边权，$A[i][i]=$连出的边权和.
【BZOJ 4031: [HEOI2015]小Z的房间】矩阵树定理，注意gauss消元辗转相除的写法
【BZOJ 4837: [Lydsy2017年4月月赛]LRU算法】模拟
【BZOJ 4596: [Shoi2016]黑暗前的幻想乡】矩阵树定理+容斥
【BZOJ 3517: 翻硬币】

【BZOJ 4917: [Lydsy六月月赛]Hash Killer IV】
对于t = t + (t << 10);　即 t=t*(1+2^10) mod 2^64 这种操作，
对于 t = t ^ (t >> 6); 显然
【BZOJ 4919: [Lydsy六月月赛]大根堆】树dp
【BZOJ 4488: [Jsoi2015]最大公约数】固定左端点时最多有LogAi个GCD
【BZOJ 1188: [HNOI2007]分裂游戏】算SG
【BZOJ 4950: [Wf2017]Mission Improbable】网络流
【BZOJ 4953: [Wf2017]Posterize】dp
【BZOJ 4956: [Wf2017]Secret Chamber at Mount Rushmore】签到
【BZOJ 4952: [Wf2017]Need for Speed】签到
【BZOJ 2161: 布娃娃】
【BZOJ 4561: [JLoi2016]圆的异或并】考虑一个圆被嵌套了几次，可以扫描线维护
【BZOJ 4556: [Tjoi2016&Heoi2016]字符串】sam
【BZOJ 2143: 飞飞侠】最短路
【BZOJ 2007: [Noi2010]海拔】显然每个关键点的海拔不是1就是0，于是可以用最短路
【BZOJ 4972: [Lydsy八月月赛]小Q的方格纸】前缀和
【BZOJ 4974: [Lydsy八月月赛]字符串大师】KMP
【BZOJ 4975: [Lydsy八月月赛]区间翻转】没执行一次操作，区间逆序对数的奇偶性必然变化。
【BZOJ 4976: [Lydsy八月月赛]宝石镶嵌】$n-k\ge log(max(a_i))$时，答案显然为所有数的or和，否则$n<=116$可以暴力
【BZOJ 3659: Which Dreamed It】
【BZOJ 4971: 记忆中的背包】
【BZOJ 5039: [Jsoi2014]序列维护】区间加区间乘区间和，线段树
【BZOJ 4803: 逆欧拉函数】根据$Phi(n)$的因子反推n可能存在的素数因子，然后暴搜
【BZOJ 3643: Phi的反函数】同4803
【】

BZOJ水题大乱斗2

Posted on by

[upd 2016.9.29] 今天好无聊不如来刷排位
[upd 2016.10.22] 干脆在vjudge上屯着吧
[upd 2016.10.23] 周末10题斩~
[upd 2016.10.28] bc89 fst了B，可怜我的RATING
[upd 2016.10.29] 19点做完！撒花

#50/50

题目 解法
2653: middle 经典题，静态数列强制在线询问区间中位数，可持久化线段树+二分
3207: 花神的嘲讽计划Ⅰ 可持久化线段树+uint hash
3932: [CQOI2015]任务查询系统 可持久化线段树，离线处理，单点修改，区间前k大和
2588: Spoj 10628. Count on a tree 可持久化线段树，静态树，强制在线链上第k小
3123: [Sdoi2013]森林 可持久化线段树，森林，强制在线支持连边，链上第k小，把小的树暴力重构就行
3744: Gty的妹子序列 可持久化线段树，强制在线区间逆序对数
3289: Mato的文件管理 莫队，区间逆序对数
1025: [SCOI2009]游戏 \(f{i,j}\)表示前\(i\)个质数中\(\sum_{i=1}^m{p_i ^{m_i}}\) 为j的数的个数，则显然\(f_{i,j}=f_{i-1,j}+\sum_k f_{i-1,j-p^k}\), 初始值\(f_{0,0}=1\),\(ans=\sum_{i=0}^n f_{tot,i}\)
1058: [ZJOI2007]报表统计 开2个set
3930: [CQOI2015]选数 安利 http://blog.csdn.net/popoqqq/article/details/44917831
4451 : [Cerc2015]Frightful Formula fft mod 1e9+7 分块写法 安利http://www.cnblogs.com/clrs97/p/5308851.html 交题在LA7329
1061: [Noi2008]志愿者招募 安利PoPoQQQ的题解[单纯形][http://blog.csdn.net/popoqqq/article/details/44310605]
3112: [Zjoi2013]防守战线 和上题没差，单纯形的对偶就是A换成\(A^T\),b,c对调，n,m互换。\(Ay\ge b,min(Cy)\)
BZOJ 3308/tyvj P1564: 九月的咖啡店 神结论题，只有1， 单个质数的若干幂次，两个质数a,b(\(a<\sqrt n < b\))的幂次的乘积可能取到,附大爷[题解][http://blog.csdn.net/popoqqq/article/details/45725661]
1821: [JSOI2010]Group 部落划分 Group 对点对连边并排序，并查集贪心
3555: [Ctsc2014]企鹅QQ 枚举不同字母的位置，然后2遍hash
3212: Pku3468 A Simple Problem with Integers 呵呵
3680: 吊打XXX 爬山算法http://hzwer.com/4139.html
1193: [HNOI2006]马步距离 大范围搜索，小范围暴搜，假设当前(0,0),目标(x,y)贪心的具体方法：当\(x\ge y,x-4\ge 2y\)时，走\((4,0)\),否则走\((4,2)\)
1876: [SDOI2009]SuperGCD 普通的高精度要处理高精%高精，显然不行，于是使用[stein][http://baike.baidu.com/link?url=QtSt9ZVKwuGIjELH8a3jSuqaVmngX8LDull4siXeR971xC37AK5BTIEOgWNAILEbTJn_PWAEUtMewPiwRm4t3q]加速(Stein算法是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法)
2843: 极地旅行社 LCT裸题!板子里居然没有find_root(),o(︶︿︶)o 唉
2134: 单选错位 期望=可能情况/总情况，单独考虑每道题，\(ans=\sum_1^n{\frac {min(a,b)} {ab} }= \sum_1^n{\frac {1} {max(a,b)} }\),其中a,b为相邻两道题的选项数
1077: [SCOI2008]天平 由于天平重量只有1,2,3我们可以计算2个砝码重量差值的上下界，然后dp，安利http://blog.csdn.net/scyjcp/article/details/52622261
1103: [POI2007]大都市meg dfs手写栈，求出dfs序，然后用树状数组处理前缀和
1303: [CQOI2009]中位数图 暴力从中位数向两边走
1304: [CQOI2009]叶子的染色 显然随便取一个根节点，然后设\(f_{i,j}\)为子树i在点i染颜色j时的最小染色数，显然有\(f_{i,j}=\sum_{v}min(f_{v,j}-1,f_{v,j\bigwedge 1})\)
1305: [CQOI2009]dance跳舞 二分+网络流，将男生成一条容量为k的边\(x\to y\)，如果和喜欢的人，就从x走，否则从y走，女生同理。
3171: [Tjoi2013]循环格 循环格是完美的当且仅当每个点入度出度均为1，所以可以建立2分图跑最小费用流。
3442: 学习小组 本来以为是带上下界的最小费用可行流，结果看到了[Tunix][http://www.cnblogs.com/Tunix/p/4354843.html]的解法，可以跑最小费用最大流了
3440: 传球游戏 找出一堆环加外向树，然后各种特判
3444: 最后的晚餐 显然存在大于3个点的环，或者存在点度数>2是无解的。于是发现有解的充要条件是暗恋关系形成链。\(ans=(a+b)!2^b\) 其中a+b是连通块个数，b是点数\(\ge 2\)的链个数，注意重边
4236: JOIOJI 设JOI分别出现x,y,z次，记录前缀的(y-x,z-x)的出现最早位置，扫一遍。
4706: B君的多边形 打表，OEIS - A001003 -  super-Catalan numbers or little Schroeder numbers
2741: 【FOTILE模拟赛】L 分块枚举段首+可持久化字典树
4260: Codechef REBXOR 可持久化线段树维护前后缀最优值fa(1).jpg
1019: [SHOI2008]汉诺塔 考虑2种移动方法http://blog.sina.com.cn/s/blog_76f6777d0101b8l1.html
1021: [SHOI2008]Debt 循环的债务 \(f_{i,j,k}\)表示前i种面值分完后，A和B分别有j和k元的最小步数
3439: Kpm的MC密码 反转字符串并把它们丢入字典树，然后用dfs序+主席树求第k大
1044: [HAOI2008]木棍分割 第一问二分答案，第二问dp，滚动数组+双指针优化
1862: [Zjoi2006]GameZ游戏排名系统 同1056
2780: [Spoj]8093 Sevenk Love Oimaster 广义SAM求parent树,dfs序求区间内有多少不同权值
1786: [Ahoi2008]Pair 配对 通过交换法可以发现填入的数单调不降，且k很小，可以用O(nk)的dp解决
1831: [AHOI2008]逆序对 同上
4524: [Cqoi2016]伪光滑数 http://blog.csdn.net/lych_cys/article/details/51158560,
2734: [HNOI2012]集合选数 神奇的dp，http://blog.csdn.net/aarongzk/article/details/50753250
3438: 小M的作物 最大权闭合子图版题
4245: [ONTAK2015]OR-XOR 拆位，贪心，每次留下“可选分割点”的位置的集合
1060: [ZJOI2007]时态同步 令\(f_i\)为\(i\)为根的子树的最远叶节点距，然后贪心
1053: [HAOI2007]反素数ant 假设x是反质数，设x的约数个数\(\tau(x)=(k1+1)(k2+1)\dots(kn+1)\),和取哪个质数无关，故可认为取的是前k个质数，且k单调不增。。。暴搜
1087: [SCOI2005]互不侵犯King 状压dp