A.Social Distancing

题意：

给定和，要找个整点，使得他们两两距离的平方和最大，并且所有点到原点的距离必须小于

题解：

cf460E。网上找了一份能过的代码(还有一份暴力枚举的只能过66.6%)戳我~
然后打个表就行
打表代码

#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;
struct point
{
    int x, y;
    point(int a = 0, int b = 0)
    {
        x = a;
        y = b;
    }
} t;
point operator-(point a, point b)
{
    return point(a.x - b.x, a.y - b.y);
}
int operator*(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}
vector<point> p;
vector<int> now, bes;
int n, r, ans;
void dfs(int chos, int las, int sx, int sy, int sx2, int sy2)
{
    if (chos == n)
    {
        if (ans < n * (sx2 + sy2) - sx * sx - sy * sy)
        {
            ans = n * (sx2 + sy2) - sx * sx - sy * sy;
            bes = now;
        }
        return;
    }
    for (int i = las; i < p.size(); i++)
    {
        now.push_back(i);
        dfs(chos + 1, i, sx + p[i].x, sy + p[i].y, sx2 + p[i].x * p[i].x, sy2 + p[i].y * p[i].y);
        now.pop_back();
    }
}
int main()
{
    freopen("out.txt", "w", stdout);
    for (int l = 1; l <= 8; l++)
        for (int k = 1; k <= 30; k++)
        {
            n = l,r = k;
            p.clear();
            now.clear();
            bes.clear();
            int i, s;
            for (i = -r; i <= 0; i++)
            {
                p.push_back(point(i, (int)sqrt(r * r - i * i)));
                while (p.size() > 2 && (p[p.size() - 2] - p[p.size() - 3]) * (p[p.size() - 1] - p[p.size() - 2]) >= 0)
                {
                    p[p.size() - 2] = p[p.size() - 1];
                    p.pop_back();
                }
            }
            s = p.size();
            for (i = s - 2; i >= 0; i--)
                p.push_back(point(-p[i].x, p[i].y));
            for (i = 1; i < s; i++)
                p.push_back(point(-p[i].x, -p[i].y));
            for (i = s - 2; i > 0; i--)
                p.push_back(point(p[i].x, -p[i].y));
            ans = 0;
            dfs(0, 0, 0, 0, 0, 0);
            printf("%d,", ans);
        }
    return 0;
}

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int ans[8][30]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,16,36,64,100,144,196,256,324,400,484,576,676,784,900,1024,1156,1296,1444,1600,1764,1936,2116,2304,2500,2704,2916,3136,3364,3600,8,32,76,130,224,312,416,554,722,896,1064,1248,1512,1746,2016,2264,2600,2888,3218,3584,3912,4344,4712,5138,5612,6062,6536,6984,7520,8084,16,64,144,256,400,576,784,1024,1296,1600,1936,2304,2704,3136,3600,4096,4624,5184,5776,6400,7056,7744,8464,9216,10000,10816,11664,12544,13456,14400,24,96,218,384,624,880,1188,1572,2014,2496,2984,3520,4224,4870,5616,6336,7224,8056,9008,9984,10942,12080,13144,14326,15624,16896,18184,19488,20968,22480,36,144,324,576,900,1296,1764,2304,2916,3600,4356,5184,6084,7056,8100,9216,10404,11664,12996,14400,15876,17424,19044,20736,22500,24336,26244,28224,30276,32400,48,192,432,768,1224,1740,2356,3102,3954,4896,5872,6960,8280,9564,11016,12456,14160,15816,17666,19584,21500,23688,25808,28122,30624,33120,35664,38266,41200,44076,64,256,576,1024,1600,2304,3136,4096,5184,6400,7744,9216,10816,12544,14400,16384,18496,20736,23104,25600,28224,30976,33856,36864,40000,43264,46656,50176,53824,57600};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,r;
        scanf("%d%d",&n,&r);
        printf("%d\n",ans[n-1][r-1]);
    }
    return 0;
}

B.Mask Allocation

题意：

有个口罩，要求装最少的箱，使得在个数平均的情况下，既能分箱分给个医院，也能分给个医院。输出字典序最大输出方案

题解：

令，因为要凑出个医院，因此每箱口罩最多为个。
考虑个医院的情况，上限为，为了使箱数最少，因此要尽可能多的装个，每个医院要箱，因此可以封装个的口罩，还需要个口罩。
再考虑个医院，已经分配了箱的口罩，因此还有的医院需要的口罩。
结合上面两种医院，问题就从变为了，推到就觉得很熟悉，这就是，那照着求的写法写即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 210;
vector<int> ans;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ans.clear();
        int n, m;
        scanf("%d%d", &n, &m);
        int a = min(n, m);
        int b = max(n, m);
        while (a)
        {
            for (int i = 1; i <= b - b % a; i++)
                ans.push_back(a);
            int t = b % a;
            b = a;
            a = t;
        }
        printf("%d\n", ans.size());
        for (auto i : ans)
            printf("%d ", i);
        puts("");
    }
    return 0;
}

C.A National Pandemic

题意：

现在有一棵大小为的树，有个操作，每次有三种操作：
定义为从到的边数
1 位置上的权值，同时所有位置的权值加上
2. 将位置的权值对取个最小值
3. 问位置的权值是多少

题解：

对于操作，只需要令根节点的值即可，那么其他点的权值就是，因为每进行一次操作就要，同时对于节点还要减去，每次的已经用统计了，因此可以用记录操作的次数，结果就是。
但是发现带入根节点到节点路径上的点结果不对，结果不应该是而是，为了使操作统一，可以用树链剖分来维护链，当对进行操作时，让整条链上的值都加上（是因为原来，然后这条链上的需要，），因此结果为，其中表示与路径上每个点的结果之和，但是刚才讨论的其实是对路径上的每条边都，这里用的是对每个点，当然你实现的时候可以用边来表示，只需要把中最后一次换成即可，这里就直接减去了，最终答案为
对于操作，因为每次都只知道根节点的权值，每个点的权值就是直接算的，可以为每个节点设置一个变量，这时每个节点的权值就为，每个算出这个结果与进行比较，如果比就将权值赋给即可
对于操作就是上述的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int head[maxn], dfn[maxn], dep[maxn], siz[maxn], top[maxn], son[maxn], fa[maxn];
int n, m, cnt, tot;
ll ad[maxn], T[maxn << 2], lazy[maxn << 2];
struct Edge
{
    int v, next;
} E[maxn << 1];

void init()
{
    memset(head, -1, sizeof(head));
    memset(son, -1, sizeof(son));
    memset(ad, 0, sizeof(ad));
    memset(T, 0, sizeof(T));
    memset(lazy, 0, sizeof(lazy));
    cnt = tot = 0;
}

void addedge(int u, int v)
{
    E[cnt].v = v;
    E[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs1(int x, int f, int deep)
{
    siz[x] = 1;
    fa[x] = f;
    dep[x] = deep;
    for (int i = head[x]; ~i; i = E[i].next)
    {
        int v = E[i].v;
        if (v == f)
            continue;
        dfs1(v, x, deep + 1);
        siz[x] += siz[v];
        if (son[x] == -1 || siz[son[x]] < siz[v])
            son[x] = v;
    }
}

void dfs2(int x, int tp)
{
    dfn[x] = ++tot;
    top[x] = tp;
    if (son[x] != -1)
        dfs2(son[x], tp);
    for (int i = head[x]; ~i; i = E[i].next)
    {
        int v = E[i].v;
        if (v == fa[x] || v == son[x])
            continue;
        dfs2(v, v);
    }
}
ll pushup(int rt)
{
    T[rt] = T[rt << 1] + T[rt << 1 | 1];
}
void pushdown(int rt, int l, int r)
{
    if (lazy[rt])
    {
        int mid = l + r >> 1;
        T[rt << 1] += (mid - l + 1) * lazy[rt];
        T[rt << 1 | 1] += (r - mid) * lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void update(int l, int r, int L, int R, int rt, ll val)
{
    if (L <= l && r <= R)
    {
        T[rt] += (r - l + 1) * val;
        lazy[rt] += val;
        return;
    }
    pushdown(rt, l, r);
    int mid = l + r >> 1;
    if (R <= mid)
        update(l, mid, L, R, rt << 1, val);
    else if (L > mid)
        update(mid + 1, r, L, R, rt << 1 | 1, val);
    else
    {
        update(l, mid, L, mid, rt << 1, val);
        update(mid + 1, r, mid + 1, R, rt << 1 | 1, val);
    }
    pushup(rt);
}

ll query(int l, int r, int L, int R, int rt)
{
    if (L <= l && r <= R)
        return T[rt];
    pushdown(rt, l, r);
    int mid = l + r >> 1;
    if (R <= mid)
        return query(l, mid, L, R, rt << 1);
    else if (L > mid)
        return query(mid + 1, r, L, R, rt << 1 | 1);
    else
        return query(l, mid, L, mid, rt << 1) + query(mid + 1, r, mid + 1, R, rt << 1 | 1);
}

void modify(int u, int v, ll val)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        update(1, n, dfn[top[u]], dfn[u], 1, val);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])
        swap(u, v);
    update(1, n, dfn[v], dfn[u], 1, val);
}

ll ask(int u, int v)
{
    ll ans = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        ans += query(1, n, dfn[top[u]], dfn[u], 1);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v])
        swap(u, v);
    ans += query(1, n, dfn[v], dfn[u], 1);
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        dfs1(1, 0, 0);
        dfs2(1, 1);
        int num = 0;
        ll val = 0;
        while (m--)
        {
            int op, x, w;
            scanf("%d%d", &op, &x);
            if (op == 1)
            {
                scanf("%d", &w);
                num++;
                modify(1, x, 2);
                val += w - dep[x];
            }
            else if (op == 2)
            {
                ll v = val + ask(1, x) - 1ll * dep[x] * num - query(1, n, 1, 1, 1);
                if (v > ad[x])
                    ad[x] = v;
            }
            else
                printf("%lld\n", val + ask(1, x) - 1ll * dep[x] * num - query(1, n, 1, 1, 1) - ad[x]);
        }
    }
    return 0;
}

D.Fake News

题意：

给定一个，判断是否为一个平方数

题解：

从只有和，因此直接猜了猜就过了QAQ
具体证明

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n;
        scanf("%lld",&n);
        if(n==1||n==24)
            puts("Fake news!");
        else 
            puts("Nobody knows it better than me!");
    }
    return 0;
}

H.Dividing

题意：

正整数二元组 Legend Tuple (n, k) 是这样定义的

  • (1, k) 总是 Legend Tuple
  • 若 (n, k) 是 Legend Tuple, 那么 (n + k, k) 也是
  • 若 (n, k) 是 Legend Tuple, 那么 (nk, k) 也是

统计有多少个 Legend Tuple (n, k) 满足 , 其中和是不超过 的整数

题解：

显然和就为答案
因此答案为。裸的数论分块，考虑到会重复，因此把的贡献单独给出，从开始即可
数论分块

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll f(ll n, ll k)
{
    ll ans = 0;
    for (ll l = 2, r = 0; l <= k; l = r + 1)
    {
        if (n / l == 0)
            break;
        r = n / (n / l);
        r = min(r, k);
        ans += (r - l + 1) % mod * (n / l) % mod;
        ans = ans % mod;
    }
    return ans;
}

int main()
{
    ll n, k;
    scanf("%lld%lld", &n, &k);
    ll ans = n + k - 1;
    ans = (n + k - 1 + f(n, k) + f(n - 1, k)) % mod;
    printf("%lld\n", ans);
    return 0;
}

J.Pointer Analysis

题意：

一个程序中有个对象, 每个对象有个成员指针变量. 同时还有个普通的指针变量. 给定条赋值 语句, 询问在以任意顺序执行每条语句无限多次的过程中, 每个指针变量可能指向的对象集合.
图片说明

题解：

第1、2种操作就是赋值。
对于第3、4种操作，比如 A = B.f ，B.f 说的是 B 指向的对象（所以要判断B是否为空）的成员变量 f ，而这个成员变量 f 指向了另一个对象，与 B 是无关的，搞个三维数组，然后进行赋值。A.f = B 反过来写就是了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans[30][30], a[30][30][30];
char s1[222][5], s2[222][5];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%s%s%s", s1[i] + 1, s2[i] + 1, s2[i] + 1);
    int T = n;
    while (T--)
    {
        for (int i = 1; i <= n; i++)
        {
            int l1 = strlen(s1[i] + 1);
            int l2 = strlen(s2[i] + 1);
            int c1 = s1[i][1] - 'A';
            int c2 = s2[i][1] - 'A';
            if (l1 == l2)
            {
                if (s2[i][1] >= 'a') //A = a
                    ans[c1][s2[i][1] - 'a'] = 1;
                else // A = B
                    for (int j = 0; j < 26; j++)
                        ans[c1][j] |= ans[c2][j];
            }
            else if (l2 >= 3) // A = B.f
            {
                int c3 = s2[i][3] - 'a';     //c3是成员
                for (int j = 0; j < 26; j++) //j是对象
                    if (ans[c2][j])          //k是第二层对象
                        for (int k = 0; k < 26; k++)
                            ans[c1][k] |= a[c3][j][k];
            }
            else // A.f = B
            {
                int c3 = s1[i][3] - 'a';
                for (int j = 0; j < 26; j++)
                    if (ans[c1][j])
                        for (int k = 0; k < 26; k++)
                            a[c3][j][k] |= ans[c2][k];
            }
        }
    }
    for (int i = 0; i < 26; i++)
    {
        printf("%c: ", 'A' + i);
        for (int j = 0; j < 26; j++)
            if (ans[i][j])
                printf("%c", 'a' + j);
        puts("");
    }
    return 0;
}