头像

Tilbur

挂到考上重邮计科学硕为止




离线:3分钟前


最近来访(863)
用户头像
2049687365
用户头像
歪比歪比
用户头像
TheGiao
用户头像
acwing_zfw
用户头像
QAQlzy
用户头像
长夜难明
用户头像
Peter_5
用户头像
Alexshwing
用户头像
彩色铅笔
用户头像
reene
用户头像
YikN
用户头像
ljhs
用户头像
提子面包
用户头像
Jackyc
用户头像
0118
用户头像
国家特级退堂鼓演奏家
用户头像
iron_qi
用户头像
原野追逐s
用户头像
15084948533
用户头像
eyetofreedom


Tilbur
33分钟前
#include <bits/stdc++.h>
using namespace std;
const int N = 10;

int path[N];
int n;
bool st[N];

void dfs(int u){
    if(u>=n){
        for (int i = 0; i <n; i ++ ) printf("%d ",path[i]);
        puts("");
    }else{
        for (int i = 1; i <=n; i ++ ){
            if(st[i]==false){
                path[u]=i;
                st[i]=true;
                dfs(u+1);
                st[i]=false;
            }
        }
    }

}

int main()
{
    memset(st, 0, sizeof st);
    cin>>n;
    dfs(0);
    return 0;
}



Tilbur
33分钟前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;

void dfs(int u, int s, int state)
{
    if (s == m)
    {
        for (int i = 0; i < n; i ++ )
            if (state >> i & 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }
    if (u == n) return;

    for (int i = u; i < n; i ++ )
    {
        dfs(i + 1, s + 1, state + (1 << i));
    }
}

int main()
{
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}



Tilbur
35分钟前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

void dfs(int u, int state){
    if(u == n){
        for(int i = 0; i < n; i ++ )
            if(state >> i & 1)
                printf("%d ", i + 1);
        puts("");
        return;
    }
    dfs(u + 1, state | (1 << u));
    dfs(u + 1, state);
}

int main()
{
    scanf("%d", &n);
    dfs(0, 0);
    return 0;
}



Tilbur
39分钟前
#include <bits/stdc++.h>
using namespace std;

const int N = 32;

int a[32][2];
struct{
    int type;
    int t[32];
}door[100010];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++ ){
        string op;
        int t;
        cin >> op >> t;
        if(op == "OR") door[i].type = 1;
        if(op == "XOR") door[i].type = 2;
        if(op == "AND") door[i].type = 3;
        int idx = 0;
        while(t){
            door[i].t[idx ++ ] = t % 2;
            t /= 2;
        }
    }
    for(int i = 0; i <= 31; i ++ ){
        a[i][1] = 1;
    }

    for(int i = 0; i <= 31; i ++ ){
        for(int j = 0; j < n; j ++ ){
            if(door[j].type == 1){
                a[i][0] |= door[j].t[i];
                a[i][1] |= door[j].t[i];
            }
            if(door[j].type == 2){
                a[i][0] ^= door[j].t[i];
                a[i][1] ^= door[j].t[i];
            }
            if(door[j].type == 3){
                a[i][0] &= door[j].t[i];
                a[i][1] &= door[j].t[i];
            }
        }
    }

    int ans = 0;
    bool flag = true;
    for(int i = 30; ~i; i -- ){
        if(m >> i){
            if(a[i][0] >= a[i][1]) ans += a[i][0] << i;
            else ans |= a[i][1] << i, m -= 1 << i;
        }
        else ans |= a[i][0] << i;
    }

    printf("%d", ans);

    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

Tilbur
2小时前
#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int w[N][N];
int f[1 << 20][N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            scanf("%d", &w[i][j]);

    memset(f, 0x3f, sizeof f);

    f[1][0] = 0;

    for(int i = 1; i < n; i ++ )
        f[(1 << i) + 1][i] = w[0][i];


    for(int i = 0; i < 1 << n; i ++ ){
        for(int j = 0; j < n; j ++ ){
            if((i >> j & 1) == 0){
                for(int k = 0; k < n; k ++ ){
                    if(i >> k & 1){
                        f[i | (1 << j)][j] = min(f[i | (1 << j)][j], f[i][k] + w[k][j]);
                    }
                }
            }
        }
    }
    printf("%d", f[(1 << n) - 1][n - 1]);

    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

Tilbur
2小时前
#include <cstdio>
using namespace std;

typedef long long ll;

ll qadd(ll a,ll b,ll p){
    ll res=0;
    while(b){
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}

int main()
{
    ll a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld\n",qadd(a,b,p));
    return 0;
}


活动打卡代码 AcWing 3973. 无线网络

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

const int N = 1e5 + 10;
const double eps = 1e-8;
typedef long long LL;
LL a[N], b[N];
LL dist[N];
bool st[N];
int n, m;

void init(){         //二分找距离每个奶牛最近的基站, 存在dist数组里
    for(int i = 0; i < n; i ++ ){
        LL x = a[i];
        int l = 0, r = m - 1;
        while(l < r){
            int mid = l + r + 1>> 1;
            if(b[mid] <= x) l = mid;
            else r = mid - 1;
        }
        dist[i] = abs(x - b[l]);
        l = 0, r = m - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(b[mid] >= x) r = mid;
            else l = mid + 1;
        }
        dist[i] = min(dist[i], abs(x - b[l]));
    }
}

bool check(LL mid){
    for(int i = 0; i < n; i ++ ){
        if(dist[i] > mid) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++ ){
        scanf("%lld", &a[i]);
    }
    for(int i = 0; i < m; i ++ ){
        scanf("%lld", &b[i]);
    }
    init();

    LL l = 0, r = 1e11;
    //二分答案
    while(l < r){
        LL mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld", l);

    return 0;
}


活动打卡代码 AcWing 3972. 方格集数量

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

const int N = 100;
typedef long long LL;
int w[N][N];
LL f[N][N];
int n, m;

void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(!j) f[i][j]=1;
            else f[i][j] = f[i-1][j]+f[i-1][j-1];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            scanf("%d", &w[i][j]);

    LL ans = n * m;
    init();

    for(int i = 0; i < n; i ++ ){
        int cnt1 = 0, cnt2 = 0;
        for(int j = 0; j < m; j ++ ){
            if(w[i][j]) cnt1 ++ ;
            else cnt2 ++ ;
        }
        for(int j = 2; j <= cnt1; j ++ )
            ans += f[cnt1][j];
        for(int j = 2; j <= cnt2; j ++ )
            ans += f[cnt2][j];
    }

    for(int j = 0; j < m; j ++ ){
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0; i < n; i ++ ){
            if(w[i][j]) cnt1 ++ ;
            else cnt2 ++ ;
        }
        for(int i = 2; i <= cnt1; i ++ )
            ans += f[cnt1][i];
        for(int i = 2; i <= cnt2; i ++ )
            ans += f[cnt2][i];
    }

    printf("%lld", ans);

    return 0;
}


活动打卡代码 AcWing 3971. 最小的商

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

const int N = 110;
int a[N];
int n, k;

int main(){
    int T;
    cin >> T;
    while(T -- ){
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i ++ ){
            scanf("%d", &a[i]);
        }
        int ans = 1e9;
        for(int i = 1; i <= n; i ++ ){
            if(k % a[i] == 0)
                ans = min(ans, k / a[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}


活动打卡代码 AcWing 1053. 修复DNA

Tilbur
2天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, M = 1010, K = 25;
const int INF = 0x3f3f3f3f;

int n;
char s[M];
int tr[N * K][4], cnt[N * K], idx;
int fail[N * K], q[N * K];
int f[M][N * K];

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}
void insert(char s[])
{
    int p = 0;
    for (int i = 0; s[i]; ++ i)
    {
        int u = get(s[i]);
        if (!tr[p][u]) tr[p][u] = ++ idx;
        p = tr[p][u];
    }
    cnt[p] = 1;
}
void build()
{
    int tt = -1, hh = 0;
    for (int i = 0; i < 4; ++ i)
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];
    while (hh <= tt)
    {
        int u = q[hh ++ ];
        for (int i = 0; i < 4; ++ i)
        {
            if (tr[u][i])
                fail[tr[u][i]] = tr[fail[u]][i],
                cnt[tr[u][i]] |= cnt[fail[tr[u][i]]],//看他跳转的状态是否是匹配成功状态
                q[ ++ tt] = tr[u][i];
            else
                tr[u][i] = tr[fail[u]][i];
        }
    }
}
void solve()
{
    //initializing
    memset(fail, 0, sizeof fail);
    memset(cnt, 0, sizeof cnt);
    memset(f, 0x3f, sizeof f);
    memset(tr, 0, sizeof tr);
    f[0][0] = 0;
    idx = 0;
    //input and build the AC Automaton
    for (int i = 1; i <= n; ++ i) cin >> s, insert(s);
    cin >> s + 1; build();
    int n = strlen(s + 1);
    //dp
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j <= idx; ++ j)
        {
            //枚举下一个字符
            for (int k = 0; k < 4; ++ k)
            {
                int cost = get(s[i + 1]) != k;  //修复下一个字符的费用
                int p = tr[j][k];               //下一个字符的自动机状态
                if (!cnt[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + cost);
            }
        }
    }
    int res = INF;
    for (int j = 0; j <= idx; ++ j) res = min(res, f[n][j]);
    if (res == INF) res = -1;
    cout << res << endl;
}
int main()
{
    int T = 1;
    while (cin >> n, n)
    {
        cout << "Case " << T ++ << ": ";
        solve();
    }
    return 0;
}