赛后补了几道

赛中我就写了两个...

看了眼榜没几个人做。就没看。

最后发现就是一个DP（但是我觉得复杂度有点迷）

题意：$n$只青蛙有参数$l,w,h$分别表示弹跳力，体重，身高，在一口深为$d$的井里

一只青蛙不能承受比他重的重量，问最多有多少只能出去（达到高度严格大于d）

重的肯定比轻的晚出去，那么轻的肯定由重的来转移，所以先排序，从重到轻的排

$dp_{i}$表示体重为i最高能叠多高 瞎jb转移一下就好了

#include 
      
       #include 
       
        #include 
        
         #define ll long longusing namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }    return x * f;}const int N = 1e5 + 10;const int M = 1e8 + 10;struct P {    int l, w, h;    bool operator < (const P &rhs) const {        return w > rhs.w;    }} p[N];int dp[M], n, d, ans;int main() {    n = read(), d = read();    for (int i = 1; i <= n; i++) p[i].l = read(), p[i].w = read(), p[i].h = read();    ans = 0;    sort(p + 1, p + n + 1);    for (int i = 1; i <= n; i++) {        if (dp[p[i].w] + p[i].l > d) ans++;        for (int j = p[i].w + 1; j < min(p[i].w * 2, M); j++) {            dp[j - p[i].w] = max(dp[j-p[i].w], dp[j] + p[i].h);        }     }    printf("%d\n", ans);    return 0;}
        
       
      

 

#include 
      
       #include 
       
        using namespace std;const int N = 1010;int a[N];int n;char s[N];int main() {    scanf("%d", &n);    bool ans = true;    for (int i = 1; i <= n; i++) {        scanf("%s", s);        int len = strlen(s);        if (s[0] == 'm') a[i] = i;        else {            int x = 0;            for (int j = 0; j < len; j++) x = x * 10 + s[j] - '0';            a[i] = x;            if (x != i) {                ans = false;            }        }    }    puts(ans?"makes sense":"something is fishy");    return 0;}
       
      

 

阅读理解题啊。自己瞎糊了一发。读不下去。就丢给队友了。

不管了。

 

题意：分别有$n,m$个士兵，每个士兵有一个血量，有d个攻击，等概率分给每一个士兵。

问敌方士兵全死（m）的概率是多少

队友过的。学习了新知识，概率记忆化+状压

用一个long long来表示状态

unordered_map来存状态对应的概率 再回溯搜索即可 tql

#include 
      
       #define ll long longusing namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }    return x * f;}unordered_map
       
         mp;int a[2][10];ll getsta() {    ll ret = 0;    for (int i = 1; i <= 6; i++) ret = ret * 10 + 1LL * a[1][i];    for (int i = 1; i <= 6; i++) ret = ret * 10 + 1LL * a[0][i];    return ret;}double dfs(ll sta, int d) {    if (mp.count(sta)) return mp[sta];    if (sta < 1000000) return 1;    if (d == 0) return 0;    int sum = 0;    for (int i = 0; i < 2; i++)         for (int j = 1; j <= 6; j++)            sum += a[i][j];    double ret = 0;    for (int i = 0; i < 2; i++) {        for (int j = 1; j <= 6; j++) {            if (!a[i][j]) continue;            a[i][j]--;            a[i][j-1]++;            ll s = getsta();            double res = dfs(s, d - 1);            a[i][j]++;            a[i][j-1]--;            mp[s] = res;            ret += a[i][j] * 1.0 / sum * res;        }    }    return ret;}int main() {    int n = read(), m = read(), d = read();    for (int i = 1, x; i <= n; i++) x = read(), a[0][x]++;    for (int i = 1, x; i <= m; i++) x = read(), a[1][x]++;    double res = dfs(getsta(), d);    printf("%.8f\n", res);    return 0;}
       
      

 

题意：有m台机器，每台机器有名字，价格p，每分钟能工作多少c，充一次电能工作多久t，充电需要多久r

有l面积的地待作，问平均每周能工作一次的机器中价格最小的那个，相同的按输入顺序输出

队友把10080说成10800能忍？

平均一下直接就把充电需要的时间给平均进来 得到每分钟工作多少的p'

再用$l/p'$和10080比就得出答案了

可能难就难在输入部分吧。

#include 
      
       using namespace std;struct Node{    string name;    int p , c, t, r;    double cc;}b[105];bool vis[105];int main(){    ios::sync_with_stdio(false);    int m;    int l;    cin >> l >> m;    string a;    getline(cin,a);    for(int i=1;i<=m;i++)    {        getline(cin,a);        int sta = 0;        b[i].name = "";        b[i].p = b[i].c = b[i].r = b[i].t = 0;        for(int j=0;j
      

 

题意： 0 1串 给你00出现的次数a 01出现的次数b 10出现的次数c 11出现的次数d

问能否构造出01串

WA了好几发 一度崩溃

首先由a d能推出0和1的个数 必定是一个C(n, 2) 把a和d乘二开根 和加一相乘是否等于2a和2d来判断

第二部分

用两个数组表示

$a_{i}$表示第i个0后面出现了几个1

$b_{i}$表示第i个0前面出现了几个1

必定有$a_{i} + b_{i} = cnt_{1}$        $a_{i}\geq a_{i+1}$        $b_{i}\leq b_{i+1}$

$\sum ^{cnt_{0}}_{i=1}a_{i} = b$            $\sum ^{cnt_{0}}_{i=1}b_{i} = c$

所以$b + c = cnt_{0}\times cnt_{1}$才有解

随便举几个例子发现贪心的构造均能满足答案

如样例 3 4 2 1

得到$cnt_{0} = 3$   $cnt_{1} = 2$

$a_{i}$ : 2 2 0

$b_{i}$ : 0 0 2

得到 00110 也符合

所以直接构造就完了

不过要注意

0 0 0 0直接输出0或1就可以了

a为0或d为0的情况 如果$b + c = 0$ 那么对应的0的个数或1的个数为0 否则才为1

然后瞎jb输出就完了

#include 
      
       #include 
       
        #include 
        
         using namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}int main() {    int a = read(), b = read(), c = read(), d = read();    int sqra = sqrt(2 * a), sqrd = sqrt(2 * d);    bool ans = true;    if ((a + b + c + d) == 0) {        puts("0");        return 0;    }    if (sqra * (sqra + 1) != a * 2 || sqrd * (sqrd + 1) != d * 2) {        ans = false;    } else {        int cnt0 = sqra, cnt1 = sqrd;        cnt0++, cnt1++;        if (cnt1 == 1 && (b + c) == 0) cnt1 = 0;        if (cnt0 == 1 && (b + c) == 0) cnt0 = 0;        //printf("%d %d\n", cnt0, cnt1);        if (b + c != cnt0 * cnt1) {            ans = false;        } else {            if (cnt1 == 0) {                while (cnt0--) putchar('0');                return 0;            }            if (cnt0 == 0) {                while (cnt1--) putchar('1');                return 0;            }            int k = b / cnt1;            for (int i = cnt0; i > cnt0 - k; i--) putchar('0');            cnt0 -= k;            k = b - k * cnt1;            if (k) {                k = cnt1 - k;                for (int i = cnt1; i > cnt1 - k; i--) putchar('1');                cnt1 -= k;                putchar('0'), cnt0--;            }                while (cnt1--) putchar('1');            while (cnt0--) putchar('0');            return 0;        }    }    if (!ans) puts("impossible");    return 0; }
        
       
      

 

题意：一棵树n个节点，k种颜色，问有多少种方案用上k个颜色并且相邻两节点颜色不同

我以为要用树形dp做，赛后看题解才明白是个容斥。

用k种的情况是$k\times \left( k-1\right) ^{n-1}$然后其中包含了只用了k-1种 只用了k-2种...的情况

容斥一下就好了

#include 
      
       #define ll long longusing namespace std;inline ll read() {    ll x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }    return x * f;}const ll mod = 1e9 + 7;const int N = 2550;ll C[N][N];void init() {    for (int i = 0; i < N; i++) C[i][0] = 1, C[i][1] = i;    for (int i = 1; i < N; i++)        for (int j = 2; j <= i; j++)            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;}ll qm(ll a, ll b) {    ll res = 1;    while (b) {        if (b & 1) res = res * a % mod;        a = a * a % mod;        b >>= 1;    }    return res;}int main() {    init();    ll n = read(), k = read();    for (int i = 1; i < n; i++) read();    ll ans = 0, flag = 1;    for (int i = k; i >= 1; i--) {        ll temp = flag * i * qm((ll)i - 1, n - 1) % mod * C[k][i];        ans = (ans + temp + mod) % mod;        flag = -flag;    }            printf("%lld\n", ans);    return 0;}