期望得分：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=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int a[51][51],b[51][51]; int main() { int n; read(n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(b[i][j]); int x2a,y2a,x2b,y2b; bool ok; int ans=0; for(int len=n;len;len--) for(int xa=1;xa+len-1<=n;xa++) for(int ya=1;ya+len-1<=n;ya++) for(int xb=1;xb+len-1<=n;xb++) for(int yb=1;yb+len-1<=n;yb++) if(a[xa][ya]==b[xb][yb]) { ok=true; for(int x=1;x<=len&&ok;x++) for(int y=1;y<=len&&ok;y++) if(a[xa+x-1][ya+y-1]!=b[xb+x-1][yb+y-1]) ok=false; if(ok) { ans=len;printf("%d",ans);return 0;} } }
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[11],t[11]; int front[N],to[M],nxt[M],tot=1,val[M],from[M]; int dis1[11][N],dis2[11][N]; bool vis[N]; int in[N],front2[N],nxt2[N<<1],to2[N<<1],val2[N<<1],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=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; 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=1;i<=k;i++) read(s[i]),read(t[i]); int u,v,w; for(int i=1;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],63,sizeof(dis1[w])); memset(vis,false,sizeof(vis)); dis1[w][S]=0; cur.dis=0;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],63,sizeof(dis2[w])); memset(vis,false,sizeof(vis)); dis2[w][S]=0; cur.dis=0;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=1;i<=k;i++) dijkstra1(i),dijkstra2(i); } void topsort() { queue<int>q; for(int i=1;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=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%d",ans); } void solve() { bool ok; int u,v; for(int i=2;i<=tot;i++) { ok=true; u=from[i]; v=to[i]; if(dis1[1][u]+val[i]+dis2[1][v]!=dis1[1][t[1]]) continue; for(int j=2;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(); }