Task1
小 W 得到了一堆石子，要放在 N 条水平线与 M 条竖直线构成的网格的交点上。
因为小 M 最喜欢矩形了， 小 W 希望知道用 K 个石子最多能找到多少四边平行于坐标轴的
长方形，它的四个角上都恰好放着一枚石子。
对于 100%的数据：N<=30000，保证任意两点不重合，K<=N*M
简单题，枚举即可
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 typedef long long ll; 8 ll n,m,k,ans,now,a,b,c,p,q; 9 int main(){ 10 freopen("rectangle.in","r",stdin); 11 freopen("rectangle.out","w",stdout); 12 cin>>n>>m>>k; 13 for(int i=1;i<=n;i++){ 14 a=i;b=k/i;c=k%i;now=p=q=0; 15 if(b>m) continue; 16 now=(a*(a-1)/2)*(b*(b-1)/2); 17 if(a<n){ 18 if(c>b) continue; 19 p=now+c*(c-1)/2*a; 20 } 21 if(b<m){ 22 if(c>a) continue; 23 q=now+c*(c-1)/2*b; 24 } 25 ans=max(ans,max(p,q)); 26 } 27 cout<<ans; 28 return 0; 29 }
Task 2
小 W 发现了一个神奇的数列： 这就是著名的 Fibonacci
Sequence = =!。
众所周知，小 M 的数学超级超级好，于是给小 W 出了一道题：
给小 W 两个数 X,Y,其中 X ≤ Y≤ 2^31−1。
小 W 任务就是求出 Fibonacci 数列第 X~Y 项的和除以 10000 的余数。
然而小 W 是数学战五渣，于是只能把这个任务交给机智的你啦。
对于 100%的数据：T<=1000,Y<=2^31-1
简单题，矩阵快速幂裸题
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string.h> 7 #define il inline 8 using namespace std; 9 const int mod=10000; 10 int base[3][3],ans[3][3],tmp[3][3],s,t,T; 11 il void mul(int a[3][3],int b[3][3],int c[3][3]){ 12 memset(tmp,false,sizeof(tmp)); 13 for(int i=0;i<3;i++) 14 for(int j=0;j<3;j++) 15 for(int k=0;k<3;k++) 16 tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod; 17 for(int i=0;i<3;i++) 18 for(int j=0;j<3;j++) 19 c[i][j]=tmp[i][j]; 20 } 21 il int est(int n){ 22 if(n==0) return 0; 23 if(n==1) return 1; 24 if(n==2) return 2; 25 memset(base,0,sizeof(base)); 26 memset(ans,0,sizeof(ans)); 27 ans[0][0]=ans[1][1]=ans[2][2]=1; 28 base[0][1]=base[0][2]=base[1][0]=base[1][1]=base[1][2]=base[2][2]=1; 29 for(int pow=n-2;pow;pow>>=1){ 30 if(pow&1) mul(ans,base,ans); 31 mul(base,base,base); 32 } 33 return (ans[0][2]+ans[1][2]+ans[2][2]*2)%mod; 34 } 35 il void init(){ 36 scanf("%d%d",&s,&t); 37 printf("%d ",(mod+est(t)-est(s-1))%mod); 38 } 39 int main(){ 40 freopen("fibonacci.in","r",stdin); 41 freopen("fibonacci.out","w",stdout); 42 scanf("%d",&T); 43 for(int i=1;i<=T;i++) init(); 44 return 0; 45 }
Task 3
小 W 千辛万苦做出了数列题，突然发现小 M 被困进了迷宫里。
迷宫是一个有 N(2≤N≤1000)个顶点 M(N−1≤M≤N∗(N − 1)/2 ) 条边的无向连通图。
设 dist1[i]表示在这个无向连通图中， 顶点 i 到顶点 1 的最短距离。
为了解开迷宫，现在要求小 W 在这个图中删除 M − (N − 1)条边，使得这个迷宫变成一
棵树。设 dist2[i]表示在这棵树中，顶点 i 到顶点 1 的距离。
小 W 的任务是求出有多少种删除方案，使得对于任意的 i，满足 dist1[i]=dist2[i]。
快点帮助小 W 救出小 M 吧！
对于 100%的数据：2≤N≤1000
最短路径树计数
预处理最短路
因为每个节点链接到从1出发的最短路的距离相等节点是等价的
所以直接统计即可
1 #include<stdio.h> 2 #include<iostream> 3 #include<stdlib.h> 4 #include<algorithm> 5 #include<math.h> 6 #include<string> 7 #include<string.h> 8 #include<queue> 9 #define il inline 10 using namespace std; 11 const int N=2001; 12 int n,m,M=0,inq[N],d[N],p[N][N],g[N]; 13 long long ans=1; 14 queue<int> q; 15 struct edge{int next,to,val; 16 } e[2000001]; 17 struct data{int dist,id; 18 } b[N]; 19 il void addedge(int x,int y,int z){ 20 e[++M]=(edge){g[x],y,z};g[x]=M; 21 } 22 il bool cmp(data a,data b){ 23 return a.dist<b.dist; 24 } 25 int main(){ 26 freopen("treecount.in","r",stdin); 27 freopen("treecount.out","w",stdout); 28 scanf("%d%d",&n,&m); 29 for(int i=0;i<=n+1;i++) 30 for(int j=0;j<=n+1;j++) 31 p[i][j]=p[j][i]=(1<<20); 32 for(int i=1,x,y,z;i<=m;i++){ 33 scanf("%d%d%d",&x,&y,&z); 34 addedge(x,y,z); 35 addedge(y,x,z); 36 p[x][y]=p[y][x]=z; 37 } 38 for(int i=1;i<=n;i++) d[i]=(1<<20); 39 memset(inq,false,sizeof(inq)); 40 d[1]=0;q.push(1); 41 while(!q.empty()){ 42 int h=q.front();q.pop();inq[h]=false; 43 for(int i=g[h];i;i=e[i].next) 44 if(d[e[i].to]>d[h]+e[i].val){ 45 d[e[i].to]=d[h]+e[i].val; 46 if(!inq[e[i].to]){ 47 inq[e[i].to]=true; 48 q.push(e[i].to); 49 } 50 } 51 } 52 for(int i=1;i<=n;i++){ 53 b[i].dist=d[i]; 54 b[i].id=i; 55 } 56 sort(b+1,b+n+1,cmp); 57 for(int i=2;i<=n;i++){ 58 int cnt=0; 59 for(int j=1;j<i;j++) 60 if(b[j].dist+p[b[j].id][b[i].id]==b[i].dist) 61 cnt++; 62 ans=ans*cnt%2147483647ll; 63 } 64 cout<<ans; 65 return 0; 66 }