总结: 猜结论,"可行即最优"
A: 给定 A,B,C, 每次每个数变成另外两个数的和, 求 k 次后 B-A 的值.
观察发现就是 B-A,A-B 依次出现, 根据 k 的奇偶性输出即可.
B: 给定一个 n 的排列, 每次可以将一个数移到开头或结尾, 求变成 1,2,...,n 所需的最小步数.
找到一个最长的 i,i+1,...,j 满足在排列中的位置递增, 这些数可以保留, 答案就是 n-(j-i+1).
C: 给定一个数列 A, 初始数列 X 全为 0, 每次可以让 X[i+1]=X[i]+1, 求最少多少次能变成 A.
首先特判掉 A[1]>0 和 A[i+1]>A[i]+1 的情况, 然后如果 A[i+1]=A[i]+1, 那么只需要 ans++, 否则 ans+=A[i+1].
D: 给你一棵无根树, 你可以在树中任意新增点, 然后将树染色, 满足以同一颜色的任意两个点为根的两棵树同构, 问最少要多少种颜色, 且在颜色数最少的情况下, 这棵树最少有多少个度数为 1 的点.
找到一个点使以这个点为根的树深度最小 (这个深度同时也是 $\lceil \frac{D}{2} \rceil$,D 为树的直径长).
如果使得深度最小的点有两个, 那么显然要让这棵树关于这两个点轴对称. 如果有一个, 可以使整棵树关于这个点中心对称, 也可以任选一个和这个点相邻的点, 让这棵树关于这两个点轴对称. 两种方案讨论一下即可.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define rep(i,l,r) for (int i=l; i<=r; i++)
- typedef long long ll;
- using namespace std;
- const int N=210;
- int n,u,v,mn,p,cnt,tot,h[N],a[N],d[N],to[N],nxt[N],b[N],dep[N][N];
- void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
- void dfs(int x,int fa,int k){
- dep[k][x]=dep[k][fa]+1;
- for (int i=h[x],v; i; i=nxt[i])
- if ((v=to[i])!=fa) dfs(v,x,k);
- }
- ll work(int x,int y){
- ll res=1;
- memset(b,0,sizeof(b));
- rep(i,1,n){
- int p=min(dep[x][i],dep[y][i]);
- b[p]=max(b[p],d[i]-1);
- }
- rep(i,1,n) if (b[i]) res*=b[i]; else break;
- return res<<1;
- }
- ll work1(int x){
- ll res=1;
- memset(b,0,sizeof(b));
- rep(i,1,n) b[dep[x][i]]=max(b[dep[x][i]],d[i]-1);
- rep(i,2,n) if (b[i]) res*=b[i]; else break;
- return res*d[x];
- }
- int main(){
- freopen("d.in","r",stdin);
- freopen("d.out","w",stdout);
- scanf("%d",&n); mn=n+1;
- rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u),d[u]++,d[v]++;
- rep(i,1,n) dfs(i,0,i);
- rep(i,1,n) rep(j,1,n) dep[i][0]=max(dep[i][0],dep[i][j]);
- rep(i,1,n) mn=min(mn,dep[i][0]);
- rep(i,1,n) if (dep[i][0]==mn) a[++tot]=i;
- if (tot==2) printf("%d %lld\n",mn-1,work(a[1],a[2]));
- else{
- ll ans=work1(a[1]);
- for (int i=h[a[1]]; i; i=nxt[i]) a[++tot]=to[i];
- rep(i,2,tot) ans=min(ans,work(a[1],a[i]));
- printf("%d %lld\n",mn,ans);
- }
- return 0;
- }
- D
来源: http://www.bubuko.com/infodetail-2610427.html