2020 ccpc 威海

目录

A. Golden Spirit

大意:

一座桥桥两侧各有 n 个老人,每个老人都需要去桥对面休息 x 分钟后再返回,背一个人过桥一次需要t分钟,最少需要多少分钟使所有老人都完成休息

思路:

模拟,需要判断将所有老人都送到彼此的对面之后,第一个开始休息的老人能否开始回去,能的话直接开始送他回去,否则则需要判断是留在左边等这个老人还是去对面等第二个老人

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
long long  t, n, x, sum,T;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>x>>t;
        sum = 0;
        if(x<(2*n*t-2*t)){
            sum = 4 * n * t;
        }
        else{
            long long sum1, sum2;
            sum1 = 4 * n * t + (x - 2 * n * t + 2 * t);
            if(x>(2*n*t)){
                sum2 = 2 * n * t + t + (x - 2 * n * t) + 2 * n * t;
            }
            else{
                sum2 = 2 * n * t + t + 2 * n * t;
            }
            sum = min(sum1, sum2);
        }
        cout << sum << endl;
    }
    return 0;
}

C. Rencontre

大意:

给出一棵带权树,记 \(f( u1 , u2 , u3 )=min_{v \in T}(dis(u1,v)+dis(u2,v)+dis(u3,v))\),由于u1、u2、u3不确定,因此确定三个点 u1 , u2 , u3 后,需要找到一个点 v 到三个点的距离之和最小,现在给出 u1 , u2 , u3 的可行取值,问 f 函数的期望是多少。

思路:

对于给定的三个点$ u1 , u2 , u3 \(,可以确定唯一的点\)v$使得距离最小,为\(1/2*((dis(u1,u2)+dis(u2,u3)+dis(u3,u1))\)

那么问题可以转化为\(1/2*(E(dis(u1,u2)+E(dis(u2,u3))+E(dis(u3,u1)))\)

而对于\(E(dis(u,v))\),有:\(E(dis(u1,u2))= \frac { \sum_{x \in {u_1} }\sum_{y \in {u_2} }dis(x,y)}{|u_1||u_2|}\)

所以可以根据每条边的贡献来求,对于每条边,计算他左右属于不同集合的点的数量,然后乘上权值即可

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
typedef long long LL;
int n;
LL size[N][5],cnt[N];
double res = 0;
vector<pair<LL, LL>> mp[N];
void dfs1(int now,int fa){
    //cout << now << ' ' << fa << endl;
    for (int i = 0; i < mp[now].size();i++){
        LL ne = mp[now][i].first;
        if(ne==fa){
            continue;
        }
        dfs1(ne, now);
        for (int j = 0; j < 3;j++){
            size[now][j] += size[ne][j];
        }
    }
}

void dfs2(int now,int fa){
    for (int i = 0; i < mp[now].size();i++){
        LL ne = mp[now][i].first;
        LL w = mp[now][i].second;
        if(ne==fa){
            continue;
        }
        dfs2(ne, now);
        for (int j = 0; j < 3;j++){
            for (int k = 0; k < 3;k++){
                if(j!=k){
                    res += 1.0 * (size[1][j] - size[ne][j]) * 1.0 * (size[ne][k]) * 1.0 * w / cnt[j] / cnt[k] / 2.0;
                }
            }
        }
    }
}

int main(){
    cin >> n;
    for (int i = 1; i < n;i++){
        LL x, y,w;
        cin >> x >> y >> w;
        mp[x].push_back({y,w});
        mp[y].push_back({x,w});
    }
    for (int i = 0; i < 3;i++){
        int num;
        cin >> num;
        cnt[i] = num;
        for (int j = 0; j < num;j++){
            int x;
            cin >> x;
            size[x][i]++;
            //cout << x << ' ' << size[x][i] << endl;
        }
    }
    
    dfs1(1, 0);
    dfs2(1, 0);
    printf("%.10f\n",res);
    return 0;
}

D.ABC Conjecture

大意: 给定一个c,范围1e18.问是否能够产生a、b,使得c=a+b且rad(abc)<c。rad(n)为n的素数乘积

思路: 如果一个数字分解质因数后所有素数的次数都为1,那么no;否则yes

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int t;
LL n;
const int maxn = 10000;
const int S = 20;
LL factor[maxn];
int tot;  // 记录有几个质因子

//返回(a * b) % c,a,b,c<2^63
LL multi_mod(LL a, LL b, LL c) {
    a %= c;
    b %= c;
    LL ret = 0;
    while(b) {
        if (b & 1) {
            ret += a;
            if (ret >= c) ret -= c;
        }
        a <<= 1;
        if(a >= c) a -= c;
        b >>= 1;
    }
    return ret;
}

//返回x^n mod c ,非递归版
LL pow_mod(LL x, LL n, LL mod) {
    LL ret = 1;
    while(n) {
        if(n & 1) ret = multi_mod(ret, x, mod);
        x = multi_mod(x, x, mod);
        n >>= 1;
    }
    return ret;
}

//以a为基,n-1=x*2^t,检验n是不是合数
bool check(LL a, LL n, LL x, LL t) {
    LL ret = pow_mod(a, x, n), last = ret;
    for (int i = 1; i <= t; i++) {
        ret = multi_mod(ret, ret, n);
        if (ret == 1 && last != 1 && last != (n-1)) return 1;
        last = ret;
    }
    if (ret != 1) return 1;
    return 0;
}

/*素数测试*/
bool Miller_Rabin(LL n) {
    LL x = n - 1, t = 0;
    while ((x & 1) == 0) x >>= 1, t++;
    bool flag = 1;
    if (t >= 1 && (x & 1) == 1) {
        for(int k = 0; k < S; k++) {
            LL a = rand()%(n-1) + 1;
            if (check(a, n, x, t)) {
                flag = 1; break;
            }
            flag = 0;
        }
    }
    if (!flag || n == 2) return 0;
    return 1;
}

LL gcd(LL a,LL b) {
    if (a == 0) return 1;
    if (a < 0) return gcd(-a, b);
    while (b) {
        LL t = a % b;
        a = b;
        b = t;
    }
    return a;
}

/*大整数素因子分解*/
LL Pollard_rho(LL x, LL c) {
    LL i = 1, x0 = rand() % x, y = x0, k = 2;
    while(1) {
        i++;
        x0 = (multi_mod(x0, x0, x) + c) % x;
        LL d = gcd(y - x0, x);
        if (d != 1 && d != x) {
            return d;
        }
        if (y == x0) return x;
        if (i == k) {
            y = x0;
            k += k;
        }
    }
}

//递归进行质因数分解N
// 输入n为要质因数分解的大整数,质因数分解完后tot为质因数个数,factor存储分解后得到的质因数
// 使用pollard_rho随机算法
void findfac(LL n) {
    if (!Miller_Rabin(n)) {
        factor[tot++] = n;  
        return;
    }
    LL p = n;
    while(p >= n) p = Pollard_rho(p, rand() % (n-1) + 1);
    findfac(p);
    findfac(n / p);
    return ;
}
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        if(n==1){
            cout<<"no"<<endl;
            continue;
        }
        tot = 0;
        findfac(n);
        set<LL> s;
        int flag = 0;
        for (int i = 0; i < tot;i++){
            if(s.count(factor[i])){
                flag = 1;
                break;
            }
            s.insert(factor[i]);
        }
        if(flag){
            cout << "yes" << endl;
        }
        else{
            cout << "no" << endl;
        }
    }
    return 0;
}

G.Caesar Cipher

大意: 给定一个数组 ,范围为 [0,65536),有以下两种操作:

  1. 给出 x , y 把 [x , y] 内的每个数 + 1 同时对 65536 取模。
  2. 给出 x,y,L , 查询区间 [x , x + L - 1] 和区间 [y , y + L - 1]是否完全相同。

思路:

哈希+线段树

看队友博客吧,具体不想写了:

https://blog.csdn.net/m0_49959202/article/details/110440308

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int const N = 5e5 + 10, mod = 1e9 + 7;
int n, m, T, base = 131;
int Hash[N << 2], lazy[N << 2], maxv[N << 2], a[N], sum[N], p[N];

void pushup(int u, int l, int r) {
    int mid = l + r >> 1;
    int len_r = r - mid;
    Hash[u] = (Hash[u << 1] * (LL)p[len_r] % mod + Hash[u << 1 | 1]) % mod;
    maxv[u] = max(maxv[u << 1], maxv[u << 1 | 1]);
    return;
}

void build(int u, int l, int r) {
    if (l == r) {
        Hash[u] = a[l];
        lazy[u] = 0;
        maxv[u] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u, l, r);
}

void pushdown(int u, int l, int r) {
    if (!lazy[u]) return;
    int mid = (l + r) >> 1;
    int len_l = mid - l + 1, len_r = r - mid;
    Hash[u << 1] = (Hash[u << 1] + (LL)lazy[u] * sum[len_l - 1] % mod) % mod;
    Hash[u << 1 | 1] = (Hash[u << 1 | 1] + (LL)lazy[u] * sum[len_r - 1] % mod) % mod;
    maxv[u << 1] = (maxv[u << 1] + lazy[u]) % mod;
    maxv[u << 1 | 1] = (maxv[u << 1 | 1] + lazy[u]) % mod;
    lazy[u << 1] = (lazy[u << 1] + lazy[u]) % mod;
    lazy[u << 1 | 1] = (lazy[u << 1 | 1] + lazy[u]) % mod;
    lazy[u] = 0;
    return;
}

void modify(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        Hash[u] = (Hash[u] + sum[r - l]) % mod;
        maxv[u] = (maxv[u] + 1) % mod;
        lazy[u] = (lazy[u] + 1) % mod;
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) modify(u << 1, l, mid, L, R);
    if (mid < R) modify(u << 1 | 1, mid + 1, r, L, R);
    pushup(u, l, r);
    return;
} 

void modify2(int u, int l, int r) {
    if (maxv[u] < 65536) return;
    if (l == r) {
        maxv[u] -= 65536;
        Hash[u] -= 65536;
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (maxv[u << 1] >= 65536) modify2(u << 1, l, mid);
    if (maxv[u << 1 | 1] >= 65536) modify2(u << 1 | 1, mid + 1, r);
    pushup(u, l, r);
    return;
}

LL query(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return Hash[u];
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    LL res = 0;
    if (L <= mid) res = query(u << 1, l, mid, L, R) % mod;
    if (mid < R) res = (res * (LL)p[max(0, min(r, R)) - mid] % mod + query(u << 1 | 1, mid + 1, r, L, R)) % mod;
    return res;
}

int main() {
    cin >> n >> m;
    p[0] = sum[0] = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        p[i] = (LL)p[i - 1] * base % mod;
        sum[i] = (sum[i - 1] + p[i]) % mod;
    }
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int op, a, b;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &a, &b);
            modify(1, 1, n, a, b);
            modify2(1, 1, n);
        }
        else {
            int l1, r1, l2, r2, len;
            scanf("%d%d%d", &l1, &l2, &len);
            r1 = l1 + len - 1, r2 = l2 + len - 1;
            int t1 = query(1, 1, n, l1, r1);
            int t2 = query(1, 1, n, l2, r2);
            if (t1 == t2) puts("yes");
            else
                puts("no");
        }
    }
    return 0;
}

H. Message Bomb

大意:

n个小组,m个人,s个操作,op=1代表x加入了y小组,op=2代表x退出了y小组,op=3代表x在y小组内发了一条消息。问最后每个人收到了多少条消息

思路:

当x加入群组y的时候,减去当前y群组收到的消息数,离开的时候再加上(有点类似前缀和的思想),最后如果还在群组里记得要加上当前的的消息数。

一开始没看见每个人可以同时加入多个群组....所以需要用一个set维护这个人加入了哪些群组,最后遍历一下

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int n, m, s,mes[N],res[N],send[N];
set<int> in[N];
int main(){
    cin>>n>>m>>s;
    for (int i = 1; i <= s;i++){
        int op, x, y;
        cin >> op >> x >> y;
        if(op==1){
            res[x] -= mes[y];
            in[x].insert(y);
        }
        else if(op==2){
            res[x] += mes[y];
            in[x].erase(y);
        }
        else{
            mes[y]++;
            send[x]++;
        }
    }
    set<int>::iterator it;
    for (int i = 1; i <= m;i++){
        for (it = in[i].begin(); it != in[i].end();it++){
            res[i] += mes[*it];
        }
        res[i] -= send[i];
        cout << res[i] << endl;
    }
        return 0;
}

L. Clock Master

大意: 把 n 拆分为若干数的和,使得这些数的 lcm 最大,输出 log(lcm)。\(1<=n<3*10^4\)

思路: 由于lcm要最大,因此拆分出来的数字要尽可能互质,那么就是分组背包,将每个质数和他的幂次方放进一个背包,枚举每个质数的次数

#include<bits/stdc++.h>

using namespace std;

const int N = 30010 + 5;
typedef long long LL;
int t, n,prime[N],cnt;
bool st[N];
double dp[N], logs[N];
void init(){
    for (int i = 2; i < N; ++i) {
        if (!st[i]) prime[cnt++] = i; // 如果这个数字没有被记录,那么这个数字必然为素数,记录一下
        for (int j = 0; prime[j] <= (N-1)/i; ++j) {
            st[prime[j] * i] = true;  // 筛掉pj*i这个合数
            if (i % prime[j] == 0)  break; // i%pj==0,说明pj是i的最小素因子,因此i*素数的最小素因子也是pj,在i递增的时候也会被筛掉,因此不需要在这里判断
        }                
    }
    for (int i = 0; i < N;i++){
        logs[i] = log(i);
    }
}
int main(){
    init();
    for (int i = 0; i < cnt;i++){//分组
        for (int j = N-1; j >= prime[i];j--){//01
            for (int k = prime[i]; k <= j;k*=prime[i]){
                dp[j] = max(dp[j], dp[j - k] + logs[k]);
            }
        }
    }
    cin>>t;
    while(t--){
        scanf("%d", &n);
        printf("%.8lf\n", dp[n]);
    }
        return 0;
}
上一篇:css选择器(常规选择器,伪类选择器,伪元素选择器,根元素选择器)


下一篇:计时器js