投稿
  1. 首页
  2. C

第45届ICPC沈阳站部分题解（D、F、G、H、I、K）

利润及利润分配表 • 2022-6-25 • C • 阅读 38

第45届ICPC沈阳站部分题解（D、F、G、H、I、K）,第1张

文章目录
      • D-前缀和思想+dfs
      • F-贪心
      • G
      • H-双指针+dp
        • 题意
        • 思路
        • 代码
      • I-追及问题+裴蜀定理
      • K-前缀和+积分的定义
        • 题意
        • 思路
      • 参考链接

传送门

本文CSDN

本文juejin

难度：G < F < K < D < I < H。

作者：hans774882968以及hans774882968

D-前缀和思想+dfs

题意：直接看题干，易懂。

去年比赛的时候觉得这是个规律题，发现可以用n小的答案生成n大的答案，写了2小时以上，200多行代码，却wa了。因此不想再尝试这种令人伤悲的做法。

dfs做法：首先，统计区间内1的个数，很容易联想到前缀和。因为只要求s[r]和s[l-1]奇偶性不同，所以前缀和可以改成前缀异或，s[0] = 0。设前缀异或数组有x个0（则有n+1-x个1），试求下标对个数表达式。只考虑枚举左或右端点很难得到式子，因此考虑一个点既可以当左也可以当右。对于i = 0，只能作为l-1，贡献为1的个数；对于i = n，只能作为r，贡献为num[!s[n]]；对于其他i，左侧的num[!s[i]]使它作为r，右侧的num[!s[i]]使它作为l-1，因此贡献仍为num[!s[i]]。综上，总贡献2*num[0]*num[1]，但每个区间都被统计2次，所以除以2，下标对个数为x*(n+1-x)。求这个函数的最值是初中数学，n为奇数时，x = (n+1)/2 = n/2 + 1；否则x = up(n+1,2) = n/2 + 1或(n+1)/2，up表示向上取整。

于是我们得到一条关键性质：前缀异或数组的0和1的个数都不超过n/2 + 1。结合题目要求的，字典序最小的100个解，于是可以考虑dfs，用关键性质剪枝。

坑：

  1. 需要小心MLE，建议找到100个答案后直接调exit(0)退出，而不是return，占用更多栈空间。另外字符串要使用外部空间，而非传参。
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e5 + 5;

int n;
char s[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

void dfs (int cur, int sum, int v0, int v1, int &out_n) {
    if (v0 > n / 2 + 1 || v1 > n / 2 + 1) return;
    if (cur >= n) {
        puts (s);
        if ( (++out_n) >= 100) exit (0);
        return;
    }
    s[cur] = 'b';
    dfs (cur + 1, sum, v0 + !sum, v1 + sum, out_n);
    s[cur] = 'r';
    dfs (cur + 1, !sum, v0 + sum, v1 + !sum, out_n);
}

int main() {
    read (n);
    printf ("%lld\n", n % 2 ? 1LL * (n + 1) * (n / 2 + 1) / 2 : (1LL * n * (n + 2) / 4) );
    int out_n = 0;
    dfs (0, 0, 1, 0, out_n);
    return 0;
}
F-贪心

题意：把数组划分为若干个区间，使得区间内部升序排序后，整个数组是升序的。问最多能划分多少个区间。

整体思路为当前数组与升序排序的数组进行比对，并贪心。需要注意，可能有多个相同的数，贪心原则就按输入顺序排序，这样就确定每个下标的数的期望排名rk数组。对于新区间的开头i，有rk[i] >= i，就向右找到最小的点j，使得max(rk[i~j]) <= j，这样这个新区间才满足要求。

#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e6 + 5;

int n, a[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (n);
    vector<pii> b (n + 1);
    vector<int> rk (n + 1);
    rep (i, 1, n) read (a[i]), b[i].first = a[i], b[i].second = i;
    sort (b.begin() + 1, b.end() );
    rep (i, 1, n) rk[b[i].second] = i;
    int ans = 0;
    for (int u = rk[1], i = 1;;) {
        while (i < u) {
            ++i;
            u = max (u, rk[i]);
        }
        ++ans;
        if (i >= n) break;
        u = rk[++i];
    }
    printf ("%d\n", ans);
    return 0;
}
G

签到，代码略。

H-双指针+dp 题意

你需要租借自行车。直接租用一辆自行车的花费为r <= 1e9。现在给你n <= 500种折扣卡：

  • 每种折扣卡的有效期为d天，即第t天购入，t ~ t+d-1天有效。
  • 每种折扣卡可以让从购买时刻开始的k个自行车免费。
  • 折扣卡价格为c。1 <= d,k,c <= 1e9。

接下来输入m <= 1e5行，每行两个数p和q，表示第p天要租借q个自行车。保证p两两不同。0 <= p <= 1e9, 0 <= q <= 3e5, sum(q) <= 3e5。输出一个整数，表示最小总花费。

思路

3e5 * 500 = 1.5e8，故显然可以先展开出q个p再排序，表示以一个自行车的租借为单位来决策，然后再考虑dp。我首先考虑的是二维dp，即dp[i][j]表示第i次租借使用第j种折扣的最小总花费。但这样即使用上线段树也是n * 3e5 * log(n * 3e5)，过不了。那就考虑一维dp，并在转移方程中体现有效期和有效次数。定义dp[i]表示前i次租借的最小总花费，则dp[sum(q)]为答案（下面设n0 = sum(q)），显然dp[0] = 0。

转移：考虑朴素的转移方程的伪代码：

for i = range(1,n0+1):
    dp[i] = dp[i-1] + r
    for j in range(1,n+1):
        for k in range(x[j][i],i):
            dp[i] = min(dp[i],dp[k-1]+c[j])

x[j][i]表示购买的是第j种折扣卡，且满足第i次租借时还有效的最小的租借下标，用代码表示就是i <= x + k[j] - 1 && a[i] <= a[x] + d[j] - 1。dp[k-1]+c[j]表示买卡后，第k次就开始免费。

因为dp定义有单调性，所以第3层循环可以去掉，直接取dp[x[j][i]-1]+c[j]，这样复杂度就对了。

x[j][i]求法：j不变，x[j][i]随i单增。因此可以用双指针。

代码
  1. 看着是银牌题，算法其实不难理解，AC代码也不长。
  2. 不要真的开x[j][i]数组，取址太多，会TLE。只有把求x的过程和dp转移耦合在一起，减少取址，才能过。
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 3e5 + 5, M = 502;

int m, n, r;
int a[N], d[M], k[M], c[M], tmp[M];
LL dp[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (m, n, r);
    rep (i, 1, m) read (d[i], k[i], c[i]);
    int n0 = 0;
    rep (_, 1, n) {
        int x, y;
        read (x, y);
        re_ (i, 0, y) a[++n0] = x;
    }
    n = n0;
    sort (a + 1, a + n + 1);
    rep (i, 1, m) tmp[i] = 1;
    rep (i, 1, n) {
        dp[i] = dp[i - 1] + r;
        rep (j, 1, m) {
            int x = tmp[j];
            while (! (i <= x + k[j] - 1 && a[i] <= a[x] + d[j] - 1) ) ++x;
            dp[i] = min (dp[i], dp[x - 1] + c[j]);
            tmp[j] = x;
        }
    }
    printf ("%lld\n", dp[n]);
    return 0;
}
I-追及问题+裴蜀定理

题意：给你一个钟，有H小时，每小时有M分钟。问从0点开始，时钟转完一圈的时间内（即到H*M-1分钟），分钟和时钟的夹角小于等于2*pi*A/(H*M)的分钟有几个。

以分钟为单位，时针和分钟在t ∈ [0, H*M-1]分钟的角度分别为2*pi*t/(H*M)和2*pi*t/M。列出所求不等式：|(2*pi*t/(H*M) % (2*pi)) - (2*pi*t/M % (2*pi))| <= 2*pi*A/(H*M)。因为只关注整数分钟，2*pi是无关紧要的，两边同时乘H*M/(2*pi)得：

|t % (H*M) - (H*t) % (H*M)| <= A

故：-A <= (t*(H-1)) % (H*M) <= A，即：

  1. (t*(H-1)) % (H*M) <= A
  2. (t*(H-1)) % (H*M) >= H*M-A，两边同时加上H*M同余而得。

约定down(x,y)为x向下整除y。如down(-2,3) = -1。这里用到的性质：

  1. down(x+k*y,y) = down(x,y) + k，k ∈ Z。

两边同时除以g = gcd(H-1,H*M)，构造互质性，1式变成：(t*(H-1)/g) % (H*M/g) <= down(A,g)（3）。

由裴蜀定理，当gcd(x,m) = 1，t*x = y (mod m)的每个y都能解出同余意义下唯一的t。所以3式的解数为down(A,g)+1。2式转化为小于等于H*M-A-1，再两边同除以g的解数为down(H*M-A-1,g)+1。

注意除以g后的一个解对应原式的g个解，因此还要乘g。得1式的解数g*(down(A,g)+1)；3式的解数H*M - g*(down(H*M-A-1,g)+1) = g*(H*M/g - 1 - down(H*M-A-1,g)) = g*(-1-down(-A-1,g))（由向下取整性质1可得）。由向下取整性质1，只需要验证A = 0~g-1的情况下，该式子都等于g*down(A,g)（即可推广到任意A了），验证没问题。

最终答案g*(2*down(A,g)+1)。

坑：

  1. 当2*A = H*M，1式和2式算重了A = H*M/2的部分，所以需要特判。此时每个整数分钟都满足。
  2. x负数y正数的时候，别忘了cpp的除法是逼近0的，不是向下取整。
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e6 + 5;

LL h, m, a;

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

LL down (LL x, LL y) {
    if (x >= 0) return x / y;
    return x / y - (x % y < 0);
}

int main() {
    read (h, m, a);
    if (2 * a == h * m) printf ("%lld\n", h * m);
    else {
        LL g = __gcd (h - 1, h * m);
        LL v1 = a / g + 1, v2 = -1 - down (-a - 1, g);
        printf ("%lld\n", g * (v1 + v2) );
    }
    return 0;
}
K-前缀和+积分的定义 题意

机器学习中，真正例TP、真负例TN、假正例FP、假负例FN，则TPR = TP / (TP + FN), FPR = FP / (FP + TN)。FPR为自变量，TPR为因变量的曲线叫做ROC曲线，其定积分为AUC，定义式如下：
A U C = ∫ 0 1 m a x θ ∈ R { T P R ( θ )   ∣   F P R ( θ ) < = r }   d r AUC=\int_0^1 max_{\theta \in R} \{TPR(\theta)\ |\ FPR(\theta)<=r\}\ dr AUC=∫01​maxθ∈R​{TPR(θ) ∣ FPR(θ)<=r} dr
给你一个分类器对n个样本的分类结果，+ / -表示样本实际为正负例，s表示置信度分数。你选择一个阈值theta，大于等于该阈值即预测为正例，否则预测为负例，于是每个theta对应一个TPR和FPR。求AUC。

思路

显然theta只在置信度分数的点附近变化才对TPR和FPR有影响。因此排序+枚举每个样本，s[i]表示取下标大于等于i的为预测正例，小于i的为预测负例。i变化时需要快速得到左侧和右侧的'+'、'-'数目，可以维护差值或前缀和，这里我们选择了不容易写错的前缀和。

观察int tp = sump[n] - sump[i - 1], fn = sump[i - 1], fp = sumn[n] - sumn[i - 1], tn = sumn[i - 1]，可得结论：i加1，tpr和fpr中至多只有一个变化。因此算积分的时候直接算每个矩形的面积和即可。

坑：

  1. 注意AUC的积分式要取最大TPR(theta)，即最大化TP最小化FN，所以升序排序分数相同时，要把'+'排'-'的左边。
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e6 + 5;

int n, sump[N], sumn[N];

void dbg() {
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
    read (x);
    read (r...);
}

struct Node {
    bool po;
    int s;
} a[N];

bool cmp (Node &x, Node &y) {
    if (x.s ^ y.s) return x.s < y.s;
    return x.po > y.po;
}

int main() {
    read (n);
    rep (i, 1, n) {
        char po[5];
        scanf ("%s%d", po, &a[i].s);
        a[i].po = (po[0] == '+');
    }
    sort (a + 1, a + n + 1, cmp);
    rep (i, 1, n) {
        sump[i] = sump[i - 1] + a[i].po;
        sumn[i] = sumn[i - 1] + (!a[i].po);
    }
    double ans = 0, l_fpr = -1;
    rep (i, 1, n + 1) {
        int tp = sump[n] - sump[i - 1], fn = sump[i - 1], fp = sumn[n] - sumn[i - 1], tn = sumn[i - 1];
        double tpr = 1.0 * tp / (tp + fn), fpr = 1.0 * fp / (fp + tn);
        if (l_fpr != -1) {
            ans += 1.0 * tpr * (l_fpr - fpr);
        }
        l_fpr = fpr;
    }
    printf ("%.10lf\n", ans);
    return 0;
}
参考链接
  1. https://blog.csdn.net/m0_60243915/article/details/119169111

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/1498149.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
利润及利润分配表 利润及利润分配表 一级用户组
0 0
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表（0条）

保存