[USACO06DEC]牛的过山车Cow Roller Coaster

题目描述

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget.

The roller coaster will be built on a long linear stretch of land of length L (1 ≤ L ≤ 1,000). The roller coaster comprises a collection of some of the N (1 ≤ N ≤ 10,000) different interchangable components. Each component i has a fixed length Wi (1 ≤ Wi ≤ L). Due to varying terrain, each component i can be only built starting at location Xi (0 ≤ Xi ≤ L - Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component.

Each component i has a “fun rating” Fi (1 ≤ Fi ≤ 1,000,000) and a cost Ci (1 ≤ Ci ≤ 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows’ total budget is B (1 ≤ B ≤ 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

奶牛们正打算造一条过山车轨道．她们希望你帮忙，找出最有趣，但又符合预算的方案．过山车的轨道由若干钢轨首尾相连，由x=0处一直延伸到X=L(1≤L≤1000)处．现有N(1≤N≤10000)根钢轨，每根钢轨的起点 Xi(0≤Xi≤L- Wi)，长度wi(l≤Wi≤L)，有趣指数Fi(1≤Fi≤1000000)，成本Ci(l≤Ci≤1000)均己知．请确定一种最优方案，使得选用的钢轨的有趣指数之和最大，同时成本之和不超过B(1≤B≤1000)．

输入输出格式

输入格式：

Line 1: Three space-separated integers: L, N and B.

Lines 2..N+1: Line i+1 contains four space-separated integers, respectively: Xi, Wi, Fi, and Ci.

输出格式：

Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

输入输出样例

输入样例#1：

输出样例#1：

说明

Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.

题解

~~今天一觉睡到8点半，迷迷糊糊来到机房开了这道题随手写了个01背包结果华丽爆零~~

这道题的状态当然要带上位置（一看位置那么小就是dp的一维嘛）

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#define maxn 10005
#define maxm 1005
#define INF 0x3fffffff
int f[maxm][maxm] , n , l , m;
struct Node{
	int x , len , c , w;
	bool operator < (const Node& g)const{
		return x < g.x;
	}
}p[maxn];
std::vector<Node> q[maxm];
int main()
{
	scanf("%d%d%d",&l,&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d%d%d",&p[i].x,&p[i].len,&p[i].c,&p[i].w) , q[p[i].x + p[i].len].push_back(p[i]);
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= l ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			f[i][j] = -INF;
	f[0][0] = 0;
	for(int i = 1 ; i <= l ; ++i){
		for(int j = m ; j >= 1 ; --j)
			for(int k = 0 ; k < q[i].size() ; ++k){
				if(q[i][k].w > j)	continue;
				if(f[i-q[i][k].len][j-q[i][k].w] == -INF)	continue;
				f[i][j] = std::max(f[i][j] , f[i-q[i][k].len][j-q[i][k].w] + q[i][k].c);
			}
	}
	if(f[l][m] == -INF){
		puts("-1");return 0;
	}
	printf("%d\n",f[l][m]);
}

P2194 HXY烧情侣

题目描述

众所周知，HXY已经加入了FFF团。现在她要开始喜（sang）闻（xin）乐（bing）见（kuang）地烧情侣了。这里有n座电影院，n对情侣分别在每座电影院里，然后电影院里都有汽油，但是要使用它需要一定的费用。m条单向通道连接相邻的两对情侣所在电影院。然后HXY有个绝技，如果她能从一个点开始烧，最后回到这个点，那么烧这条回路上的情侣的费用只需要该点的汽油费即可。并且每对情侣只需烧一遍，电影院可以重复去。然后她想花尽可能少的费用烧掉所有的情侣。问最少需要多少费用，并且当费用最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对1e9+7取模的结果。

（注：这里HXY每次可以从任何一个点开始走回路。就是说一个回路走完了，下一个开始位置可以任选。所以说不存在烧不了所有情侣的情况，即使图不连通，HXY自行选择顶点进行烧情侣行动。且走过的道路可以重复走。）

输入输出格式

输入格式：

第一行，一个整数n。

第二行，n个整数，表示n个情侣所在点的汽油费。

第三行，一个整数m。

接下来m行，每行两个整数xi，yi，表示从点xi可以走到yi。

输出格式：

一行，两个整数，第一个数是最少费用，第二个数是最少费用时的方案数对1e9+7取模

输入输出样例

输入样例#1：

复制

输出样例#1：

复制

3 1

输入样例#2：

输出样例#2：

10 2

说明

数据范围：

对于30%的数据，1<=n，m<=20；

对于10%的数据，保证不存在回路。

对于100%的数据，1<=n<=100000，1<=m<=300000。所有输入数据保证不超过10^9。

题解

思考后不难发现每个scc的代价是最小值，方案数是所有scc的最小值的数目相乘。

一开始我还准备建新图dp，后来想了想转移方程发现就是相乘。。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#include <map>
#define mod 1000000007
#define maxn 100005
#define maxm 300005
int head[maxn] , cnt , tot[maxn] , idx , dfn[maxn] , low[maxn] , scct , scc[maxn] , v[maxn] , x, y , n , m , f[maxn] , g[maxn] , d[maxn];
long long ans1 , ans2 = 1 ;
bool ins[maxn];
std::map<int , bool> rep[maxn];
struct edge{
	int next , to;
}e[maxm*2];
struct Node{
	int fr , to;
}er[maxm*2];
inline void add(int x , int y){
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
	++d[y];
}
std::stack<int> st;
void Tarjan(int x)
{
	dfn[x] = low[x] = ++idx;
	st.push(x);
	ins[x] = true;
	for(int i = head[x] ; i ; i = e[i].next){
		if(!dfn[e[i].to]){
			Tarjan(e[i].to);
			low[x] = std::min(low[x] , low[e[i].to]);
		}
		else if(ins[e[i].to])	low[x] = std::min(low[x] , dfn[e[i].to]);
	}
	if(dfn[x] == low[x])
	{
		++scct;
		int minn = 0x7f7ffff , count = 1;
		while(st.top() != x)
		{
			if(v[st.top()] < minn){
				minn = v[st.top()];
				count = 1;
			}
			else if(v[st.top()] == minn){
				++count;
			}
			scc[st.top()] = scct;
			ins[st.top()] = false;
			st.pop();
		}
		
		//last element judge
		if(v[st.top()] < minn){
			minn = v[st.top()];
			count = 1;
		}
		else if(v[st.top()] == minn){
			++count;
		}
		scc[st.top()] = scct;
		ins[st.top()] = false;
		st.pop();
		
		//final update
		f[scct] = minn , g[scct] = count;
	}
}
int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n ; ++i)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	int mtr = 0;
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d%d",&x,&y) , add(x,y) , er[++mtr].fr = x , er[mtr].to = y;
	for(int i = 1 ; i <= n ; ++i){
		if(dfn[i])	continue;
		while(!st.empty())	st.pop();
		Tarjan(i);
	}
	for(int i = 1 ; i <= scct ; ++i)
		ans1 += f[i] , (ans2 *= g[i]) %= mod;
	printf("%lld %lld\n",ans1,ans2);
//	std::memset(e,0,sizeof(e));
//	std::memset(head,0,sizeof(head));
//	std::memset(d,0,sizeof(d));
//	cnt = 0;
//	for(int i = 1 ; i <= mtr ; ++i){
//		int u = er[i].fr , v = er[i].to;
//		if(!vis[scc[u]][scc[v]]){
//			add(scc[u] , scc[v]);
//			vis[scc[u]][scc[v]] = true;
//		}
//	}
	
}

NOIp 2016 D1T3 换教室

题目描述

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 2n2n 节课程安排在 nn 个时间段上。在第 ii（1 \leq i \leq n1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 c_ici 上课，而另一节课程在教室 d_idi 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 nn 节安排好的课程。如果学生想更换第 ii 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 ii 个时间段去教室 d_idi 上课，否则仍然在教室 c_ici 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 ii 节课程的教室时，申请被通过的概率是一个已知的实数 k_iki，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 mm 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 mm 门课程，也可以不用完这 mm 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 vv 个教室，有 ee 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 ii（1 \leq i \leq n-11≤i≤n−1）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

输入输出格式

输入格式：

第一行四个整数 n,m,v,en,m,v,e。nn 表示这个学期内的时间段的数量；mm 表示牛牛最多可以申请更换多少节课程的教室；vv 表示牛牛学校里教室的数量；ee表示牛牛的学校里道路的数量。

第二行 n 个正整数，第 i（1 \leq i \leq n1≤i≤n）个正整数表示 c_ici，即第 ii 个时间段牛牛被安排上课的教室；保证 1 \le c_i \le v1≤ci≤v。

第三行 n 个正整数，第 i（1 \leq i \leq n1≤i≤n）个正整数表示 d_idi，即第 ii 个时间段另一间上同样课程的教室；保证 1 \le d_i \le v1≤di≤v。

第四行 n 个实数，第 i（1 \leq i \leq n1≤i≤n）个实数表示 k_iki，即牛牛申请在第 ii 个时间段更换教室获得通过的概率。保证 0 \le k_i \le 10≤ki≤1。

接下来 e 行，每行三个正整数 a_j, b_j, w_j，表示有一条双向道路连接教室

$a_j, b_j$

，通过这条道路需要耗费的体力值是 w_jwj；保证

$1 \le a_j, b_j \le 300， 1 \le w_j \le 300$

保证

$1 \leq n \leq 2000，0 \leq m \leq 2000，1 \leq v \leq 300，0 \leq e \leq 90000$

保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。

保证输入的实数最多包含 33 位小数。

输出格式：

输出一行，包含一个实数，四舍五入精确到小数点后恰好22位，表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于

$4 \times 10^{-3}4×10−3$

。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

输入输出样例

输入样例#1：

3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5 
1 2 5
1 3 3
2 3 1

输出样例#1：

2.80

说明

【样例1说明】

所有可行的申请方案和期望收益如下表:

【提示】

道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同一间教室。
请注意区分n,m,v,e的意义, n不是教室的数量, m不是道路的数量。

特殊性质1:图上任意两点 a_iai, b_ibi, a_iai≠ b_ibi间,存在一条耗费体力最少的路径只包含一条道路。

特殊性质2:对于所有的 1≤ i≤ n1≤i≤n， k_i= 1ki=1 。

题解

是个很sb的概率期望dp

~~然而我一开始读错了题~~

状态设计：

$f(i,j,0/1)$

表示前i个课程申请了j次，当前申不申请。

转移傻逼组合合并期望，不写了（巨麻烦）

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 305
#define maxm 2005
#define INF 9999999
int n , m , p , enums , dis[maxn][maxn] , c[maxm] , d[maxm];
double k[maxm] , f[maxm][maxm][2];
int main(){
	scanf("%d%d%d%d",&n,&m,&p,&enums);
	std::memset(dis,0x3f,sizeof(dis));
	for(int i = 1 ; i <= n ; ++i)	
		scanf("%d",&c[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&d[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lf",&k[i]);
	int x , y , curd;
	for(int i = 1 ; i <= enums ; ++i)
		scanf("%d%d%d",&x,&y,&curd) , dis[x][y] = dis[y][x] = std::min(dis[x][y] , curd);
	for(int k = 1 ; k <= p ; ++k)
		for(int i = 1 ; i <= p ; ++i)
			for(int j = 1 ; j <= p ; ++j)
				dis[i][j] = std::min(dis[i][k] + dis[k][j] , dis[i][j]);
	for(int i = 1; i <= p ; ++i)
		dis[i][i] = 0;
	for(int i = 0 ; i <= n ; ++i)
		for(int j = 0 ; j <= m ; ++j)
			f[i][j][0] = f[i][j][1] = INF;
	f[1][1][1] = 0 , f[1][0][0] = 0;
	for(int i = 2 ; i <= n ; ++i){
		f[i][0][0] = f[i-1][0][0] + dis[c[i]][c[i-1]];
		for(int j = 1 ; j <= std::min(i,m); ++j){
			f[i][j][0] = std::min(f[i][j][0] , f[i-1][j][0] + dis[c[i]][c[i-1]]);
			f[i][j][0] = std::min(f[i][j][0] , f[i-1][j][1] + k[i-1] * dis[c[i]][d[i-1]] + (1-k[i-1]) * dis[c[i]][c[i-1]]);
			f[i][j][1] = std::min(f[i][j][1] , f[i-1][j-1][0] + k[i] * dis[d[i]][c[i-1]] + (1-k[i]) * dis[c[i]][c[i-1]]);
			f[i][j][1] = std::min(f[i][j][1] , f[i-1][j-1][1] + k[i]*k[i-1]*dis[d[i]][d[i-1]] + k[i]*(1-k[i-1])*dis[d[i]][c[i-1]] + (1-k[i])*k[i-1]*dis[c[i]][d[i-1]] + (1-k[i]) * (1-k[i-1]) * dis[c[i]][c[i-1]]);
		}
	}
	double ans = 9999999;
	for(int i = 0 ; i <= m ; ++i)		
		ans =  std::min(ans , std::min(f[n][i][0] , f[n][i][1]));
	printf("%.2lf",ans);
}

卢卡斯定理

${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},$

其中：

$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$

并且

$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$

是m和n的p进制展开。当m < n时，二项式系数

${\tbinom {m}{n}}=0$

时间复杂度应该是

$O(plogp)$

证明

对于素数p和n，满足1≤n≤p-1, 二项式系数

${\binom {p}{n}}={\frac {p\cdot (Images/4d54e3bb49e3cf69447eb3920cf7a95aacaf9c39-1540611932701.svg)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}$

可被p整除。由此可得，在母函数中

$(Images/90bb619431407faa7b1defbcede9e2a2e30541b3-1540612009000.svg)^{p}\equiv 1+X^{p}{\pmod {p}}.$

应用数学归纳法可证，对于任意非负整数i，有

$(Images/3d9a26921adfb3a7a705e577b2903d92cbb9ca23-1540612054863.svg)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.$

对于任意非负整数m和素数p，将m用p进制表示,注意到

${\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(Images/5c7f3b0d8c8aa2103fc847a7c311bb520f1fdc07-1540612121021.svg)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}$

证明好复杂。。

然后是Code：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long

LL n,m,Mod;

LL fast_pow(LL a,LL p)
{
    LL ans=1LL;
    for (;p;p>>=1,a=a*a%Mod)
        if (p&1)
            ans=ans*a%Mod;
    return ans;
}
LL inv(LL x)
{
    return fast_pow(x,Mod-2);
}
LL C(LL n,LL m)
{
    if (m>n) return 0LL;
    LL up=1LL,down=1LL;
    for (LL i=n-m+1;i<=n;++i) up=up*i%Mod;
    for (LL i=1;i<=m;++i) down=down*i%Mod;
    return up*inv(down)%Mod;
}
LL lucas(LL n,LL m)
{
    if (m>n) return 0LL;
    LL ans=1;
    for (;m;n/=Mod,m/=Mod)
        ans=ans*C(n%Mod,m%Mod)%Mod;
    return ans;
}
int main()
{
    while (~scanf("%lld%lld%lld",&n,&m,&Mod))
        printf("%lld\n",lucas(n-m+1,m));
}
--------------------- 
作者：Clove_unique

然后这个东西必须模数互质，和crt一样没用，所以我们有了

EXLUKAS

~~暂时没看懂，以后再说。~~

Cantor Expansion

是个很基础的东西了。

展开公式

$X=a_{n}(Images/e9b98a7afd5ee43a1c3649845dac9daa1634e71e-1540620549557.svg)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!$

一个n^2的计算过程，看上去没什么卵用。

如n=5,x=96时：

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)
用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.
用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.
用5去除2!得到2余1，类似地，这一位是3.
用1去除1!得到1余0，这一位是2.
最后一位只能是1.
所以这个数是45321.

逆运算也没了，就这样。

[USACO11FEB]牛线Cow Line

题目背景

征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

题目描述

The N (1 <= N <= 20) cows conveniently numbered 1…N are playing yet another one of their crazy games with Farmer John. The cows will arrange themselves in a line and ask Farmer John what their line number is. In return, Farmer John can give them a line number and the cows must rearrange themselves into that line.

A line number is assigned by numbering all the permutations of the line in lexicographic order.

Consider this example:

Farmer John has 5 cows and gives them the line number of 3.

The permutations of the line in ascending lexicographic order: 1st: 1 2 3 4 5

2nd: 1 2 3 5 4

3rd: 1 2 4 3 5

Therefore, the cows will line themselves in the cow line 1 2 4 3 5.

The cows, in return, line themselves in the configuration ‘1 2 5 3 4’ and ask Farmer John what their line number is.

Continuing with the list:

4th : 1 2 4 5 3

5th : 1 2 5 3 4

Farmer John can see the answer here is 5

Farmer John and the cows would like your help to play their game. They have K (1 <= K <= 10,000) queries that they need help with. Query i has two parts: C_i will be the command, which is either ‘P’ or ‘Q’.

If C_i is ‘P’, then the second part of the query will be one integer A_i (1 <= A_i <= N!), which is a line number. This is Farmer John challenging the cows to line up in the correct cow line.

If C_i is ‘Q’, then the second part of the query will be N distinct integers B_ij (1 <= B_ij <= N). This will denote a cow line. These are the cows challenging Farmer John to find their line number.

N(1<=N<=20)头牛，编号为1…N，正在与FJ玩一个疯狂的游戏。奶牛会排成一行（牛线），问FJ此时的行号是多少。之后，FJ会给牛一个行号，牛必须按照新行号排列成线。

行号是通过以字典序对行的所有排列进行编号来分配的。比如说：FJ有5头牛，让他们排为行号3，排列顺序为：

1：1 2 3 4 5

2：1 2 3 5 4

3：1 2 4 3 5

因此，牛将在牛线1 2 4 3 5中。

之后，奶牛排列为“1 2 5 3 4”，并向FJ问他们的行号。继续列表：

4：1 2 4 5 3

5：1 2 5 3 4

FJ可以看到这里的答案是5。

FJ和奶牛希望你的帮助玩他们的游戏。他们需要K(1<=K<=10000)组查询，查询有两个部分：C_i将是“P”或“Q”的命令。

如果C_i是’P’，则查询的第二部分将是一个整数A_i（1 <= A_i <= N！），它是行号。此时，你需要回答正确的牛线。

如果C_i是“Q”，则查询的第二部分将是N个不同的整数B_ij（1 <= B_ij <= N）。这将表示一条牛线，此时你需要输出正确的行号。

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and K

* Lines 2..2K+1: Line 2i and 2*i+1 will contain a single query.

Line 2*i will contain just one character: ‘Q’ if the cows are lining up and asking Farmer John for their line number or ‘P’ if Farmer John gives the cows a line number.

If the line 2i is ‘Q’, then line 2i+1 will contain N space-separated integers B_ij which represent the cow line. If the line 2i is ‘P’, then line 2i+1 will contain a single integer A_i which is the line number to solve for.

输出格式：

* Lines 1..K: Line i will contain the answer to query i.

If line 2i of the input was ‘Q’, then this line will contain a single integer, which is the line number of the cow line in line 2i+1.

If line 2i of the input was ‘P’, then this line will contain N space separated integers giving the cow line of the number in line 2i+1.

输入输出样例

输入样例#1：

输出样例#1：

1 2	1 2 4 3 5 5

说明

题解

cantor展开的模板题。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 21
long long n , q , x , qr[maxn];
bool vis[maxn];
char ch;
inline long long fac(long long x)
{
	long long ans = 1;
	for(int i = 1 ; i <= x ; ++i)
		ans *= i;
	return ans ;
}
inline void cantor(long long x){
	--x;
	std::memset(vis,false,sizeof(vis));
	for(int i = 1 ; i <= n ; ++i){
		int cur = x / fac(n-i) , j;
		for(j = 1 ; j <= n; ++j){
			if(!vis[j]){
				if(!cur)	break;
				--cur;
			}
		}
		vis[j] = true;
		printf("%d ",j);
		x %= fac(n-i);
	}

	putchar(10);
}
inline long long revcantor()
{
	long long ans = 0;
	for(int i = 1 ; i <= n ; ++i){
		int rank = 0;
		for(int j = i + 1 ; j <= n ; ++j){
			if(qr[i] > qr[j]) ++rank;
		}
		ans += 1ll * fac(1ll*(n-i)) * rank;
	}
	return ans + 1;
	
}
int main()
{
	scanf("%lld%lld",&n,&q);
	for(int i = 1 ; i <= q ; ++i)
	{
		std::cin>>ch;
		if(ch == 'P'){
			scanf("%lld",&x);
			cantor(x);
		}else{
			for(int j = 1 ; j <= n ; ++j)
				scanf("%lld",&qr[j]);
			std::cout << revcantor() << std::endl;
		}
	}
}

[USACO11OPEN]学习语言Learning Languages

题目描述

Farmer John’s N (2 <= N <= 10,000) cows, conveniently numbered 1..N, are fluent in some M (1 <= M <= 30,000) languages, also conveniently numbered from 1..M. Cow i can speak in K_i (1 <= K_i <= M) languages, namely L_i1, L_i2,…, L_{iK_i} (1 <= L_ij <= M). FJ’s cows aren’t THAT smart, so the sum of K_i over all cows i is at most 100,000.

Two cows can’t directly talk to each other unless both speak a common language. However, cows can pass messages along, translating if necessary. In other words, cows A and B can have a conversation if and only if there exists a sequence of cows T_1, T_2, …, T_k such that A and T_1 share a language, T_1 and T_2 share a language, etc., and T_k and B share a language.

Farmer John wishes that his cows could be even more social, so he wants all his cows to be able to socialize with any other cow. He can buy books to teach any one of his cows any language he pleases. Being a fairly frugal farmer, FJ wants to purchase the minimum number of books necessary to enable all of his cows to speak to each other. Help him determine:

* The minimum number of books he must purchase

* Any set of books assigned to cows in any order which will help him meet this goal; a program will grade your output.

By way of example, suppose there are three cows named Alberta, Bessie, and Contessa along with three languages denoted as #1, #2, and #3. Alberta can speak languages #2 and #3, Bessie can speak language #2, and Contessa can speak language #1. Currently, Alberta and Bessie can talk to each other, but Contessa is left alone.

1 #2 #3

Alberta x x

Bessie x

Contessa x

FJ wants to fix this situation, so he can buy Contessa a book to teach her language #2. This will ensure all cows speak the same language, so they can all communicate with one another.

Note that an alternate solution exists: instead, FJ could buy

Contessa a book to teach her language #3. Not all cows would speak the same language, but this would still be a valid solution because Contessa could communicate through Alberta (who also speaks language #3) if she wants to talk to Bessie. Other alternatives exist, and any valid alternate solution will also be accepted.

农夫约翰的N（2<=N<=10,000）只奶牛标号为1..N，同样的有M（1<=M<=30,000）种牛语标号为1..M，第i只奶牛会说K_i（1<=K_i<=M）种牛语，分别为L_i1，L_i2，…，L_{iK_i}（1<=L_ij<=M），农夫的奶牛不是特别聪明，所以K_i的累加和不大于100,000。

两只奶牛只有当他们至少有一门语言一样的时候才可以沟通。否则这两只奶牛就需要别人来帮他们翻译才能交流。换句话说，A和B要进行沟通，他们可以通过T_1，T_2，…，T_k来传递，比如A和T_1，T_1和T_2，…，T_k和B进行交流。

农夫希望他的奶牛可以多多沟通，所以他买了很多课本去教她的奶牛语言。当然农夫非常的吝啬，他希望买最少的书就可以让所有的奶牛可以交流。你的任务就是帮他算出最少需要买几本书。

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes the languages that cow i can speak with (K_i)+1 space-separated integers: K_i, L_i1,

L_i2,…,L_i{K_i}.

输出格式：

* Line 1: A single integer that is the minimum number of books that FJ must purchase.

* Lines 2..B+1: Line i+1 contains two space-separated integers: the language id # and the id # of the cow to receive book i. If multiple solutions exist, print any one.

输入输出样例

输入样例#1：

输出样例#1：

1
2

1 
2 3

题解

一道很不错的并查集的题。

我们把没头奶牛合并到每种语言，同一个集合内的奶牛就能互相交流=并查集。

注意不要把并查集写疵了。

Code：

1
2

P1868 饥饿的奶牛

题目描述

有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。

现用汉语翻译为：

有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。

输入输出格式

输入格式：

第一行，N，如题

接下来N行，每行一个数x，y，如题

输出格式：

一个数，最多能吃到的牧草堆数

输入输出样例

输入样例#1：

输出样例#1：

说明

1<=n<=150000

0<=x<=y<=3000000

题解

这个题以前我写过

$O(n^2)$

的dp。

那个题我是直接找当前区间前的和本区间不相交的最大f值。

但是这道题显然不能这么做了。

然后我们可以按照右端点排序，然后在当前区间我们二分一个右端点小于当前区间左端点的最大的f值。

但是假如状态设计为以第i个区间结尾的最优值不能保证二分的状态值最大。

所以我们每次继承上一次的状态值就保证单调不降了，状态的含义应该修改成以前i个区间结尾的最大答案。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
struct Node{
	int l , r , val;
	bool operator < (const Node& x)const {
		return r < x.r;
	}
}p[maxn];
int n , f[maxn] , ans;
int find(int x)
{
	int l = 0 , r = n , ans = 0;
	while(l <= r){
		int mid = l + r >> 1;
		if(p[mid].r < x)	ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d%d",&p[i].l,&p[i].r) , p[i].val = p[i].r - p[i].l + 1;
	std::sort(p+1,p+n+1);
	for(int i = 1 ; i <= n ; ++i){
		f[i] = f[i-1];
		int j = find(p[i].l);
		f[i] = std::max(f[i] , f[j] + p[i].val);
	}
	for(int i = 1 ; i <= n ; ++i)
		ans = std::max(ans , f[i]);
	printf("%d",ans);
}

[USACO06NOV]糟糕的一天Bad Hair Day

题意翻译

农夫约翰有N (N \leq 80000)N(N≤80000)头奶牛正在过乱头发节。每一头牛都站在同一排面朝东方，而且每一头牛的身高为h_ihi。第NN头牛在最前面，而第11头牛在最后面。对于第ii头牛前面的第jj头牛，如果h_i>h_{i+1}hi>hi+1并且h_i>h_{i+2}hi>hi+2 \cdots⋯ h_i>h_jhi>hj，那么认为第ii头牛可以看到第i+1i+1到第jj头牛

定义C_iCi为第ii头牛所能看到的别的牛的头发的数量。请帮助农夫约翰求出\sum_{i=1}^n C_i∑i=1nCi

题目描述

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

= =

= - = Cows facing right —>

= = =

= - = = =

= = = = = =

1 2 3 4 5 6 Cow#1 can see the hairstyle of cows #2, 3, 4

Cow#2 can see no cow’s hairstyle

Cow#3 can see the hairstyle of cow #4

Cow#4 can see no cow’s hairstyle

Cow#5 can see the hairstyle of cow 6

Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

输入输出格式

输入格式：

Line 1: The number of cows, N.

Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

输出格式：

Line 1: A single integer that is the sum of c1 through cN.

输入输出样例

输入样例#1：

输出样例#1：

题解

单调栈一眼题（这就是交上去WA了3次结果看题解发现少了等号的理由吗？）

最开始WA是因为用各种奇怪的姿势统计答案错了，之后发现等号没弹栈结果多统计了。。

思路很简单：我们只需要知道每头牛从自己最远能看到哪，而且是连续的，然后也不必知道具体每头牛，考虑对答案的贡献就行了。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#define maxn 80005
int n , h[maxn];
long long tot , ans;
struct Node{
	int v , k;
	bool operator < (const Node& x)const{
		return v < x.v;
	}
}p[maxn];
std::stack<int> st;
int main(){
	scanf("%d",&n);
	for(int i = 1 ; i <= n ;++i)
		scanf("%d",&h[i]);
	for(int i = 1 ; i <= n ; ++i)
	{
		int k = 0;
		while(!st.empty() && h[st.top()] <= h[i]){
			++k;
			st.pop();
		}
		ans += st.size();
		st.push(i);
	}
	tot += st.size();
	printf("%lld",ans);
}

[COI2007] Patrik 音乐会的等待

题目描述

N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

输入输出格式

输入格式：

输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。

接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。

输出格式：

输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。

输入输出样例

输入样例#1：

输出样例#1：

题解

上一题的加强版，做了半天。。

这题要多考虑不少情况，主要是可以相等导致的

其中最坑的一种情况是来几个一样的来个小的再来个一样的然后来个大的，能考虑到这种情况就AC了。

所以我们栈中每个元素同时要维护多少个相等的，不必连续

原因是假设来了一个大的，它可以把所有和这个相等的都加上而不重复计数

总之是个很坑的细节题，得考虑周全。

Code：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#define maxn 500005
#define pii std::pair<int,int>
#define mp(x,y) std::make_pair((x),(y))
int n , h[maxn];
long long tot , ans;
std::stack<pii> st;
int main(){
	scanf("%d",&n);
	for(int i = 1 ; i <= n ;++i)
		scanf("%d",&h[i]);
	for(int i = 1 ; i <= n ; ++i)
	{
		pii p(h[i],1);
		for( ; !st.empty() && st.top().first <= h[i] ; st.pop()){
			ans += st.top().second;
			if(st.top().first == h[i])	p.second += st.top().second;
		}
		if(!st.empty()) ++ans;
		st.push(p);
	}
	printf("%lld",ans);
}

[HEOI2014]南园满地堆轻絮

题目描述

小 Z 是 ZRP（Zombies’ Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近他研究起了诗词音律的问题。

在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应的音符就是这样的：

1 2	南园满地堆轻絮，愁闻一霎清明雨 1 1 5 5 6 6 5 4 4 3 3 2 2 1

因而可以发现，1 1 5 5 6 6 5 4 4 3 3 2 2 1这串音符就成为了研究音律的关键。

小 Z 翻阅了众多史料发现，过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，将它的音调修改的不下降，而且使得修改幅度最大的那个音符的修改幅度尽量小。即如果把一个包含 nn 个音符的曲子看做是一个正整数数列 A[1] \cdots A[n]A[1]⋯A[n]，那么目标是求另一个正整数数列 B[1]…B[n]B[1]…B[n]，使得对于任意的 1≤i<n1≤i<n 有 B[i] ≤B[i+1]B[i]≤B[i+1]，而且使得 Ans = Max\{|A[j]-B[j]|,1≤j≤n\}Ans=Max{∣A[j]−B[j]∣,1≤j≤n}尽量小。小 Z 很快就想清楚了做法，但是鉴于他还忙着写诗，所以这个任务就交给了你。

输入输出格式

输入格式：

由于数据规模可能较大，因此采用如下方式生成数据。

每个数据包含 7 个数：n,S_a,S_b,S_c,S_d,A[1],Modn,Sa,Sb,Sc,Sd,A[1],Mod，即共有 n 个音符，第一个音符为 A[1]。

生成规则如下：定义生成函数 F(x) = S_ax^3 + S_bx^2 + S_c*x + S_dF(x)=Sa∗x3+Sb∗x2+Sc∗x+Sd; 那么给出递推公式 A[i] =( F(A[i-1]) + F(A[i-2]) )\%modA[i]=(F(A[i−1])+F(A[i−2]))%mod，此处规定 A[0] = 0A[0]=0. 由于中间过程的数可能会特别大，所以要求每一步与 AA 中的每个数都对一个给定的数 ModMod 取模。

输出格式：

输出一行，包含一个正整数 AnsAns。

输入输出样例

输入样例#1：

复制

1	3 815 6901 3839 178 199 10007

输出样例#1：

复制

说明

【数据范围】

对于 10% 的数据， n≤3n≤3

对于 20% 的数据, n≤10n≤10

对于 30% 的数据, n≤100n≤100

对于 50% 的数据, n≤1000n≤1000

对于 70% 的数据, n≤100000n≤100000

对于 100% 的数据,#include

【友情提示】

样例中生成的数列为： 199 4568 1901，此时将 4568 修改为 3234,1901 也修改为 3234 即可，代价为 1334。

题解

其实是一道比较简单的贪心了。

假如序列是上升的，显然不用调整。

假如来了一个下降的，那么和它之前最大的一起调整到两者的平均值，由于序列单调不降其他值调整的标准都小于它。调整到平均值显然是一个调整幅度最大中的最小，注意向上取整这种边界问题。

Code:

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
#define max(a,b) (a) > (b) ? (a) : (b)
ll n , a , b , c , d , cur , A1 , A2 , A3 , mod , ans;
inline ll F(ll x)
{
    ll c1 = 0 , c2 = 0 , c3 = 0 , g = x * x % mod;
    c1 = a * x % mod * g % mod;
    c2 = b * g % mod;
    c3 = c * x % mod;
    return (c1 + c2 + c3 + d) % mod;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&A2,&mod);
    ll maxx = A2;
    for(register int i = 2 ; i <= n ; ++i){
        A3 = (F(A2) + F(A1))% mod;
        if(A3 < 0) A3 += mod;
        maxx = max(maxx , A3);
        ans = max(ans , (maxx - A3 + 1) / 2);
        A1 = A2 , A2 = A3;
    }
    printf("%lld\n",ans);
}