Codeforces Round 749 div.1 2 A-E

A. Windblume Ode

题意：给一个数字集合（\(n\ge3\)），要从中取出尽可能多的数字，使之和为合数

判断总和是否为质数，是质数就随便去掉一个奇数就好了

int n, m;
int a[maxn];
 
void solve(){
    cin >> n;
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    for(int i=2;i<sum;i++){
        if(sum % i == 0){
            cout << n << '\n';
            for(int i=1;i<n;i++) cout << i << ' ';
            cout << n <<'\n';
            return;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i] %2 == 1){
            cout << n - 1 << '\n';
            bool f = false;
            for(int j=1;j<=n;j++){
                if(j == i) continue;
                if(f) cout << ' ';
                else f = true;
                cout << j;
            }
            cout << '\n';
            return;
        }
    }
}

B. Omkar and Heavenly Tree

题意：要构造一个 \(n\) 个节点的数，满足 \(m\) 个约束。一个约束描述为 \(a,b,c\)，表示节点 \(b\) 不能在 \(a,c\) 之间的简单路径上，（\(m\lt n\)）

这题乍一看没什么思路，突破口在于 \(m \lt n\) 这个条件，我们发现，至少有一个节点没有被约束，设它为 \(mid\)

只需要把其他所有点都直接连在 \(mid\) 上即可

int n, m;
int vis[maxn];
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        vis[i] = 0;
    }
    for(int i=1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        vis[y] = 1;
    }
    int mid;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            mid = i;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        if(i != mid){
            cout << mid << ' ' << i << '\n';
        }
    }
 
}

C. Omkar and Determination

题意：给出一个 \(n\times m\) 的地图，每一格可以是空地或墙，每个空地上存在一个机器人，它可以向左或向上走；

​ 对于一个地图，我们可以把所有能走出地图的空格染成白色，其他格子染成黑色；

​ 如果一个地图可以仅根据染色后的结果推断出原先的图（哪些是空地哪些是墙），那么称这个地图是有决心的；

​ 接下来有 \(q\) 个询问，每次询问从 \(x_1\) 列到 \(x_2\) 列的这个子图是不是有决心的。

解：考虑什么样的图的有决心的，可以想到如果存在这样的两个墙，一定不是有决心的（右下角无法确定） \[ \begin{gather*} 0 1\\ 1 ? \end{gather*} \] ​ 再想一想可以发现，所有有决心的图都一定不包含这种东西

​ 对于每一列 \(j\)，如果 \(j\) 和 \(j+1\) 列中存在这样的形状就记这列为1，前缀和搞一下查询就好了

string s[1000004];
int n, m, sum[1000004];
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        s[i] = '0' + s[i];
    }
    for(int i=1;i<=n;i++) sum[i] = 0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<m;j++){
            if(s[i][j] == 'X' && s[i-1][j+1] == 'X'){
                sum[j] = 1;
            }
        }
    }
    for(int j=2;j<=m;j++) sum[j] += sum[j-1];
    int Q;
    cin >> Q;
    while(Q--){
        int l, r;
        cin >> l >> r;
        if(sum[r-1]-sum[l-1] == 0) cout << "YES\n";
        else cout << "NO\n";
    }
}

D. Omkar and the Meaning of Life

题意：交互题，要猜一个 \(n\) 的排列 \(p_1,p_2...p_n\) ，每次猜测可以输入一个长度为 \(n\) 的数列 \(a_1,a_2...a_n\)，随后形成一个新的序列 \(s\)，根据 \(s_i = a_i+p_i\) ，然后会返回 \(s\) 中第一次重复出现元素的下标，都不重复则返回0，询问至多 \(2n\) 次

解：交互题往往有个构造题的思路，先考虑给所有数都加上1，唯独最后一个数加 \(x\)，如果 \(p_n + x \gt n+1\)，那么输出为0，否则有其他输出，那么可以从小到大枚举 \(x\)，最多 \(n\) 次即可猜出 \(p_n\) 的数值

现在知道最后一位数的值了，接下来给所有数都加上 \(p_n\)，唯独最后一位数加上1，就可以知道1所在的位置

依次类推，再 \(n\) 次查询即可知道所有数的位置。

int n, a[maxn];
 
void solve(){
    cin >> n;
    a[n] = 1;
    for(int k=n;k>=2;k--){
        cout << "? ";
        for(int i=1;i<n;i++) cout << 1 << ' ';
        cout << n-k+2 << endl;
        cout.flush();
        int re;
        cin >> re;
        if(re == 0){
            a[n] = k;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        if(i == a[n]) continue;
        cout << "? ";
        for(int j=1;j<n;j++) cout << a[n] << ' ';
        cout << i << endl;
        cout.flush();
 
        int re;
        cin >> re;
        a[re] = i;
    }
    cout << "!";
    for(int i=1;i<=n;i++) cout << ' ' << a[i];
    cout << endl;
}

D2. Half of Same

题意：和D1一样，区别在于只需要有一半数减去若干个 \(k\) 后变成相同的数字

\(n\le40, -10^6\le a_i \le 10^6\)

先考虑，如果有一个 \(k\)，我们怎么判断它是否合法：

可以让每个数都减 \(k\) 减到第一次小于 \(mi\) 为止，然后数一下有多少数是相同的

这个Judge过程是 \(O(n)\) 的

那么有多少个 \(k\) 需要judge呢？

可以从1到2e6全部枚举一遍，\(O(2e6\times n)\) 看似可行，然而被卡常了

想到这个 \(k\) 一定是某两个数的差的约数，又因为 \(n\) 很小，可以非常暴力地枚举任意两个数，再枚举它们差的约数，总复杂度 \(O(n^2\sqrt{2\times10^6}\times n)\)

int a[50];
int mia, mxa;
int num[5000009];
int n;
 
bool judge(int k){
    bool re = false;
    for(int i=1;i<=n;i++){
        int t = a[i] - (a[i]-mia+k-1)/k*k;
        num[t]++;
        if(num[t] >= n/2) re = true;
    }
    for(int i=1;i<=n;i++){
        int t = a[i] - (a[i]-mia+k-1)/k*k;
        num[t]--;
    }
    return re;
}
 
void solve(){
    cin >> n;
    mia = 2e8, mxa = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i] += 4000000;
        mia = min(mia, a[i]);
        mxa = max(mxa, a[i]);
    }
 
    sort(a+1, a+n+1);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(a[j] != a[i]){
                i = j - 1;
                break;
            }
            if(j - i + 1 >= n/2){
                cout << "-1\n";
                return;
            }
        }
    }
 
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int d = abs(a[j] - a[i]);
            for(int k=1;k<=sqrt(d);k++){
                if(d % k != 0) continue;
                if(judge(k)) ans = max(ans, k);
                if(judge(d/k)) ans = max(ans, d/k);
            }
        }
    }
    cout << ans << '\n';
}

E. Moment of Bloom

个人感觉最妙的一道题，做的时候一点思路没有，一看题解恍然大悟

题意：有一个 \(n\) 节点，\(m\) 条边的连通图（无重边自环），有 \(q\) 个操作，每次操作仅给出 \(a,b\) 两个点，可以在两点间任选一条简单路径，使路径上的边权都+1（初始为0），问这 \(q\) 个操作后能否使所有边权均为偶数？如果不能输出需要额外操作的数量

解：一个点相邻边的边权之和 = 以这个点为端点的路径条数 + 其他经过这个点的路径条数 * 2

​ 那么如果一个点在操作中出现了奇数次，那么它连的边权之和也为奇数，也就是说必然存在一条边不满足条件

​ 所以可以统计所有操作中各个点出现的次数，如果存在奇数次的点，答案即为NO，额外需要奇数点个数/2次操作

​ 所有点均出现偶数次，答案即为YES，这题还要求输出每一个操作所选择的路径，怎么构造呢——

​ 其实很简单，把图改造成任一个生成树，然后走唯一路径就好了（（具体可以颅内理解一下，不难证明正确性

int n, m;
int cnt[maxn];
vector<int> vp[maxn];
vector<int> vt[maxn];
 
struct Query{
    int x, y;
}q[maxn];
 
int vis[maxn];
void dfs(int p){
    vis[p] = true;
    for(auto &v : vp[p]){
        if(!vis[v]){
            vt[p].push_back(v);
            vt[v].push_back(p);
            dfs(v);
        }
    }
}
 
int ans[maxn], hd;
bool dfsf(int p, int fa, int t){
    ans[++hd] = p;
    if(p == t) return true;
    for(auto &v : vt[p]){
        if(v != fa){
            if(dfsf(v, p, t)) return true;
        }
    }
    hd--;
    return false;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int x, y;
        cin >> x >> y;
        vp[x].push_back(y);
        vp[y].push_back(x);
    }
    int qm;
    cin >> qm;
    for(int i=1;i<=qm;i++){
        cin >> q[i].x >> q[i].y;
        cnt[q[i].x]++;
        cnt[q[i].y]++;
    }
    int odd = 0;
    for(int i=1;i<=n;i++) odd += cnt[i]%2;
    if(odd > 0){
        cout << "NO\n";
        cout << odd/2 << '\n';
    }else{
        cout << "YES\n";
        dfs(1);
        for(int i=1;i<=qm;i++){
            hd = 0;
            dfsf(q[i].x, -1, q[i].y);
            cout << hd << '\n';
            for(int j=1;j<hd;j++) cout << ans[j] << ' ';
            cout << ans[hd] << '\n';
        }
    }
}