Openjudge BJUTACM 19g系列代码

发表评论

题目链接：
http://bjutacm.openjudge.cn/lianxi/?page=2

A题：求树的直径（有大佬说这题有毛病，数据水，还有可能的情况是一个孤立点+环。）

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
#include<iostream>
#include<vector>
using namespace std;
vector<int> edges[10005];
int depth[10005];
int n,s;
void getDepth(int node,int father){
    depth[node]=depth[father]+1;
    for(int i=0;i<edges[node].size();i++){
        if(edges[node][i]!=father)getDepth(edges[node][i],node);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    if(n==0){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==0)s=i;
        edges[i].push_back(x);
        edges[x].push_back(i);
    }
    getDepth(s,0);
    s=1;
    for(int i=2;i<=n;i++)if(depth[i]>depth[s])s=i;
    getDepth(s,0);
    int node=1;
    for(int i=2;i<=n;i++)if(depth[i]>depth[node])node=i;
    cout<<depth[node];
}

B题：栈模拟

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
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;
string s;
long long getInt(int & ptr){
    stack<int> st;
    for(;ptr<s.size();){
        if('0'<=s[ptr]&&s[ptr]<='9'){
            st.push(s[ptr]-'0');
            ptr++;
        }
        else break;
    }
    long long value=0;
    while(!st.empty()){
        value*=10;
        value+=st.top();
        st.pop();
    }
    return value;
}
long long oper(long long x,long long y,char c){
    switch(c){
        case '+':return x+y;break;
        case '-':return x-y;break;
        case '*':return x*y;break;
        case '/':return x/y;break;
    }
    return -1;
}
void solve(){
    cin>>s;
    reverse(s.begin(),s.end());
    int ptr=0;
    long long result=getInt(ptr);
    while(ptr<s.size()){
        char c=s[ptr++];
        long long y=getInt(ptr);
        result=oper(result,y,c);
    }
    cout<<result<<'\n';
}
int main(){
    int n;
    cin>>n;
    while(n--){
        solve();
    }
}

C题：赛场上没做出来，赛后看题解做的。赛场上一直以为是欧拉回路，拼命判度数怎么都不对，后来就放弃了。正解是网络流最大流，建双向边，每条边的容量为1，看最后从1点到n点的流量是否大于等于2。[EK算法]

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<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 30005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1];
int head[vN];
bool vis[vN];
struct Pre { int preNode, eID; }pre[vN];
inline void create1Edge(int u, int v, int w) {
    to[++ePtr] = v;
    value[ePtr] = w;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
inline void createEdge(int u, int v, int w) {
    create1Edge(u, v, w);
    create1Edge(v, u, 0);
}
inline bool bfs(int s, int t) {
    queue<int> q;
    memset(vis, false, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s].preNode = s;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (!vis[dest] && value[i]) {
                pre[dest].preNode = x;
                pre[dest].eID = i;
                vis[dest] = true;
                if (dest == t)return 1;
                q.push(dest);
            }
        }
    }
    return 0;
}
inline int EK(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int minV = INF;
        for (int i = t; i != s; i = pre[i].preNode)minV = min(minV, value[pre[i].eID]);
        for (int i = t; i != s; i = pre[i].preNode) {
            value[pre[i].eID] -= minV;
            value[pre[i].eID ^ 1] += minV;
        }
        ans += minV;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        createEdge(x, y, 1);
        createEdge(y, x, 1);
    }
    if (EK(1, n) >= 2)cout << "Yes";
    else cout << "No";
}

[Dinic算法]

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 30005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1];
int head[vN], dis[vN], cur[vN];
inline void create1Edge(int u, int v, int w) {
    to[++ePtr] = v;
    value[ePtr] = w;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
inline void createEdge(int u, int v, int w) {
    create1Edge(u, v, w);
    create1Edge(v, u, 0);
}
inline bool bfs(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] == INF && value[i] != 0) {
                dis[dest] = dis[x] + 1;
                q.push(dest);
            }
        }
    }
    return dis[t] != INF;
}
inline int dfs(int x, int t, int maxflow) {
    if (x == t)return maxflow;
    int ans = 0;
    for (int i = cur[x]; ~i; i = nxt[i]) {
        int dest = to[i];
        if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;
        cur[x] = i; //当前弧优化
        int f = dfs(dest, t, min(value[i], maxflow - ans));
        value[i] -= f;
        value[i ^ 1] += f;
        ans += f;
    }
    return ans;
}
inline int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        ans += dfs(s, t, INF);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        createEdge(x, y, 1);
        createEdge(y, x, 1);
    }
    if (dinic(1, n) >= 2)cout << "Yes";
    else cout << "No";
}

D题，解一元二次方程判delta>=0：

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
int main(){
    long long x;
    cin>>x;
    long long re=x*x-4*x;
    if(re>=0)cout<<"YES";
    else cout<<"NO";
}

E题，赛场上不知道，看题解做出来的。计算几何 n维超立方体的边数公式为n*2^{n-1}，n太大，不能直接算，采取边读边模的方法，用费马小定理化简幂次，相乘输出。

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
#include<iostream>
#include<string>
using namespace std;
const long long MOD = 1000000007;
string n;
long long getMOD(long long mod) {
    long long result = 0;
    for (int i = 0; i < n.size(); i++) {
        result *= 10;
        result += n[i] - '0';
        result %= mod;
    }
    return result;
}
long long quickpow(long long x, long long y, long long mod) {
    if (y == 0)return 1;
    long long result = quickpow(x, y / 2, mod);
    result = result * result % mod;
    if (y & 1)result = result * x % mod;
    return result;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    long long exp = (getMOD(MOD - 1)-1+MOD-1)%(MOD-1);
    long long n2 = getMOD(MOD);
    cout << quickpow(2, exp, MOD) * n2 % MOD;
}

F题：挖坑，有空就填，没空算了
G题：简单模拟，注意看清题就行

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main(){
    long long n,cnt=0;
    cin>>n;
    while(n!=1){
        if(n%2==0)n/=2;
        else n+=2*n+1;
        cnt++;
    }
    cout<<cnt;
}

H题：内存只给1M，之前用unordered_map一直报RE，后来出题方提示MLE在DOMJudge上会显示RE，于是回去查内存了。正解是摩尔投票算法。之前好像见过这个算法，就稀里糊涂的写上去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n,x,cnt=0;
    cin>>n;
    cin>>x;
    cnt=1;
    for(int i=2;i<=n;i++){
        int t;
        cin>>t;
        if(cnt==0){
            x=t;
            cnt=1;
        }else if(x==t)cnt++;
        else cnt--;
    }
    cout<<x;
}

I题：DP，竟然赛场上推出来了，平时一般都是推不出来的，可能是因为赛场上比较着急所以一下子灵光乍现。。转移方程直接看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int costs[3][1005];
int f[3][1005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=0;j<3;j++)cin>>costs[j][i];
    for(int i=1;i<=n;i++){
        f[0][i]=min(f[1][i-1],f[2][i-1])+costs[0][i];
        f[1][i]=min(f[0][i-1],f[2][i-1])+costs[1][i];
        f[2][i]=min(f[0][i-1],f[1][i-1])+costs[2][i];
    }
    cout<<min(f[0][n],min(f[1][n],f[2][n]));
}

J题：倒序输出数字，如果字符串做的话注意卡前导0的情况，不如干脆直接用int读入while输出一下再特判0就完事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int x;
    cin>>x;
    if(x==0){
        cout<<0;
        return 0;
    }
    while(x){
        cout<<x%10;
        x/=10;
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注