2018年7月

数颜色

本该是暑假集训的高级数据结构的练习题,按照出题大佬的本意要用树套树做的,然而那玩意太麻烦了不会写于是学了学传闻中能解决一切区间问题的莫队算法。具体的使用在我题目中写的注释很详细网上也有很多莫队算法的教程我就不展开说明了。

学习笔记:

  • 不带修改的分块每块大小:sqrt(n),理论时间复杂度O(n*sqrt(n))
  • 带单点修改的分块大小:n2/3,理论时间复杂度O(n5/3)
  • 单点修改的修改过程记录修改前和修改后的值而不是初始值和修改后的值
  • 排序关键字:左区间所在块号,右区间所在块号,修改的时间(如果存在修改)
  • 主要结构

    • 状态转移函数

      • 区间转移(步长为1)
      • 时间转移(步长为1)
    • 数据读入
    • 询问(修改)排序
    • 对询问循环

      • 对时间进行状态转移
      • 对区间进行转移
      • 记录当前询问的答案
    • 输出答案

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题解

高档题。题意大概是单点修改和区间查询,区间查询要求得到某一区间内的颜色数。
套可持久化的莫队算法。

代码

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

const int N = 10005;
const int COLORNUM = 1000005;

struct Query {
    int l, r, time, id;
}q[N];//询问情况
struct Change {
    int pos, New, Old; 
}c[N];//改变情况
int n, m;
int s[N], color[COLORNUM], now[N],ans[N];//s初始输入 now记录某次变量转移后的情况 color记录某种颜色的数量情况 ans记录询问的答案情况
int t, Time, unit, Ans, l(1), r, T;//t记录询问次数 Time记录更改次数 unit记录单元大小 Ans记录当前区间与修改时间的答案 l,r记录当前区间左右端点 T记录当前修改到具体某一次

inline int whichUnit(int a) {//判断当前位置处于哪一个unit
    return a / unit + 1;
}

inline bool cmp(Query a, Query b)//以区间左,右端点,询问时间排序,其中左,右端点分别以unit来划分;
{
    return whichUnit(a.l) == whichUnit(b.l) ? (whichUnit(a.r) == whichUnit(b.r) ? a.time<b.time : a.r<b.r) : a.l<b.l;
}

inline void revise(int x, int d) {//转移状态,以某次区间修改转移
    color[x] += d; 
    if (d>0)Ans += color[x] == 1;
    if (d<0)Ans -= color[x] == 0;
}

inline void going(int x, int d) {//转移状态,以某次颜色修改转移
    if (l <= x && x <= r) {
        revise(d, 1);
        revise(s[x], -1);
    }
    s[x] = d;
}

int main() {
    scanf("%d%d", &n, &m);
    unit = pow(n, (double)2 / 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        now[i] = s[i];
    }
    for (int i = 1; i <= m; i++) {
        char type; 
        int x, y; 
        scanf(" %c %d%d", &type, &x, &y);
        if (type == 'Q')q[++t] = Query{ x, y, Time, t };
        if (type == 'R')c[++Time] = Change{ x, y, now[x] }, now[x] = y;
    }
    sort(q + 1, q + t + 1, cmp);

    for (int i = 1; i <= t; i++)
    {
        while (T<q[i].time)going(c[T + 1].pos, c[T + 1].New), T++;
        while (T>q[i].time)going(c[T].pos, c[T].Old), T--;

        while (l<q[i].l)revise(s[l], -1), l++;
        while (l>q[i].l)revise(s[l - 1], 1), l--;
        while (r<q[i].r)revise(s[r + 1], 1), r++;
        while (r>q[i].r)revise(s[r], -1), r--;

        ans[q[i].id] = Ans;
    }
    for (int i = 1; i <= t; i++)
        printf("%d\n", ans[i]);
}

F. Mars rover

题目链接

Codeforces Round #499 (Div. 2)--F. Mars rover

题解

高档题。题意大概是给定一个图,每个节点可能包含 AND (2 inputs), OR (2
inputs), XOR (2 inputs), NOT (1 input) 四种情况,除此之外还有 IN 节点作为输入。所有输入经过一系列逻辑运算后将得到一个输出。现给定这些输入,求改变每个输入节点后输出节点的值。

首先从将每个节点对初始输入的值所表达的值求出来。
之后将输出标记为重要,并从输出节点开始对每个节点标记,标记规则如下:

  • 如果该节点为不重要,则它的输入节点均为不重要
  • 如果该节点为重要,若改变某一输入节点的值该节点的值改变,则这一输入节点为重要,否则这一输入节点为不重要。

最后判断每个输入节点是否为重要节点,如果是则输出输出节点原本的值的否,如果不是则输出输出节点原本的值。

一定要注意逻辑运算符的优先级,我被这个坑了几十分钟。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, k, q1;
struct MyStruct
{
    bool self, isimportant;
    int in1, in2;
    int type;//and=0,or=1,xor=2,not=3,in=4
} a[1000005];
char s[5];
vector<int>inputs;

void pd(int i) {
    if (a[i].type == 4)return;
    if (a[i].isimportant == false) {
        a[a[i].in1].isimportant = false;
        pd(a[i].in1);
        if (a[i].type != 3) {
            a[a[i].in2].isimportant = false;
            pd(a[i].in2);
        }
    }
    else {
        if (a[i].type == 0) {
            if (((!a[a[i].in1].self)&(a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self)&(a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 1) {
            if (((!a[a[i].in1].self) | (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) | (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 2) {
            if (((!a[a[i].in1].self) xor (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) xor (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 3) {
            a[a[i].in1].isimportant = true;
            pd(a[i].in1);
        }
    }
}



bool fill(int i) {
    switch (a[i].type) {
    case 4:
        return a[i].self;
    case 0:
        a[i].self = fill(a[i].in1) & fill(a[i].in2);
        return a[i].self;
    case 1:
        a[i].self = fill(a[i].in1) | fill(a[i].in2);
        return a[i].self;
    case 2:
        a[i].self = fill(a[i].in1) xor fill(a[i].in2);
        return a[i].self;
    case 3:
        a[i].self = !fill(a[i].in1);
        return a[i].self;
    }
}

int main() {
    memset(a, 0, sizeof(a));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%s", &s);
        if (s[0] == 'A') {
            a[i].type = 0;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'O') {
            a[i].type = 1;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'X') {
            a[i].type = 2;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'N') {
            a[i].type = 3;
            scanf("%d", &a[i].in1);
        }
        else if (s[0] == 'I') {
            a[i].type = 4;
            scanf("%d", &a[i].in1);
            a[i].self = a[i].in1;
            inputs.push_back(i);
        }
    }

    fill(1);
    a[1].isimportant = true;
    pd(1);

    for (auto i : inputs) {
        if (a[i].isimportant) printf("%d", !a[1].self);
        else printf("%d", a[1].self);
    }
}

E. Border

题目链接

Codeforces Round #499 (Div. 2)--E. Border

题解

高档题。题意大概是对于n个数与k进制,求出a1b1+a2b2+...+an*bn模k所得的可能的数,其中ai为给定的数,bi为任意非负整数。

将所有给定的数字取最大公约数即为我们所要考虑的最小的单元,假设所得的数为a,则ab(b为任意非负整数)模k可能的数的数量为k/gcd(a,k),即只要依次标记并输出0a,2a,...,(k/gcd(a,k)-1)a即可。

代码

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
int a, q1;
bool output[100005];

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    cin >> n >> k;
    scanf("%d", &a);
    n--;
    while (n--) {
        scanf("%d", &q1);
        a = gcd(a, q1%k);
    }

    q1 = 0;
    for (int i = 1; i <= k / gcd(a, k); i++) {
        q1 += a;
        output[q1%k] = true;
    }

    cout << k / gcd(a, k) << endl;
    for (int i = 0; i < k; i++) {
        if (output[i])cout << i << ' ';
    }
}

D. Rocket

题目链接

Codeforces Round #499 (Div. 2)--D. Rocket

题解

中档题,交互题。题意大概是通过多次询问求出一个距离,距离小于等于一个给定的最大值,返回值包含了询问与答案的大小关系的信息。返回值有可能是错误的,返回的答案是否正确取决于一个长度不超过30的数组,数组长度已知,这个数组循环使用,如果当前位置的值为1返回正确答案,若为0返回错误答案。

注意到数据规模小于230,询问次数不大于60次。我们首先以最大值询问数组长度的次数,得到数组的信息,之后再通过二分来求出正确答案,极限情况下刚好询问次数为60次。

我的代码懒得写二分怕错不过原理差不多,注意询问的值不能超过最大值否则会返回Wrong Answer,我因此跪了七八次。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int m, n, q1;
int p[31], pow2[31];

int main()
{
    cin >> m >> n;
    pow2[0] = 1;
    for (int i = 1; i < 31; i++) {
        pow2[i] = pow2[i - 1] << 1;
    }
    for (int i = 0; i < n; i++) {
        printf("%d\n", m);
        fflush(stdout);
        scanf("%d", &q1);
        if (q1 == -1) p[i] = 1;
        else if (q1 == 1) p[i] = 0;
        else return 0;
    }
    int ans = 0;
    int num = 0;
    for (int i = 29; i >= 0; i--) {
        if (ans + pow2[i]>m)continue;
        printf("%d\n", ans + pow2[i]);
        fflush(stdout);
        scanf("%d", &q1);
        if (p[num%n] == 0)q1 = -q1;
        if (q1 == 1) {
            ans += pow2[i];
        }
        else if (q1 == 0) {
            return 0;
        }
        num++;
    }
    printf("%d\n", ans);
}

C. Fly

题目链接

Codeforces Round #499 (Div. 2)--C. Fly

题解

简单题。题意大概是一个火箭要飞往多个星球,起飞与降落需要与重量(包含火箭自身及燃料)及某个给定系数相关的燃料,求最小所需的燃料。

由给定的燃料消耗公式从终点逆推回起点,假设飞达后重量为m,系数为a,则本次飞行小号燃料为m/(a-1),飞行前总重量为m+m/(a-1)。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const double w = 0.0000001;
int n;
double ans, m, q1;
double a[1005], b[1005];

int main()
{
    cin >> n >> m;
    double pre = m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (fabs(a[i] - 1)<w) {
            cout << -1; return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        if (fabs(b[i] - 1)<w) {
            cout << -1; return 0;
        }
    }
    for (int i = n; i >= 1; i--) {
        q1 = m / (b[i%n] - 1);
        m += q1;
        q1 = m / (a[i - 1] - 1);
        m += q1;
    }
    printf("%.10lf", m - pre);
}

B. Planning The Expedition

题目链接

Codeforces Round #499 (Div. 2)--B. Planning The Expedition

题解

简单题。题意大概是有m种食物,每种食物有若干份,n个人取食物且每个人只能取一种食物,求n个人中拿最少的人拿多少份。

注意到数据规模只有可怜的100,从100到0枚举一遍即可。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, m;
int a[105], b[105];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        b[a[i]]++;
    }
    for (int i = 100; i >= 1; i--) {
        int temp = 0;
        for (int j = 1; j <= 100; j++) {
            temp += b[j] / i;
        }
        if (temp >= n) {
            cout << i;
            return 0;
        }
    }
    cout << 0;    
}

A. Stages

题目链接

Codeforces Round #499 (Div. 2)--A. Stages

题解

简单题。题意大概是给定一组小写字母,每个字母的权重为ai-'a'+1。要求出一个序列满足对于任意ai,ai+1-ai>=2,输出权重之和。

记录每个字母有无出现,直接贪心一遍能取则取即可。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, k, now, ans, num;
string s;
bool a[233];

int main()
{
    cin >> n >> k >> s;
    for (auto i : s) {
        a[i - 'a' + 1] = true;
    }
    now = -1;
    for (int i = 1; i <= 26; i++) {
        if (i > now + 1 && a[i]) {
            now = i;
            ans += i;
            num++;
        }
        if (num == k)break;
    }
    if (num == k)cout << ans;
    else cout << -1;
}

E. Intercity Travelling

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--E. Intercity Travelling

题解

高档题。题意大概是某人从x=0旅行至x=n,在上次休息过后走当前公里的疲劳值为ai,休息点的位置不确定,求疲劳值之和的数学期望。
对于某个位置x=i,疲劳值为ai的可能休息点情况数为2^(n-i)种,疲劳值为aj(j<i)的可能休息点情况数为2^(n-i-1)种。处理过后发现对于某个疲劳值ai,其总的出现情况数为2^(n-i)+2^(n-i-1)*(n-i)。之后直接套公式即可。

代码

#include <iostream>
using namespace std;
const long long mod = 998244353;
long long n;
long long a[1000005];
long long b[1000005];
long long ans(0);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    b[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        b[i] = (b[i - 1] << 1) % mod;
    }
    for (int i = 1; i <= n; i++) {
        ans += a[i] * b[n - i] % mod;
        ans += a[i] * b[n - i - 1] % mod * (n - i) % mod;
    }
    cout << ans % mod;
}

D. Relatively Prime Graph

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--D. Relatively Prime Graph

题解

中档题。题意大概是要求构成n个点m条边个图。图要求满足联通,每个边连接的两个点最大公约数为1,没有重边自环。
如果m<n-1图不联通,否则直接两重循环判断如果最大公约数为1则连接两点。

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
vector <pair<int, int>> v;
int n, m;
int main() {
    cin >> n >> m;
    if (m < n - 1) { 
        cout << "Impossible"; 
        return 0;
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1)v.push_back({ i,j });
            if (v.size() == m) {
                cout << "Possible" << endl;
                for (auto k : v) {
                    cout << k.first << ' ' << k.second << endl;
                }
                return 0;
            }
        }
    }
    cout << "Impossible";
}

C. Annoying Present

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--C. Annoying Present

题解

简单题。题意大概是给定一个长度为n初始值均为0的数组。对数组做m次操作后求数组算术平均值的最大值。
操作输入x,d,操作为a[j]+x+d*dist(i,j),i为可以选择的某个位置。
分析后发现操作后数组之和的变化与原数组无关,当d大于0时i选择1或n数组之和最大,当d小于0时i选择trunc((1+n)/2)数组之和最大。由此对于每次操作直接用等差数列公式计算即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;

long long n, m;
long long ans, x, d;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> d;
        ans += x * n;
        if (d > 0) {
            ans += d * n * (n - 1) / 2;
        }
        else {
            ans += ((n % 2 == 0) ? (n / 2 * n / 2 * d) : ((n + 1) / 2 * (n - 1) / 2 * d));
        }
    }
    printf("%.20lf",(double)ans / n);
}