A
首先发现对于2操作,每种素因子可以单独考虑,然后取出步数最多的计入答案,然后分别加上对每种素因子的1操作;
第二步我犯了个错误,以为最优方案是把素因子指数按二进制操作,在1的位置执行1操作,0的位置执行2操作倍增;
然后发现是错的,执行一次1操作后,之后的2操作可以完全代替1操作,这样可以节省对其他素因子的1操作...
int getbit(int x)
{
int cur=,res=;
while (cur<x) cur+=cur,res++;
return res;
}
int BigFatInteger::minOperations(int A, int B)
{
initprm();
int ans=,p=;
for (int i= ; i<cnt ; i++) if (A%prm[i]==)
{
int t=;
while (A%prm[i]==) A/=prm[i],t+=B;
ans ++;
p = max(p,getbit(t));
}
return ans+p;
}
B
题解的思路真的很棒...
首先为了简化问题,需要猜想+证明一些性质:
1) 每条边必须是整数; (无理数+无理数=无理数...)
2) L不能是奇数; (基于性质1,因为多边形形成闭合回路,坐标的奇偶变化是偶数,x0->x0,y0->y0)
接下来发现L为偶数的时候可以构造出rectangle,于是问题化简为找到一个满足要求的triangle.
然后根据格点的离散性,对称性,可以把可能的点集缩小,最后o(n2)的暴力枚举/打表.
struct node{int x,y;};
vector<node>p;
vector<int>d;
int sqt[INF+];
bool check(int x,int y)
{
int dist = x*x+y*y;
if (dist>=INF || !sqt[dist]) return false;
d.push_back(sqt[dist]);
return true;
}
int getdist(node a,node b)
{
int tmp = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
if (tmp>=INF || !sqt[tmp]) return INF;
return sqt[tmp];
}
double find(int l)
{
double res = -1e20;
for (int x= ; x<=l/ ; x++ )
for (int y= ; y<=l/ ; y++ )
if (check(x,y)) p.push_back((node){x,y});
int n = p.size();
for (int i= ; i<n ; i++ )
for (int j=i+ ; j<n ; j++ ) if(d[i]+d[j]<l)
{
int t = getdist(p[i],p[j]);
if (d[i]+d[j]+t!=l) continue;
if (p[i].y*p[j].x==p[i].x*p[j].y) continue;
int tmp = max(d[i],max(d[j],t)) - min(d[i],min(d[j],t));
if (res< || res>tmp) res=tmp;
}
return res;
}
double FindPolygons::minimumPolygon(int L)
{
if (L% || L<) return -1.0;
else
{
for (int i= ; i<= ; i++ ) sqt[i*i]=i;
double ans = find(L);
if (ans>=0.0) return ans;
else return (L%==)?:;
}
}
C
不在info中的点可以乘一个排列数,问题化简为求满足info的方案数.
如果确定了info1[i]为a,那么info2[i]只能选取以a为前缀的集合...
如果info2[i]在info1中还出现过,可以递推下去考虑...
然后就会发现这个问题涉及到一个树形结构.
把所有string造成一棵前缀树,重述问题就是:假设info1[i]位置放a,info2[i]位置只能在a的子树中.
f(x,mask) 表示当前在第i个节点,分配mask集合的方案数.
答案就是f(root,11..1).
对于每个f(x,mask)有两种决策,分配给x,不分配.
然后解决子问题g(x,son,mask2) 表示给x的son分配剩下mask的方案数.
优化:预处理所有合法状态的转移.
const int mod = (int)1e9 + ;
class SimilarNames {
public:
int count(vector <string>, vector <int>, vector <int>);
};
vector<int>valid,nxt[MASK],sub[MASK],e[maxn];
map<int,int>ha;
const int root = ;
int n,m,k,id[MASK];
int getk(vector<int>u,vector<int>v){
for (int i= ; i<m ; i++ ){
if (!ha.count(u[i])) u[i]=ha[u[i]]=ha.size()-;
if (!ha.count(v[i])) v[i]=ha[v[i]]=ha.size()-;
}
return ha.size();
}
void buildtree(vector<string>names){
sort(names.begin(),names.end());
for (int i= ; i<n ; i++ ){
int fa = root;
for (int j=i- ; j>= ; j-- )
if (names[i].substr(,names[j].size())==names[j]){
fa = j;break;
}
e[fa].push_back(i);
}
}
void pretreat(vector<int>u,vector<int>v){
memset(id,-,sizeof(id));
for (int i=,j ; i<(<<k) ; i++ ){
for ( j= ; j<m ; j++ ){
int p = <<ha[u[j]];
int q = <<ha[v[j]];
if ((i&p) && ((i&q)==)) break;
}
if (j==m) {
valid.push_back(i);
id[i] = valid.size()-;
}
}
for (int i= ; i<(int)valid.size() ; i++ )
for (int j= ; j<k ; j++ ) if(valid[i]&(<<j)){
if (id[valid[i]^(<<j)]!=-)
nxt[i].push_back(id[valid[i]^(<<j)]);
}
for (int i= ; i<(int)valid.size() ; i++ )
for (int j=valid[i] ; ; j=(j-)&valid[i]){
if (id[j]!=- && id[valid[i]-j]!=-)
sub[i].push_back(id[j]);
if (!j) break;
}
}
int f[maxn][MASK],g[maxn][MASK];
int add(int &x,int y){
x += y;
while (x>=mod) x-=mod;
return x;
}
int getg(int cur,int s,int mask){
if (s>=) return g[e[cur][s]][mask];
else return !valid[mask];
}
void dfs(int cur){
int s = e[cur].size();
for (int i= ; i<s ; i++ )
dfs(e[cur][i]); for (int i= ; i<s ; i++ ){
for (int j= ; j<(int)valid.size() ; j++ ){
for (int x= ; x<(int)sub[j].size() ; x++ ){
int A = valid[j];
int B = valid[sub[j][x]];
int p = getg(cur,i-,id[B]);
int q = f[e[cur][i]][id[A-B]];
g[e[cur][i]][j] = add(g[e[cur][i]][j],((llong)p*q)%mod);
}
}
} for (int i= ; i<(int)valid.size() ; i++ ){
f[cur][i] = add(f[cur][i],getg(cur,s-,i));
if (cur!=root){
for (int j= ; j<(int)nxt[i].size() ; j++ )
f[cur][i] = add(f[cur][i],getg(cur,s-,nxt[i][j]));
}
}
}
int SimilarNames::count(vector <string> names, vector <int> u, vector <int> v){
n = names.size();
m = u.size();
k = getk(u,v);
buildtree(names);
pretreat(u,v);
dfs(root);
llong ans = f[root][id[(<<k)-]];
for (int i=n-k ; i> ; i-- ) ans = (llong)(ans*i)%mod;
return (int)ans;
}