艾呀喵啊 (特判与大数)

题目描述:

艾星人和喵星人开战了!

但是CWY发现,这只是大宇宙意志的一场“阴谋”,旨在控制艾星和喵星的人口数量。

战争最后的结果无非就是两败俱伤,人口锐减。

但是CWY想知道是艾星和喵星的人口总数是多少,以此预知战争的伤亡情况。

艾星和喵星人口总数为n,分别标号1到n,其中艾星人的标号是1到n中属于给定的等差数列或等比数列的数字。

给定等差数列的首项a,公差b,等比数列的首项c,公比d,你的任务是求出艾星人的个数。

输入格式:

一行,5个整数,分别是a,b,c,d,n。

(1≤a,b,c,n≤1012,  1≤d≤105。)

对于80%的数据,1≤n≤1000000。

输出格式:

一个整数,表示艾星人个数。

输入输出样例:

输入样例

1  1  1  2  1000

3  3  1  2  1000

452  24  4  5  600

输出样例

1000

343

10

样例解释

产生的等差数列是:1,2,3,4,….

产生的等比数列是:1,2,4,8,….

所以【1,1000】范围内所有标号都是艾星人的。

 

艾星人的10个数分别是: 4,20,100,452,476,500,524,548,572,596

 

 

今天不知道为什么调试器暴走……

而且把a>n的特判给打反

这题就是先算出等比的,再算等差(指数函数很快,记得用int64) ,再特判

Program queue;
var
   a,b,c,d,n,ans,i,ii:int64;
function is_ok:boolean;
begin
   if (a>n) then exit(false);

   if (c-a>=0) then
      if ((c-a) mod b=0) then
         if ((c-a) div b>=-1) then exit(true);
   exit(false);

end;
begin
   assign(input,'queue.in');
   assign(output,'queue.out');
   reset(input);
   rewrite(output);


   read(a,b,c,d,n);
   if (a>n) then ans:=0
   else ans:=(n-a) div b+1;

   while (c<=n) do
   begin
      if (not(is_ok) ) then inc(ans);
      c:=c*d;
      if (d=1) then break;
   end;
   writeln(ans);

   close(input);
   close(output);

end.

后院 (组合数+线段判重)

题目描述】

    左下角是(0,0),右上角是(W,H)的网格上,有(W+1)*(H+1)个格点。现在要在格点上找N个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于D。求方案数模1,000,000,000。

【输入格式】

    第一行一个整数T,表示数据组数。

       接下来T行,每行四个整数N,W,H,D,意义如题目描述。

【输出格式】

    T行,每行一个整数表示答案。

【输入输出样例】

backyard.in

backyard.out

6

2 4 4 1

13 36 48 5

5 5 5 1

50 49 49 1

6 5 5 2

10 55 75 5

300

2

88

102

0

490260662

 

【数据规模】

    20%的数据,N,W,H,D≤10。

    50%的数据,W,H,D≤100。

    另20%的数据,N≤5。

    100%的数据,N≤50,W,H,D≤500,T≤20。

 

首先是C(n,k) 的求法

	C[0][0]=1;
	for (int i=1;i<=501;i++)
	{
		C[i][0]=C[i][i]=1;
		for (int j=1;j<=i-1;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%F;
	}

这个要背……

其次是判重

每次枚举是不要枚举一条直线,而要枚举一条线段(前后端点必取的)

注意要把线段放入点中,有(n-1)*(k-1)条线段,这些线段是为了让每段都大于d的最小点数,注意最小间隔+1的精度为ceil(k=trunc(d/dis-1e-7)+1)

注意在这种有长度限制(>=d)的题中,先把要添的点填上,再算组合数)

这样就没重复了,枚举一条线段的数量 显然为 (w-i+1)*(h-j+1) 注意用Longlong

回到原题,发现这样是无法考虑N=1,即只有一个店的情况,故特判,显然为网格上的所有点(w+1)*(h+1)

还要考虑堆成的线段->但是横纵线是不需要*2的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (50+10)
#define MAXW (500+10)
#define MAXH (500+10)
#define MAXD (500+10)
#define MAXT (20+10)
#define F (1000000000)
#define eps 1e-10
int t,n,w,h,d;
long long C[MAXW][MAXH]={0};
int gcd(int a,int b)
{
	if (b==0) return a;
	else return gcd(b,a%b);
}
int main()
{
	freopen("backyard.in","r",stdin);
	freopen("backyard.out","w",stdout);
	scanf("%d",&t);

	C[0][0]=1;
	for (int i=1;i<=501;i++)
	{
		C[i][0]=C[i][i]=1;
		for (int j=1;j<=i-1;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%F;
	}

	while (t)
	{
		long long ans=0;
		scanf("%d%d%d%d",&n,&w,&h,&d);


		// 枚举 totnode-2取 ? 时。至少有2个点才不会Re
		if (n==1)
		{
			cout<<(w+1)*(h+1)<<endl;
			t--;
			continue;
		}

		for (int i=0;i<=w;i++)
			for (int j=0;j<=h;j++)	//(0,0)->(x,y)
			{
				if (i==0&&j==0) continue;
				int g=gcd(i,j);
				int totnode=g+1;  //直线上整点数
				if (totnode<n) continue;
				double dis=sqrt(double((i/g)*(i/g)+(j/g)*(j/g)));
				int k=int(trunc(double(d)/dis-eps))+1; //最少的能拼凑>=d的dis段数	eg:d=2 dis=1 k=2	d=2.5 dis=1 k=3
				if (k*(n-1)+1>totnode) continue; //段数n*[...)  +右端点
				ans=(ans+(i==0||j==0?1:2 )*((((w-i+1)*(h-j+1))%F)*(C[totnode-2-(n-1)*(k-1)][n-2]%F)))%F;  //横线 纵线的特判
		//		cout<<ans;

		//		cout<<i<<' '<<j<<' '<<ans<<endl;
			}
		t--;
		printf("%dn",ans);
	}
//	while (1);
	return 0;
}

分割矩阵 (二分范围[L,R))

   分割矩阵

                   (browine.c/cpp/pas)

【问题描述】

    有N*M的一个非负整数矩阵。现在要把矩阵分成A*B块。矩阵先水平地切A-1刀,把矩阵划分成A块。然后再把剩下来的每一块独立地切竖着B-1刀。每块的价值为块上的数字和。求一种方案,使得最小价值块的价值最大。

【输入格式】

    第一行四个整数N,M,A,B。

    接下来N行,每行M个非负整数。代表这个矩阵

【输出格式】

    一个数字。最小价值块的价值。

【样例输入】

5 4 4 2

1 2 21

3 1 1 1

2 0 1 3

1 1 1 1

1 1 11

【样例输出】

    3

 

样例解释见图片

【数据规模】

   1<=A<=N<=500

   1<=B<=M<=500

    其他数字小于4000。

 

 二分的同志请注意了

m=(l+r)/2 <-----这句是永远也枚不到L与R的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (500+10)
#define MAXM (500+10)
#define MAXT (2000000+10)
int n,m,t1,t2,a[MAXN][MAXM],sum[MAXN][MAXM]={0};
bool is_ok(int l,int r,int _m)
{
	int tot=0,p=0;
	for (int i=1;i<=m;i++)
	{
		tot+=sum[r][i]-sum[l-1][i];
		if (tot>=_m) {tot=0;p++;}
	}
	if (p>=t2) return 1;
	else return 0;
}
bool is_ok_(int _m)
{
	int p=0,l=1;
	for (int i=1;i<=n;i++)
	{
		if (is_ok(l,i,_m)) {l=i+1;p++;}
	}
	if (p>=t1) return 1;
	else return 0;
}
int main()
{
	freopen("browine.in","r",stdin);
	freopen("browine.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&t1,&t2);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			sum[i][j]=sum[i-1][j]+a[i][j];
		}
	/*
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			printf("%d ",sum[i][j]);
		}
	*/
//	cout<<(is_ok_(4));
	int l=1,r=1,ans=0;
	for (int j=1;j<=m;j++) r+=sum[n][j];

	for (int i=1;i<=60;i++)
	{
		int m_=(l+r)/2;
		if (is_ok_(m_)) {l=ans=m_;}
		else r=m_;
	}
	printf("%dn",ans);

//	while (1);
	return 0;
}

 

混合图 (h[u]误写成h[q[u]]……)

                                     混合图

                   (dizzy.c/cpp/pas)

【问题描述】

    有一张N个点,M1条有向边,M2条无向边组成的混合图。询问一个给所有无向边定向的方案。使得最终的图中没有环。保证一定有解。

【输入格式】

    第一行,三个数字N,M1,M2。

    接下来M1+M2行,每行两数字Ai,Bi。表示一条边。

    前M1条是有向边。方向是Ai到Bi。

【输出格式】

    输出M2行,按输出顺序输出为无向边确定的方向。Ai Bi或Bi Ai。

    有多解时输出任意解。

【样例输入】

4 2 3

1 2

4 3

1 3

4 2

3 2

【样例输出】

1 3

2 4

2 3

【数据规模】

    1<=N<=100 000

    1<=M1,M2<=100000

 

拓扑排序即使有重边也成立!

请务必注意哈希表h[u]别多套一个q[u]……

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define MAXM (100000+10)
int n,m1,m2,indegree[MAXN]={0},head[MAXN],next[MAXM]={0},edge[MAXM]={0},tot=0;
void addedge(int u,int v)
{
	edge[++tot]=v;
	next[tot]=head[u];
	head[u]=tot;
}
int q[MAXN*2];
bool b[MAXN]={0};
void topsort()
{
	int head_=1,tail=0;
	for (int i=1;i<=n;i++)
		if (indegree[i]==0)
		{
			q[++tail]=i;b[i]=1;
		}
	while (head_<=tail)
	{
		int now=q[head_];
		int p=head[now];
		while (p)
		{
			int v=edge[p];
			indegree[v]--;
			if (indegree[v]==0)
			{
				q[++tail]=v;b[v]=1;
			}
			p=next[p];
		}
		head_++;
	}
}
int h[MAXN];
int main()
{
	freopen("dizzy.in","r",stdin);
	freopen("dizzy.out","w",stdout);
	scanf("%d%d%d",&n,&m1,&m2);
	memset(head,0,sizeof(head));
	for (int i=1;i<=m1;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
		indegree[v]++;
	}
	topsort();
	for (int i=1;i<=n;i++)
	{
		h[q[i]]=i;
	//	cout<<q[i]<<' ';
	}
/*
	for (int i=1;i<=n;i++) cout<<q[i]<<' ';
	cout<<endl;
	for (int i=1;i<=n;i++) cout<<h[i]<<' ';
	cout<<endl;
*/
	for (int i=1;i<=m2;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if (h[u]<h[v]) printf("%d %dn",u,v);
		else printf("%d %dn",v,u);
	}
//	while (1);
	return 0;
}

Tyvj P2053(线段覆盖‘s精度误差&析构函数)

众所周知,精度误差是很坑人的东西

而且有的时候有了eps反而会错(考虑你的条件是严苛还是放宽)

从 0 到  x0 的覆盖中,点的排序就是一例

首先要尽可能以x排序,然后左端点尽量靠右

但是左端点会爆误差……所以先考虑 端点的误差是否可以忽略,如果不行就算相等)

第二处是排序的对象

理论上是从0到x0 不合条件的都被赋0了……

但是 有可能出现 0<x0<a[i].x<a[i+7].x这样的 整条线段不在里面的情况 此时若用max min 那么 会忽略左端点 (我们的本意是让不在区间内的点的区间删了-要删就全删)

故 需考虑·这样的情况

 <-最右边的黄色和青色的

第三处是答案(终极精度误差)   你要让最左端点<eps和最右端点<x0-eps 这里的限制应为严苛(倘若放宽,最左端点为0(前面已经让它∈[0.x0])都不行的话  会出现永远不可能的情况 


#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXX (10000+10)
#define MAXH (100+10)
#define MAXN (2*7+10)
double h,x0,m;
const double eps=1e-10;
bool cmp(const double a,const double b);
bool equal(const double a,const double b)
{
	if (-eps<a-b&&a-b<eps) return 1;
	else return 0;
}
struct node  //表示线段端点 y=1表示左端点 y=-1有端点
{
	double x,y;
	node():x(0.0),y(0.0){}
	node(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(const node a,const node b){return equal(a.x,b.x)?a.y>b.y:cmp(a.x,b.x);/*(a.y!=b.y)?a.y>b.y:a.x+eps<b.x||a.x-eps<b.x;*/ /* ? */	}
}a[MAXN];
double x[MAXN],r[MAXN];
bool cmp(const double a,const double b)
{
//	cout<<(a-eps<b)<<endl;
	return ((a-eps<b)||(a+eps<b));
}
bool is_ok(double m)
{
	for (int i=1;i<=7;i++)
	{
		if (h<=r[i]+m)
		{
			double dis=sqrt(pow((r[i]+m),2)-pow((h),2));
		//	if (dis<0) cout<<dis<<' ';
			a[i].x=max(0.0,x[i]-dis);a[i+7].x=min(x0,x[i]+dis);
		//	if (max(0.0,x[i]-dis)>min(x0,x[i]+dis)) cout<<x[i]-dis<<' '<<x[i]+dis;

		}
		else a[i].x=a[i+7].x=0;
		if (a[i].x>a[i+7].x) a[i].x=a[i+7].x=0;
		a[i].y=1;a[i+7].y=-1;
	}
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;
	sort(a+1,a+1+14);
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;

	for (int i=1,j=0;i<14;i++)
	{
		j+=a[i].y;
		if (!j) return 0;
	}
//	if (cmp(0.0,a[1].x)||cmp(a[14].x,x0)) return 0;
	if ((eps<a[1].x)||(a[14].x<x0-eps)) return 0;
	return 1;
}
int main()
{
//	freopen("rainbow.in","r",stdin);
	scanf("%lf%lf",&h,&x0);
	for (int i=1;i<=7;i++) scanf("%lf%lf",&x[i],&r[i]);

//	for (int i=1;i<=7;i++) cout<<r[i]<<' ';

/*	node a=node(3.0,-1.0);
	node b=node(2.0,-1.0);
	cout<<(a<b)<<endl;
*/
	double l=0.0,r=x0+h+1;
//	cout<<is_ok(60.0);
	while (r-l>eps)
	{
		double m=(l+r)/2;
		if (is_ok(m)) r=m;
		else l=m;
	}
	printf("%.2lfn",r);

//	while (1);
	return 0;
} 



CF 217B(逆向思维-Fibonacci)

这题是逆向思维贪心……当时咋没想到……

本题启示:memset的效率与for一遍差不多,故千万memset导致超时……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (1000000+10)
int n,r,minchange=MAXN;
bool ans[MAXN]={0},res[MAXN];
bool flag=0;
int calc()
{
	int tot=0;
	for (int i=2;i<=n;i++) if (!res[i]^res[i-1]) tot++;
	return tot;
}
void relax()
{
/*	for (int i=1;i<=n;i++) cout<<res[i]<<' ';
	cout<<endl;
*/	int now=calc();
	if (!flag||now<minchange)
	{
		flag=1;minchange=now;
		memcpy(ans,res,sizeof(ans));
		return;
	}
	if (now>minchange) return;


	for (int i=2;i<=n;i++)
	{
		if (ans[i]<res[i]) return ;
		if (ans[i]>res[i])
		{
			memcpy(ans,res,sizeof(ans));
			return;
		}
	}
}
bool is_ok(int l,int r)
{
//	memset(res,0,sizeof(res));
	res[1]=1;
	for (int i=n;i>1;i--)
	{
		if (!l||!r) return 0;
		if (r<l) {l=l-r; res[i]=1;}
		else {r-=l; res[i]=0;}
	}
	if (l!=1||r!=1) return 0;
	relax();
	for (int i=2;i<=n;i++) res[i]=!res[i];
	relax();
}
int main()
{
	cin>>n>>r;
	for (int i=1;i<=r;i++)
	{
		flag=is_ok(i,r)|flag;
//1		cout<<i<<endl;
	}
	if (!flag) cout<<"IMPOSSIBLEn";
	else
	{
		cout<<minchange<<'n';
		for (int i=1;i<=n;i++)
		{
			if (ans[i]) printf("T");
			else printf("B");
		}
		printf("n");
	}
//	while (1);
	return 0;
}

环上的游戏(贪心-博弈)

环上的游戏(cycle

有一个取数的游戏。初始时,给出一个环,环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后,将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏,两人轮流取数,取数的规则如下:

(1)选择硬币左边或者右边的一条边,并且边上的数非0;

(2)将这条边上的数减至任意一个非负整数(至少要有所减小);

(3)将硬币移至边的另一端。

如果轮到一个玩家走,这时硬币左右两边的边上的数值都是0,那么这个玩家就输了。

如下图,描述的是Alice和Bob两人的对弈过程,其中黑色节点表示硬币所在节点。结果图(d)中,轮到Bob走时,硬币两边的边上都是0,所以Alcie获胜。

现在,你的任务就是根据给出的环、边上的数值以及起点(硬币所在位置),判断先走方是否有必胜的策略。

 

【输入格式】

第一行一个整数N(N≤20),表示环上的节点数。

第二行N个数,数值不超过30,依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。

 

【输出格式】

仅一行。若存在必胜策略,则输出“YES”,否则输出“NO”。

 

【样例】

cycle.incycle.out

4 YES

2 5 3 0

cycle.incycle.out

3 NO

0 0 0

最后取到数的人获胜

稍加模拟

不难发现

0-x-x-x-x-x-x-1-x-x-x-x-x-0

显然任意取一个数,若全取,则

0-10-10-0

  ↑

对方再取 0- 9-10-0

我记续取 0- 9-0-0

    ↑

想办法让对方只能向一个方向取

0-x-x-x-x-0

  ↑

此时奇数次必胜,偶数次必败

若两个方向都是偶数个x

0-x-x-x-x- 0

        ↑

此时无论我怎么取

0-x-(x-?)-x-x-0

     ↑   

于是又成了必胜态,故上次为必败态

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20+10)
int n;
int a[MAXN];
bool flag=0;
int main()
{
	freopen("cycle.in","r",stdin);
	freopen("cycle.out","w",stdout);

	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int i=1; while (a[i]) i++;
	if ((i-1)%2) flag=1;
	i=n; while (a[i]) i--;
	if ((n-i)%2) flag=1;

	if (flag) printf("YESn");
	else printf("NOn");

//	while (1);
	return 0;
}

高级打字机 (Tries)

Problem 1 高级打字机(type.cpp/c/pas)

【题目描述】

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。

请为这种高级打字机设计一个程序,支持如下3种操作:

1.T x:在文章末尾打下一个小写字母x。(type操作)

2.U x:撤销最后的x次修改操作。(Undo操作)

(注意Query操作并不算修改操作)

3.Q x:询问当前文章中第x个字母并输出。(Query操作)

文章一开始可以视为空串。

 

【输入格式】

第1行:一个整数n,表示操作数量。

以下n行,每行一个命令。保证输入的命令合法。

 

【输出格式】

每行输出一个字母,表示Query操作的答案。

 

【样例输入】

7

T a

T b

T c

Q 2

U 2

T c

Q 2

【样例输出】

b

c

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

这题要用字典树(Tries)

还有msm(倍增算法)

另外 补充一点

char  s[0]   或者 char 

scanf("%s",s)

 这句会存不下""

因此会把正在循环的自变量i 变成 0

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define LOGMAXN (16+10)
int n,tot=0;
struct Tnode
{
	int deep,f[LOGMAXN];
	char edge;
	Tnode()
	{
		memset(f,0,sizeof(f));
		deep=-1;
		edge='';
	}
	Tnode(char _edge,int _fa,int _deep)
	{
		memset(f,0,sizeof(f));
		f[0]=_fa;
		edge=_edge;
		deep=_deep;
	}
	int logdeep()
	{
		return int(trunc(log(deep)/log(2)));
	}
}node[MAXN];
int log2(int a)
{
	return int(trunc(log(a)/log(2)));
}
void msm(Tnode &a)
{
	int n=a.logdeep();
//	if (n==1) return;
	for (int i=1;i<=n;i++)
	{
		a.f[i]=node[a.f[i-1]].f[i-1];
	}
}
void type()
{
	char c;
	scanf("%s",&c);
	tot++;
	node[tot]=Tnode(c,tot-1,node[tot-1].deep+1);
	msm(node[tot]);
}

void quere()
{
	int p;
	scanf("%d",&p);
	Tnode now=node[tot];
	p=now.deep+1-p; //第i's 祖先
	while (p)
	{
		int i=log2(p);
		p-=(1<<i);
		now=node[now.f[i]];

	}
	printf("%cn",now.edge);

}
void undo()
{
	int p;
	scanf("%d",&p);
	tot++;
	node[tot]=node[tot-1-p];
}
int main()
{
	freopen("type.in","r",stdin);
	freopen("type.out","w",stdout);
	scanf("%d",&n);
	node[0]=Tnode();
	for (int ii=1;ii<=n;ii++)
	{
//		printf("%dn",ii);
		char s[10];
//		printf("%dn",ii);
		scanf("%s",s);
//		printf("%dn",ii);
//		while(1);
		switch(s[0])
		{
			case 'T':type();break;
			case 'U':undo();break;
			case 'Q':quere();break;
		}


	}
//	while (1);
	return 0;
}

POJ 2115(线性同余方程)

怎样求解线性同余方程可看下方

本题要求(b-a)%(2^k)=(cx)%(2^k)   -2^k< b-a<2^k   的x的最小正整数解


解方程 ax=b (mod n)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
long long a,b,c,k,x,y; // (b-a)%(2^k)=(cx)%(2^k) -2^k<b-a<2^k
long long shl(long long p,long long k)
{
	k--;
	while (k)
	{
		p*=2;
		k--;
	}
	return p;

}
long long exgcd(long long a,long long b)
{
	if (b==0)
	{
		x=1;
		y=0;
		return a;
	}

	long long ans=exgcd(b,a%b);
	long long x1=y;
	long long y1=x-(a/b)*y;
	x=x1;
	y=y1;
	return ans;

}
long long modular(long long a,long long b,long long n)
{

	long long d=exgcd(a,n);
	if (b%d) return -1;
	long long x0=x*(b/d) % n;
	/*
		d=ax(mod n)
		d*(b/d)=ax(b/d) (mod n)
		设x(b/d)=x0
		则 b=a*x0 (mod n)
		因 b=a*(x0+t*(n/d) )=a*x0+ a*n/d =[a*x0+(a/d)*n] (mod n)=a*x0 (mod n)
		-> 求 [x0+t*(n/d)]min>0
		 t==d -> (x0+n) mod n -> 正数解
				 (x0+n) mod n -k(n/d)>0   k->max
				 (x0+n) mod n mod (n/d) =(x0+n) mod (n/d)
	*/
//	cout<<x0<<' '<<n/d<<endl;
	return (x0+n)%(n/d);
}
//long long

int main()
{
	while (scanf("%d%d%d%d",&a,&b,&c,&k)!=EOF )
	{
		/// << -> long long's case
		 /*
		long long p=1LL<<32;
		long long m=((long long)1<<32);
		cout<<p<<' '<<m<<endl;
		*/
		if (a==0&&b==0&&c==0&&k==0) break;   //(b-a)%(2^k)=(cx)%(2^k) b-a<2^k
		long long p2_k=shl(2,k);
		long long ans=modular(c,(b-a+p2_k)%(p2_k),p2_k);
		if (ans==-1) cout<<"FOREVERn";
		else cout<<ans<<endl;
	}
	return 0;
}

DNA序列 (各点只出现1次的Dp序)

DNA序列(dna)

题目描述

来自JSSI(Jinkela State Scientific Institute)的科学家们尝试制造一个长度为N并且只包含A的DNA序列,不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改,来得到一个全部是A的序列。篡改的方式有两种:

1 更改某一位上部件的状态(A变成B,B变成A)

2 更改某个前缀内所有部件的状态

两种操作的代价都为1。

你的任务自然是求最小代价。

输入

第一行为N,序列长度。

第二行是一个长度为N且只包含A和B的字符串,表示初始序列。

输出

最小代价。

样例输入

12

AAABBBAAABBB

样例输出

4

数据范围

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

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

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

当一个题目有几种只可能出现1次的操作,而某些操作对后续操作的影响相同,且之后的操作不会对前面影响

便可根据对后续情况影响的状况Dp,乃至D成了贪心

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (1000000+10)
int n;
char s[MAXN];
char turn(const char a)
{
	if (a=='A') return 'B';
	else return 'A';
}
int F[2]={0,1};
int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s);
	for (int i=n-1;i>=0;i--)
	{
//		cout<<F[0]<<' '<<F[1]<<endl;
		int f0=min(F[0]+(s[i]=='B'),F[1]+1+(s[i]=='B'));
		int f1=min(F[0]+1+(s[i]=='A'),F[1]+(s[i]=='A'));
		F[0]=f0;
		F[1]=f1;
	}
	cout<<min(F[0],F[1])<<endl;


//	while (1);
	return 0;
}