A、怪盗-1412

签到题,很明显最多的就是这样连续的排序,方案数就很简单算了
一开始数据好像锅了,气的我一个py党直接当场弃坑不打了。因为数据溢出了……打出负数来了吧……

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

int main() {
    int T = read();
    while (T--) {
        ll n = read(), m = read(), k = read();
        printf("%lld\n", n / 2 * m * k * (n - n / 2));
    }
    return 0;
}

B、Dis2

我的思路可能比较落后,一遍建树,对数一次遍历找到节点深度以及直接子节点个数。
那么题目要我们求得就是选定节点,他子节点的直接子节点个数之和,以及父节点直接子节点个数之和减一,在判断深度是不是大于二,大于二累加一。

私货、标答写的挺简单,没有奇奇怪怪的数组,安利一波。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 2e5 + 7; //节点数
const int M = 2e5 + 7; //路径数
const int INF = 0x3f3f3f3f;
int head[N], tot = 0;//前向星变量
int son[N], ans[N];
int father[N], deep[N];
struct Node {
    //int u; //起点
    //int w; //权值
    int v, next;
} edge[M << 1];

void add(int u, int v) {
    tot++;
    //edge[tot].u = u;
    edge[tot].v = v;
    //edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}

void dfs1(int x, int fa) {
    father[x] = fa;
    deep[x] = deep[fa] + 1;
    int cnt = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].v;
        if (y == fa)    continue;
        ++son[x];
        dfs1(y, x);
    }
}

void dfs2(int x, int fa) {
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].v;
        if (y == fa)    continue;
        ans[x] += son[y];
        dfs2(y, x);
    }
    if (father[x])    ans[x] += son[father[x]] - 1;
    if (deep[x] > 2)    ++ans[x];
}

int main() {
    int n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add(u, v); add(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i)
        write(ans[i]), putchar(10);
    return 0;
}

C、序列卷积之和

数论……杀我,菜鸡不会推式子怎么办,一个办法要么猜,要么打表,那么就写个四重循环打个系数表吧。

for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            for (int k = i; k <= j; ++k)
                for (int l = k; l <= j; ++l)
                    ++num[k][l];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            printf("a[%d][%d]=%d\n", j, i, num[j][i]);


再化简一下你就会惊奇的发现下面那个式子!!

a1*(5a1+4a2+3a3+2a4+1a5)+
a2*2*(4a2+3a3+2a4+1a5)+
a3*3*(3a3+2a4+1a5)+
a4*4*(2a4+1a5)+
a5*5a5

找规律应该挺容易的吧,本菜鸡都发现了,)赛后22S才码完……裂开,那么就再处理一下前缀和就可以了。

什么你打表都不会,那没事了,还是去看海绵宝宝吧。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 2e5 + 7;
int num[50][50];
ll a[N];
ll b[N];

int main() {
    int n = read();
    /*for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            for (int k = i; k <= j; ++k)
                for (int l = k; l <= j; ++l)
                    ++num[k][l];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            printf("a[%d][%d]=%d\n", j, i, num[j][i]);*/
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        b[i] = (b[i - 1] + a[i] * (n - i + 1) % MOD) % MOD;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        (ans += a[i] * i % MOD * (b[n] - b[i - 1] + MOD) % MOD) %= MOD;
    write(ans), putchar(10);
    return 0;
}