T1:【QZOI2020Round1T1】忘记保存的文件(T111415)

算法:模拟

定位:陶陶摘苹果弱化版签到题

std:

//By: Luogu@rui_er(122461)
//this is the std-test
#include <iostream>
using namespace std;

int main()
{
    int n, m, k;
    cin>>n>>m; 
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        if(k > m) ++cnt;
    }
    cout<<cnt<<endl;
    return 0;
}

T2:【QZOI2020Round1T2】哈希哈希(T113599)

算法:类似于桶排序

定位:签到题

std:

//By: Luogu@rui_er(122461)
//this is the std-test 
#include <iostream>
using namespace std;

int hash_table[10001];

int Hash(int x, int mod)
{
    return x%mod;
}

int main()
{
    int n, mod;
    cin>>n>>mod;
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        ++hash_table[Hash(a, mod)];
    }
    int m = 1;
    for(int i=0;i<mod;i++) m = max(m, hash_table[i]);
    if(m == 1) cout<<"orz"<<endl;
    else cout<<m<<endl;
    return 0;
}

T3:【QZOI2020Round1T3】魔镜(T113853)

算法:线段树/树状数组/分块

定位:算法基础题

std:

//By: Luogu@rui_er(122461)
//this is the std_test
#include <iostream>
using namespace std;

#define MAXN 5001
#define Int inline int
#define Void inline void
#define Reg register
int n, m;
int a[MAXN+1], d[MAXN+1], c[MAXN+1];

Int lowbit(int x)
{
    return x & (-x);
}

Int sum(int x)
{
    Reg int ans = 0;
    while(x > 0)
    {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

Int query(int l, int r)
{
    return sum(r) - sum(l-1);
}

Void update(int x, int delta)
{
    while(x <= n)
    {
        c[x] += delta;
        x += lowbit(x);
    }
}

Void init(void)
{
    for(Reg int i=1;i<=n;i++) update(i, d[i]);
}

int main()
{
    cin>>n>>m;
    for(Reg int i=1;i<=n;i++)
    {
        cin>>a[i];
        d[i] = a[i] - a[i-1];
    }
    init();
    Reg int o, p, q, k;
    for(Reg int i=1;i<=m;i++)
    {
        cin>>o;
        if(o == 1)
        {
            cin>>p>>q>>k;
            update(p, k);
            update(q+1, -k);
        }
        else
        {
            cin>>p;
            cout<<query(1, p)<<endl;
        }
    }
    return 0;
}

T4:【QZOI2020Round1T4】八卦圈(T114091)

算法:二分图最大匹配(匈牙利/EK/Dinic)

定位:算法BOSS题

std:

//By: Luogu@rui_er(122461)
//this is the std-test
#include <iostream>
#include <memory.h>
using namespace std;

int n, m, e;
int match[1001], map[1001][1001], flag[1001];
int now;

bool find(int l)
{
    for(int i=1;i<=m;i++)
    {
        if(map[l][i] && flag[i] != now)
        {
            flag[i] = now;
            if(match[i] == 0 || find(match[i]))
            {
                match[i] = l;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m>>e;
    int u, v;
    for(int i=0;i<e;i++)
    {
        cin>>u>>v;
        if(u > n || v > m) continue;
        map[u][v] = 1;
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        now++;
        if(find(i))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

T5:【QZOI2020Round1T5】神秘密码(T114609)

状态:错题

T6:【QZOI2020Round1T6】天天爱下棋(T114802)

算法:树形结构、LCA

难点:构建树

解析:因为对于每一种状态(a, b, c),从两边向中间跳的方式都最多只有一种。根节点就是a、b、c成等差数列时。将有序三元组(a, b, c)为节点内容建树即可。

定位:一般人不会做的题

std:

//By: Luogu@rui_er(122461)
//this is the std-test
#include <iostream>
using namespace std;
typedef long long ll;

ll dep1, dep2;

ll findRoot(ll a, ll b, ll c, ll &dep, ll &d)
{
    ll d1 = b - a, d2 = c - b;
    while(d1 != d2)
    {
        if(d1 < d2)
        {
            ll div = d2 / d1;
            ll com = d2 % d1;
            if(!com)
            {
                dep += div - 1;
                d = d1;
                return a+d1*(div-1);
            }
            else
            {
                dep += div;
                d2 = com;
                a += div * d1;
                b += div * d1;
            }
        }
        else
        {
            ll div = d1 / d2;
            ll com = d1 % d2;
            if(!com)
            {
                dep += div - 1;
                d = d2;
                return a;
            }
            else
            {
                dep += div;
                d1 = com;
                b -= div * d2;
                c -= div * d2;
            }
        }
    }
    dep = 0;
    d = d1;
    return a;
}

void findFather(ll &a, ll &b, ll &c, ll k)
{
    ll d1 = b - a, d2 = c - b;
    while(k)
    {
        if(d1 < d2)
        {
            ll div = d2 / d1;
            ll com = d2 % d1;
            if(div >= k)
            {
                a += k * d1;
                b += k * d1;
                if(b == c)
                {
                    b = a;
                    a -= d1;
                }
                return;
            }
            k -= div;
            b = c - com;
            a = b - d1;
            d2 = com;
        }
        else
        {
            ll div = d1 / d2;
            ll com = d1 % d2;
            if(div >= k)
            {
                c -= k * d2;
                b -= k * d2;
                if(a == b)
                {
                    b = c;
                    c -= d2;
                }
                return;
            }
            k -= div;
            b = a + com;
            c = b + d2;
            d1 = com;
        }
    }
}

int main()
{
    ll a, b, c, x, y, z, p, q, cnt = 0;
    cin>>a>>b>>c>>x>>y>>z;
    if(a == b || b == c || c == a || x == y || y == z || z == x)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    ll sum1 = a + b + c;
    ll sum2 = x + y + z;
    ll max1 = max(a, max(b, c));
    ll max2 = max(x, max(y, z));
    ll min1 = min(a, min(b, c));
    ll min2 = min(x, min(y, z));
    a = min1, b = sum1 - max1 - min1, c = max1;
    x = min2, y = sum2 - max2 - min2, z = max2;
    ll pp = findRoot(a, b, c, dep1, p);
    ll qq = findRoot(x, y, z, dep2, q);
    if(pp != qq || p != q)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    if(dep1 < dep2)
    {
        cnt += dep2 - dep1;
        findFather(x, y, z, cnt);
    }
    if(dep1 > dep2)
    {
        cnt += dep1 - dep2;
        findFather(a, b, c, cnt);
    }
    ll l = 0, r = min(dep2, dep1), ans = 0;
    while(l <= r)
    {
        ll mid = (l + r) / 2;
        ll aa = a, bb = b, cc = c, xx = x, yy = y, zz = z;
        findFather(aa, bb, cc, mid);
        findFather(xx, yy, zz, mid);
        if(aa == xx && bb == yy && cc == zz) ans = 2 * mid, r = mid - 1;
        else l = mid + 1;
    }
    cout<<ans+cnt<<endl;
    return 0;
}