[洛谷11月月赛]

比赛链接

T1

思路

按照斐波那契的式子到着往前推就行，f[i]=f[i+2] - f[i+1],当找到某个值使得f[i] = 0,f[i+1] = 1的时候就停止。

代码

//https://www.luogu.org/problemnew/show/P4994
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int main() {
    int ans = 0;
    int m = read(),now = 1, lst = 0; 
    while(now != 0 || lst != 1) {
        ans++;
        int k = now;
        now = (lst - now + m) % m;
        lst = k;
    }
    cout<<ans + 1;
    return 0;
}

T2

思路

将序列排序，然后每次从一段跳另一端。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 310;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int a[N];
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    int l = 0,r = n;
    sort(a,a+n+1);
    int bz = 0;
    ll ans = 0;
    while(l < r) {
        ans += (a[r] - a[l]) * (a[r] - a[l]);
        if(bz & 1) r--;
        else l++;
        bz ^= 1;
    }
    cout<<ans;
    return 0;
}

T3

思路

没看懂题意，所以去瞄(chao)了一眼(fa)题解。

大概思路就是，计算出从全0到这个状态有多少种情况，再计算出从这个状态到全1有多少种情况，将他们与这个状态的歉意值乘起来，就是这个状态整个的贡献。

因为一个状态1的位置是无所谓的，所以只看1的个数即可。用f[i]表示从0到i个1的时候的情况数量。枚举j表示最后一次放了多少个1，\(f[i] = \sum\limits_{j=1}^i{f[i-1]*C(_i^j)}\)

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 30,mod = 998244353;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll f[N];
ll C[N][N];
int n, m;
void pre() {
    C[0][0] = 1;
    for(int i = 1;i <= n; ++i) {
        C[i][0] = 1;
        for(int j = 1;j <= i;++j) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] >= mod ? C[i][j] -= mod : 0;
        }
    }
    f[0] = 1;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= i;++j) {
            f[i] += f[i-j] * C[i][j] % mod;
            f[i] >= mod ? f[i] -= mod : 0;
        }
    }
}

char s[N];
ll ans;
int main() {
    n = read(),m = read();
    pre();
    while(m--) {
        scanf("%s",s + 1);
        int w = read();
        int tot = 0;
        for(int i = 1;i <= n;++i) {
            if(s[i] == '1') tot++;
        }
        ans += f[tot] * f[n-tot] % mod * w % mod;
        ans >= mod ? ans-= mod : 0;
    }
    cout<<ans;
    return 0;
}