期望得分：100+0+100=200
实际得分：100+5+100=205
T1
空间卡到30M。。
n<=2.5*1e7
若x是整除区间[1,n]每个数的最小的数，那么对[1,n]每个数分解质因数，
ai=2^x*3^y*5^z……
x=2^max(x) * 3^max(y) * 5^max(z) * ……
max(x)=floor (logx n)
只有5000以内的素数的指数才会>=2，所以500之后的素数打个表
代码13M，不传了
T2 bzoj 1567 Blue Mary的战役地图
正解二维哈希，但是严重不满n^7枚举可过
考试的时候zz的把return0 写成break，gg
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
inline void read (int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
int a[][],b[][];
int main()
{
int n;
read(n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
read(a[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
read(b[i][j]);
int x2a,y2a,x2b,y2b;
bool ok; int ans=;
for(int len=n;len;len--)
for(int xa=;xa+len-<=n;xa++)
for(int ya=;ya+len-<=n;ya++)
for(int xb=;xb+len-<=n;xb++)
for(int yb=;yb+len-<=n;yb++)
if(a[xa][ya]==b[xb][yb])
{
ok=true;
for(int x=;x<=len&&ok;x++)
for(int y=;y<=len&&ok;y++)
if(a[xa+x-][ya+y-]!=b[xb+x-][yb+y-]) ok=false;
if(ok) { ans=len;printf("%d",ans);return ;}
}
}
T3[SDOI2009]Elaxia的路线 增强版
2个人改成k个人
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1501
#define M 4000001
using namespace std;
int n,m,k;
int s[],t[];
int front[N],to[M],nxt[M],tot=,val[M],from[M];
int dis1[][N],dis2[][N];
bool vis[N];
int in[N],front2[N],nxt2[N<<],to2[N<<],val2[N<<],tot2;
int dp[N];
struct node
{
int num,dis;
bool operator < (node q)const
{
return dis>q.dis;
}
}cur,nt;
void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
void add(int u,int v,int w)
{
to[++tot]=v;nxt[tot]=front[u];front[u]=tot;val[tot]=w;from[tot]=u;
to[++tot]=u;nxt[tot]=front[v];front[v]=tot;val[tot]=w;from[tot]=v;
}
void add2(int u,int v,int w)
{
to2[++tot2]=v;nxt2[tot2]=front2[u];front2[u]=tot2;val2[tot2]=w;in[v]++;
}
void init()
{
read(n); read(m); read(k);
for(int i=;i<=k;i++) read(s[i]),read(t[i]);
int u,v,w;
for(int i=;i<=m;i++)
{
read(u); read(v); read(w);
add(u,v,w);
}
}
void dijkstra1(int w)
{
priority_queue<node>q;
int S=s[w],T=t[w];
memset(dis1[w],,sizeof(dis1[w]));
memset(vis,false,sizeof(vis));
dis1[w][S]=;
cur.dis=;cur.num=S;
q.push(cur);
int now;
while(!q.empty())
{
cur=q.top(); q.pop();
now=cur.num;
if(vis[now]) continue;
vis[now]=true;
if(dis1[w][now]!=cur.dis) continue;
for(int j=front[now];j;j=nxt[j])
if(dis1[w][to[j]]>dis1[w][now]+val[j])
{
dis1[w][to[j]]=dis1[w][now]+val[j];
nt.dis=dis1[w][to[j]];
nt.num=to[j];
q.push(nt);
}
}
}
void dijkstra2(int w)
{
priority_queue<node>q;
int T=s[w],S=t[w];
memset(dis2[w],,sizeof(dis2[w]));
memset(vis,false,sizeof(vis));
dis2[w][S]=;
cur.dis=;cur.num=S;
q.push(cur);
int now;
while(!q.empty())
{
cur=q.top(); q.pop();
now=cur.num;
if(vis[now]) continue;
vis[now]=true;
if(dis2[w][now]!=cur.dis) continue;
for(int j=front[now];j;j=nxt[j])
if(dis2[w][to[j]]>dis2[w][now]+val[j])
{
dis2[w][to[j]]=dis2[w][now]+val[j];
nt.dis=dis2[w][to[j]];
nt.num=to[j];
q.push(nt);
}
}
}
void pre()
{
for(int i=;i<=k;i++) dijkstra1(i),dijkstra2(i);
}
void topsort()
{
queue<int>q;
for(int i=;i<=n;i++)
if(!in[i]) q.push(i);
int now;
while(!q.empty())
{
now=q.front(); q.pop();
for(int i=front2[now];i;i=nxt2[i])
{
dp[to2[i]]=max(dp[to2[i]],dp[now]+val2[i]);
in[to2[i]]--;
if(!in[to2[i]]) q.push(to2[i]);
}
}
int ans=;
for(int i=;i<=n;i++) ans=max(ans,dp[i]);
printf("%d",ans);
}
void solve()
{
bool ok;
int u,v;
for(int i=;i<=tot;i++)
{
ok=true;
u=from[i]; v=to[i];
if(dis1[][u]+val[i]+dis2[][v]!=dis1[][t[]]) continue;
for(int j=;j<=k&&ok;j++)
if(dis1[j][u]+val[i]+dis2[j][v]!=dis1[j][t[j]] && dis2[j][u]+val[i]+dis1[j][v]!=dis2[j][s[j]]) ok=false;
if(ok) add2(u,v,val[i]);
}
topsort();
}
int main()
{
freopen("yukari.in","r",stdin);
freopen("yukari.out","w",stdout);
init();
pre();
solve();
}