CheaSim Blog
发表更新学习笔记5 分钟读完 (大约793个字)

我是Makefile

我是Makefile

我是makefile而不是makelove。最近学校开了Linux这门课，于是我就开始自学Linux了，看的是《Linux就是这个范儿》。实名制推荐，语言又风趣又实在。

什么是Makefile

作为一名程序员，我们第一个程序大概率是通过vs或者是vc6.0来写的。这些都是IDE集成开发环境，他们帮我们做了很多事情，很多底层的事情。其中比较重要的就是编译这个命令了。如果像我参加acm的，会知道如果经常只是写一个单cpp文件的话，我们只需要使用GCC中的g++命令就可以完成将cpp文件编译成可执行文件，但是如果我们是写一个项目呢？如果我们的项目中有好几个头文件，好几个cpp文件呢？这时候makefile就出现了。

Makefile的作用就是自动化编译，一旦我们写好了makefile文件，只需要一个make命令，整个工程就能自动编译。Makefile定义了一系列的规则，来指定哪些文件需要先编译，哪些文件需要后编译，就像一个shell脚本一样。

IDE是高手的挡泥板，却是新手的遮阳伞。

我在南大的编译原理课件中就看到，他们项目的要求也是要用Makefile来完整的做一个项目的。南大还是南大啊。

Makefile的基本概念

目标、条件和命令

对于Makefile来说，最最重要的就是目标、条件和命令这三大要素。

  • 目标是make要产生的东西或者是要做的事情
  • 条件是用于产生目标所需要的文件
  • 命令是有条件转化为目标的方法

举个例子

1
2
main.o:main.c line.h buffer.h tedef.h
	cc -c -o main.o main.c

main.o就是目标，main.c line.h buffer.h tedef.h就是条件，最下面那句”cc -c -o main.o main.c”就是命令。

all命令就是Makefile的默认目标。

基本语法

Makefile是看成是一种解释型语言，一般解释型语言都是采用“自顶向下”的解释逻辑。

tip:所有命令都是需要以\tab开头的，规定如此

变量

作为一种类似语言的东西，那么变量肯定是少不了啊。Makefile中的变量类似于宏替代，采用的语法。

1
CC := gcc -g

这就定义了一个变量，变量的名称是CC，变量的值是”gcc -g”，我们可以用”$()或者${}”来替代。

自动变量

Makefile中有特殊变量，他们可以自动取用一条规则中目标和条件中的元素，这样就可以节省输入文件名和条件文件名的力气。ps:确实在vim一键编译中我也看到了类似的东西。

并且自动变量不需要加$().

发表更新学习计划1 分钟读完 (大约206个字)

4月计划

4月9日

  • 背单词
  • 数学全书复习
  • cf两道题目

4月10日

上午满课，下午2点可以开始学习。

  • 背一篇作文，熟悉到能够默写。
  • cf两道题目
  • 数学10道小题 —3道
  • linux作业完成
  • makefile搞定一下，顺便把原来历史遗留的编译原理大作业用makefile写一下。pro~

结果看知乎看到六点，英语也没背，就去做了个ccpc2050热身赛的题目。

4月17日 周三

上午下午各一节课。有点难受。上午三四节的时间摸鱼。

下午3.40左右开始正式学习

  • 背单词
  • cf.div2 D和E solve
  • 数学20题，先看笔记后做题
  • 至少看一节视频，并做笔记。 汤神！！！
发表更新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;
}
发表更新Linux几秒读完 (大约46个字)

Linux学习笔记

Linux

这个学期上了Linux，顺便做点笔记。 看的书是 《Linux就是这个范儿》 还挺有意思的。

实验(Linux进程管理和通信)

发表更新蓝桥杯4 分钟读完 (大约543个字)

第十届蓝桥杯题解

第十届蓝桥杯题解(个人向)

第一题 平方和

算$1 ​$到$2019​$中含有$2,0,1,9​$的数的平方和。

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

bool check(int x){
    while(x){
        int t = x % 10;
        x /= 10;
        if(t == 1 || t == 0 || t == 9 || t == 2) return true;
    }
    return false;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    ll ans = 0;

    rep(i,1,2019+1){
        if(check(i)) ans += 1ll * i*i;
    }
    printf("%lld\n",ans);
    return 0;
}

第二题 数列求值

求类似斐波那契数列$f[i] = f[i-1] + f[i-2] + f[i-3]$ ，求$f[20190324]%10000$。

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
#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 a[10];
const int mod = 1e4;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    a[0] = 1;
    a[1] = 1;
    a[2] = 1;
    rep(i,3,20190324){
        a[3] = (a[0] + a[1] + a[2]) % mod;
        rep(j,0,3) a[j] = a[j+1];
    }
    printf("%d\n",a[2]);
    return 0;
}

第三题 最大降雨量

答案34.贪心即可。注意中位数的中位数

第四题 迷宫

第九题 糖果

题意

有n袋糖，里面有m种糖，每袋糖有k个，问至少取几包才能攒够所有种类的糖。

$n \leq 100;m,k\leq 20​$

题解

状压dp。我场上直接上暴力了。但是场下经过队友提示，发现就是个简单的状压dp。

因为他的$m$低于20所以我们可以用二进制位来表示。总的复杂度$O(2^m *n)$

状态转移方程 $dp[S|i] = min(dp[S|i],dp[i]+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
#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,k;
const int maxm = 21;
const int maxn = 110;
int dp[1<<maxm];
int sta[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    rep(i,0,n){
        rep(j,0,k){
            int x; scanf("%d",&x);
            dp[i] |= (1<<(x-1));
        }
    }
    rep(i,0,(1<<m)) dp[i] = INF;
    dp[0] = 0;
    for(int i = 0;i<(1<<m);i++){
        rep(j,0,n){
            dp[i|sta[j]] = min(dp[i]+1,dp[i|sta[j]]);
        }
    }
    printf("%d\n",dp[(1<<m)-1]!=INF?dp[(1<<m)-1]:-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;
}
发表更新蓝桥杯3 分钟读完 (大约509个字)

蓝桥杯历届题目

还有6天蓝桥杯了

开始刷历届练习题了。

小计算器

题意

实现一个直接的计算器。没有四则运算规则优先级。并且能够有进制转换

题解

数字转换字符串的时候,$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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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;
typedef  long long ull;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxchar = 100;
const int maxn = 100;
char s[maxn];
int k;
char ans[maxn];
void solve(ull x){
    memset(ans,0,sizeof(ans));
    ull t = k;
    int cnt = 0;
    if(x==0) ans[0] = '0';
    while(x){
        if(x%t < 10){
            ans[cnt++] = x%t+'0';
        }else{
            ans[cnt++] = x%t+'A'-10;
        }
        x/=t;
    }
    int len = strlen(ans);
    rep(i,0,len/2) swap(ans[i],ans[len-1-i]);
}
char tt[maxn];
ull real_num(){
    int len = strlen(tt);
    ull t = 0;
    ull cnt = 1;
    per(i,0,len){
        if(tt[i]>='A' && tt[i]<='Z'){
            t += cnt * (tt[i] - 'A' +10);
        }else{
            t += cnt * (tt[i] - '0');
        }
        cnt*= k;
    }
    return t;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    cin>>n;
    ull now = 0;
    int sign = 0;
    k = 10;
    bool init = false;
    rep(i,0,n){
        cin>>s;
        if(s[0] == 'C' && s[1] == 'L') {
            now = 0;
            init = true;
        }else if(s[0] == 'N'){
            cin>>tt;
            ull temp = real_num();
            if(init){
                now = temp;
                init = false;
                continue;
            }
            if(sign == 1) now += temp;
            else if(sign == 2) now -= temp;
            else if(sign == 3) now *= temp;
            else if(sign == 4) now /= temp;
            else now %= temp;
        }else if(s[0] == 'A'){
            sign = 1;
        }else if(s[0] == 'S'){
            sign = 2;
        }else if(s[0] == 'M' && s[1] == 'U'){
            sign = 3;
        }else if(s[0] == 'D'){
            sign = 4;
        }else if(s[0] == 'M'){
            sign = 5;
        }else if(s[0] == 'E'){
            solve(now);
            cout<<ans<<'\n';
        }else{
            cin>>k;
        }
    }
    return 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
#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;
int fa[maxn*maxn];
int Find(int x){
    if(fa[x] == x) return x;
    else return fa[x] = Find(fa[x]);
}
int Union(int x,int y){
    int i = Find(x);int j = Find(y);
    if(i!=j) fa[j] = i;
}
int n,m;
int k;
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,n*m+1) fa[i] = i;
    rep(i,0,k){
        int x,y; scanf("%d%d",&x,&y);
        Union(x,y);
    }
    int ans = 0;
    rep(i,1,n*m+1) if(fa[i] == i) ans++;
    printf("%d\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;
}
发表更新考研路漫漫2 分钟读完 (大约308个字)

三月计划

March

每天记录一点在计算中心的计划。

a plan a day,a master i will be. even a phD!

3/11

  • 背一单元单词
  • 高数第一单元finish
  • hash题目搞定
  • 不看贴吧
  • 不看斗鱼

hash完成了两道。

贴吧看的飞起。斗鱼看的飞起。

3/12

  • 颓废一天

3/13

  • 上计算机网络
  • 不看Bilibili
  • 不看斗鱼
  • 不看贴吧
  • 不看知乎
  • 不点外卖

3/14

  • 背单词
  • 帮个同学搬宿舍
  • cf回顾+字符串题目

3/15

  • 不看Bilibili
  • 不看斗鱼
  • 不看贴吧
  • 不看知乎
  • 不点外卖
  • 背单词
  • 高数题目做做做 并纠错。

3/16

3/17

  • 不看Bilibili
  • 不看斗鱼
  • 不看贴吧
  • 不看知乎
  • 不点外卖

3/18

  • 不看Bilibili
  • 不看斗鱼
  • 不看贴吧
  • 不看知乎
  • 不点外卖
  • 计算机网络作业搞定
  • 高数课后习题 整理一下
  • cf题目D搞定
  • 蓝桥杯题目+字符串题目 at least 5 p

蓦然回首已经是四月9号了。

看来我还是比较摸鱼的。

计划都没有实施的比较完善。

我决定，开启流浪四月计划，四月每周更新一下一周做了什么事情。

发表更新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;
}
关注我

链接

分类

最新文章

归档

标签

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.
×