A. Make Even

最大的次数不会超过2,如果数字中没有偶数一定是不合法的情况,若合法但开头数字为偶数操作一次即可(对奇数而言)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int n;cin >> n;
    if(n % 2 == 0)cout << 0 << endl;
    else 
    {
        int ok = false;
        int t1;
        for(int i = 0,t = n; t; i ++)
        {
            if((t % 10) % 2 == 0)ok = true;
            if(t / 10 == 0)t1 = t;
            t /= 10;
        }
        if(!ok)cout << -1 << endl;
        else 
        {
            if(t1 % 2 == 0)cout << 1 << endl;
            else cout << 2 << endl;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

Team Composition: Programmers and Mathematicians

在最大团队数和二者人数之间取一个最小就是答案

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int n,m;cin >> n >> m;
    cout << min(n,min(m,(n + m) / 4)) << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

C. Polycarp Recovers the Permutation

我们可以发现最大值在内部一定不能构造出来
构造方案:将最大值放在最右边,将其余数逆序输出即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N];

void solve()
{
    int n;cin >> n;
    int maxv = 0,idx;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        if(maxv < a[i])
        {
            maxv = a[i];
            idx = i;
        }
    }

    if(a[0] != maxv && a[n - 1] != maxv)
    {
        cout << -1 << endl;
        return;
    }

    for(int i = n - 1; i >= 0; i --)
    {
        if(i == idx)continue;
        cout << a[i] << " ";
    }

    cout << maxv << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

D. Weights Assignment For Tree Edges

题目大意:给定我们一个b数组和p数组,要我们构造出一组合法的距离
b[i]:i的父节点是b[i],p:p[i]到根节点的距离要小于p[i + 1]到根节点的距离

不合法情况:根节点没排在第一位,或者是儿子的距离小于父亲
构造方案:对于某个节点,让他到根的距离等于父节点+1即可
最终输出的是每条边的长度,也就是每个点到其父节点的距离

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int b[N],p[N],dist[N];

void solve()
{
    memset(dist, -1, sizeof dist);
    int n;cin >> n;
    for(int i = 1; i <= n; i ++) cin >> b[i];//b用来取出一个点的父节点
    for(int i = 1; i <= n; i ++) cin >> p[i];//p是结点构造顺序

    //根节点不在p的第一位
    if(b[p[1]] != p[1])
    {
        cout << -1 << endl;
        return;
    }

    dist[p[1]] = 0;//第一位是0
    //扫一遍p数组
    for(int i = 2; i <= n; i ++)
    {
        if(dist[b[p[i]]] == -1)//说明此时已经遍历到儿子,但是父亲没有被更新,即dist[父]>dist[儿]
        {
            cout << -1 << endl;
            return;
        }
        dist[p[i]] = dist[p[i - 1]] + 1;
    }

    for(int i = 1; i <= n; i ++)
        cout << dist[i] - dist[b[i]] << " ";//减去父节点才是这条边的长度
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}

E1. Escape The Maze (easy version)

题目大意:给定我们一颗无向树,其中朋友在某k个结点上,每移动一步花费一点时间
我们初始在1号点,如果能走到叶子节点并且没有与朋友碰面就算获胜,反之朋友胜

我们可以跑一边bfs处理出朋友到所有结点的时间dist
然后以从1号点跑bfs,距离数组是d,如果在某个点有d>=dist,一定是不合法的
若无,走到叶子结点获胜

//这题用memset会超时,要用for循环初始化
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int h[N],e[M],ne[M],idx,din[N];
int dist[N],d[N];
queue<int>q;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void bfs1()
{
    while(!q.empty())
    {
        auto t = q.front();q.pop();
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] == -1)
            {
                dist[j] = dist[t] + 1;
                q.push(j);
            }
        }
    }
}

bool bfs2()
{
    queue<int>qq;
    d[1] = 0;
    qq.push(1);
    while(!qq.empty())
    {
        auto t = qq.front();qq.pop();
        //cout << t << " ";
        //如果能走到叶节点就算成功
        if(din[t] == 1 && t != 1) return true;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            //cout << j << endl;
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                //说明走到这个节点一定会被抓,直接剪掉这颗子树
                if(d[j] >= dist[j])continue;
                qq.push(j);
            }
        }
    }
    return false;
}

void solve()
{
    while(!q.empty())q.pop();
    int n,k;cin >> n >> k;

    for(int i = 1; i <= n + 10; i ++)
    {
        h[i] = -1,dist[i] = -1,d[i] = -1;
        din[i] = 0;
        idx = 0;
    }

    memset(dist,-1,sizeof dist);
    for(int i = 0; i < k; i ++)
    {
        int x;cin >> x;
        dist[x] = 0;
        q.push(x);
    }

    for(int i = 0; i < n - 1; i ++)
    {
        int a,b;cin >> a >> b;
        add(a,b),add(b,a);
        din[a] ++,din[b] ++;
    }

    bfs1();
    if(bfs2())cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}