头像

_如鲸向海

题解复习用




离线:7分钟前


最近来访(36)
用户头像
冰之韵
用户头像
刘小可
用户头像
赤赤
用户头像
零_37
用户头像
azhou
用户头像
ephemeral.
用户头像
小熊熊
用户头像
Gift
用户头像
zyj..
用户头像
itdef
用户头像
AcWing2AK
用户头像
魔法学徒
用户头像
听雨.无尘明月夜
用户头像
故事丶还未结束_5
用户头像
日川纲坂
用户头像
紫芋仙子
用户头像
21KINGDMG
用户头像
Yes
用户头像
bpommoqd
用户头像
haozi


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
int tt = -1;
int hh = 0;
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int topsort(){
    for(int i = 1;i<=n;i++)
       if(!d[i]) q[++tt] = i;

    while(hh<=tt){
        int t = q[hh++];
        for(int i = h[t];i!=-1;i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j]==0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}
int main(){
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;

        add(a,b);

        d[b] ++;
    }
    if(!topsort()) puts("-1");
    else{
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        puts("");
    }
}


活动打卡代码 AcWing 847. 图中点的层次

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;

}
int bfs( ){

    memset(d, -1, sizeof d);
    queue<int> que;
    que.push(1);
    d[1] = 0;
    while(que.size()){
         int t = que.front();
         que.pop();

         for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                que.push(j);
            }
        }
    }
    return d[n];
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}


活动打卡代码 AcWing 846. 树的重心

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
const int M = N*2;
int h[N];
int e[M],ne[M],idx;
int n;
int ans = N;
bool st[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u){
    st[u] = true;

    int sum = 0;
    int size = 0;
    for(int i = h[u];i!=-1;i = ne[i]){
        int j = e[i];
        if(st[j]) continue;

            int s = dfs(j);
            size = max(size,s);
            sum += s;

    }

    size = max(size,n-sum-1);

    ans = min(ans,size);

    return sum+1;
}
int main(){
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    printf("%d\n", ans);

    return 0;
}



C++ 代码(甲级01day)

#include <iostream>
#include <algorithm>
using namespace std;
const int N =  10010;
int a[N],dp[N];
int start[N];
int main(){
    start[0] = 1;//边界处理
    int number;
    int res = -2e9;
    cin>>number;
    int end = 0;//记录结束位置
    int flag = 0;

    for(int i = 1;i<=number;i++){
        cin>>a[i];
        if(a[i]>=0) flag = 1;
    }

    for(int i = 1;i<=number;i++)
    {
        if(a[i]>dp[i-1]+a[i]) 
        start[i] = i;
        else 
        start[i] = start[i-1];

        dp[i] = max(dp[i-1]+a[i],a[i]);
        if(res<dp[i]) end = i;
        res = max(res,dp[i]);
    }
    if(!flag){
        res = 0;
        cout<<res<<" "<<a[1]<<" "<<a[number]<<endl;
    }
    else
       cout<<res<<" "<<a[start[end]]<<" "<<a[end]<<endl;

    return 0;
}



C++ 代码(甲级01day)

#include <iostream>
#include <string>
using namespace std;
int num;
int main(){
    string early = "24:00:00";
    string end = "00:00:00";
    string name;
    string sign_in;
    string sign_out;
    string result_in;//开门人
    string result_out;//锁门人

    cin>>num;

    while(num--){
        cin>>name>>sign_in>>sign_out;
        if(sign_in<early){
            early =sign_in;
            result_in = name;
        }
        if(sign_out>end){
            end = sign_out;
            result_out = name;
        }
    }

    cout<<result_in<<" "<<result_out;

}



C++ 代码(甲级01day)

#include <iostream>
#include <string>
using namespace std;
string s[10] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int main(){
    string str;
    cin>>str;
    int num;
    for(int i = 0;i<str.length();i++)
    {
        num += str[i] - '0';
    }

    str = to_string(num);

    for(int i = 0;i<str.length();i++)
       cout<<s[str[i]-'0']<<" ";
}



C++ 代码(甲级01day)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int h[N],e[N*N],ne[N*N],idx;//无双向边不需要记录st状态数组
typedef pair<int,int> PII;//用于记录节点的id和depth
queue<PII> q;
int n,m;
void add(int a,int b){//构建树
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void bfs(){
     q.push({1,0});

     int ans = 0,cur = 0;//cur存上一个访问节点的depth
     while(q.size()){
         auto t = q.front();
         q.pop();

         int depth = t.second;
         int u = t.first;

         if(cur<depth){//说明此时到了树的下一层,需要把ans输出;
            cur = depth;
            cout<<ans<<" ";
            ans = 0;
         }

         //将子节点推入队列中
         bool success = false;
         for(int i = h[u];i!=-1;i = ne[i]){
             int j = e[i];
             q.push({j,depth+1});
             success = true;
         }
         if(!success) ans++;//此时邻接表中除了表头无其他节点说明访问到了叶节点
     }

     cout<<ans<<" ";//最后的一层节点

}
int main(){
    memset(h,-1,sizeof h);

    cin>>n>>m;

    for(int i = 0;i<m;i++){
        string father;
        int k = 0;
        int id = 0;
        cin>>father;
        if(father[0] == '0') id = father[1] - '0';
        else id = (father[0] - '0')*10 + father[1] - '0';

        cin>>k;

        for(int j = 0;j<k;j++){
            int u;
            string child;
            cin>>child;
            if(child[0] == '0') u = child[1] - '0';
            else u = (child[0] - '0')*10 + child[1] - '0';

            add(id,u);//构建树
        }
    }

    bfs();

    return 0;

}


活动打卡代码 AcWing 791. 高精度加法

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int> a,vector<int> b){
    vector<int> c;
    int t = 0;
    for(int i = 0;i<a.size()||i<b.size();i++){

        if(i<a.size()) t+= a[i];

        if(i<b.size()) t+= b[i];

        c.push_back(t%10);

        t = t/10;

    }
    if(t) c.push_back(1);
    return c;
}
int main(){
    string a,b;
    vector<int> vec1,vec2;

    cin>>a>>b;

    for(int i = a.length() - 1;i>=0;i--) vec1.push_back(a[i]-'0');
    for(int i = b.length() - 1;i>=0;i--) vec2.push_back(b[i]-'0');

    vector<int> c = add(vec1,vec2);

    for(int i = c.size() - 1;i>=0;i--) cout<<c[i];

    cout<<endl;

    return 0;

}



C++ 代码(甲级01day)

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;

    a = a+b;

    char str[12];

    int flag  = 0;

    if(a<0) flag = 1;

    string s = to_string(abs(a));

    reverse(s.begin(), s.end());

    int j = 0;
    for(int i = 0,count = 1;i<s.length();i++){
        str[j++] = s[i];
        if(count%3==0&&i!=s.length()-1){
            str[j++] = ',';
        }
        count++;
    }

    if(flag)  str[j++] = '-';  

    reverse(str,str+j);

    str[j] = '\0';

    cout<<str<<endl;

}



C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int mod = 1013;
bool H[mod];
bool Hash(int number){
     int k = number%mod;
     if(H[k] == false){
         H[k] = true;
         return false;
     }

     return true;
}
int main(){
    int n,num = 0;
    vector<int> vec;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>num;
        if(Hash(num)==false) vec.push_back(num);
    }

    sort(vec.begin(),vec.end());

    cout<<vec.size()<<endl;
    for(auto p: vec)
       cout<<p<<" ";
    cout<<endl;


    return 0;
}