Codeforces_832

A.判断n/k的奇偶性。

#include<bits/stdc++.h>
using namespace std;

long long n,k;

int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> k;
    long long t = n/k;
    if(t%2) cout << "YES" << endl;
    else    cout << "NO" << endl;
    return 0;
}

---

B.先计算l = len(ss)-len(s去掉*后)，若l小于0，则肯定NO。从左到右一个个判断，遇到*的时候，直接判断ss中l个字母。还要注意*在末尾的情况。

#include<bits/stdc++.h>
using namespace std;

string s,ss;
int n;
map<char,int> mp;

int main()
{
    ios::sync_with_stdio(0);
    cin >> ss >> s >> n;
    for(int i = 0;i < ss.length();i++)  mp[ss[i]] = 1;
    s = ' '+s;
    while(n--)
    {
        cin >> ss;
        ss = ' '+ss;
        int t = ss.length()-s.length()+1,flag = 1;
        if(t < 0)
        {
            cout << "NO" << endl;
            continue;
        }
        int i = 1,j = 1;
        for(;i < s.length() && j < ss.length();i++,j++)
        {
            if(s[i] == '?')
            {
                if(!mp.count(ss[j]))    flag = 0;
            }
            else if(s[i] == '*')
            {
                j--;
                while(t--)
                {
                    j++;
                    if(mp.count(ss[j])) flag = 0;
                }
            }
            else if(s[i] != ss[j])  flag = 0;
        }
        if(i < s.length() && s[i] == '*')   i++;
        if(flag && i == s.length() && j == ss.length()) cout << "YES" << endl;
        else    cout << "NO" << endl;
    }
    return 0;
}

---

C.二分时间，对于每一个时间，更新每个向左的人的满足区间和向右的人的满足区间，只要两个区间相交，则该时间符合。

#include<bits/stdc++.h>
using namespace std;

int n;
long long s;
struct xx
{
    long long x,v,d;
}a[100005];

bool ok(double t)
{
    long long l1 = 1000001,r1 = 0,l2 = 1000001,r2 = 0;
    for(int i = 1;i <= n;i++)
    {
        if(a[i].d == 1)
        {
            if(a[i].v*t >= a[i].x)
            {
                l1 = 0;
                r1 = 1000000;
            }
            else if((a[i].v+s)*t >= a[i].x)
            {
                l1 = min(l1,a[i].x);
                r1 = max(r1,a[i].x+(long long)((s*t+a[i].v*t-a[i].x)*(s-a[i].v))/s);
            }
        }
        else
        {
            if(a[i].v*t >= 1000000-a[i].x)
            {
                l2 = 0;
                r2 = 1000000;
            }
            else if((a[i].v+s)*t >= 1000000-a[i].x)
            {
                r2 = max(r2,a[i].x);
                l2 = min(l2,a[i].x-(long long)((s*t+a[i].v*t-1000000+a[i].x)*(s-a[i].v))/s);
            }
        }
    }
    if(l1 > r2 || l2 > r1)  return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> s;
    for(int i = 1;i <= n;i++)   cin >> a[i].x >> a[i].v >> a[i].d;
    double l = 0,r = 1000000;
    for(int i = 1;i <= 100;i++)
    {
        double mid = (l+r)/2;
        if(ok(mid)) r = mid;
        else    l = mid;
    }
    cout << fixed << setprecision(10) << l << endl;
    return 0;
}

---

D.先假定一个根，每个询问分别计算3个点为f点时的ans，期间用到lca。

#include<bits/stdc++.h>
using namespace std;

int n,q,dep[100005] = {0},fa[100005][25];
vector<int> v[100005];

void dfs(int now,int pre)
{
    dep[now] = dep[pre]+1;
    for(int i = 0;i < v[now].size();i++)
    {
        int t = v[now][i];
        if(t == pre)    continue;
        fa[t][0] = now;
        dfs(t,now);
    }
}

int lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    int t = dep[x]-dep[y];
    for(int i = 0;i <= 20;i++)
    {
        if((1<<i)&t)    x = fa[x][i];
    }
    if(x == y)  return x;
    for(int i = 20;i >= 0;i--)
    {
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int f(int x,int y,int z)
{
    int xy = lca(x,y),xz = lca(x,z),yz = lca(y,z);
    int ans = dep[x]-max(dep[xy],dep[xz])+1;
    if(xy == xz)    ans += dep[yz]-dep[xy];
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 2;i <= n;i++)
    {
        int x;
        cin >> x;
        v[i].push_back(x);
        v[x].push_back(i);
    }
    dfs(1,0);
    for(int i = 1;i <= 20;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            fa[j][i] = fa[fa[j][i-1]][i-1];
        }
    }
    while(q--)
    {
        int x,y,z;
        cin >> x >> y >> z;
        int ans1 = f(x,y,z);
        int ans2 = f(y,x,z);
        int ans3 = f(z,x,y);
        cout << max(ans1,max(ans2,ans3)) << endl;
    }
    return 0;
}