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=1; while(k) { if(k&1) res=res*x%p; x=x*x%p; k=k>>1; } return res; } void work() { a=a%p; mo[1]=a; rep(i,2,n) { mo[i]=fast(mo[i-1],i)%p; } } int main() { freopen("A-large-practice.in","r",stdin); freopen("A-large-practice.out","w",stdout); scanf("%d",&TT); for(int t1=1;t1<=TT;++t1) { scanf("%lld%lld%lld",&a,&n,&p); work(); printf("Case #%d: %lld ",t1,mo[n]); } return 0; }
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=110; 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,1,n) { scanf("%d",&r[i]); } rep(i,1,n) { scanf("%d",&l[i]); } } inline void init() { tot=0; rep(i,1,n) { rep(j,i+1,n) { addedge(i,j,r[i]^l[j]); addedge(j,i,l[i]^r[j]); } } rep(i,1,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=0; sum=0; rep(i,0,tot-1) { if(findfa(edge[i].to)!=findfa(edge[i].from)) { uni(edge[i].to,edge[i].from); cnt++; sum+=edge[i].val; } if(cnt==n-1) break; } } int main() { freopen("B-large-practice.in","r",stdin); freopen("B-large-practice.out","w",stdout); int TT; scanf("%d",&TT); rep(t1,1,TT) { Input(); init(); kruskal(); printf("Case #%d: %lld ",t1,sum); } return 0; }
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=45; 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-1,n) mi[x][y][i][y-1]=INF; rep(j,y-1,m) mi[x][y][x-1][j]=INF; } void Input() { scanf("%d%d",&n,&m); // printf("n=%d m=%d ",n,m); rep(i,1,n) { rep(j,1,m) { scanf("%d",&a[i][j]); } } rep(i,1,n) //×óÉϽǶ¥µã { rep(j,1,m) { // printf("i=%d j=%d ",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-1][q]),mi[i][j][p][q-1]); // printf("%d ",mi[i][j][p][q]); } // printf(" "); } } } memset(dp,0,sizeof(dp)); } int f(int u,int d,int l,int r) { if(u==d&&l==r) return 0; // printf("u=%d d=%d l=%d r=%d dp=%d mi=%d ",u,d,l,r,dp[u][d][l][r],mi[u][l][d][r]); if(dp[u][d][l][r]>0) return dp[u][d][l][r]; int ans=0; rep(i,u,d-1) { ans=max(ans,f(u,i,l,r)+f(i+1,d,l,r)); } rep(j,l,r-1) { ans=max(ans,f(u,d,l,j)+f(u,d,j+1,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,1,TT) { Input(); printf("Case #%d: %d ",t1,f(1,n,1,m)); } return 0; }