进度: 3/13
F : Permutation
分析: 签到 ,构造 , 位置1、3、5、7....依次填入1,2,3,4...... ,x 位置2、4、6、8.....依次填入x+1,x+2,x+3......
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 4; int ans[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n,now=0; scanf("%d",&n); for(int i=1;i<=n;i++) if(i&1) ans[i]=++now; for(int i=1;i<=n;i++) if(i%2==0) ans[i]=++now; for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n"); } return 0; }H:A Simple Stone Game
分析: x一定是sum(所有数之和)的某个质因子,枚举sum的所有质因子计数取最小的即可
code :
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 3; ll a[maxn],pre[maxn],b[maxn]; vector<ll> p; int main() { int t; scanf("%d",&t); while(t--) { int n; ll sum=0; p.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum+=a[i]; } for(ll i=2;i*i<=sum;i++) if(sum%i==0) { while(sum%i==0) sum/=i; p.push_back(i); } if(sum>1) p.push_back(sum); ll ans=1e17,tmp; for(int i=0;i<p.size();i++) { tmp=0; for(int j=1;j<=n;j++) b[j]=a[j]; for(int j=1;j<=n;j++) b[j]=b[j]%p[i]; sort(b+1,b+1+n); for(int j=1;j<=n;j++) pre[j]=pre[j-1]+b[j]; for(int j=n;j>=1;j--) if(pre[j]==tmp) break; else tmp+=p[i]-b[j]; ans=min(ans,tmp); } printf("%lld\n",ans); } return 0; }D : X-Men
分析: 猜结论,求最远的两个X-man之间的距离,按照求树的直径做树形dp或两次搜索可解决
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1003; int ver[2*maxn],nx[2*maxn],head[maxn],tot; int a[maxn],cnt,vis[maxn],dis[maxn]; void add(int x,int y){ ver[++tot] = y; nx[tot] = head[x];head[x] =tot; } void dfs(int x){ vis[x] = 1; for(int i = head[x];i;i = nx[i]){ int y = ver[i]; if(vis[y])continue; dis[y] = min(dis[y],dis[x]+1); dfs(y); } } int main() { int t,n,m,x,y; cin >> t; while(t--){ cin >> n >> m; tot = cnt = 0; for(int i = 0;i<=n;++i)head[i] = 0,vis[i] = 0,dis[i] = 1e5; for(int i = 1;i <= m;++i) scanf("%d",&a[++cnt]); for(int i = 1;i < n;++i){ scanf("%d%d",&x,&y); add(x,y);add(y,x); } dis[a[1]] = 0; dfs(a[1]); int f = a[1],num = 0; for(int i = 1;i<=cnt;++i){ if(dis[a[i]]>num){ num = dis[a[i]]; f = a[i]; } } int MAX = num; for(int i =1;i <= n;++i)vis[i] = 0,dis[i] = 1e5; dis[f] = 0; dfs(f); for(int i =1;i<=cnt;++i){ MAX =max(MAX,dis[a[i]]); } double tt = MAX/2; printf("%.2f\n",tt); } return 0; }