CF 237E(字母选取-费用流)

题目大意:有一字符串S,你需要从n个字符串中选取一些来拼出这个串,第i个字符串代价为i,限制取P次,问最小代价(无解输出-1)

建立超源S=0,超汇T=n+26+1 

1-n的结点为字符串 n+1-n+26的结点为字符

则可得——————————————————

从S向字符串连(最多可取数量),费用为i

从字符向T连(欲取数量)

从字符串向字符连(字符串可取该字母的数量)

得到图

跑费用……

!负数的布尔值为1.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (200+10)
#define M26 100
#define A 96
#define NONE (2139062143)
int map[MAXN][MAXN]={0},cost[MAXN][MAXN]={0},stf[M26]={0};
int start=0,end,n;
char s[5000];

int d[MAXN],pre[MAXN],q[MAXN*8];
bool b[MAXN];
void spfa()
{
	memset(b,0,sizeof(b));
	memset(d,127,sizeof(d));
	memset(q,0,sizeof(q));
	memset(pre,0,sizeof(pre));

	int head=1,tail=1;
	q[1]=start;b[start]=1;d[start]=0;
	while (head<=tail)
	{
		int now=q[head];
		for (int i=0;i<=end;i++)
		if (map[now][i]>0&&d[now]+cost[now][i]<d[i])
		{
			d[i]=d[now]+cost[now][i];
			pre[i]=now;
			if (!b[i])
			{
				q[++tail]=i;
				b[i]=1;
			}

		}

		b[now]=0;
		head++;
	}



}
void hllp()
{
	int totalcost=0;
	while (1)
	{
		spfa();
		if (d[end]==NONE) break;
		int flow=NONE,i=end;
		do
		{
			flow=min(flow,map[pre[i]][i]);
			i=pre[i];
		}while (i!=start);
		i=end;
		do
		{
			totalcost+=flow*cost[pre[i]][i];
			map[pre[i]][i]-=flow;
			map[i][pre[i]]+=flow;
			i=pre[i];
		}while (i!=start);

	}
	for (int i=end-27;i<end;i++)
	if (map[i][end])
	{
		cout<<"-1n";
		return;

	}
	cout<<totalcost<<endl;
}



int main()
{
//	freopen("c.in","r",stdin);
	scanf("%s",s);
	scanf("%d",&n);
	int len=strlen(s);
	for (int i=0;i<len;i++) stf[s[i]-A]++;
	end=n+27;
	for (int i=1;i<=26;i++) map[n+i][end]=stf[i];
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s);
		scanf("%d",&map[start][i]);
		memset(stf,0,sizeof(stf));
		for (int j=0;j<strlen(s);j++) stf[s[j]-A]++;
		for (int j=1;j<=26;j++) map[i][n+j]=stf[j];
		cost[0][i]=i;
		cost[i][0]=-cost[0][i];
	}
/*	for (int i=0;i<=end;i++)
		for (int j=0;j<=end;j++)
			if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/	hllp();
	cout<<'n';
/*	for (int i=0;i<=end;i++)
		for (int j=0;j<=end;j++)
			if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/
	return 0;
}

调色盘 (3维k点最小最远点对-容斥原理)

调色盘(pastele)

题目描述

Albus得到了一份礼物:来自Polaris的水彩油墨包。

Polaris的油墨包里面有N个颜色,现在Albus打算选其中的K种来作一幅风景画。

既然是风景画,颜色就不能太突兀。因此Albus进行了如下的定义:

每个颜色由三个属性刻画:R[i],G[i],B[i]。

两个颜色的“距离”指它们三个属性的最大差值,也就是Max(|Ri-Rj|,|Gi-Gj|,|Bi-Bj|)。

而K个颜色的距离,指的是其中任意两个颜色的最大距离。

你的任务是求出可能的最小距离。

 

输入

第一行两个整数N和K。

接下来N行,每行三个整数R[i],G[i],B[i]。

输出

可能的最小距离。

 

样例输入

5 3

6 6 4

6 2 7

3 1 3

4 1 5

6 2 6

样例输出

2

解释

选1,4,5三个颜色。

数据范围

对于10%的数据,N<=10

对于50%的数据,0<=Ri,Gi,Bi<=20,2<=K<=N<=100

对于80%的数据,0<=Ri,Gi,Bi<=50,2<=K<=N<=10000

对于100%的数据,2<=K<=N<=100000,0<=Ri,Gi,Bi<=150

a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

容斥原理

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (150+10)
#define MAXX (151)
int n,k,a[MAXN][MAXN][MAXN]={0},c[MAXN][MAXN][MAXN]={0};
int Node_count(int x,int y,int z,int l)
{
	if (z-l<0||y-l<0||z-l<0) return 0;
	return c[x][y][z]+c[x-l][y-l][z]+c[x][y-l][z-l]+c[x-l][y][z-l]-c[x-l][y][z]-c[x][y-l][z]-c[x][y][z-l]-c[x-l][y-l][z-l];

}
int main()
{
	freopen("pastele.in","r",stdin);
	freopen("pastele.out","w",stdout);

	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x+1][y+1][z+1]++;
	}


	/*
		a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
		c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

	*/

	for (int x=1;x<=MAXX;x++)
		for (int y=1;y<=MAXX;y++)
			for (int z=1;z<=MAXX;z++)
				c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

	/*
	for (int i=1;i<=10;i++)
	for (int j=1;j<=10;j++)
	for (int k=1;k<=10;k++)
		if (c[i][j][k]) cout<<i<<' '<<j<<' '<<k<<' '<<c[i][j][k]<<endl;
	cout<<Node_count(6,6,6,6);
	*/

	int ans=MAXX;//成立 区间  (0 ,MAXX]
	for (int x=MAXX;x>=1;x--)
		for (int y=MAXX;y>=1;y--)
			for (int z=MAXX;z>=1;z--)
			{
				if (ans&&k<=Node_count(x,y,z,ans)) ans--;
			}
	cout<<ans<<endl;


//	while (1);
	return 0;
}

翻转排序 (sort)

翻转排序(sort)

题目描述

Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作,是翻转排列的某一段。思考很久之后,他决定用以下方式让这个排列有序:

 

1 找到每一个极大的下降子序列(子序列要求连续)

2 对于每个长度大于1的极大下降子序列,对它进行翻转

3 如果排列依然不是有序的,转1

 

我们举一个例子:初始排列是(5 3 1 4 2)

一开始极大的下降子序列是(5 3 1)(4 2)

把这些序列翻转后得到1 3 5 2 4

接下来的极大下降子序列是(1)(3)(5 2)(4)

翻转后是13 2 5 4

接下来的极大下降子序列是(1)(3 2)(5 4)

翻转后是12 3 4 5,满足要求

 

定义翻转一个子序列的费用为1(注意一轮翻转的费用可能大于1),那么上面的费用一共是2+1+2=5。

 

现在,给你一个排列,你要求出对这个排列排序的费用。

另外题目保证:第一次划分时,所有极大下降子序列的长度都是偶数

输入

第一行一个整数N

第二行表示N个数的排列

输出

所需费用。如果不能排序,输出-1

 

样例输入

4

3 1 4 2

样例输出

3

数据范围

对于10%的数据,N<=10

对于40%的数据,N<=3000

对于100%的数据,N<=100000

可以证明一定能排序,否则一定能进行交换。

由于,第一次划分时,所有极大下降子序列的长度都是偶数,没有单个点,故之后的解尽可能在递增序列接口,长度不超过2

(6 5) (2 1) (4 3)

 5 (6--1 ) 2--3 4 

如果有单个点

(7 6 1) 4 (5 3 2)

 1 6 (7 4 2) 3 5

并且第一轮翻转之后不会有长度>=3的极长下降子序列

于是问题变成了求逆序对的个数,归并排序或者树状数组解决

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define INF (0xfffffff)
int n,a[MAXN];
long long ans=0;
int le[MAXN],re[MAXN];
int len(int l,int r)
{
	return r-l+1;
}
void mergesort(int l,int r)
{
	if (l>=r) return;
	int m=(l+r)>>1;
	mergesort(l,m);
	mergesort(m+1,r);
	memcpy(le+1,a+l,sizeof(int)*(m-l+1));
	memcpy(re+1,a+m+1,sizeof(int)*(r-m));
	le[m-l+2]=re[r-m+1]=INF;
	int i=1,j=1;
	for (int k=l;k<=r;k++)
		if (le[i]<re[j])
		{
			a[k]=le[i];
			i++;
		}
		else
		{
			a[k]=re[j];
			j++;
			ans+=m-l+1-(i-1);
		}
}
int main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int h=1;
	for (int i=1;i<n;i++)
	{
		if (a[i]<a[i+1])
		{
			if (h!=i)
			{
				ans++;
				for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2  ) ],a[(i+h)/2+j]);
//				for (int k=1;k<=n;k++) cout<<a[k]<<' ';
//				cout<<endl;
			}
			h=i+1;
		}
	}
	if (h!=n)
	{
		ans++;
		int i=n;
		for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2  ) ],a[(i+h)/2+j]);
//		for (int k=1;k<=n;k++) cout<<a[k]<<' ';
//		cout<<endl;
	}

	mergesort(1,n);


	cout<<ans<<endl;
//	while (1);
	return 0;
}

运算符重载

什么是运算符的重载?

         运算符与类结合,产生新的含义。 

为什么要引入运算符重载?

         作用:为了实现类的多态性(多态是指一个函数名有多种含义)

怎么实现运算符的重载?

方式:类的成员函数 或 友元函数(类外的普通函数)

规则:不能重载的运算符有 .  和 .* 和 ?: 和 ::  和 sizeof

友元函数和成员函数的使用场合:一般情况下,建议一元运算符使用成员函数,二元运算符使用友元函数

        1、运算符的操作需要修改类对象的状态,则使用成员函数。如需要做左值操作数的运算符(如=,+=,++)

        2、运算时,有数和对象的混合运算时,必须使用友元

        3、二元运算符中,第一个操作数为非对象时,必须使用友元函数。如输入输出运算符<<和>>

具体规则如下:

运算符

建议使用

所有一元运算符

成员函数

= ( ) [ ]  ->

必须是成员函数

+= -= /= *= ^= &= != %= >>= <<= , 似乎带等号的都在这里了.

成员函数

所有其它二元运算符, 例如: –,+,*,/

友元函数

<< >>

必须是友元函数

2. 参数和返回值

     当参数不会被改变,一般按const引用来传递(若是使用成员函数重载,函数也为const).

     对于返回数值的决定:

     1) 如果返回值可能出现在=号左边, 则只能作为左值, 返回非const引用。

     2) 如果返回值只能出现在=号右边, 则只需作为右值, 返回const型引用或者const型值。

     3) 如果返回值既可能出现在=号左边或者右边, 则其返回值须作为左值, 返回非const引用。

运算符重载举例:

+和 -运算符的重载:

  1. class Point    
  2. {    
  3. private:    
  4.     int x;   
  5. public:    
  6.     Point(int x1)  
  7.     {   x=x1;}    
  8.     Point(Point& p)     
  9.     {   x=p.x;}  
  10.     const Point operator+(const Point& p);//使用成员函数重载加号运算符  
  11.     friend const Point operator-(const Point& p1,const Point& p2);//使用友元函数重载减号运算符  
  12. };    
  13.   
  14. const Point Point::operator+(const Point& p)  
  15. {  
  16.     return Point(x+p.x);  
  17. }  
  18.   
  19. Point const operator-(const Point& p1,const Point& p2)  
  20. {  
  21.     return Point(p1.x-p2.x);  
  22. }  

调用:

  1. Point a(1);    
  2. Point b(2);  
  3. a+b;  //正确,调用成员函数  
  4. a-b;  //正确,调用友元函数  
  5. a+1;  //正确,先调用类型转换函数,把1变成对象,之后调用成员函数  
  6. a-1;  //正确,先调用类型转换函数,把1变成对象,之后调用友元函数  
  7. 1+a;  //错误,调用成员函数时,第一个操作数必须是对象,因为第一个操作数还有调用成员函数的功能  
  8. 1-a;  //正确,先类型转换 后调用友元函数  

总结:

1、由于+ -都是出现在=号的右边,如c=a+b,即会返回一个右值,可以返回const型值
2、后几个表达式讨论的就是,数和对象混合运算符的情况,一般出现这种情况,常使用友元函数

3、双目运算符的重载:

      重载运算符函数名:operator@(参数表)

      隐式调用形式:obj1+obj2

      显式调用形式:obj1.operator+(OBJ obj2)---成员函数

                                  operator+(OBJ obj1,OBJ obj2)---友元函数

      执行时,隐式调用形式和显式调用形式都会调用函数operator+()

++和--运算符的重载:

  1. class Point    
  2. {    
  3. private:    
  4.     int x;   
  5. public:    
  6.     Point(int x1)  
  7.     {   x=x1;}    
  8.     Point operator++();//成员函数定义自增  
  9.     const Point operator++(int x); //后缀可以返回一个const类型的值  
  10.     friend Point operator--(Point& p);//友元函数定义--  
  11.     friend const Point operator--(Point& p,int x);//后缀可以返回一个const类型的值  
  12. };    
  13.   
  14. Point Point::operator++()//++obj  
  15. {  
  16.     x++;  
  17.     return *this;  
  18. }  
  19. const Point Point::operator++(int x)//obj++  
  20. {  
  21.     Point temp = *this;  
  22.     this->x++;  
  23.     return temp;  
  24. }  
  25. Point operator--(Point& p)//--obj  
  26. {  
  27.     p.x--;  
  28.     return p;  
  29.          //前缀形式(--obj)重载的时候没有虚参,通过引用返回*this 或 自身引用,也就是返回变化之后的数值  
  30. }  
  31. const Point operator--(Point& p,int x)//obj--  
  32. {  
  33.     Point temp = p;  
  34.     p.x--;  
  35.     return temp;  
  36.          // 后缀形式obj--重载的时候有一个int类型的虚参, 返回原状态的拷贝  
  37. }  

函数调用:

  1. <pre class="cpp" name="code">Point a(1);  
  2. Point b(2);  
  3. a++;//隐式调用成员函数operator++(0),后缀表达式  
  4. ++a;//隐式调用成员函数operator++(),前缀表达式  
  5. b--;//隐式调用友元函数operator--(0),后缀表达式  
  6. --b;//隐式调用友元函数operator--(),前缀表达式  
  7. cout<<a.operator ++(2);//显式调用成员函数operator ++(2),后缀表达式  
  8. cout<<a.operator ++();//显式调用成员函数operator ++(),前缀表达式  
  9. cout<<operator --(b,2);//显式调用友元函数operator --(2),后缀表达式  
  10. cout<<operator --(b);//显式调用友元函数operator --(),前缀表达式 </pre>  

 总结:

1、a++

       函数返回:temp(临时变量)

       函数返回是否是const类型:返回是一个拷贝后的临时变量),不能出现在等号的左边(临时变量不能做左值),函数的结果只能做右值,则要返回一个const类型的值

      ++a

       函数返回:*this;

      函数返回是否是const类型:返回原状态的本身,返回值可以做左值,即函数的结果可以做左值,则要返回一个非const类型的值

2、前后缀仅从函数名(operator++)无法区分,只能有参数区分,这里引入一个虚参数int x,x可以是任意整数。

3、单目运算符的重载:

      重载运算符函数名:operator@(参数表)

      隐式调用形式:obj1@  或 @obj1

      显式调用形式:

             成员函数:

                    obj1.operator@( )//前缀

                    obj1.operator@(0)//后缀

             友元函数:

                    operator@(OBJ obj)//前缀

                    operator@(OBJ obj,int x)//后缀

      执行时,隐式调用形式和显式调用形式都会调用函数operator@()

 重载下标运算符[ ]

  1. class Point    
  2. {    
  3. private:    
  4.     int x[5];   
  5. public:    
  6.     Point()  
  7.     {  
  8.         for (int i=0;i<5;i++)  
  9.         {  
  10.             x[i]=i;  
  11.         }  
  12.     }   
  13.     int& operator[](int y);  
  14. };    
  15. int& Point::operator[](int y)  
  16. {  
  17.     static int t=0;  
  18.     if (y<5)  
  19.     {  
  20.         return x[y];  
  21.     }  
  22.     else  
  23.     {  
  24.         cout<<"下标出界";  
  25.         return t;  
  26.     }     
  27. }  

调用:

  1. Point a;  
  2. for (int i=0;i<10;i++)  
  3. {  
  4.          cout<<a[i]<<endl;//无论i下标是否越界,每当使用a[i]时,都会调用[]的重载  
  5. }  
  6. a[0]=10;  

重载下标运算符[ ]的目的:

          1、对象[x]  类似于 数组名[x],更加符合习惯

          2、可以对下标越界作出判断

语法:

        重载方式:只能使用成员函数重载

        函数名:operator[ ](参数表)

        参数表:一个参数,且仅有一个参数,该参数设定了下标值,通常为整型,但是也可以为字符串( 看成下标)。

        函数调用:显式调用:Obj[arg]-对象[下标]

                              隐式调用:obj.operator[ ](arg)  

        返回类型:

               1、返回函数引用 + 返回成员的实际类型(由程序员根据函数体定义)

               2、因为返回值可以做左值和右值,应该不使用返回值为const类型

                     但是,为了能访问const对象,下标运算符重载有非const和const两个版本。(待定写)

 如:int&  Point::operator[](int y)//为什么使用返回引用:返回的值可以做左值,也可以做右值,则必须使用返回引用

 重载运算符( )

  1. class Point    
  2. {    
  3. private:    
  4.     int x;   
  5. public:    
  6.     Point(int x1)  
  7.     {   x=x1;}    
  8.     const int operator()(const Point& p);  
  9. };    
  10.   
  11. const int Point::operator()(const Point& p)  
  12. {  
  13.     return (x+p.x);  
  14. }  
  1. 调用:  
  2. Point a(1);  
  3. Point b(2);  
  4. cout<<a(b);  

重载运算符( )的目的:

          1、对象( )  类似于 函数名(x),更加符合习惯

语法:

        重载方式:只能使用成员函数重载

        重载后还可以继续重载

        函数名:operator( )(参数表)

        参数表:参数随意,具体根据实际情况而定。

        函数调用:显式调用:Obj(x)

                            隐式调用:obj.operator( )(x)  

        返回类型:

               1、返回成员的实际类型随意,具体由程序员根据函数体定义

               2、因为返回值只能做右值,只读,应该使用返回值为const类型


重载输入输出操作符<< >>

  1. class Point    
  2. {    
  3. private:    
  4.     int x;   
  5. public:    
  6.     Point(int x1)  
  7.     {   x=x1;}   
  8.     friend ostream& operator<<(ostream& cout,const Point& p);//使用友元函数重载<<输出运算符  
  9.     friend istream& operator>>(istream& cin,Point& p);//使用友元函数重载>>输出运算符  
  10. };    
  11. ostream& operator<<(ostream& cout,const Point& p)  
  12. {  
  13.     cout<<p.x<<endl;  
  14.     return cout;  
  15. }  
  16. istream& operator>>(istream& cin,Point& p)  
  17. {  
  18.     cin>>p.x;  
  19.     return cin;  
  20. }  
  1. 调用:  
  2. Point a(1);  
  3. Point b(2);  
  4. cin>>a>>b;  
  5. cout<<a<<b<<endl;   

语法:

重载方式:只能使用友元函数重载 且 使用三个引用&

函数名:

       输出流: operator<<(参数表)

       输入流:operator>>(参数表)

参数表:固定(容易出错啊),两个参数均用引用&

       输出流: 必须是两个参数:对输出流ostream& 和 对象

                        第一个操作数cout,定义在文件iostream中,是标准类类型ostream的对象的引用。

                        如:ostream& cout,const Point& p

       输入流:必须是两个参数:对输入流ostream& 和 对象

                       第一个操作数是cin,定义在文件iostream,实际上是标准类类型istream的对象的引用

                       如:instream& cin,const Point& p

函数调用:

       输出流: 显式调用:cout<<对象

                        隐式调用: operator<<(cout,对象)

       输入流:显式调用:cin>>对象

                        隐式调用: operator>>(cin,对象)

返回类型:返回类型固定 + 使用返回函数引用(满足连续输出)

       输出流: 返回ostream&

                        如:ostream& operator<<(ostream& cout,const Point& p)

       输入流:返回:istream&

                        如:istream& operator>>(istream& cin,Point& p)

注意:为什么输入输出操作符的重载必须使用友元函数?

因为:成员函数要求是有对象调用,则第一个参数必须是类的对象,但是<<和>>第一个参数是流的对象引用。

故,不能使用成员函数