A题：
给定A,N,P,计算A的N!次幂对P取模的结果。
数据范围：
T次测试，1 ≤ T ≤ 100
1<=A,N,P<=105
快速幂一下就好了。O(nlogn)。
AC代码：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=1e5+1e4;
long long mo[MAXN];
int TT;
long long a,n,p,ans;
long long fast(long long x,long long k)
{
long long res=;
while(k)
{
if(k&) res=res*x%p;
x=x*x%p;
k=k>>;
}
return res;
}
void work()
{
a=a%p;
mo[]=a;
rep(i,,n)
{
mo[i]=fast(mo[i-],i)%p;
}
}
int main()
{
freopen("A-large-practice.in","r",stdin);
freopen("A-large-practice.out","w",stdout);
scanf("%d",&TT);
for(int t1=;t1<=TT;++t1)
{
scanf("%lld%lld%lld",&a,&n,&p);
work();
printf("Case #%d: %lld\n",t1,mo[n]);
}
return ;
}
B题：
图论建模挺巧妙。
题目大意为你有n张牌，正反面各一个数，记为Ri,Bi。
每次操作可以选出两张牌i,j
你可以选择积分增加Ri^Bj或者增加Rj^Bi
从两张牌中选出一张移出游戏，另一张放回牌堆。
反复操作直至只剩一张牌。
要求游戏结束时积分最小。输出最小积分。
数据范围：
T次测试，1<=T<=100
1<=N<=100
1 ≤ Ri ≤ 109
1 ≤ Bi≤ 109
我看了google给的思路才会的，惭愧。
首先注意到双向性：增加同样的积分，操作既可以移出i也可以移出j
然后注意到一共必然是n-1次操作。
考虑把每张牌视作一个点，一个从开始到结束的策略即为一个图上的生成树。
求最小生成树即可。
O(ElogE)
AC代码：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=;
int n,tot,cnt;
long long sum;
int r[MAXN];
int l[MAXN],father[MAXN];
struct Edge
{
int to,from;
int val;
Edge() {}
Edge(int a,int b,int c) {to=a,from=b,val=c;}
}edge[MAXN*MAXN];
inline void addedge(int a,int b,int c)
{
edge[tot++]=Edge(a,b,c);
}
bool cmp(Edge x,Edge y)
{
return x.val<y.val;
}
inline void Input()
{
scanf("%d",&n);
rep(i,,n)
{
scanf("%d",&r[i]);
}
rep(i,,n)
{
scanf("%d",&l[i]);
}
}
inline void init()
{
tot=;
rep(i,,n)
{
rep(j,i+,n)
{
addedge(i,j,r[i]^l[j]);
addedge(j,i,l[i]^r[j]);
}
}
rep(i,,n) father[i]=i;
sort(edge,edge+tot,cmp);
}
int findfa(int x)
{
if(father[x]==x) return x;
else return father[x]=findfa(father[x]);
}
int uni(int x,int y)
{
int fx=findfa(x);
int fy=findfa(y);
father[fy]=fx;
}
void kruskal()
{
cnt=;
sum=;
rep(i,,tot-)
{
if(findfa(edge[i].to)!=findfa(edge[i].from))
{
uni(edge[i].to,edge[i].from);
cnt++;
sum+=edge[i].val;
}
if(cnt==n-) break;
}
}
int main()
{
freopen("B-large-practice.in","r",stdin);
freopen("B-large-practice.out","w",stdout);
int TT;
scanf("%d",&TT);
rep(t1,,TT)
{
Input();
init();
kruskal();
printf("Case #%d: %lld\n",t1,sum);
}
return ;
}
C题：
描述起来有点复杂：
给你一个n*m个格子的矩阵，每个格子里有一个数。
现要将其切成n*m个1*1的格子。
每次只能纵切或者横切。每次切割增加积分的规则如下：
每个独立的子矩阵（就是已经被切开的小矩阵）会贡献一个值，值为这个独立矩阵中的最小元素的值。
要求最后积分最小。
数据范围：
T次测试，1<=T<=100
1<=N,M<=40
记忆化搜索。
先得dp预处理一下子矩阵的最小元素值以供调用。
设mi[i][j][p][q]表示以左上角的点(i,j)和右下角的点(p,q)确定的矩阵中元素的最小值，a[][]存储题目给的矩阵。
固定i,j，枚举p,q
mi[i][j][p][q]为a[i][j]，mi[i][j][p-1][q],mi[i][j][p][q-1]三者之间的最小值。O(M^2N^2)
再记忆化搜索一下，O(M^2N^2(M+N))
总复杂度：O(M^2N^2(M+N))
AC代码：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=;
const int INF=0x3f3f3f3f;
int n,m;
int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int mi[MAXN][MAXN][MAXN][MAXN];
inline void initmi(int x,int y)
{
rep(i,x-,n) mi[x][y][i][y-]=INF;
rep(j,y-,m) mi[x][y][x-][j]=INF;
}
void Input()
{
scanf("%d%d",&n,&m);
// printf("n=%d m=%d\n",n,m);
rep(i,,n)
{
rep(j,,m)
{
scanf("%d",&a[i][j]);
}
}
rep(i,,n) //×óÉϽǶ¥µã
{
rep(j,,m)
{
// printf("i=%d j=%d\n",i,j);
initmi(i,j);
rep(p,i,n) //ÓÒϽǶ¥µã
{
rep(q,j,m)
{
mi[i][j][p][q]=min(min(a[p][q],mi[i][j][p-][q]),mi[i][j][p][q-]);
// printf("%d ",mi[i][j][p][q]);
}
// printf("\n");
}
}
}
memset(dp,,sizeof(dp));
}
int f(int u,int d,int l,int r)
{
if(u==d&&l==r) return ;
// printf("u=%d d=%d l=%d r=%d dp=%d mi=%d\n",u,d,l,r,dp[u][d][l][r],mi[u][l][d][r]);
if(dp[u][d][l][r]>) return dp[u][d][l][r];
int ans=;
rep(i,u,d-)
{
ans=max(ans,f(u,i,l,r)+f(i+,d,l,r));
}
rep(j,l,r-)
{
ans=max(ans,f(u,d,l,j)+f(u,d,j+,r));
}
dp[u][d][l][r]=ans+mi[u][l][d][r];
return ans+mi[u][l][d][r];
}
int main()
{
freopen("C-large-practice.in","r",stdin);
freopen("C-large-practice.out","w",stdout);
int TT;
scanf("%d",&TT);
rep(t1,,TT)
{
Input();
printf("Case #%d: %d\n",t1,f(,n,,m));
}
return ;
}