2019.11.5
开方
可以找到规律der 然后特判 开方五次最大为(2^{32}-1) 注意可能有前导零
要注意特殊数据(0,1)== 然后我没有注意到(1)... 行叭我是瘟猪
int main(){
//freopen("sqrt.in","r",stdin);
//freopen("sqrt.out","w",stdout);
for(;scanf("%s",s+1)!=EOF;){
n=strlen(s+1),x=0ll,st=1;
while(s[st]=='0'&&st<=n) ++st;
if(n-st+1>=11){puts("TAT");continue;}
for(int i=st;i<=n;++i)
x=(x<<3)+(x<<1)+(s[i]^48);
if(x>=((ll)1<<32)){puts("TAT");continue;}
if(x==0) {puts("TAT");continue;}
if(x==1){puts("0");continue;}
if(x<4){puts("1");continue;}
if(x<16){puts("2");continue;}
if(x<256){puts("3");continue;}
if(x<65536){puts("4");continue;}
else puts("5");
}
return 0;
}
染色
我离正解只差一个暴力撕烤
发现就是构成一个树
先prim构一个最小的树 后面不管搞不搞多边形肯定也是这样连边 把这样连的时候的边记录下来
然后暴力枚举多边形的染色情况 用并查集来维护 按照之前记录的边来加入
struct node{int x,y;}a[N],e[N];
struct duo{int k,c,a[N];}b[M];
int dist(int x,int y){return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);}
bool cmp(node x,node y){return mp[x.x][x.y]<mp[y.x][y.y];}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void work(int sta){
ll ret=0;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i)
if((1<<(i-1))&sta){
ret+=b[i].c;
for(int j=2,x=find(b[i].a[1]);j<=b[i].k;++j) f[find(b[i].a[j])]=x;
}
for(int i=1;i<n;++i)
if(find(e[i].x)!=find(e[i].y)) ret+=mp[e[i].x][e[i].y],f[f[e[i].x]]=f[e[i].y];
ans=min(ans,ret);
}
int dis[N],pre[N];bool vis[N];
void prim1(){
for(int i=1,u=0;i<=n;++i,u=0){
for(int j=1;j<=n;++j) if(!vis[j]&&dis[j]<dis[u]) u=j;
vis[u]=1,ans+=dis[u],e[i-1]=(node){pre[u],u};
for(int v=1;v<=n;++v) if(!vis[v]) dis[v]>mp[u][v]?dis[v]=mp[pre[v]=u][v]:1;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T1.txt","r",stdin);
#endif
rd(n),rd(m);
for(int i=1;i<=n;++i) rd(a[i].x),rd(a[i].y);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) mp[i][j]=mp[j][i]=dist(i,j);
memset(dis,inf,sizeof(dis)),dis[1]=0,prim1();
sort(e+1,e+n,cmp);
for(int i=1;i<=m;++i){
rd(b[i].k),rd(b[i].c);
for(int j=1;j<=b[i].k;++j) rd(b[i].a[j]);
}
for(int i=1;i<(1<<m);++i) work(i);
printf("%lld",ans);
return 0;
}
心情
动态规划杀我(QAQ)
首先做必须要做的预处理，将⼤小相同且相邻的数字用 len[i]，color[i] 表示出来。color 记录的是数字，len 记录的是 长度
例如：({1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 4}) 则 (len = {3, 2, 2, 3, 1, 1} color ={1, 2, 3, 4, 5, 4})
我们要处理的是许多小串，可以想到将⼤问题划归成若⼲个 小问题，可以用区间 DP。于是可以先确定两维(f[i,j])表示处理区间([i,j])的最⼤值，但是这样⽆法处理跨区间连接起来⼀起消的问题。
看题目范围：n ≤ 300
猜想空间用三维。于是再引进⼀个 k，这个 k 表示什么呢？
为了能使处理到后面能够使用前面得到的东西，我们用 k 表 示在区间([i,j])后再接上长度为 k 的串得到的值。(f[i, j, k])表示将((color[i], len[i])· · ·(color[j − 1], len[j − 1]),(color[j], len[j] + k))合并的最⼤值。
如果消掉第(j)个数字，那么(f[i, j, k] = f[i, j − 1, 0] + (len[j] + k)^2)
如果将第(j)个数字连着前面的数字⼀起消掉，那么我们还要 再枚举⼀个(p (i ≤ p < j))使得(color[j]=color[p]: f[i, j, k] = f[i, p, k + len[j]] + f[p + 1, j − 1, 0])
于是得到转移⽅程：$f[i, j, k] = max{f[i, j−1, 0]+(len[j]+k) 2 , f[i, p, k+len[j]]+f[p+1, j−1, 0]} $
int dfs(int i,int j,int k){
if(f[i][j][k]) return f[i][j][k];
if(i>j) return 0;
f[i][j][k]=dfs(i,j-1,0)+(len[j]+k)*(len[j]+k);
for(int p=pre[j];p>=i;p=pre[p])
f[i][j][k]=max(f[i][j][k],dfs(i,p,k+len[j])+dfs(p+1,j-1,0));
return f[i][j][k];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T1.txt","r",stdin);
#endif
rd(n);
for(int i=1,pre=1;i<=n;++i)
rd(a[i]),(pre!=i&&a[pre]==a[i])?++len[tt]:(col[++tt]=a[i],pre=i,++len[tt]);
for(int i=1;i<=tt;++i) pre[i]=las[col[i]],las[col[i]]=i;
printf("%d",dfs(1,tt,0));
return 0;
}
summary
-
又双叒叕犯sb错误
-
思路还是混乱
-
dp杀我！！！