BZOJ 五月胡乱补题

【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

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

2关于F逆元的公式: inv(2)=(F+1)>>1
证:[(F+1)>>1]2(modF)=F+1(modF)=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

达卡 2012 Game of MJ

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

注意问题可以转化成有若干 0122 人轮流取要求不能是 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 未分类

BZOJ 五月胡乱补题

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八月月赛]宝石镶嵌】nklog(max(ai))时,答案显然为所有数的or和,否则n<=116可以暴力
【BZOJ 3659: Which Dreamed It】
【BZOJ 4971: 记忆中的背包】
【BZOJ 5039: [Jsoi2014]序列维护】区间加区间乘区间和,线段树
【BZOJ 4803: 逆欧拉函数】根据Phi(n)的因子反推n可能存在的素数因子,然后暴搜
【BZOJ 3643: Phi的反函数】同4803
【】

BZOJ水题大乱斗2

[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]游戏 fi,j表示前i个质数中mi=1pmii 为j的数的个数,则显然fi,j=fi1,j+kfi1,jpk, 初始值f0,0=1,ans=ni=0ftot,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换成AT,b,c对调,n,m互换。Ayb,min(Cy)
BZOJ 3308/tyvj P1564: 九月的咖啡店 神结论题,只有1, 单个质数的若干幂次,两个质数a,b(a<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)贪心的具体方法:当xy,x42y时,走(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=n1min(a,b)ab=n11max(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]叶子的染色 显然随便取一个根节点,然后设fi,j为子树i在点i染颜色j时的最小染色数,显然有fi,j=vmin(fv,j1,fv,j1)
1305: [CQOI2009]dance跳舞 二分+网络流,将男生成一条容量为k的边xy,如果和喜欢的人,就从x走,否则从y走,女生同理。
3171: [Tjoi2013]循环格 循环格是完美的当且仅当每个点入度出度均为1,所以可以建立2分图跑最小费用流。
3442: 学习小组 本来以为是带上下界的最小费用可行流,结果看到了[Tunix][http://www.cnblogs.com/Tunix/p/4354843.html]的解法,可以跑最小费用最大流了
3440: 传球游戏 找出一堆环加外向树,然后各种特判
3444: 最后的晚餐 显然存在大于3个点的环,或者存在点度数>2是无解的。于是发现有解的充要条件是暗恋关系形成链。ans=(a+b)!2b 其中a+b是连通块个数,b是点数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 循环的债务 fi,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]时态同步 fii为根的子树的最远叶节点距,然后贪心
1053: [HAOI2007]反素数ant 假设x是反质数,设x的约数个数τ(x)=(k1+1)(k2+1)(kn+1),和取哪个质数无关,故可认为取的是前k个质数,且k单调不增。。。暴搜
1087: [SCOI2005]互不侵犯King 状压dp

CCPC长春游记

今年下半年赛季第一场比赛,我们去了长春。

Day1:

被强行起了个大早,大约9点出的门,然而比起主席天没亮就出门还是太晚[话说他真的睡了吗],先是打车去了酒店,然后大巴去了机场,中间耽误了好久,大巴上看到主席在鄂尔多斯~~烤羊腿~~转机的画面……我还是继续睡觉吧……

到了机场已经是接近中午了,由于起得太早没来得及吃早餐(主席:喵~),一行人在机场吃50一份的快餐,可能是由于没糍早餐的报应,lz和mg都糍完了我的那份还在Loading,出门就涱了一波RP。

一路在飞机上睡觉,中途在通辽转机发现主席一伙人已经坐电车~~出去玩了~~找酒店,话说通辽机场阳光好充裕啊去晒日光浴……我还是睡觉吧。。

到了长春才发现自己带的旅行箱完全没用,本来以为零下几十度结果连零都没下1,到旅店时已经很晚了。本来想在下榻的酒店随便叫份外卖,结果被mg拉出去吃烤肉(为什么是烤肉),中间mg策划我们一行人去看电影(嘛反正我平常是不去这种资本主义横行的地方~~还不是因为穷~~),中间主席跑过来说要一起看,结果为了看电影,我点的最后一道菜只好打包带走

achieve

大晚上看了最晚一场电影看到半夜,话说明天还起得来吗?

Day2:

没有任何悬念的错过了酒店早餐,和主席它们跑去报道,从南边进去以后看到了一片建筑工地差点以为走错地方,向右拐进入一个小门,话说吉大好厉害好大好豪华好奢侈好享受好度假村,校园里居然有网吧游泳池商厦台球馆电影院美食城汉堡王,一行人打算在汉堡王刷关送的饭票,尽管门口有写让用实际上并不让用,然而等知道了这点的时候队都排完了……なるほど ,那个告示是故意引人入店的》

下午测试赛,发现我们的校徽被人换掉了-((‵□′))- 。我先看了A,结果由于没看出successive 是连续的意思,结果没做出来……,mg开启手算第二题模式,最后仔细一看发现不是Catalan数吗……实力1A,lz徒手找规律,过掉一到本来好像要gauss期望dp的题,我分类讨论一波,强行过掉C。我们队成功开启·真·无双做题模式,1人1T1A,结果榜单上没有我们,仔细一看交错号了(GG),交到了中科大(喵)去了

然后我们去了伪满皇宫,由于关门进不去,去了旁边的抗日战争主题博物馆,中间大家走散了,出来的时候,主席骗mg说我还没出来,结果mg已经出来了在出口的树下,,敢情被坑的是我……话说都快比赛了这么掉RP没问题吗~

晚上一行人去万达玩密室逃脱,路上被主席一路tc,我们玩得是星际迷航主题,开局是转盘语音容错率低差评,中途逃生舱把写得英文看成请误触碰(我不是故意的……),中间把密码器当工作人员使用的了(自带跳过重要线索光环),后面不明意义的圆盘需要跳回前几个房间,没注意到不做评价,解方程没有使用Hints好评,最后那个Hash表沦落到用Hint(不好意思说自己是竞赛党了),最后结局开船意义不明(强行凑谜题个数)

Day3:

早上起来随便喝了点豆浆上战场,开局看标题,mg默默给题目打上送分,进阶,不可做题的标签2

,开局mg开始手速题,迅速过了Triangle,忘了n=1时/gcd稍微在 Fraction 下欠了一个罚时,我开局看 Binary Indexed Tree不会做3,改看其它题,中途mg开kmp的Sequence I,由于白书kmp板子有点小问题稍微发了点时间,途中我给出了Harmonic Value Description的构造解做法,一共就几行,稍微挽回了一点罚时。

中途我把Ugly Problem 的解构造出来了,由于要用高精,mg让我上Java,然后mg和lz讨论其他题去了,由于之前想当然漏掉几种特判,再加上太久没用java差点交文件时把类名写错,不辛坑了一波队友(我对不起你们),将近1h才过掉这题,此时只剩下一个多小时了。

继续看题发现Sequence II 之前好像在哪里做过,好开心这不是主席树么(主席:喵~)。二话不说敲了10min板子,结果不小心写了动态开节点的线段树的板子(考得这么残念罪魁祸首),最终mg强行主席树手写成功(中途由于节点数开小了re了一发),然后最后剩15min实在写不了题,进入喝茶聊天给其它队制造压力mode。

考完后弦歌队刚飞机先遛了,留下我们和隔壁西电成员讨论题目解法,话说这次考这么惨4好伤心啊……败北航队dalao,%%众dalao,这次SJTU出的题目质量不错,但最后没有讲题差评。

晚上去了之前玩密室的万达,要么怎么说人家吉大地理位置好。接下来mg带我们队玩了一波街机厅,然后又去打了台球,中途去吃了日本寿司,mg点的太多结果又剩了一堆没吃完。晚上被mg带去网吧~~玩守望~~学习,话说网吧机子配置好好难怪mg经常去网吧。

Day4:

半夜本来想交Uber, 被mg说动走回酒店,结果走了0.5h发现南门校门锁了(bad end),没办法原路返回(0.5 h) ,结果实在受不了打车回去,打车地点离网吧不远sad story. 回到酒店,叫了pizza,结果左等右等pizza就是不来,mg由于手被冻僵了就先去睡了,我等着等着睡着了(最好3点半送到匹萨的时候我意识模糊的接了电话,让它放在楼下,话说直到最后我都没见到pizza)。

虽然和mg立志一定要吃到早餐,然而由于睡前实力忘了闹钟,结果睡到了中午12点5(mg表示中途起来叫我,我翻面继续睡,然后他也继续睡了……)。 为了弥补遗憾,我们一行人去了东北菜馆,点了一桌子菜,结果菜上来才发现是8个人的量,只好打包带走……

本来还打算试试电车,结果由于时间紧,又只好叫了Uber,就这样离开了长春还真是充满了遗憾呢……不过我还是先补完作业再说吧。

后记:主席又打算和妹子出去玩我就不写在正文里了。


  1. 长春当时的气温在7,8度左右 
  2. 结果好像都猜错了%%% 
  3. 正解是数位dp,统计2个数lcp中1的个数 
  4. 结果我们一个亿Ag,弦歌打铁(主席:我以后拒绝去这种5题不保铜的赛区)。 
  5. 本来计划好了去长春电影制片厂 

BZOJ 水题50乱做

[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]圆上的整点
数学题,求a2+b2=c2(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]硬币购物
我们先算出不考虑限制时的方案数fs,如果一个硬币超出限制,那么至少要使用di+1次,此时答案为fsci(di+1),我们可以用容斥定理解决问题
2298: [HAOI2011]problem a
考虑一个人的话:“有ai个人分数比我高,bi个人分数比我低”等价于“我的排名在[L,R]区间中,这个区间中人的成绩相同“,然后就可以变成线段覆盖问题,贪心即可。
4653: [Noi2016]区间
将区间按长度排序,枚举最长区间长度,显然最短区间长度满足单调性,只需要确认“m个区间共同包含至少一个位置”,用线段树维护最大值即可。
1192: [HNOI2006]鬼谷子的钱袋
k个钱袋最多能凑出2k1的所有钱数
1800: [Ahoi2009]fly 飞行棋
暴力。
1856: [Scoi2010]字符串
回顾卡特兰数的推导过程,发现ans=C(n+m,n)C(n+m,n+1)


1801: [Ahoi2009]chess 中国象棋
炮的攻击范围为,横行竖行,跳过一个棋子打一个,距离不限
故原题为求nm的矩阵中同行同列只能放至多2个炮的方案数
fi,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=ni=1nj=1Bi,jaiajni=1Ciai
我们把这转化为最大权闭合子图最小割
答案=所有点正权值之和-最小割
3875: [Ahoi2014]骑士游戏
令f_i为杀死i的最小代价,那么有fi=min(Ki,vfvi)
状态之前的转移有环,我们考虑《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]密码箱
x2=1modn等价于n|(x1)(x+1)然后暴力枚举因子就行
1038: [ZJOI2008]瞭望塔
半平面交,把分段点(包括边界)取出来
2618: [Cqoi2006]凸多边形
拆成一堆直线半平面交
4517: [Sdoi2016]排列计数
错排公式D(0)=1,D(1)=0,D(i)=(i1)(D(i1)+D(i2))
有个求一段阶乘的逆元的小技巧

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


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

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读错题),只有直接关系能看到信息
差分后得到,ansi=t2t1+t3t4+...+tntn1暴力维护