分类: cf - CheaSim Blog
发表更新cf3 分钟读完 (大约522个字)

[dp+graph] CodeForces - 721C

[dp+graph] CodeForces - 721C

题意

给定一个有向无环图DAG，之后问从点$1$走到点$n$中，在一定的费用要求下，最多能经过多少个点。并给出经过的点。

题解

$n \leq 5000$

我们可以考虑一下二维dp，定义一个dp数组

  • $dp[i][j]$代表着在$i$这个点到终点，经过$j$个点所需要花费的最少时间。

之后利用dfs进行更新。因为是深度优先，所以经过的点不用在遍历一遍。

对于记录经过的点，可以用一个二维数组代表，第$j$个点的时候下一个点是什么。

错误的思想。 WA14

定义两个数组，一个记录已知这个点到达$n$最少耗-费的时间，一个记录已知这个点到达$n$最多的点数。之后利用这两个数组进行剪枝，但是已知wa14的点，我也不知道为什么。可能是dfs的顺序有关。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
int n,m,T,cnt;
int head[maxn],vis[maxn];
struct node{
    int to,next;
    ll val;
}G[maxn];
void init(){
    memset(head,-1,sizeof(head));
    cnt = 1;
}
void addedge(int u,int v,int val){
    G[cnt].to = v;
    G[cnt].val = val;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int dp[maxn][maxn], bef[maxn][maxn];
void dfs(int u){   
    vis[u] = 1;
    if(u==n) return;
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(vis[v]==0) dfs(v);
        rep(j,1,n){
            if(dp[v][j] + G[i].val < dp[u][j+1]){
                dp[u][j+1] = dp[v][j] + G[i].val;
                bef[u][j+1] = v;
            }
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&T);
    init();
    memset(dp,0x3f,sizeof(dp));
    rep(i,1,m+1){
        int u,v,val; scanf("%d%d%d",&u,&v,&val);
        addedge(u,v,val);
    }
    dp[n][1] = 0;
    dfs(1);
    int idx = 1;
    per(i,1,n+1){
        if(dp[1][i] <= T){
            printf("%d\n",i);
            idx = i;
            break;
        }
    }
    printf("1 ");
    int cnt = 1;
    while(idx > 1){
        printf("%d ",bef[cnt][idx]);
        cnt = bef[cnt][idx--];
    }
    return 0;
}
发表更新cf3 分钟读完 (大约407个字)

[cf548]Edgy Trees

Codeforces Round #548 (Div. 2)

C.Edgy Trees

题意

给一个树，树上的边分为黑色或者红色，现在我们定义一个序列[𝑎1,𝑎2,…,𝑎𝑘]

  • 我们按照次序经过序列中的每一个点(最短路径)
  • 如果进过至少一条黑边，那这个序列就是好的。

题解

至少一条的反义词就是一条都没有，这道题就是找没有黑边的子树。之后答案就是每个子树中的个数的$k$次方。

想着树形dp做，想了很久都没有写出来。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll mod = 1e9+7;
const int maxn = 1e5+10;
int cnt,n,k;
int head[maxn];
struct node{
    int next,to,val;
}G[maxn<<1];
void addedge(int u,int v,int val){
    G[cnt].next = head[u];
    G[cnt].to = v;
    G[cnt].val = val;
    head[u] = cnt++;
}
void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}
int vis[maxn];
int t = 0;
void dfs(int u,int fa){
    t ++;
    vis[u] = 1;
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v == fa) continue;
        if(vis[v]) continue;
        if(G[i].val == 0)dfs(v,u);
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    ll x = a;
    while(b){
        if(b&1) res  = res * x % mod;
        b >>= 1;
        x = x*x%mod;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    init();
    scanf("%d%d",&n,&k);
    rep(i,0,n-1){
        int u,v,val; scanf("%d%d%d",&u,&v,&val);
        addedge(u,v,val); addedge(v,u,val);
    }
    ll ans = pow3(n,k);
    ll last = 0;
    rep(i,1,n+1){
        if(vis[i]==0) dfs(i,-1);
        ll temp = t - last;
        last = t;
        ans = (ans + mod - pow3(temp,k)) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}
发表更新cf7 分钟读完 (大约1009个字)

[Codeforces Round #546 (Div. 2)题解]

Codeforces Round #546 (Div. 2)

D题题目读错把爷给整自闭了，此篇题解除了D都只有代码了

A. Nastya Is Reading a Book

做法

暴力

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n;
vector<int> ve;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        int l,r;scanf("%d%d",&l,&r);
        ve.push_back(r);
    }
    int page; scanf("%d",&page);
    int idx = lower_bound(ve.begin(),ve.end(),page) - ve.begin();
    printf("%d\n",n-idx);

    return 0;
}

B. Nastya Is Playing Computer Games

题解

找规律。 两个一组要六次。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    int n,a;
    scanf("%d%d",&n,&a);
    int ans = 0;
    if(n&1) ans+=3,ans += (n-1)*3;
    else ans += n*3;
    int mmin = min(n-a,a-1);
    ans += mmin;
    printf("%d\n",ans);


    return 0;
}

C. Nastya Is Transposing Matrices

题解

只有从左下到右上的有用。找规律。

我写得坐标变换有点绕。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 5e2+10;
int mx1[maxn][maxn], mx2[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx1[i]+j);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx2[i]+j);
    bool ans = true;
    n = max(n,m);
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,i+1){
            mmp[mx1[i-j][j]]++;
        }
        rep(j,0,i+1){
            mmp[mx2[i-j][j]]--;
            if(mmp[mx2[i-j][j]] == 0) mmp.erase(mx2[i-j][j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,n-i){
            mmp[mx1[n-j][i+j]]++;
        }
        rep(j,0,n-i){
            mmp[mx2[n-j][i+j]]--;
            if(mmp[mx2[n-j][i+j]] == 0) mmp.erase(mx2[n-j][i+j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }

    if(ans) puts("YES");
    else puts("NO");
    return 0;
}

D. Nastya Is Buying Lunch

题意

Nastya去排队，队伍中有这样一个规律。

  • 已知有$m$对$(i,j)$，他们如果是相邻的话，并且$i$在$j$的前面，那么他们就可以调换位置。

问Nastya能够往前调换多少次位置，已知Nastya在最后一名。

题解

一开始我是看错题意，以为是可以隔空调换，直接想着用图论找一个环或者是找一个树来做。没有想到必须要相邻才能换，那么我们就可以这样想，我们的答案最多就只有$Nastya能够往前交换的人的数量$。之后我们尽可能的就是将不能交换的人往前面移动，能交换的人往后面移动。之后由于是一个一个相邻的同学移动，所以如果从前开始尽量往后移动的话，有可能会有的同学到达不到Nasyta的范围了。从后往前交换，那么我们就是将不可换的同学尽量地想前面推，之后如果前面的同学先交换到后面，那么对河Nasyta可以到达的来说，他也是一定能交换到Nasyta到达的点的。

举个栗子:

4 4

1 2 3 4

2 4

1 4

1 2

1 3

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 3e5+10;
int idx[maxn];
set<int> st[maxn];
int a[maxn];
int vis[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,n+1){
        int x; scanf("%d",&x);
        a[i] = x; idx[x] = i;
    }
    rep(i,0,m){
        int x,y; scanf("%d%d",&x,&y);
        st[x].insert(y);
        if(y == a[n]) vis[x] = 1;
    }
    per(i,1,n-1){
        if(vis[a[i]] == 0) continue;
        int t = i;
        while(t<n-1 && st[a[t]].find(a[t+1]) != st[a[t]].end()){
            swap(a[t],a[t+1]);
            t++;
        }
    }
    int ans = 0;
    per(i,1,n){
        if(vis[a[i]] == 0) break;
        ans++;
    }
    printf("%d",ans);
    return 0;
}
发表更新cf9 分钟读完 (大约1325个字)

[cf545]A-D题解

Codeforces Round #545 (Div. 2)

ps 小生不才，比赛时只做出3道。后面补了一道。

Sushi for Two

题意

给定一个只含有1或者2的数组，让你找出一个子数组，子数组要求是$n个1 和 m个2$并要求$min(n,m)$最大。

题解

暴力模拟.

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    vector<int> ve;
    int n; scanf("%d",&n);
    int cnt1 = 0,cnt2 = 0;
    int ans = 0;
    rep(i,0,n) scanf("%d",a+i);
    int cnt = 0;
    while(cnt<n){
        cnt1= 0;
        cnt2 = 0;
        while(a[cnt] == 1){
            cnt++;
            cnt1++;
        }
        ve.push_back(cnt1);
        while(a[cnt] == 2){
            cnt++;
            cnt2++;
        }
        ve.push_back(cnt2);
    }
    int len = ve.size();
    rep(i,0,len-1){
        ans = max(ans,2*min(ve[i],ve[i+1]));
    }
    printf("%d\n",ans);
    return 0;
}

Circus

题意

给定$n$个人，其中每个人可能会表演小丑也可能会表演杂技演员。要求把$n$个人分成两堆。要求

  • 第一队只能表演小丑，第二队只能表演杂技演员
  • 第一队中小丑的个数和第二队中杂技演员的个数相等
  • 两队的人数相同。

题解

暴力枚举，因为人可以分为四类。所以我们可以枚举出其中两类的分配，之后通过条件舍掉一些答案，得到正确答案。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e3+10;
int idx[maxn][maxn];
int col_idx[maxn][maxn];
int mx[maxn][maxn];
int n,m;
int cnt_row[maxn];
int cnt_col[maxn];
int ans[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m){
        scanf("%d",mx[i] + j);
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(j,0,m-1){
            if(ve[j] == ve[j+1]) cnt_row[i]++;
        }
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(i,0,n-1){
            if(ve[i] == ve[i+1]) cnt_col[j]++;
        }
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(j,0,m) idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(i,0,n) col_idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(i,0,n) rep(j,0,m){
        int x = idx[i][j];
        int y = col_idx[i][j];
        int temp = 0;
        if(x>y){
            temp = max(m - cnt_row[i], n + abs(x-y) - cnt_col[j]);
        }else{
            temp = max(n - cnt_col[j], m + abs(x-y) - cnt_row[i]);
        }
        ans[i][j] = temp;
    }
    rep(i,0,n) rep(j,0,m) {
        printf("%d%c",ans[i][j],j==m-1?'\n':' ');
    }

    return 0;
}

C. Skyscrapers

题意

较为简单，自己看吧。

题解

离散化+一些技巧。

因为横竖上最大值会因为中间而改变，所以答案是在

$$max(n-cnt[i],m+abs(x-y)-cnt[j])$$

中产生的。其中$cnt[i]$表示行的重复个数，$cnt[j]$表示列的重复个数。$x,y$表示在行和列中的排名。

我做的有一点烦

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 1e3+10;
int idx[maxn][maxn];
int col_idx[maxn][maxn];
int mx[maxn][maxn];
int n,m;
int cnt_row[maxn];
int cnt_col[maxn];
int ans[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m){
        scanf("%d",mx[i] + j);
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(j,0,m-1){
            if(ve[j] == ve[j+1]) cnt_row[i]++;
        }
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        rep(i,0,n-1){
            if(ve[i] == ve[i+1]) cnt_col[j]++;
        }
    }
    rep(i,0,n){
        vector<int> ve;
        rep(j,0,m) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(j,0,m) idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(j,0,m){
        vector<int> ve;
        rep(i,0,n) ve.push_back(mx[i][j]);
        sort(ve.begin(),ve.end());
        auto iter = unique(ve.begin(),ve.end());
        ve.erase(iter,ve.end());
        rep(i,0,n) col_idx[i][j] = lower_bound(ve.begin(),ve.end(),mx[i][j]) - ve.begin();
    }
    rep(i,0,n) rep(j,0,m){
        int x = idx[i][j];
        int y = col_idx[i][j];
        int temp = 0;
        if(x>y){
            temp = max(m - cnt_row[i], n + abs(x-y) - cnt_col[j]);
        }else{
            temp = max(n - cnt_col[j], m + abs(x-y) - cnt_row[i]);
        }
        ans[i][j] = temp;
    }
    rep(i,0,n) rep(j,0,m) {
        printf("%d%c",ans[i][j],j==m-1?'\n':' ');
    }

    return 0;
}

D. Camp Schedule

题意

给定两串字符串$s,t$。要求把$s$重新排列使得$s$中的子串里，$t$出现的次数尽可能多。

题解

kmp

我们可以想象一下，如果要$s$中要有尽量多的$t$，那么首先我们在$s$的最前面是一个$t$。之后我们需要加入后续的数字，使得尽可能多的像$t$。这和kmp的思想是很相似的。就是我们在最后一个字母失配之后，我们应该跳转到的那个字母开始，继续匹配就可以匹配成一个字符串了。

举个栗子吧。

111000

101

这个例子中，我们先在$s$的前面放一个$101$。

之后我们需要配一个字母，使得尽量减少失配的字符串的长度，所以我们加入$len[next]$，也就是$0$。之后我们加入$1$形成了$10101$这样就产生了两个$t$。之后我们模拟这样子的行为就可以了。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e5+10;
char s[maxn],t[maxn];
int nxt[maxn];
void getnxt(char *str){
    int len = strlen(str);
    int i = 0, j = -1;
    nxt[0] = -1;
    while(i<len){
        if(j==-1 || str[i] == str[j]){
            i++,j++;
            nxt[i] = j;
        }else{
            j = nxt[j];
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%s",s); scanf("%s",t);
    getnxt(t);
    int len = strlen(t);
    int sz = 0;
    int cnt0 = 0,cnt1 = 0;
    int len1 = strlen(s);
    rep(i,0,len1){
        if(s[i] == '1') cnt1++;
        else cnt0++;
    }
    int i = 0;
    bool flag = true;
    while(flag && cnt0 > 0 && cnt1 > 0){
        for(i;i<len;i++){
            if(t[i] == '1' && cnt1-- > 0) printf("1");
            else if(t[i] == '0' && cnt0-- > 0) printf("0");
            else {
                flag = false;break;
            }
        }
        i = nxt[len];
    }
    while(cnt0-->0) printf("0");
    while(cnt1-->0) printf("1");
    return 0;
}
发表更新cf3 分钟读完 (大约425个字)

[cf541D]Gourmet choice (缩点+dfs)

Gourmet choice

题意

给定$n$个蛋糕和$m$个蛋糕，和他们之间的大小关系。问给所有的蛋糕一个可能最小的值，使得关系成立。

题解

首先由于有$=$的存在，有一些蛋糕的值是要一样的。所以我们需要把题目中的相等的点给缩到一起。

之后用dfs把值给确定下来。

其中缩点用到的技巧很厉害。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
vector<int> e[maxn];
// m is behind of the n
int fa[maxn];
int Find(int x){
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int i,int j){
    int x = Find(i);
    int y = Find(j);
    if(x!=y) fa[x] = y;
}
int ind[maxn],use[maxn],vis[maxn];
char mx[maxn][maxn];
int n,m;
// flag means the 矛盾
bool flag;
int dp[maxn];
void dfs(int x,int dep){
    if(flag) return ;
    dp[x] = max(dp[x],dep);
    for(auto to:e[x]){
        if(vis[to]) {
            flag = true;
            return ;
        }
        if(dep+1>dp[to]){
            vis[to] = 1;
            dfs(to,dep+1);
            vis[to] = 0;
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n){
        scanf("%s",mx+i);
    }
    rep(i,0,n+m) fa[i] = i;
    rep(i,0,n)
        rep(j,0,m)
            if(mx[i][j] == '=')
                Union(i,n+j);
    rep(i,0,n) rep(j,0,m){
        int x = Find(i); int y = Find(j+n);
        if(mx[i][j] == '<'){
            e[x].push_back(y);
            ind[y] ++;
            use[x] = 1;
        }else if(mx[i][j] == '>'){
            e[y].push_back(x);
            ind[x] ++;
            use[y] = 1;
        }else{
            use[x] = 1;
        }
    }
    bool fflag = false;
    rep(i,0,n+m){
        if(use[i] && ind[i] == 0){
            fflag = true;
            vis[i] = 1;
            dfs(i,1);
            vis[i] = 0;
        }
    }
    if(fflag == false || flag){
        puts("No");
    }else{
        puts("Yes");
        rep(i,0,n) printf("%d ",dp[Find(i)]);
        puts("");
        rep(i,n,m+n) printf("%d ",dp[Find(i)]);
    }
    return 0;
}
发表更新cf9 分钟读完 (大约1406个字)

Codeforces Round #542

Codeforces Round #542

A. Be Positive

题意

给定一个数组$a_1,a_2,…,a_n$，让你到一个数字，是的数组内的所有数字处以这个数字之后，数组内大于0的数字超过$\cfrac{n}{2}$的上界。

题解

由于没有要求整除，所以直接看负数多还是正数多，哪个超过上届，就用$-1或者1$

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 1e3+10;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&n);
    int cnt1=0,cnt2=0;
    rep(i,0,n){
        scanf("%d",a+i);
        if(a[i]>0) cnt1++;
        if(a[i]<0) cnt2++;
    }
    int ans = 0;
    if(n%2) n++;
    if(cnt1>=n/2) ans = 1;
    if(cnt2>=n/2) ans = -1;
    printf("%d",ans);
    return 0;
}

B. Two Cakes

题意

两个人要买$n$层蛋糕，他们必须从$1$开始买到$n$，之后给定$2n$个蛋糕店，他们从$1$这个点出发，之后去买蛋糕。其中一旦一个人从一家蛋糕店买了蛋糕，那么另外一个人就不能在那家蛋糕店买蛋糕。问两个人花费的最少步数是多少？

题解

由于每一步只有两种可能，一个人去$x+1$中的一家蛋糕店，另外一个人去另一家。每一步的选择都只有两种，且无后效性。所以我们用贪心来解决。每一步的时候都选择花费步数最少的选择。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
int n;
struct node{
    int idx,val;
    bool operator<(const node &x){
        return val < x.val;
    }
}a[maxn<<1];
int vis[maxn*2];
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,2*n){
        int x; scanf("%d",&x);        
        a[i].idx = i+1; a[i].val = x;
    }
    sort(a,a+2*n);
    int cnt = 0;
    int now1 = 1, now2 = 1;
    ll ans = 0;
    for(int i=0;i<2*n;i+=2){
        int temp = INF;
        int x1 = abs(now1 - a[i].idx) + abs(now2 - a[i+1].idx);
        int x2 = abs(now2 - a[i].idx) + abs(now1 - a[i+1].idx);
        if(x1>x2){
            now2 = a[i].idx;
            now1 = a[i+1].idx;
        }else{
            now1 = a[i].idx;
            now2 = a[i+1].idx;
        }
        ans += 1ll * min(x1,x2);
    }
    printf("%lld\n",ans);


    return 0;
}

C. Connect

题意

Alice要从一个陆地到另外一块陆地，需要建造一座大桥，问桥的花费要最少。

  • 桥的花费是欧几里得距离的平方
  • 只能建造一座桥
  • 可能不需要建造桥

题解

由于只建造一座桥，所以我们可以枚举起始点的陆地和终点的陆地，之后挑选出最近的点。

由于数据小，随便做。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
int stx,sty,edx,edy;
int dir[4][2] = {1,0, -1,0, 0,1, 0,-1};
const int maxn = 100;
int vis[maxn][maxn];
char mx[maxn][maxn];
vector<pII > st;
vector<pII > ed;
void bfs(int x,int y,bool sign){
    vis[x][y] = 1;
    queue<pair<int,int> >q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int xx = q.front().first; int yy = q.front().second;
        q.pop();
        if(sign) st.push_back(make_pair(xx,yy));
        else ed.push_back(make_pair(xx,yy));
        rep(i,0,4){
            int xxx = xx + dir[i][0];
            int yyy = yy + dir[i][1];
            if(xxx<0 || xxx >=n || yyy<0 || yyy>=n) continue;
            if(mx[xxx][yyy] == '1') continue;
            if(vis[xxx][yyy])  continue;
            vis[xxx][yyy] = 1;
            q.push(make_pair(xxx,yyy));
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d",&n);
    scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
    stx--;sty--;edx--;edy--;
    rep(i,0,n){
        scanf("%s",mx+i);
    }
    int ans = INF;
    bfs(stx,sty,1);
    bfs(edx,edy,0);
    int len1 = st.size();
    int len2 = ed.size();
    rep(i,0,len1){
        rep(j,0,len2){
            int x1 = st[i].first;
            int y1 = st[i].second;
            int x2 = ed[j].first;
            int y2 = ed[j].second;
            ans = min(ans,(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        }
    }
    printf("%d\n",ans);
    return 0;
}

D2. Toy Train

题意

Alice开火车，他火车的轨道是确定的，之后火车开的方向也是确定的，火车的轨迹是一个圈，轨迹上有很多站点，每个站点上有糖果。

  • 火车在站点上只可以拿起一个糖果
  • 火车在站点上可以放下无限个糖果

目标是将所有站点上的糖果放到指定的站点所花费的时间最小。

题解

由于每一个站点都是独立的。你只需要管他是怎么拿起来的。所以每一个站点如果有$x$个糖果，那么从他开始至少要$x-1$圈加上一个最短的距离。所以我们可以枚举每一个站点所需要的最远距离。

假设从$i$起始点到$j$站点。那么我们开始的距离是$dis(i,j)=(j-i+n)\mod n$。

之后我们需要$x-1$圈。$(x-1)\times n$

之后我们需要从那个点到最近的放置点.$dis(j,z) = (z-j+n)\mod n$

之后两层循环即可。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
const int maxm = 2e2+10;
int n,m;
vector<int> candys[maxn];
int ans[maxn];
int main(){
#ifdef LOCAL
    freopen("4.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,m){
        int x,y;scanf("%d%d",&x,&y);
        candys[x-1].push_back(y-1);
    }
    int mmax = 0;
    rep(i,0,n){
        mmax = max(mmax,(int)candys[i].size());
    }
    // ans 
    rep(i,0,n){
        int ans = 0;
        rep(j,0,n){
            if(candys[j].size()==0)continue;
            int temp = (j-i+n)%n;
            int tx = INF;
            for(auto &x: candys[j]){
                tx = min(tx,(x-j+n)%n);
            }
            ans = max(ans, ((int)candys[j].size()-1)*n + tx + temp);
        }
        printf("%d ",ans);
    }
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×