2020HDU多校第六场

Divisibility （HDU-6835） （1009）

题意：就是在什么情况下，对于b进制数x以及任意b进制数y，y的各位数字的和能被x整除可以推出y能被x整除；y的各位数字的和不能被x整除可以推出y不能被x整除。

思路：https://www.cnblogs.com/lipoicyclic/p/13449188.html

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        ll b, x;
        cin >> b >> x;
        if ((b - 1) % x == 0)
            cout << "T" << endl;
        else
            cout << "F" << endl;
    }
    return 0;
}

Little Rabbit’s Equation （HDU-6828）（1002）

题意：判断给出的表达式在哪种进制下成立。

思路：直接把字符串截成三段，从小到大枚举每种进制即可。注意的地方：开long long 如果有一位数比当前枚举到的进制还大，直接跳过这种情况。

AC代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int Atoi(string s, int radix)
{
    int ans = 0;
    for (int i = 0; i < s.size(); i++)
    {
        char t = s[i];
        if (t >= '0' && t <= '9')
        {
            if (t - '0' >= radix)
                return -1;
            ans = ans * radix + 1ll * (t - '0');
        }
        else
        {
            if (1ll * (t - 'A' + 10) >= radix)
                return -1;
            ans = ans * radix + 1ll * (t - 'A' + 10);
        }
    }
    return ans;
}
bool calc(int a, int b, int c, char opt)
{
    if (opt == '+')
    {
        return a + b == c;
    }
    else if (opt == '-')
    {
        return a - b == c;
    }
    else if (opt == '*')
    {
        return a * b == c;
    }
    else
    {
        if (b == 0)
            return -1;
        return a % b == 0 && a == b * c;
    }
}
int main()
{
    string s;
    while (cin >> s)
    {
        int opt = -1, eq = -1;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] >= '0' && s[i] <= '9' || s[i] >= 'A' && s[i] <= 'Z')
                continue;
            if (opt == -1)
                opt = i;
            else
                eq = i;
        }
        string a = s.substr(0, opt);
        string b = s.substr(opt + 1, eq - opt - 1);
        string c = s.substr(eq + 1);
        bool flag = 0;
        for (int i = 2; i <= 16; i++)
        {
            int aa = Atoi(a, i), bb = Atoi(b, i), cc = Atoi(c, i);
            if (aa == -1 || bb == -1 || cc == -1)
                continue;
            if (calc(aa, bb, cc, s[opt]))
            {
                cout << i << endl;
                flag = 1;
                break;
            }
        }
        if (!flag)
        {
            cout << -1 << endl;
        }
    }
}

A Very Easy Graph Problem （HDU-6832）（1006）

题意：给你一个n个点,m条无向边的图，每个点有是黑点或者白点，要你求所有黑点和所有白点的最短路的和。

思路：这道题的边权是2的幂次，显然我们发现边权前面所有边相加都不如这条边长，因此其实本题的最短路径就是最小生成树。之后对于答案只需要计算每条边的贡献即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
using namespace std;
struct node
{
    int a, b;
    ll w;
} s[N];
int p[N];
int a[N];
int h[N], e[N], ne[N], idx;
ll w[N];
int cnt1, cnt2;
ll f[N][2];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
int find(int x)
{
    if (x != p[x])
    {
        p[x] = find(p[x]);
    }
    return p[x];
}
ll ans = 0;
void dfs(int u, int fa)
{
    int i;
    if (a[u])
        f[u][1] = 1;
    else
        f[u][0] = 1;
    for (i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        dfs(j, u);
        f[u][1] += f[j][1];
        f[u][0] += f[j][0];
        ans = (ans + w[i] * (f[j][0] * (cnt1 - f[j][1]) % mod + f[j][1] * (cnt2 - f[j][0]) % mod) % mod) % mod;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int i;
        ans = 0;
        cnt1 = 0;
        cnt2 = 0;
        memset(h, -1, sizeof h);
        memset(f, 0, sizeof f);
        for (i = 1; i <= n; i++)
        {
            p[i] = i;
            cin >> a[i];
            if (a[i])
                cnt1++;
            else
                cnt2++;
        }
        for (i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            ll w = qmi(2, i);
            s[i] = {u, v, w};
        }
        for (i = 1; i <= m; i++)
        {
            int pa = find(s[i].a);
            int pb = find(s[i].b);
            if (pa != pb)
            {
                p[pa] = pb;
                add(s[i].a, s[i].b, s[i].w);
                add(s[i].b, s[i].a, s[i].w);
                p[pa] = pb;
            }
        }
        dfs(1, 0);
        cout << ans << endl;
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦