A.The beautiful values of the palace

题意：

给定一个阶的螺旋矩阵，其中个点是有价值的，个询问，每次询问求出和组成的矩形内的价值图片说明

题解：

通过分析推出公式可以的算出螺旋矩阵每一个点的价值，先求出目标块在哪一圈层，然后判断在所在圈的哪一侧边，分类计算即可。对于求值本质是一个二位前缀和，但是考虑到复杂度求出二位前缀和显然是行不通的。可以对点按x坐标进行升序，这样可以保证这样我们只要求出小于等于的值之和即可。可以用树状数组或者主席树解决。

方法一：主席树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int t, n, m, p, root[N], cnt;
int x1, x2, yz1, yz2;
vector<int> vx, vy;
struct nod {
    int x, y, w;
    bool operator<(const nod &a)const {
        return x < a.x;
    }
} no[N];
struct node {
    int l, r;
    ll sum;
} zxs[N * 40];
ll getn(ll x, ll y)
{
    ll t = min(min(x, y), min(n - x + 1, n - y + 1));
    ll ta = 4 * (t - 1) * (n - t + 1);
    if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
    else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
    else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
    else ta += 3 * n - 7 * t + x + 4;//上侧边
    return ta;
}


ll cal(ll x) {
    ll sum = 0;
    while (x)
        sum += x % 10, x /= 10;
    return sum;
}
void add(int l, int r, int pre, int &now, int pos, ll num) {
    zxs[++cnt] = zxs[pre], now = cnt, zxs[cnt].sum += num;
    if(l == r)
        return;
    int m = (l + r) >> 1;
    if(pos <= m)
        add(l, m, zxs[pre].l, zxs[now].l, pos, num);
    else
        add(m + 1, r, zxs[pre].r, zxs[now].r, pos, num);
}
ll query(int pl, int pr, int l, int r, int L, int R) {
    if(pl <= l && r <= pr)
        return zxs[R].sum - zxs[L].sum;
    ll m = (l + r) >> 1, ans = 0;
    if(pl <= m)
        ans += query(pl, pr, l, m, zxs[L].l, zxs[R].l);
    if(pr > m)
        ans += query(pl, pr, m + 1, r, zxs[L].r, zxs[R].r);
    return ans;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        cnt = 0;
        memset(root, 0, sizeof root);
        scanf("%d%d%d", &n, &m, &p);
        vx.clear(), vy.clear();
        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &no[i].x, &no[i].y);
            no[i].w = cal(getn(no[i].x, no[i].y));
            vx.push_back(no[i].x), vy.push_back(no[i].y);
        }
        sort(no + 1, no + m + 1);
        sort(vx.begin(), vx.end());//vx不能erase，因为下面二分查询的是vx的位置，erase后位置少了就不准了。
        sort(vy.begin(), vy.end()), vy.erase(unique(vy.begin(), vy.end()), vy.end());
        int sz = vy.size();
        for(int i = 1; i <= m; i++) {
            int ny = lower_bound(vy.begin(), vy.end(), no[i].y) - vy.begin() + 1;
            add(1, sz, root[i - 1], root[i], ny, no[i].w);
        }
        while(p--) {
            //由于y坐标离散化的是他们的值，所以相同值离散化后是一样的
            scanf("%d%d%d%d", &x1, &yz1, &x2, &yz2);//下面二分的是位置，lx,ly要用lower_bound计算离散化后的位置
            int lx = lower_bound(vx.begin(), vx.end(), x1) - vx.begin() + 1;
            int ly = lower_bound(vy.begin(), vy.end(), yz1) - vy.begin() + 1;
            //这里用upper_bound是为了查找下一个位置，防止和lx相同
            int rx = upper_bound(vx.begin(), vx.end(), x2) - vx.begin();
            //这里的upper_bound也是查找下一个位置，和x一样，但不能用
            //lower_bound(vy.begin(), vy.end(), no[i].y) - vy.begin() + 1;
            //因为如果这样的话，当yz2恰好是一个没有点在上面的坐标，所以要找离它最近的而且比它小的坐标，
            //若比它大，则多计算了就
            int ry = upper_bound(vy.begin(), vy.end(), yz2) - vy.begin();
            printf("%lld\n", query(ly, ry, 1, sz, root[lx - 1], root[rx]));
        }
    }
    return 0;
}

方法二：树状数组

#include <bits/stdc++.h>
#define maxn 1000005
#define lowbit(x) ((x)&(-x))
#define _for(i, a) for(LL i = 0; i < (a); i++)
#define _rep(i, a, b) for(LL i = (a); i <= (b); i++)
typedef long long LL;
using namespace std;

struct poi {
    LL x, y, flag, pos, val;
    poi() {}
    poi(LL x, LL y, LL flag, LL pos, LL val) :x(x), y(y), flag(flag), pos(pos), val(val) {}
    bool operator < (poi t) {
        if (x != t.x) return x < t.x;
        if (y != t.y) return y < t.y;
        return pos < t.pos;
    }
};

LL getval(LL x, LL y, LL n) {
    LL t = min(min(x, y), min(n - x + 1, n - y + 1));
    LL ta = 4 * (t - 1) * (n - t + 1);
    if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
    else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
    else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
    else ta += 3 * n - 7 * t + x + 4;//上侧边
    return ta;
}

LL T[maxn * 2];

LL getnum(LL x, LL n) {
    LL ans = 0;
    while (x > 0) {
        ans += T[x];
        x -= lowbit(x);
    }
    return ans;
}

void upd(LL x, LL y, LL n) {
    while (x <= n) {
        T[x] += y;
        x += lowbit(x);
    }
}

LL n, m, p;
LL cnt = 0;
poi a[maxn * 2];
LL ans[maxn];

void init() {
    //初始化
    memset(T, 0, sizeof(T));
    memset(ans, 0, sizeof(ans));
    cnt = 0;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        init();

        cin >> n >> m >> p;
        _for(i, m) {
            //求出点的美丽值 并把点压入队列
            LL x, y;
            cin >> x >> y;
            LL tt = getval(x, y, n), _tem = 0;
            while (tt) {//求出美丽值
                _tem += tt % 10;
                tt /= 10;
            }
            a[cnt++] = poi(x, y, 0, i, _tem);
        }
        _rep(i, m, m + p - 1) {
            //把区间拆解为4个前缀和，一块压入队列，用flag区分是加还是减
            LL x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            a[cnt++] = poi(x1 - 1, y1 - 1, 1, i, 0);
            a[cnt++] = poi(x2, y1 - 1, -1, i, 0);
            a[cnt++] = poi(x1 - 1, y2, -1, i, 0);
            a[cnt++] = poi(x2, y2, 1, i, 0);
        }
        sort(a, a + cnt);

        //以时间来区分x，以树状数组来区分y
        _for(i, cnt) {
            if (a[i].pos < m) {
                //说明是点，不是区间
                upd(a[i].y, a[i].val, n);
            }
            else {
                //是区间，要我们求前缀和
                ans[a[i].pos - m] += getnum(a[i].y, n) * a[i].flag;
            }
        }
        _for(i, p) {
            cout << ans[i] << "\n";
        }
    }
    return 0;
}

B.super_log

题意：

图片说明 求最小的正整数x，使得图片说明

题解：

通过将递归式展开，展开次等于，所以为图片说明 （共 次）。根据欧拉降幂公式图片说明 。对进行重写则可以将与当作互素，从而不用讨论b与图片说明 的大小关系。
要注意这样做：
1、 快速幂和cal函数都要换成；
2、 最终答案需要模。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1001000;
int phi[maxn] = {0, 1};
ll mm(ll x, ll m)
{
    return x < m ? x : x % m + m;
}
ll pow64(ll a, ll b, ll m)
{
    ll result = 1;
    while (b)
    {
        if (b & 1)
            result = mm(result * a, m);
        a = mm(a * a, m);
        b >>= 1;
    }
    return result;
}
void caleuler()
{
    for (int i = 2; i < maxn; i++)
        if (!phi[i])
            for (int j = i; j < maxn; j += i)
            {
                if (!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
}
int t, a, b, m;
int calc(int a, int b, int m)
{
    if (m == 1)
        return 1;
    if (!b)
        return 1;
    int p = phi[m];
    int x = calc(a, b - 1, p);
    return pow64(a, x, m);
}
int main()
{
    caleuler();
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        scanf("%d%d%d", &a, &b, &m);
        printf("%d\n", calc(a, b, m) % m);
    }
    return 0;
}

转载至博客
同时贴上另一个博主总结的知识点
图片说明

D. Robots

题意：

给定一个个点条边的有向图，现在要从号结点走到号结点。对于每个点，其走向下一个点与在当前点停留不动的概率均等，第天的花费是，问走到第号结点的期望是多少

题解：

由于走向下一个点与在当前点停留不动的概率均等，那么假设点的出度为，其停留不动与走向其一个邻接点的概率为
假设从号点走到号点的期望时间为，那么花费为，可分为 与两部分

表示结点到的期望花费时间，表示结点的平方期望花费时间
又由
因此
化简可得

因此从开始反向建图，求一遍拓扑排序即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int deg[maxn];
double dp1[maxn], dp2[maxn], p[maxn];
vector<int> G[maxn];
void Topsort(int s)
{
    stack<int> st;
    st.push(s);
    while (!st.empty())
    {
        int u = st.top();
        st.pop();
        for (auto v : G[u])
        {
            deg[v]--;
            dp1[v] += p[v] * (dp1[u] + 1.0);
            dp2[v] += p[v] * (dp2[u] + 2 * dp1[u] + 1.0);
            if (!deg[v])
            {
                dp2[v] += p[v] * (2 * dp1[v] + 1);
                st.push(v);
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            dp1[i] = 0, dp2[i] = 0, p[i] = 0, deg[i] = 0, G[i].clear();
        for (int i = 0; i < m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            G[v].push_back(u);
            deg[u]++;
        }
        for (int i = 1; i <= n; i++)
        {
            if (deg[i])
            {
                p[i] = 1.0 / deg[i];
                dp1[i] += p[i];
            }
        }
        Topsort(n);
        printf("%.2lf\n", dp1[1] / 2.0 + dp2[1] / 2.0);
    }
    return 0;
}

F.Greedy Sequence

题意：

给定一个的序列，要求构造递增序列，要求，，同时要求字典序最大，求每个序列的长度

题解：

从开始，用记录的长度，那么对于只需要从到找到最大的满足，。同时发现，找到最大的只需要用线段树query(1,1,n,i-k,i+k)即可
暴力：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
map<int, int> mp;
int f[maxn];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        mp.clear();
        for (int i = 1, x; i <= n; i++)
        {
            scanf("%d", &x);
            mp[x] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            f[i] = 1;
            for (int j = i - 1; j >= 1; j--)
            {
                if (abs(mp[i] - mp[j]) <= k)
                {
                    f[i] += f[j];
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i++)
            printf("%d%c", f[i], i == n ? '\n' : ' ');
    }
    return 0;
}

线段树：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;

int n, k, m, l, r, now, sum;
int node[maxn << 2], lazy[maxn << 2];

void pushup(int rt)
{
    node[rt] = max(node[rt << 1], node[rt << 1 | 1]);
}

void build(int rt, int l, int r)
{
    node[rt] = 0;
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void update(int rt, int l, int r, int pos, int val)
{
    if (l == r)
    {
        node[rt] = val;
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
        update(rt << 1, l, mid, pos, val);
    if (pos > mid)
        update(rt << 1 | 1, mid + 1, r, pos, val);
    pushup(rt);
}
int query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return node[rt];
    int mid = l + r >> 1;
    int ans = 0;
    if (L <= mid)
        ans = max(ans, query(rt << 1, l, mid, L, R));
    if (mid < R)
        ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
}
map<int, int> mp;
int f[maxn];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        mp.clear();
        build(1,1,n);
        for (int i = 1, x; i <= n; i++)
        {
            scanf("%d", &x);
            mp[x] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            f[i] = 1;
            int x = query(1,1,n,mp[i]-k,mp[i]+k);
            f[i]+=f[x];
            update(1,1,n,mp[i],i);
        }
        for (int i = 1; i <= n; i++)
            printf("%d%c", f[i], i == n ? '\n' : ' ');
    }
    return 0;
}

H.Holy Grail

题意：

给出一个个点，条边的有向图，再给组询问，每组询问要求在间建一条权值最小的边，使图中没有负环。题目保证有解。

题解：

保证有解那么原来图中不会存在负环，那么负环只可能在添加新边的时候产生，因此边的最小边权就是最短路的相反数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int maxm = 2005;
const ll INF = 1ll << 40;
int n, m;
struct Edge
{
    int to, next;
    ll w;
} edge[maxm];
int head[maxn], tot;
inline void init()
{
    for (int i = 0; i < maxm; i++)
        edge[i].next = 0;
    for (int i = 0; i < maxn; i++)
        head[i] = -1;
    tot = 0;
}
inline void addedge(int u, int v, ll w)
{
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
queue<int> q;
ll dis[maxn];
int inq[maxn];
void spfa(int u)
{
    for (int i = 0; i < maxn; i++)
        dis[i] = INF;
    dis[u] = 0;
    inq[u] = 1;
    q.push(u);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for (int i = head[x]; ~i; i = edge[i].next)
        {
            int y = edge[i].to;
            ll z = edge[i].w;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z; //更新最短路
                if (!inq[y])
                {
                    inq[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            ll w;
            scanf("%d%d%lld", &u, &v, &w);
            addedge(u, v, w);
        }
        for (int i = 1; i <= 6; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            spfa(v);
            addedge(u, v, -dis[u]);
            printf("%lld\n", -dis[u]);
        }
    }
    return 0;
}