头像

Theo

XX小学


访客:2881

离线:17小时前


活动打卡代码 AcWing 215. 破译密码

Theo
22天前
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int primes[50005], cnt;
bool flag[50005];
int mobius[50005], sum[50005];

void init(int n)
{
    mobius[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!flag[i])
        {
            mobius[i] = -1;
            primes[cnt++] = i;
        }
        for (int j = 0; primes[j] * i <= n; j++)
        {
            int t = primes[j] * i;
            flag[t] = true;
            if (i % primes[j] == 0)
            {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }
    for (int i = 1; i <= n; i++) 
    {
        sum[i] = sum[i - 1] + mobius[i];
    }
}

int main()
{
    init(50004);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        a /= d;
        b /= d;
        int n = min(a, b);
        ll ans = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, min(a / (a / l), b / (b / l)));
            ans += (sum[r] - sum[l - 1]) * (ll)(a / l) * (b / l);
        }
        printf("%lld\n", ans);
    }
    return 0;
}



活动打卡代码 AcWing 218. 扑克牌

Theo
22天前
#include<bits/stdc++.h>
using namespace std;
const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y)
{
    double &v = f[a][b][c][d][x][y];
    if(v >= 0)
    {
       return v; 
    }
    int as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);
    if (as >= A && bs >= B && cs >= C && ds >= D) 
    {
        return (v = 0);
    }
    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if (sum <= 0) 
    {
        return (v = INF);
    }
    v = 1;
    if (a < 13) 
    {
        v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
    }
    if (b < 13) 
    {
        v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
    }
    if (c < 13) 
    {
        v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
    }
    if (d < 13) 
    {
        v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
    }
    if (x == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i++) 
        {
            t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
        }
        v += t;
    }
    if (y == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i++) 
        {
            t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
            t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
        }
        v += t;
    }
    return v;
}

int main()
{
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof(f));
    double t = dp(0, 0, 0, 0, 4, 4);
    if(t > INF / 2)
    {
        puts("-1.000");
    }
    else
    {
        printf("%.3lf\n", t);
    }
    return 0;
}



活动打卡代码 AcWing 214. Devu和鲜花

Theo
22天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL A[25];
LL n, m;
int down = 1;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) 
        {
            res = (LL)res * a % p;
        }
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i--) 
    {
        up = i % mod * up % mod;
    }
    return (LL)up * down % mod;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
    {
        cin >> A[i];
    }
    for (int j = 1; j <= n - 1; j++)
    {
        down = (LL)j * down % mod;
    }
    down = qmi(down, mod - 2, mod);
    int res = 0;
    for (int i = 0; i < 1 << n; i++)
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                sign *= -1;
                a -= A[j] + 1;
            }
        }
        res = (res + C(a, b) * sign) % mod;
    }
    cout << (res + mod) % mod << endl;
    return 0;
}



活动打卡代码 AcWing 474. 龙虎斗

Theo
23天前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll d, t, diff, n, m, p1, p2, s1, s2;

int main()
{
    cin >> n;
    ll c[n + 1];
    for(int i = 1; i <= n; i++)
    {
        cin >> c[i];
    }
    cin >> m >> p1 >> s1 >> s2;
    c[p1] += s1;
    p2 = m;
    c[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(i < m)
        {
            d += (m - i) * c[i];
        }
        if(i > m)
        {
            t += (i - m) * c[i];
        }
    }
    diff = abs(d - t);
    for(int i = 1; i <= n; i++)
    {
        if(i < m)
        {
            if(abs(d + (m - i) * s2 - t) < diff)
            {
                p2 = i;
                diff = abs(d + (m - i) * s2 - t);
            }
        }
        if(i > m)
        {
            if(abs(t + (i - m) * s2 - d) < diff)
            {
                p2 = i;
                diff = abs(t + (i - m) * s2 - d);
            }
        }
    }
    cout << p2;
    return 0;
}



活动打卡代码 AcWing 475. 摆渡车

Theo
23天前
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dta[1024], sum[1024], dp[1024][128];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> dta[i];
    }
    sort(dta + 1, dta + n + 1);
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + dta[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int wait  = 0; wait < m; wait++)
        {
            int curbus = dta[i] + wait;
            if(wait)
            {
                dp[i][wait] = dp[i][wait - 1];
            }
            else
            {
                dp[i][wait] = curbus * i - sum[i];
            }
            for(int lastbus = max(curbus - 2 * m + 1, 0); lastbus <= curbus - m; lastbus++)
            {
                int lastcarry = lower_bound(dta + 1, dta + n + 1, lastbus + 1) - (dta + 1);
                int lastwait = min(lastbus - dta[lastcarry], m - 1);
                int tmp = dp[lastcarry][lastwait] + (i - lastcarry) * curbus - (sum[i] - sum[lastcarry]);
                if(tmp < dp[i][wait])
                {
                    dp[i][wait] = tmp;
                }
            }
        }
    }
    cout << dp[n][m - 1];
    return 0;
}



活动打卡代码 AcWing 471. 棋盘

Theo
23天前
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
int ans[maxn][maxn];
int color[maxn][maxn];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m;

void dfs(int currow, int curcol, int cost, bool magic)
{
    if(cost >= ans[currow][curcol])
    {
        return;
    }
    ans[currow][curcol] = cost;
    for(int i = 0; i < 4; i++)
    {
        int nextrow = currow + dir[i][0], nextcol = curcol + dir[i][1];
        if(nextrow < 1 || nextcol < 1 || nextrow > m || nextcol > m)
        {
            continue;
        }
        if(!color[nextrow][nextcol])
        {
            if(magic)
            {
                color[nextrow][nextcol] = color[currow][curcol];
                dfs(nextrow, nextcol, cost + 2, 0);
                color[nextrow][nextcol] = 0;
            }
        }
        else if(color[nextrow][nextcol] != color[currow][curcol])
        {
            dfs(nextrow, nextcol, cost + 1, 1);
        }
        else
        {
            dfs(nextrow, nextcol, cost, 1);
        }
    }
}

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        color[x][y] = c + 1;
    }
    memset(ans, 0x7f, sizeof(ans));
    dfs(1, 1, 0, 1);
    if(ans[m][m] == 0x7f7f7f7f)
    {
        cout << -1;
    }
    else
    {
        cout << ans[m][m];
    }
    return 0;
}



活动打卡代码 AcWing 465. 买铅笔

Theo
24天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = INT_MAX;
    for (int i = 0; i < 3; i++)
    {
        int a, b;
        cin >> a >> b;
        res = min(res, (n + a - 1) / a * b);
    }
    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 442. 接水问题

Theo
26天前
#include<bits/stdc++.h>
using namespace std;
int water[105], a[10005];

int main()
{
    while(1)
    {
        int *a = new int;
    }
    return 0;
}



活动打卡代码 AcWing 428. 数列

Theo
27天前
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll get(int a, int b)
{
    ll res = 1;
    while (b--) 
    {
        res *= a;
    }
    return res;
}

int main()
{
    int n, k;
    cin >> k >> n;
    ll res = 0;
    for (int i = 0; i < 20; i++)
    {
        if (n >> i & 1)
        {
            res += get(k, i);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 208. 开关问题

Theo
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 35;

int n;
int a[N][N];

int gauss()
{
    int r, c;
    for (r = 1, c = 1; c <= n; c ++ )
    {
        int t = r;
        for (int i = r + 1; i <= n; i ++ )
            if (a[i][c])
                t = i;
        if (!a[t][c]) continue;
        for (int i = c; i <= n + 1; i ++ ) swap(a[t][i], a[r][i]);
        for (int i = r + 1; i <= n; i ++ )
            for (int j = n + 1; j >= c; j -- )
                a[i][j] ^= a[i][c] & a[r][j];
        r ++ ;
    }
    int res = 1;
    if (r < n + 1)
    {
        for (int i = r; i <= n; i ++ )
        {
            if (a[i][n + 1]) return -1;
            res *= 2;
        }
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(a, 0, sizeof a);
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i][n + 1]);
        for (int i = 1; i <= n; i ++ )
        {
            int t;
            scanf("%d", &t);
            a[i][n + 1] ^= t;
            a[i][i] = 1;
        }

        int x, y;
        while (scanf("%d%d", &x, &y), x || y) a[y][x] = 1;

        int t = gauss();
        if (t == -1) puts("Oh,it's impossible~!!");
        else printf("%d\n", t);
    }

    return 0;
}