T1
Description
有$K$个石子，石子只能放在$N$条水平线与$M$条竖直线构成的网格的交点上。
求用$K$个石子最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。
Input
第一行三个整数$N,M,K$。
Output
一个非负整数，即最多的满足条件的长方形数量。
Sample Input
3 3 8
Sample Output
5
HINT
$N\;\leq\;30000$，保证任意两点不重合，$K\;\leq\;N\;\times\;M$
Solution
很显然，最佳的方案长这样：
$xxx…xxx$ $xxx…xxx$
$xxx…xxx$ $xxx…xxx$
…… 或 ….
$xxx…xxx$ $xxx…xxx$
$xxx…x$ $xxx…xxx$
设上面两个图形的大多数行的个数为$l$，枚举$l$，$ans=max(c(k/l,2)\;\times\;c(l,2)+c(k$%$l,2)\;\times\;k/l)(1<l\;\leq\;max(n,m))$。
这题本弱有写过原题，但是考场上还是想错了QAQ
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,m,k,sum,ans;
inline bool chk(ll x,ll y){
return max(x,y)<=n&&min(x,y)<=m;
}
inline ll c2(ll k){
return k*(k-)>>;
}
inline void init(){
scanf("%lld%lld%lld",&n,&m,&k);
if(n<m){
ll t=m;m=n;n=t;
}
for(ll i=n,x,y;i>;i--){
x=k/i;y=k%i;
if(!chk(i,x+(y>))||!x) continue;
sum=c2(x)*c2(i)+c2(y)*x;
ans=max(ans,sum);
}
printf("%lld\n",ans);
}
int main(){
freopen("rectangle.in","r",stdin);
freopen("rectangle.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}
T2
Description
求$Fibonacci$数列第$X-Y$项的和除以$10000$的余数。
Input
第一行一个整数$T$，表示数据组数。
接下来$T$行，每行两个数$X,Y$，意义如题所述。
Output
$T$行，每行是一个询问的答案。
Sample Input
2
1 5
127 255
Sample Output
12
5976
HINT
$T\;\leq\;1000,X\;\leq\;Y\;\leq\;2^{31}−1$
Solution
$X,Y$这么大，很容易会想到矩乘。
$s[i]=s[i-1]+f[i]=s[i-1]+f[i-1]+f[i-2]$。
人生第一道当场A的矩乘题，感动QAQ
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 10000
using namespace std;
struct matrix{
int a[][],n,m;
}a,b,c;
int l,r,s1,s2,t;
inline matrix mul(matrix a,matrix b){
matrix c;c.n=a.n;c.m=b.m;
for(int i=;i<=c.n;i++)
for(int j=;j<=c.m;j++)
c.a[i][j]=;
for(int i=;i<=c.n;i++)
for(int j=;j<=c.m;j++)
for(int k=;k<=c.n;k++){
c.a[i][j]+=a.a[i][k]*b.a[k][j];
c.a[i][j]%=M;
}
return c;
}
inline matrix po(matrix a,int k){
matrix c;c.m=a.m;c.n=a.n;
for(int i=;i<=c.n;i++)
for(int j=;j<=c.m;j++)
if(i!=j) c.a[i][j]=;
else c.a[i][j]=;
while(k){
if(k&) c=mul(a,c);
a=mul(a,a);k>>=;
}
return c;
}
inline void init(){
scanf("%d",&t);
a.m=a.n=b.n=;b.m=;
a.a[][]=a.a[][]=a.a[][]=;
a.a[][]=a.a[][]=a.a[][]=;
b.a[][]=;b.a[][]=b.a[][]=;
while(t--){
scanf("%d%d",&l,&r);
if(l<=) s1=l-;
else{
c=mul(po(a,l-),b);
s1=c.a[][];
}
if(r<=) s2=r;
else{
c=mul(po(a,r-),b);
s2=c.a[][];
}
printf("%d\n",(s2-s1+M)%M);
}
}
int main(){
freopen("fibonacci.in","r",stdin);
freopen("fibonacci.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}
T3
Description
给定一个$N$个顶点，$M$条边的无向连通图。
设$dist1[i]$表示在这个无向连通图中，顶点$i$到顶点$1$的最短距离。
求在这张图中，有多少棵大小为$N$的树满足对于任意的$i$，$dist1[i]=dist2[i]$（$dist2[i]$表示在这棵树中，顶点$i$到顶点$1$的距离）。
Input
第一行，两个整数，$N,M$，表示有$N$个顶点和$M$条边。
接下来有$M$行，每行有$3$个整数$x,y,len(1\;\leq\;x,y\;\leq\;n,1\;\leq\;len\;\leq\;100)$，
表示顶点$x$和顶点$y$有一条长度为$len$的边。
数据保证不出现自环、重边。
Output
一行两个整数，表示满足条件的方案数$mod\;2147483647$的答案。
Sample Input
3 3
1 2 2
1 3 1
2 3 1
Sample Output
2
HINT
$2\;\leq\;N\;\leq\;1000,N−1\;\leq\;M\;\leq\;N\;\times\;(N−1)/2$
Solution
$tot[i]$表示到达点$i$满足$dis2[j]+g[j][i]=dis2[i]$的点数。
用$Dijkstra$实现即可。
考场上记录答案的方式写错了导致炸到只剩20QAQ
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1005ll
#define M 1000005ll
#define K 2147483647ll
using namespace std;
typedef long long ll;
struct graph{
ll nxt,to,w;
}e[M];
ll g[N],dis[N],tot[N],n,m,ans,cnt;
bool v[N];
inline ll read(){
ll ret=;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=ret*+c-'';
c=getchar();
}
return ret;
}
inline void addedge(ll x,ll y,ll w){
e[++cnt].nxt=g[x];g[x]=cnt;
e[cnt].to=y;e[cnt].w=w;
}
inline void init(){
n=read();m=read();
for(ll i=,j,k,l;i<=m;i++){
j=read();k=read();l=read();
addedge(j,k,l);addedge(k,j,l);
}
for(ll i=;i<=n;i++){
dis[i]=M;tot[i]=;
}
for(ll l=,p=,nxt,mi;l<=n;l++,p=nxt){
for(ll i=g[p];i;i=e[i].nxt)
if(dis[p]+e[i].w<dis[e[i].to]){
tot[e[i].to]=;
dis[e[i].to]=dis[p]+e[i].w;
}
else if(dis[p]+e[i].w==dis[e[i].to])
tot[e[i].to]=(tot[e[i].to]+)%K;
mi=M;
for(ll i=;i<=n;i++)
if(dis[i]<mi&&!v[i]){
mi=dis[i];nxt=i;
}
v[nxt]=true;
}
ans=;
for(ll i=;i<=n;i++)
ans=ans*tot[i]%K;
printf("%I64d\n",ans);
}
int main(){
freopen("treecount.in","r",stdin);
freopen("treecount.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}