SubrectanglesOfTable
简单统计题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <cmath> #include <ctime> #include <iostream> #include <sstream> #include <map> #include <algorithm> #include <string> #include <vector> using namespace std; class SubrectanglesOfTable { public: vector<long long> getQuantity(vector <string> table) { vector <long long> r(26); int m=table.size(); for(int i=0;i<m;++i) { table[i]+=table[i]; table.push_back(table[i]); } m<<=1; int n=table[0].size(); for(long long i=0;i<m;++i) for(long long j=0;j<n;++j) r[table[i][j]-'A']+=(i+1)*(j+1)*(m-i)*(n-j); return r; } }; |
IngredientProportions
构造
随便给某个原料（比如原料0）设定一个质量值，由于题目保证有唯一解，通过给出的比例关系一定可以求出其它所有原料的质量，最后将所有原料的质量统一放大或缩小到最简整数比即可得到正确解。为避免分数运算，我们可以给原料0分配一个恰当的整数质量使得以后的运算中不出现分数。先运用类似Floyd的方法求出原料0与其它所有原料的直接比例，求完后假设原料0与任意原料k的质量比为A[k]:B[k]，那么为使求得的原料k的质量为整数，原料0的质量必须为A[k]的倍数，因此我们应该给原料0分配A[1..N-1]所有数的最小公倍数这么大的质量。这样，我们得到了所有原料的整数质量，最后求出它们的最大公约数而后化为最简比。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cmath> #include <ctime> #include <iostream> #include <sstream> #include <map> #include <algorithm> #include <string> #include <vector> using namespace std; int p[11][11][2]; long long f[11]; long long gcd(long long a,long long b) { if(b==0) return a; else return gcd(b,a%b); } class IngredientProportions { public: vector <int> getMasses(vector <string> d) { memset(p,0,sizeof(p)); int n=d.size()+1; for(int i=0;i<d.size();++i) { int a=d[i][1]-'0',b=d[i][8]-'0',r=d[i][13]-'0',s=d[i][15]-'0'; p[a][b][0]=r; p[a][b][1]=s; p[b][a][0]=s; p[b][a][1]=r; } for(int k=0;k<n;++k) for(int i=0;i<n;++i) if(p[i][k][0]) for(int j=0;j<n;++j) if(p[k][j][0]&&!(p[i][j][0])) { p[i][j][0]=p[i][k][0]*p[k][j][0]; p[i][j][1]=p[i][k][1]*p[k][j][1]; } f[0]=1; for(int i=1;i<n;++i) f[0]=f[0]/gcd(f[0],p[0][i][0])*p[0][i][0]; for(int i=1;i<n;++i) f[i]=f[0]/p[0][i][0]*p[0][i][1]; long long g=f[0]; for(int i=1;i<n;++i) g=gcd(g,f[i]); vector <int> r; for(int i=0;i<n;++i) r.push_back(f[i]/g); return r; } }; |
SpecificPolyominoCovering
构造
本题的难点在于如何快速判断一个棋盘能否用给定的两种棋子填满。
注意到所有的AB嵌套棋子
ABBA
AAAA
都可以用4个B型棋子
BBBB
BBBB
替换，所以在判定时我们可以禁止AB嵌套棋子，而不失正确性。这样我们可以从上到下，从左到右扫描棋盘，每次遇到空缺先尝试B棋子再尝试A棋子，如果都不成功则判定失败，否则继续判定。（详细的正确性证明请参考官方题解）
注意到我们的判定过程实际上构造了一组解，但题目要求我们返回字典序最小的解。我们可以多次利用上述判定过程，仍然从上到下，从左到右扫描棋盘，每次遇到空缺先尝试A棋子，如果可以成功放进去A棋子并且调用上述过程判定剩下的棋盘可以填满棋子，那么就把A棋子真正放到棋盘上，否则就放B棋子，这样可以正确得出字典序最小的解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <cmath> #include <ctime> #include <iostream> #include <sstream> #include <map> #include <algorithm> #include <string> #include <vector> using namespace std; int r,c; bool u[55][55]; bool able(const vector <string> &g) { memset(u,false,sizeof(u)); for(int i=0;i<r;++i) for(int j=0;j<c;++j) if(g[i][j]=='X'&&!u[i][j]) { if(j+1<c&&g[i][j+1]=='X') u[i][j+1]=true; else if(i+1<r&&j+3<c&&g[i][j+3]=='X'&&g[i+1][j]=='X'&&g[i+1][j+1]=='X'&&g[i+1][j+2]=='X'&&g[i+1][j+3]=='X') u[i][j+3]=u[i+1][j]=u[i+1][j+1]=u[i+1][j+2]=u[i+1][j+3]=true; else return false; } return true; } class SpecificPolyominoCovering { public: vector <string> findCovering(vector <string> g) { r=g.size(); c=g[0].size(); if(!able(g)) return vector <string>(); for(int i=0;i<r;++i) for(int j=0;j<c;++j) if(g[i][j]=='X') { if(i+1<r&&j+3<c&&g[i][j+3]=='X'&&g[i+1][j]=='X'&&g[i+1][j+1]=='X'&&g[i+1][j+2]=='X'&&g[i+1][j+3]=='X') { g[i][j]=g[i][j+3]=g[i+1][j]=g[i+1][j+1]=g[i+1][j+2]=g[i+1][j+3]='A'; if(able(g)) continue; else g[i][j]=g[i][j+3]=g[i+1][j]=g[i+1][j+1]=g[i+1][j+2]=g[i+1][j+3]='X'; } g[i][j]=g[i][j+1]='B'; } return g; } }; |