计蒜客 Random Access Iterator

发表评论

原题链接：https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题，开心到爆炸，特此发题解一篇^v^

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re * re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
inline ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
    ll ch = (inv(TotNode)) % MOD;
    return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
    ll onceNonch = (1ll-onceCh+MOD) % MOD;
    ll nonch = quickpow(onceNonch, TotNode);
    ll fin = (1ll - nonch + MOD) % MOD;
    return fin;
}
int dfsMaxDep(int node) {
    int maxDep = 1;
    bool hasChild = false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        hasChild = true;
        maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
    }
    return maxDep;
}
ll dfsChance(int depth,int node){
    if (depth == MDep)return 1;
    ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        ll CurCH = dfsChance(depth + 1, edges[node][i]);
        if (CurCH) {
            ch += (CurCH * sCh) % MOD;
            ch %= MOD;
        }
    }
    return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    MDep = dfsMaxDep(1);
    memset(visited, false, sizeof(visited));
    ll ch = dfsChance(1, 1);
    cout << ch;
}

UVA1588 换抵挡装置 Kickdown

发表评论
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>
#include<map>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;
int solve(string a, string b) {
    a.append(b.size(), '0');
    for (int i = 0; i < a.size()-b.size()+1; i++) {
        bool flag = true;
        for (int j = 0; j < b.size(); j++) {
            if (a[i+j] + b[j] - '0' > '3') {
                flag = false;
                break;
            }
        }
        if (flag)
            return max(a.size()-b.size(), i + b.size());
    }
    return a.size();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a, b;
    while (cin >> a >> b)cout<<min(solve(a, b),solve(b,a))<<'\n';
}

UVA202 循环小数 Repeating Decimals

发表评论

模拟除法，当出现余数第二次相同时可以记为一个循环节。

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
#include<iostream>
#include<string>
#include<map>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;

void solve(int a, int b) {
    int OA = a;
    string strInt = to_string(a / b);
    a %= b;
    a *= 10;
    string strDec = "";
    map<int, int> dict;
    while (dict.count(a) == 0) {
        dict[a] = strDec.size();
        strDec += to_string(a / b);
        a %= b;
        a *= 10;
    }
    string strDec1 = strDec.substr(0, dict[a]);
    string strDec2 = strDec.substr(dict[a]);
    string strDec3 = "";
    if (strDec2.size() > 50) {
        strDec3 = '(' + strDec2.substr(0, 50) + "...)";
    }
    else {
        strDec3 = '(' + strDec2 + ")";
    }
    cout << OA << "/" << b << " = " << strInt << "." << strDec1 << strDec3 << '\n';
    cout << "   " << strDec2.size() << " = number of digits in repeating cycle" << '\n';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    while (cin >> a >> b)solve(a, b);
}

UVA1368 DNA序列 DNA Consensus String

发表评论

解题思路是，统计所有字符串对应位置上出现次数最多的字母，并将其拼接起来作为Hamming距离和最小的DNA序列，也可以算作贪心。

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
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;
int t, m, n;
int seq[5];
string strArr[1005];
inline void seqSet(char c) {
    switch (c) {
    case 'A':seq[1]++; break;
    case 'C':seq[2]++; break;
    case 'G':seq[3]++; break;
    case 'T':seq[4]++; break;
    }
}
char seqGet[6] = " ACGT";
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> m >> n;
        for (int i = 1; i <= m; i++)cin >> strArr[i];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            memset(seq, 0, sizeof(seq));
            for (int k = 1; k <= m; k++)seqSet(strArr[k][i]);
            int Pmax = 1;
            for (int p = 2; p <= 4; p++)
                if (seq[p] > seq[Pmax])
                    Pmax = p;
            cnt += m - seq[Pmax];
            cout << seqGet[Pmax];
        }
        cout << '\n';
        cout << cnt << '\n';
    }
}

蓝桥杯 历届试题 小计算器

发表评论

问题描述
　　模拟程序型计算器，依次输入指令，可能包含的指令有

　　1. 数字：’NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
　　2. 运算指令：’ADD’,’SUB’,’MUL’,’DIV’,’MOD’，分别表示加减乘，除法取商，除法取余
　　3. 进制转换指令：’CHANGE K’，将当前进制转换为K进制(2≤K≤36)
　　4. 输出指令：’EQUAL’，以当前进制输出结果
　　5. 重置指令：’CLEAR’，清除当前数字

　　指令按照以下规则给出：
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
　　进制转换指令可能出现在任何地方

　　运算过程中中间变量均为非负整数，且小于2^63。
　　以大写的’A’~’Z’表示10~35
输入格式
　　第1行：1个n，表示指令数量
　　第2..n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出格式
　　依次给出每一次’EQUAL’得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

可以说样例给的挺恶心。会让人想不到，这玩意要考虑还是不考虑优先级！？最后在测试下是不需要考虑优先级的。直接挨着个的算即可。还有一个点是我进制转换写错了（竟然’A’->11，生无可恋脸）一直在调这里。。。。其他没啥了。

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
#include<iostream>
#include<deque>
#include<algorithm>
#include<cassert>
#include<cstdlib>
#include<string>
using namespace std;
int n;
int radix = 10;
string radixS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
deque<long long> sll;
deque<string> sop;
long long value;
inline long long getCorDecimal(char c) {
    if ('0' <= c && c <= '9')return c - '0';
    if ('A' <= c && c <= 'Z')return c - 'A' + 10;
    assert(false);
    return -1;
}
long long Radix2Decimal(string s) {
    reverse(s.begin(), s.end());
    long long cntBase = 1, result = 0;
    for (int i = 0; i<s.size(); i++) {
        result += getCorDecimal(s[i])*cntBase;
        cntBase *= radix;
    }
    return result;
}
string Decimal2Radix(long long v) {
    string s = "";
    while (v) {
        s.push_back(radixS[v%radix]);
        v /= radix;
    }
    if (s == "")s = "0";
    reverse(s.begin(), s.end());
    return s;
}
bool calculate4Back() {
    if (sop.empty())return false;
    string & comm = sop.back();
    if (comm == "ADD")value += sll.back();
    else if (comm == "SUB")value = sll.back() - value;
    else if (comm == "MUL")value *= sll.back();
    else if (comm == "DIV")value = sll.back() / value;
    else if (comm == "MOD")value = sll.back() % value;
    else assert(false);
    sop.pop_back();
    sll.pop_back();
    sll.push_back(value);
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string comm, radixV;
        cin >> comm;
        if (comm == "NUM") {
            cin >> radixV;
            value = Radix2Decimal(radixV);
            if (!calculate4Back())sll.push_back(value);
            //cout<<Decimal2Radix(sll.front())<<endl;
        }
        else if (comm == "ADD" || comm == "SUB" || comm == "MUL" || comm == "DIV" || comm == "MOD") {
            sop.push_back(comm);
        }
        else if (comm == "CHANGE") {
            cin >> radix;
        }
        else if (comm == "EQUAL") {
            cout << Decimal2Radix(sll.front()) << endl;
        }
        else if (comm == "CLEAR") {
            sll.clear();
            sop.clear();
        }
    }
}

团体程序设计天梯赛-练习集 L3-001 凑零钱

发表评论

DFS T一个点29分代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int recorder[10005];
bool dfs(int no,int curPos,int remainValue){
    recorder[no]=money[curPos];
    if(remainValue==0)return true;
    int upp=upper_bound(money+1,money+n+1,remainValue)-money;
    for(int i=curPos+1;i<upp;i++){
        if(dfs(no+1,i,remainValue-money[i]))return true;
        else i=upper_bound(money+1,money+n+1,money[i])-money-1;
    }
    recorder[no]=0; //忘加了这个，回溯差点没做好
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",money+i);
    sort(money+1,money+n+1);
    bool flag=dfs(0,0,m);
    if(!flag)printf("No Solution");
    else{
        int i=1;
        while(recorder[i]!=0){
            if(i!=1)printf(" ");
            printf("%d",recorder[i++]);
        }
    }
}

团体程序设计天梯赛-练习集 L3-015 球队“食物链”

发表评论

如下三个坑点：
1、所给的图非对称，因为每个队打了两场比赛，每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小，而且该食物链是从1到n的排列，因此只要有环，头一个一定从1开始是字典序最小的状况，只需要从1开始DFS即可。
3、剪枝：不剪枝T一个点。在DFS中把经过的点标记，若未标记的点集中不存在与1连通的点，则不可能构成环状结构，直接return false。

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<iostream>
#include<stack>
#include<queue>
using namespace std;
int n;
char arr[25][25];
deque<int> st;
bool visited[25];
bool dfs(int curNode,int visitedNodeCnt){
    if(visited[curNode]){
        if(visitedNodeCnt==n+1&&curNode==1)return true;
        else return false;
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true;
    }
    if(!flag)return false;
    visited[curNode]=true;
    for(int i=1;i<=n;i++){
        if(i==curNode)continue;
        if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){
            if(dfs(i,visitedNodeCnt+1)){
                st.push_back(i);
                return true;
            }
        }
    }
    visited[curNode]=false;
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",arr[i]+1);
    bool flag=dfs(1,1);
    if(!flag)printf("No Solution\n");
    else{
        printf("%d",st.front());
        st.pop_front();
        while(!st.empty()){
            printf(" %d",st.back());
            st.pop_back();
        }
    }
}

大学第一学期总结

发表评论

配乐：分享Owl City/Sarah Russell的单曲《Thunderstruck》: http://music.163.com/song/33035211/?userid=82868066 (来自@网易云音乐)

这一个学期学的东西可真不少。。。经历了很多很多事情。

首先是暑假看到录取结果的时候就傻眼了，被录到土木了。直接要求复读，复读了几天感觉压力太大了，又放弃复读进大学，想着转专业进计算机。当时心里是一万个没底。整个进大学前期就是在天天痛苦怕转不了系中度过。认真学习的压力很大。

当然一进了学校就开始准备筹备参加ACM社团的事情，提前在网上就找好了本校的队友gzy和yyy一块参加比赛。本人眼光还不错^v^，在第一次ACM社团迎新赛中我队成员都名列前茅。后续ACM社团各项比赛我队都积极参加，取得了IEEExtreme 很好成绩。后续参加的团队赛作为组员什么都没干，18 ACM北京站，骗了个铜牌，后续的个人比赛蓝桥杯预选赛也取得了不错的成绩。在这个过程中结识了很多好朋友，好学长，他们给我提供了很多的帮助。正因为这些我也能在一定程度上让自己从转专业的压力中解脱出来一下。

情窦初开，曾经认定自己想追的人，但惨遭失败，从这个过程中学到很多。相信自己将来一定能够碰到与自己非常合适的伴侣！

非常认真学习，死死抓住成绩不放手，毕竟没成绩就转不了系。经过一番努力，本学期加权达到91分，超出了转计算机80分的要求。下学期压力相对轻松一点，但仍需继续努力。

寒假目标（更新：与计算机相关：1，学习面向对象，补上本学校下学期计类课程之一（看完讲义了没做几道题。2，学习神经网络课程（看了不少。3，看看coursera上的从与非门到俄罗斯方块1和2，对计算机原理有初步了解（Orz没看。4，更深层次探索计算机原理（编译原理，操作系统）和信息安全（CTF）（一点没动。5，继续学习钻研CTF（Orz。6，ACM（几乎没看，还得打比赛呢

和生活相关：1，多看看电影，多休闲^v^（电影倒是看了不少。2，多出去玩出去逛锻炼身体（没咋玩。3，学车。√

PTA 团体程序设计天梯赛-练习集 L2-012 关于堆的判断

发表评论

这道题里坑点很大：反而不利于深入学习过数据结构的同学做题。。
先贴代码：

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>
#include<string>
#include<functional>
#include<algorithm>
#include<stack>
#include<list>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
//Root is 1
//小顶堆
int n, m;
int heap[1005];
int Hsize = 0;
inline int lson(int x) {
    return x * 2;
}
inline int rson(int x) {
    return x * 2 + 1;
}
inline int father(int x) {
    return x / 2;
}
void PercolateUp(int node) {
    if (heap[node] < heap[father(node)]) {
        swap(heap[node], heap[father(node)]);
        PercolateUp(father(node));
    }
}
void insert(int x) {
    heap[++Hsize] = x;
    PercolateUp(Hsize);
}
int _findNode(int v) {
    for (int i = 1; i <= n; i++) {
        if (v == heap[i])return i;
    }
    return -1;
}
bool isRoot(int v) {
    return heap[1] == v;
}
bool isSiblings(int v1, int v2) {
    int node = _findNode(v1);
    if (node % 2 == 1)return heap[node - 1] == v2;
    else return heap[node + 1] == v2;
}
bool isParent(int C,int F){
    int node = _findNode(C);
    return heap[father(node)] == F;
}
bool isChild(int C, int F) {
    int node = _findNode(F);
    return heap[lson(node)] == C || heap[rson(node)] == C;
}
int Itype; //0 root,1 sibling,2 parent,3 child
int Ix, Iy;
char str[100];
void getInput() {
    scanf("%d", &Ix);
    scanf("%s", str);
    if (strcmp(str, "and") == 0) {
        Itype = 1;
        scanf("%d", &Iy);
        scanf("%s", str);
        scanf("%s", str);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "a") == 0) {
        Itype = 3;
        scanf("%s", str);
        scanf("%s", str);
        scanf("%d", &Iy);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "root") == 0) {
        Itype = 0;
        return;
    }
    Itype = 2;
    scanf("%s", str);
    scanf("%d", &Iy);
    return;
}
int main() {
    heap[0] = -100000;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        insert(x);
    }
    for (int i = 1; i <= m; i++) {
        getInput();
        bool flag;
        switch (Itype) {
        case 0:flag = isRoot(Ix); break;
        case 1:flag = isSiblings(Ix, Iy); break;
        case 2:flag = isParent(Iy, Ix); break;
        case 3:flag = isChild(Ix, Iy); break;
        }
        cout << (flag ? "T" : "F")<< endl;
    }
}

对我来说的坑点：一个是数据范围是有负数的！！！还有一个，儿子、父亲节点不是广义儿子、父亲节点，只是直属的，有直接相连边的，间接连接的不算，还有一个是不能使用一次全部读入到数组里从n/2下标到n一起上滤的做法，必须插入一个，上滤一次，这种算法很辣鸡。