aw。。。这好像是停课以来第一次考试哎。。。蒟蒻滚粗啦

T1.变幻莫测的数列

迷之卡常QAQ；不过窝竟然卡了90分。。。憋人都卡了85。。好神奇啊

听说卡常技巧。。。计算时暴力int转longlong，用int记录。。。反复定义的变量改全局。。。读入优化QAQ

考试时候写了两个程序，分块和线段树。。显然线段树更快一点

分块

#include <iostream> 
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define mod 1000000007ll
#define LL long long
#define NN 500010
using namespace std;

int n,q,cnt,block,belong[NN],st[NN],x;
struct REC
{
	LL a,b;
}s[NN],c[NN];
LL ans;
char ch,chh[55];
bool f;
void readl(LL &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void read(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void Build(int xx)
{
	c[xx].a=1ll,c[xx].b=0ll;
	for (int j=st[xx];j<=st[xx+1]-1;++j)
		c[xx].a=(c[xx].a*s[j].a)%mod, c[xx].b=((c[xx].b*s[j].a)%mod+s[j].b)%mod;
}
int main()
{
	freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);
	read(n), read(q);
	for (int i=1;i<=n;++i) readl(s[i].a), readl(s[i].b);
	cnt=(int) sqrt(n);
	for (int i=1;i<=n;++i) belong[i]=(i-1)/cnt+1; block=belong[n];
	block=(n-1)/cnt+1;
	for (int i=1;i<=block;++i) st[i]=(i-1)*cnt+1;
	st[block+1]=n+1;
	for (int i=1;i<=block;++i) Build(i);
	while (q--)
	{
		scanf("%s",chh);
		if (chh[0]=='Q')
		{
			read(x);
			ans=1ll;
			for (int i=1;i<belong[x];++i) ans=(ans*c[i].a%mod+c[i].b)%mod;
			for (int i=st[belong[x]];i<=x;++i) ans=(ans*s[i].a%mod+s[i].b)%mod;
			printf("%lld\n",ans);
		}
		else
			read(x), readl(s[x].a), readl(s[x].b), Build(belong[x]);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

线段树（%%%把线段树写RE的线段树大师（大雾

#include <iostream> 
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define mod 1000000007ll
#define LL long long
#define NN 500010
using namespace std;

int n,q,x;
LL ans;
struct REC
{
	int l,r,mid;
	LL a,b;
}tree[NN*6];
struct NODE
{
	LL a,b;
}s[NN];
char ch,chh[55];
void readl(LL &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void read(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void Build(int p,int x,int y)
{
	tree[p].l=x, tree[p].r=y, tree[p].mid=(x+y)>>1;
	if (x==y)
	{	tree[p].a=s[x].a%mod, tree[p].b=s[x].b%mod; return;	}
	Build(p<<1,x,tree[p].mid), Build(p<<1|1,tree[p].mid+1,y);
	tree[p].a=tree[p<<1].a*tree[p<<1|1].a%mod;
	tree[p].b=(tree[p<<1].b*tree[p<<1|1].a%mod+tree[p<<1|1].b)%mod;
}
void Change(int p,int x)
{
	if (tree[p].l==x && tree[p].r==x) tree[p].a=s[x].a, tree[p].b=s[x].b;
	else
	{	if (x<=tree[p].mid)  Change(p<<1,x);
		else Change(p<<1|1,x);
		tree[p].a=tree[p<<1].a*tree[p<<1|1].a%mod;
		tree[p].b=(tree[p<<1].b*tree[p<<1|1].a%mod+tree[p<<1|1].b)%mod;
	}
}
void Query(int p,int x,int y)
{
	if (tree[p].l==x && tree[p].r==y) 
	{	ans=((ans*tree[p].a)%mod+tree[p].b)%mod; return;	}
	else
	{
		if (y<=tree[p].mid) Query(p<<1,x,y);
		else	Query(p<<1,x,tree[p].mid), Query(p<<1|1,tree[p].mid+1,y);
	}
}
int main()
{
	freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);
	read(n), read(q);
	for (int i=1;i<=n;++i) readl(s[i].a), readl(s[i].b);
	Build(1,1,n);
	while (q--)
	{
		scanf("%s",chh);
		if (chh[0]=='Q')
		{
			read(x);
			if (x==0) { puts("1"); continue;} 
			ans=1ll; Query(1,1,x);
			printf("%lld\n",ans);
		}
		else
		{
			read(x), readl(s[x].a), readl(s[x].b);
			Change(1,x);
		}
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

T2.微型加密系统

考试骗了20分滚粗走人

骗分程序（Floyd直接输出答案。。。听说两边spfa有40分

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;

int n,m,x,y,a[110][110];

int main()
{
	freopen("microc.in","r",stdin); freopen("microc.out","w",stdout);
	while (scanf("%d%d",&n,&m))
	{
		if (n==0 && m==0) break;
		memset(a,0x3f,sizeof(a));
		for (int i=1;i<=m;++i) scanf("%d%d",&x,&y), a[x][y]=1;
		for (int k=1;k<=n;++k)
			for (int i=1;i<=n;++i)
				for (int j=1;j<=n;++j) a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
		if (a[1][2]==0x3f3f3f3f || a[2][1]==0x3f3f3f3f)
		{	puts("Impossible"); continue;	}
		printf("%d\n",a[1][2]+a[2][1]);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

新鲜出炉的FLOYD&SPFA

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define NN 110 
using namespace std;

int n,m,x,y,dis[NN][NN],a[NN][NN];
bool vis[NN][NN];
struct REC
{
	int x,y;
};
queue<REC> que;


int main()
{
	freopen("microc.in","r",stdin); freopen("microc.out","w",stdout);
	while (scanf("%d%d",&n,&m)>0 && n)
	{
		memset(a,0x3f,sizeof(a));
		for (int i=1;i<=n;++i) a[i][i]=0;
		for (int i=1;i<=m;++i) scanf("%d%d",&x,&y), a[x][y]=1;
		for (int k=1;k<=n;++k)
			for (int i=1;i<=n;++i)
				for (int j=1;j<=n;++j) a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
		memset(dis,0x3f,sizeof(dis));
		REC tmp,tmpp;
		tmp.x=1,tmp.y=1; dis[1][1]=1; vis[1][1]=1;
		que.push(tmp);
		while (!que.empty())
		{
			tmp=que.front(); que.pop();
			for (int i=1;i<=n;++i)
			{
				int j=(i!=tmp.x)&&(i!=tmp.y);
				if (a[tmp.x][i]==1 && dis[i][tmp.y]>dis[tmp.x][tmp.y]+j)
				{
					dis[i][tmp.y]=dis[tmp.x][tmp.y]+j;
					if (!vis[i][tmp.y]) vis[i][tmp.y]=1, tmpp.x=i, tmpp.y=tmp.y, que.push(tmpp);
				}
				if (a[i][tmp.y]==1 && dis[tmp.x][i]>dis[tmp.x][tmp.y]+j)
				{
					dis[tmp.x][i]=dis[tmp.x][tmp.y]+j;
					if (!vis[tmp.x][i]) vis[tmp.x][i]=1, tmpp.x=tmp.x, tmpp.y=i, que.push(tmpp);
				}
			}			
			if (tmp.x!=tmp.y)
			{
				if (dis[tmp.y][tmp.x]>dis[tmp.x][tmp.y]+a[tmp.x][tmp.y]-1)
				{
					dis[tmp.y][tmp.x]=dis[tmp.x][tmp.y]+a[tmp.x][tmp.y]-1;
					if (!vis[tmp.y][tmp.x]) vis[tmp.y][tmp.x]=1, tmpp.x=tmp.y, tmpp.y=tmp.x, que.push(tmpp);
				}
			}
			vis[tmp.x][tmp.y]=0;
		}
		if(dis[2][2]==0x3f3f3f3f) puts("Impossible");else printf("%d\n",dis[2][2]);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

T3.俄罗斯方块问题

迷之贪心

听说有两行程序

但蒟蒻太弱了只能码线段树了

线段树

#include <iostream> 
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MM 4000010
using namespace std;

int n,m,x,y;
struct REC
{
	int l,r,v,mid;
}tree[MM];
int ans=0;

void read(int &x)
{
	char c;for(x=0,c=getchar();c<'0'&&c>'9';c=getchar());
	for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());
}

void Build(int p,int x,int y)
{
	tree[p].l=x, tree[p].r=y, tree[p].v=0, tree[p].mid=(x+y)>>1;
	if (x==y) return;
	Build(p<<1,x,tree[p].mid), Build(p<<1|1,tree[p].mid+1,y);	
}

void Add(int p,int x,int y)
{
	if (tree[p].l==x && tree[p].r==y) tree[p].v++;
	else
	{
		if (y<=tree[p].mid) Add(p<<1,x,y);
		else if (x>tree[p].mid) Add(p<<1|1,x,y);
		else Add(p<<1,x,tree[p].mid), Add(p<<1|1,tree[p].mid+1,y);
	}	
}

void Query(int p,int x,int y,int v)
{
	if (x==y)	{if (v+tree[p].v>ans) ans=v+tree[p].v; return;}
	Query(p<<1,x,tree[p].mid,tree[p].v+v);
	Query(p<<1|1,tree[p].mid+1,y,tree[p].v+v);
}
int main()
{
	freopen("tetris.in","r",stdin); freopen("tetris.out","w",stdout);
	read(n), read(m);
	Build(1,1,m-1);
	for(int i=1;i<=n;++i)	{ read(x), read(y);	Add(1,x,y-1);	}
	Query(1,1,m-1,0);
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}

迷之压行

#include<cstdio>
int b[1000010],n,m,l,r,a,t,i;int main(){for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&l,&r),b[l]++,b[r]--;for(i=1;i<=m;i++)a=a>(t+=b[i])?a:t;printf("%d",a);}