Problem B. Harvest of Apples
题意：
给出n，m，求C（n，0）+C（n，1）+C（n，2）+……+C（n，m）的值。
分析；
首先定义F（n，m）=C（n，0）+C（n，1）+C（n，2）+……+C（n，m）。根据C（n，m）=C（n-1，m-1）+C（n-1，m），F（n，m）=C（n，0）+C（n-1,0）+C（n-1,1）+C（n-1，1）+C（n-1，2）+……+C（n-1，m-1）+C（n-1，m）=2*F（n-1，m）-C（n-1，m）。知道递推公式后，首先想到了矩阵快速幂，但是因为C（n-1，m）随着递推公式不停地变化，一直没有什么好办法。然后我们考虑其中某些项的计算结果是可以被其他项使用的，比如F（3,2）的结果就可以被F（5,2）使用，如果我们根据按照一定的规则排序询问后，让之前的计算结果可以被后面的询问使用，这样我们就可以大大地减少计算量。对于上述想法其实就是莫队算法的实现思想。
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int mod=1e9+7; const int maxn=1e5+100; int n,m,T,block_size; ll fac[maxn],inv[maxn],res[maxn]; struct Query { int n,m,id; bool operator < (const Query& rhs) const { if(n/block_size!=rhs.n/block_size){ return n/block_size<rhs.n/block_size; } return m<rhs.m; } }; Query q[maxn]; ll poww(ll a,ll k) { ll res=1; while(k) { if(k&1) res=res*a%mod; a=a*a%mod; k>>=1; } return res; } void init(int n) { fac[0]=fac[1]=1; for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%mod; //阶乘的逆元 inv[n]=poww(fac[n],mod-2); for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; block_size=sqrt(1e5); } ll C(int n,int m) { return fac[n]*inv[m]%mod*inv[n-m]%mod; } void mul(ll& x,ll y) { x=x*y%mod; } void add(ll& x,ll y) { x=(x+y)%mod; } void sub(ll& x,ll y) { x=(x+mod-y)%mod; } void div(ll& x,int y) { x=(x*inv[y])%mod; } int main() { // freopen("in.txt","r",stdin); init(maxn-1); scanf("%d",&T); for(int i=1;i<=T;i++){ q[i].id=i; scanf("%d%d",&q[i].n,&q[i].m); } sort(q+1,q+T+1); ll ans=1; int L=0,R=0; for(int i=1;i<=T;i++){ //一定要先把n向上递推后，在计算m //先计算m，可能导致m的值大于当前的n值 while(R<q[i].n){ mul(ans,2); sub(ans,C(R,L)); R++; } while(R>q[i].n){ R--; add(ans,C(R,L)); div(ans,2); } while(L<q[i].m){ L++; add(ans,C(R,L)); } while(L>q[i].m){ sub(ans,C(R,L)); L--; } res[q[i].id]=ans; } for(int i=1;i<=T;i++){ printf("%lld ",res[i]); } return 0; }
Problem D. Nothing is Impossible
题意：
给出n个题目，m个学生，每个题目有1个正确选项，w个错误选项。现在学生可以从n个题目中任意挑选出S个题目，前提是m个学生中一定有一个人可以做对所有题目，问S的最大值是多少？
分析：
首先根据贪心策略，我们选题时题目的错误选项越少，肯定越好。然后确定一点，对于答错了题目的人，我们就不需要再管他们了，因为他们一定不可能全对。所以整体的思想就是先根据题目的错误选项个数从小到大排序，每次计算出一共有多少个学生答对这一题，然后再让这些答对的学生去答下一题，直到学生个数为0，中间答题的个数即是S的最大值。
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int maxn=1000; int n,m,T; struct Problem { int r,w; bool operator < (const Problem& rhs) const { return w<rhs.w; } }; Problem p[maxn]; int main() { // freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&p[i].r,&p[i].w); } int cnt=0; sort(p+1,p+n+1); for(int i=1;i<=n;i++){ int all=p[i].r+p[i].w; //计算出这一题一共有多少学生答对 m=m/all+(m%all>p[i].w?m%all-p[i].w:0); if(m) cnt++; else break; } printf("%d ",cnt); } return 0; }
Problem E. Matrix from Arrays
题意：
给出一个矩阵的构造方法，然后询问子矩阵中所有数的和。
分析：
打个表后会发现矩阵的行和列都是有循环节的，然后对于子矩阵，可以通过容斥原理计算出答案。
参考博客：大佬博客
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int maxn=100; int q,L,T,len; int a[maxn]; int rect[maxn][maxn]; ll prer[maxn][maxn],sum[maxn]; void getMatrix(int n) { int cursor=0; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ rect[j+1][i-j+1]=a[cursor]; cursor=(cursor+1)%L; } } } //计算左上角为(1,1),右下角为(x,y)的子矩阵的和 ll query(int x,int y) { if(x<=0||y<=0) return 0; //计算出一行所有数的和 for(int i=1;i<=len;i++){ sum[i]=sum[i-1]+prer[i][len]*(y/len)+prer[i][y%len]; } //计算整个子矩阵的和 return sum[len]*(x/len)+sum[x%len]; } int main() { // freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { cls(sum); cls(prer); scanf("%d",&L); for(int i=0;i<L;i++){ scanf("%d",&a[i]); } len=L<<1; getMatrix(100); //计算循环节内的前缀和 for(int i=1;i<=len;i++){ for(int j=1;j<=len;j++){ prer[i][j]=rect[i][j]+prer[i][j-1]; } } scanf("%d",&q); for(int i=1;i<=q;i++){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); //因为存储矩阵是从1开始 x1++;y1++;x2++;y2++; //容斥原理 printf("%lld ",query(x2,y2)+query(x1-1,y1-1)-query(x2,y1-1)-query(x1-1,y2)); } } return 0; }
Problem J. Let Sudoku Rotate
题意：
给出一个被旋转的数独表（不合法），旋转只能逆时针旋转小的数独表（大的数独表由16个小的4x4的数独表组成），问最少需要旋转几步可以得到一个合法数独表？（顺时针旋转）
分析：
考虑两种剪枝：当前计算的旋转次数比计算出来的最优解还大，旋转后与之前被旋转区域有冲突。
参考博客：大佬博客
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int maxn=200; int T,ans; bool vis[maxn]; char str[maxn][maxn]; char temp[maxn][maxn]; //顺时针旋转 void rot(int x,int y) { for(int i=x;i<x+4;i++){ for(int j=y;j<y+4;j++){ temp[i][j]=str[x+y+3-j][i-x+y]; } } for(int i=x;i<x+4;i++){ for(int j=y;j<y+4;j++){ str[i][j]=temp[i][j]; } } } //判断旋转该数独区域后，是否与前面的行和前面的列有冲突 bool check(int x,int y) { for(int i=x;i<x+4;i++){ cls(vis); for(int j=0;j<y+4;j++){ if(vis[str[i][j]]){ return false; } vis[str[i][j]]=true; } } for(int i=y;i<y+4;i++){ cls(vis); for(int j=0;j<x+4;j++){ if(vis[str[j][i]]){ return false; } vis[str[j][i]]=true; } } return true; } void dfs(int x,int y,int sum) { if(sum>=ans) return; if(x==4){ ans=min(ans,sum); return; } if(y==4){ dfs(x+1,0,sum); return; } for(int i=0;i<4;i++){ if(check(x*4,y*4)) dfs(x,y+1,sum+i); rot(x*4,y*4); } } int main() { // freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { for(int i=0;i<16;i++){ scanf("%s",str[i]); } ans=100; dfs(0,0,0); printf("%d ",ans); } return 0; }
Problem K. Expression in Memories
题意：
定义格式为（数字 操作符 数字）并且不含前导0（数字为0是允许的）的表达式是合法的，现在表达式中除了数字（0~9），操作符（+ *），还有‘'?'，现在要求你通过改变‘？’为数字或者操作符，使表达式合法，如果无法成功输出IMPOSSIBLE。
分析：
对于每个？只有两种选择：数字或者操作符，那就枚举一下就好了，如果能填数字（1~9）就填数字，否则填操作符，如果两种情况都不行，输出IMPOSSIBLE，需要注意的是顺序不能颠倒。
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int mod=1e9+7; const int maxn=1e4+100; int n; char s[maxn]; bool isop(char ch) { if(ch=='+'||ch=='*') return true; return false; } bool judge(char* s) { int l=-1,r=-1; int slen=strlen(s); //首尾是操作符 if(isop(s[0])||isop(s[slen-1])) return false; for(int i=0;i<slen-1;i++){ //出现两个连续的操作符 if(isop(s[i])&&isop(s[i+1])) return false; } for(int i=0;i<=slen;i++){ if(i<slen&&isdigit(s[i])){ if(l==-1) l=i; r=i; } else{ //如果一个数字前面不是？且出现前导0 if(l!=-1&&s[l]=='0'&&r>l){ if(l==0) return false; if(l&&s[l-1]!='?') return false; } l=-1; } } return true; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++){ scanf("%s",s); bool flag=true; int slen=strlen(s); for(int j=0;j<slen;j++){ if(s[j]=='?'){ s[j]='1'; if(judge(s)) continue; s[j]='+'; if(judge(s)) continue; flag=false; } } if(!judge(s)) flag=false; if(flag) printf("%s ",s); else printf("IMPOSSIBLE "); } } return 0; }
Problem L. Graph Theory Homework
题意：
定义点i与点j之间的距离为sqrt（abs（wi-wj）），求1到n的最短距离。
分析：
设i，j，k的weight值为wi，wj，wk,则从i点到j点再到k点的距离dis=sqrt( |wi-wj |) + sqrt( |wj-wk| )，dis^2=|wi-wj|+|wj-wk|+C（C=2*sqrt（|wi-wj|*|wj-wk|）），直接从i点到k点的距离为d=sqrt(|wi-wk|)，d^2=|wi-wk|，根据绝对值不等式|wi-wj|+|wj-wk|>=|wi-wj+wj-wk|=|wi-wk|，所以答案直接求个1到n的距离就好了。
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int mod=1e9+7; const int maxn=1e5+100; int n,m,T; int a[maxn]; int main() { // freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } printf("%d ",(int)sqrt(1.0*abs(a[n]-a[1]))); } return 0; }