标签: 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;
}
发表更新16004 分钟读完 (大约630个字)

codeforces 1600-2200 题目刷

F. Graph Without Long Directed Paths

题意

给定一个无向图，里面没有重边也没有circle也就是自反。问把这个无向图变成有向图，怎么变才能使得图中的路径没有超过2的，就是可以穿过两条边的路径。

输出是 每条边是正向还是反向。

题解

一开始想着只能有树的格式，但是其实是找一个偶数环。如果有奇数环就一定无法实现路径小于2，偶数环都可以实现。之后将每个点指定为1或者0。之后如果1到0就把边置为1，0到1就把边置为0。详情请看代码。

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
#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 = 2e5+10;
struct node{
    int next,to;
}G[maxn<<2];
int head[maxn];
int cnt;
void init(){
    cnt = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int n,m;
map<pair<int,int>,int> mx;
int vis[maxn];
bool flag = false;
void dfs(int u,int fa,int f){
    vis[u] = f;
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v == fa) continue;
        mx[make_pair(u,v)] = f;
        mx[make_pair(v,u)] = f^1;
        if(vis[v] == -1){
        }else{
            if(vis[v]^vis[u]) continue;
            else {
                flag = true;
                continue;
            }
        }
        dfs(v,u,f^1);
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    init();
    scanf("%d%d",&n,&m);
    vector<pair<int,int> > ve;
    rep(i,0,m){
        int u,v; scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
        ve.push_back(make_pair(u,v));
    }
    memset(vis,-1,sizeof(vis));
    dfs(1,-1,1);
    if(flag) {
        puts("NO");
    }else{
        puts("YES");
        for(auto &x : ve){
            printf("%d",mx[x]);
        }
        puts("");
    }

    return 0;
}

E. Median String

题意

问两个字符串$s,t$。他们字典序中间的那个字符串是什么。

举个栗子: a 和 e的中间字符串就是c。

题解

就是模拟大数加和大数除法。将字符串看成26进制的数字。

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
#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 = 2e5+10;
char s[maxn];
char t[maxn];
char ans[maxn];
char temp[maxn];
int n;
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&n);
    scanf("%s",s+1);
    scanf("%s",t+1);
    int flag = 0;
    per(i,1,n+1){
        int tt = (s[i] + t[i] - 'a'*2 + flag);
        flag = 0;
        if(tt >= 26) flag = 1;
        temp[i] = (tt%26+'a');
    }
    int ttt = 1;
    if(flag) temp[0] = 'b';
    if(flag) ttt=0;
    flag = 0;
    rep(i,ttt,n+1){
        int tt = (temp[i] - 'a' + flag*26);
        flag = 0;
        if(tt%2==1) flag = 1;
        tt /=2;
        ans[i] = (tt+'a');
    }
    printf("%s",ans+1);
    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;
}
发表更新dp2 分钟读完 (大约364个字)

[cf706C]Hard Problem

706C - Hard problem

题意

题意很简单，就是给定$n$串字符串，对每一串字符串只有一种操作，翻转。之后每翻转一个字符串需要消耗$c_i$的能量，问至少需要多少能量是的，这$n$个字符串是以字典序排列的。

ps:相等也算按字典序

题解

dp，定义一个二维数组$dp[i][j]$。其中$i$表示第$i$个字符串中选择$j$产生字典序的最少能量消耗。$j$只有1和0，表示翻转或者不翻转，之后就是四种情况下去。具体可以看代码.

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
#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

ll n,m,q;
ll d;
const int maxn = 210;
ll num[maxn];
ll dp[maxn][12][22];
ll a[maxn];
ll MOD(ll x,ll mod){
    ll tx = x % mod;
    if(tx<0) tx += mod;
    return tx;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int T; scanf("%d",&T);
    rep(test_case,1,T+1){
        scanf("%lld%lld",&n,&q);
        rep(i,1,n+1) scanf("%lld",num+i);
        printf("Case %d:\n",test_case);
        while(q--){
            scanf("%lld%lld",&d,&m);
            rep(i,1,n+1) a[i] = MOD(num[i],d);
            memset(dp,0,sizeof(dp));
            rep(i,0,n) dp[i][0][0] = 1;
            rep(i,1,n+1){
                rep(j,1,m+1){
                    rep(k,0,d) dp[i][j][k] = dp[i-1][j][k];
                    rep(k,0,d){
                        dp[i][j][(k+a[i])%d] += dp[i-1][j-1][k];
                    }
                }
            }
            printf("%lld\n",dp[n][m][0]);
        }
    }
    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;
}
发表更新cf15003 分钟读完 (大约522个字)

Codeforces Round #499 (Div. 2)

Codeforces Round #499 (Div. 2)](http://codeforces.com/contest/1011)

A. Stages

题意

给定一段序列，每个字母代表这一个权值，比如$a$代表$1$。之后问从中挑选出一个序列，要求$a[i]$和$a[i+1]$之间相隔一个字母，问从任意顺序选择$k$个字母，最少可以有多少权值。

题解

贪心，其实如果取最大值的话， 我就有点不会了。但是取最小值可以贪心的对所有位置都取能取的最小值。

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
#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,k;
const int maxn = 60;
char s[maxn];
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    int len = strlen(s);
    rep(i,0,n) a[i] = s[i] -'a'+1;
    sort(a,a+len);
    int ans = 0;int t = 0;int si = -3;
    rep(i,0,len){
        if(si<a[i]-1 && t<k){
            ans +=a[i];
            t++;
            si = a[i];
        }
    }
    if(t==k){
        printf("%d\n",ans);
    }else{
        puts("-1");
    }
    return 0;
}

B. Planning The Expedition

题意

每个人每天都要吃一个特定种类(由你分配)的食物，你现在有$k$种食物，每个食物都有对应的数量，问怎么分配可以在当前食物下过存活尽量多的天数。

题解

二分枚举答案(坑爹cf，$m<100$二分都不用)。因为答案是递减的。

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 m,n;
const int maxn = 110;
int a[maxn],b[maxn];
bool cmp(int a,int b){
    return a>b;
}
int cnt,ans;
void dfs(int day,int idx,int p){
    if(p <= 0){
        ans = max(ans,day);
        return;
    }
    if(idx ==cnt) return;
    for(int i=1;i<=a[idx];i++){
        if(a[idx] / i < day) continue;
        dfs(day,idx+1,p-i);
    }
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,m+1){
        int x;scanf("%d",&x);
        a[x]++;
    }
    ans = 0;
    sort(a+1,a+m+1,cmp);
    rep(i,1,101) if(a[i]==0) {cnt = i;break;}
    for(ans = 1;ans<=100;ans++){
        int peo = 0;
        rep(i,1,10){
            peo += a[i]/ans;
        }
        if(peo <n){
            break;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

C.Fly

题意

每次降落和出发都需要消耗燃料，问最少带多少燃料可以来一次旅行。

题解

小学奥数题，反向做即可。

AC代码

1

D. Rocket

题意

猜数字，你问至多$60$次数字，他给出你问的数字是大了还是笑了，他有一个循环答题方案，比如第一次打错，第二次答对，循环少于$30$次。让你问出答案。

题解

循环至多$30$次暗示了你可以故意说一些已知的问题来试他。比如问-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
#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;
bool vis[100];
int query(int x){
    int y;
    cout<<x<<endl;
    fflush(stdout);
    cin>>y;
    return y;
}
int main(){
#ifdef LOCAL
    //freopen("4.in","r",stdin);
#endif
    scanf("%d%d",&m,&n);
    rep(i,0,n){
        int x = query(1);
        if(x == 0){
            cout<<1<<endl;
            return 0;
        }
        if(x<0) vis[i] = 1;
    }
    int mid = 0;int cnt = 0;
    int l,r;
    l = 1,r = m;
    while(l<=r){
        mid = (l+r)>>1;
        int y = query(mid);
        if(vis[cnt]) y = -y;
        if(y==1) l = mid+1;
        else if(y==-1)r = mid-1;
        else{
            cout<<mid<<endl;
            return 0;
        }
        cnt = (cnt+1)%n;
    }
    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.
×