151013まとめ

t1
道dpだそうです.そこで私は探しました
実は記憶化dpの思想を使いました
この問題は反省に値する.
1.エラーメッセージが間違っている
2.配列が足りない
1点目は37.5点少なく、2点目は1点少なくなったが、ツンデレの評価機は私にREを判定しなかった.
67.5以降は注意して問題を読みましょう

//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
inline void R(int &v)
{
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
bool can[1001][3001];
bool visit[1001][3001];
int n;
int a[1001],b[1001];
int _time[3000005];
pair<int,int>que[3000005];
int main()
{
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	R(n);
	for(int i=1;i<=n;i++)
	{
		R(a[i]),R(b[i]);
	}
	for(int i=1;i<=2520;i++)can[0][i]=true;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=2521;j++)
		{
			if((j-1)%(a[i]+b[i])+1<=a[i])can[i][j]=true;
		}
	}
	que[1]=make_pair(0,0);
	int head=0,tail=1;
	while(head!=tail)
	{
		head++;
		int x=que[head].first,y=que[head].second;
		for(int i=x-5;i<=x+5;i++)
		{
			if(i<0)continue;
			if(i>n)printf("%d
",_time[head]+1),exit(0);
			if(!visit[i][y+1] && can[i][y+1])
			{
				visit[i][y+1]^=1;
				que[++tail]=make_pair(i,y+1);
				_time[tail]=_time[head]+1;
			}
		}
	}
	printf("NO
");
	return 0;
}

T2
デバッグの午後、状圧dp+単調スタックメンテナンス検索+啓発式打表+黒科学技術剪定
それから20になって、再び情報を読み間違えて出力して、また手が卑しく偏点を打って、直接50点20少なくなりました
T3
NOI2014 D2T1
100 w見てびっくりしておしっこしました.の長い間bfs+lca+倍増を書いて、各種の黒科学技術は定数を減らして、最終的にやり遂げます
試験会場で

//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define mod 1000000007ll
//using namespace std;
inline void R(int &v)
{
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
int next[1000010];
char s[1000010];
int deep[1000010];
int jump[1000010][21];
struct Edge
{
	int to;
	int next;
}edge[1000010];
int first[1000010],size;
int dl[1000010];
void addedge(int x,int y)
{
	size++;
	edge[size].to=y;
	edge[size].next=first[x];
	first[x]=size;
}
void bfs()
{
	int head=0,tail=1;
	while(head!=tail)
	{
		head++;
		deep[dl[head]]=deep[next[dl[head]]]+1;
		jump[dl[head]][0]=next[dl[head]];
		for(int i=1;i<=20;i++)jump[dl[head]][i]=jump[jump[dl[head]][i-1]][i-1];
		for(int u=first[dl[head]];u;u=edge[u].next)dl[++tail]=edge[u].to;
	}
}
int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	int T;R(T);
	while(T--)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		next[1]=0;
		int now=0;
		for(int i=2;i<=len;i++)
		{
			while(now&&s[now+1]!=s[i])now=next[now];
			if(s[now+1]==s[i])now++;
			next[i]=now;
		}
		memset(first,0,sizeof first);
		size=0;
		for(int i=1;i<=len;i++)addedge(next[i],i);
		deep[0]=0;
		//cerr<<"s"<<clock()<<endl;
		bfs();
		//cerr<<"e"<<clock()<<endl;
		ll ans=1;
		for(int i=1;i<=len;i++)
		{
			if(next[i]<=(i>>1)){ans=(ans*(ll)(deep[i]-1))%mod;continue;}
			int now=i;
			for(int j=20;j>=0;j--)
			{
				if(jump[now][j]>(i>>1))now=jump[now][j];
			}
			ans=(ans*(ll)(deep[now]-1))%mod;
		}
		std::cout<<ans<<std::endl;
		//for(int i=1;i<=len;i++)printf("%d ",next[i]);
		//cerr<<clock()<<endl;
	}
}