进度: 3/13

分析: 签到 ,构造 , 位置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 :
#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;
}