头像

wyc1996

哈尔滨工业大学




离线:3天前


最近来访(15)
用户头像
tom233
用户头像
心里没有一点AC数
用户头像
张大壮
用户头像
番茄辣椒
用户头像
SeaSky
用户头像
gaga
用户头像
琅琊
用户头像
喜び
用户头像
yantian
用户头像
ycy
用户头像
zyy1313
用户头像
Diamondz
用户头像
FLY_4
用户头像
风在吹
用户头像
甜菜小笼包

活动打卡代码 AcWing 72. 平衡二叉树

wyc1996
3天前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool ans=true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root){
        if(!root)return 0;
        int left=dfs(root->left);
        int right=dfs(root->right);
        if(abs(left-right)>1)ans=false;
        return max(left,right)+1;
    }
};


活动打卡代码 AcWing 914. 樱桃网

wyc1996
5天前
#include <iostream>
#include <cstring>

using namespace std;
const int N=100010;
int p[N]; 

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin>>T;
    for(int k=1;k<=T;k++){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)p[i]=i;

        int cnt=0;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            if(p[find(a)]!=find(b)){
                p[find(a)]=find(b);
                cnt++;
            }
        }
        printf("Case #%d: %d\n",k,cnt+(n-1-cnt)*2);
    }
    return 0;
}


活动打卡代码 AcWing 696. 哈默队长

wyc1996
5天前
#include <iostream>
#include <cmath>

#define PI acos(-1)

using namespace std;

int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        int v,d;
        cin>>v>>d;
        double g=9.8;
        double l=0,r=45;
        while(r-l>1e-8){
            double mid=(l+r)/2;
            if(v*v*sin(2*mid/180*PI) / g >= d)r = mid;
            else l = mid;
        }
        printf("Case #%d: %.8lf\n",i,r);
    }
    return 0;
}


活动打卡代码 AcWing 698. 读电话号码

wyc1996
5天前
#include <iostream>
#include <cstring>

using namespace std;

string numbers[10]={
    "zero","one","two","three","four","five",
    "six","seven","eight","nine"};

string ops[10]={
    " ","double","triple","quadruple",
    "quintuple","sextuple","septuple",
    "octuple","nonuple","decuple"
};

string get_number(int k,int n)
{
    return  ops[k-1]+' '+numbers[n]+' ';    
}

int main()
{
    int T;
    cin>>T;
    for(int k=1;k<=T;k++){
        string str,op;
        cin>>str>>op;
        string res;

        int cnt=0;

        for(int i=0;i<op.size();i++){
            if(op[i]=='-')continue;
            int t=0;
            while(op[i]>='0' && op[i]<='9'){
                t=t*10+op[i]-'0';
                i++;
            }
            i--;

            for(int j=cnt;j<cnt+t;){
                int s=j,c=0;
                while(s<cnt+t && str[s]==str[j])s++,c++;
                if(c==1)res+=numbers[str[j]-'0']+' ';
                else if(c<=10)res+=get_number(c,str[j]-'0');
                else {
                    for(int x=0;x<c;x++)res+=numbers[str[j]-'0']+' ';
                }
                j=s;
            }
            cnt+=t;
        }
       printf("Case #%d:  ",k);
       cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 697. 蒙斯特

wyc1996
5天前
#include <iostream>
#include <cstring>

using namespace std;
const int N=110;
string str[N];

int main()
{
    int T;
    cin>>T;
    for(int k=1;k<=T;k++){
        int n;
        cin>>n; 

        // getline 应当注意空字符的情况

        getchar();
        for(int i=0;i<n;i++)getline(cin,str[i]);

        // 插入排序的过程
        int res=0;
        for(int i=1;i<n;i++){
            if(str[i]<str[i-1]){
                for(int j=i;j;j--)
                    if(str[j]<str[j-1])
                        swap(str[j],str[j-1]);
                res++;
            }
        }
        printf("Case #%d: %d\n",k,res);
    }
    return 0;
}


活动打卡代码 AcWing 703. 数独检查

wyc1996
5天前
#include <iostream>
#include <cstring>

using namespace std;
const int N=10;
int g[N*N][N*N];
bool st[N*N];

int main()
{
    int T;
    cin>>T;
    for(int k=1;k<=T;k++){
        int n;
        cin>>n;
        for(int i=0;i<n*n;i++)
            for(int j=0;j<n*n;j++)
                scanf("%d",&g[i][j]);

        bool success=true;
        for(int i=0;i<n*n;i++){
            memset(st,0,sizeof st);
            for(int j=0;j<n*n;j++){
                int t=g[i][j];
                if(t>n*n || t<=0)success=false;
                else if(st[t])success=false;
                else st[t]=true;
            }
        }

        for(int i=0;i<n*n;i++){
            memset(st,0,sizeof st);
            for(int j=0;j<n*n;j++){
                int t=g[j][i];
                if(t>n*n || t<=0)success=false;
                else if(st[t])success=false;
                else st[t]=true;
            }
        }

        for(int i=0;i+n<n*n;i+=n){
            for(int j=0;j+n<n*n;j+=n){
                memset(st,0,sizeof st);
                for(int a=i;a<i+n;a++){
                    for(int b=j;b<j+n;b++){
                        int t=g[a][b];
                        if(t>n*n || t<=0)success=false;
                        else if(st[t])success=false;
                        else st[t]=true;
                    }
                }
            }
        }
        if(success)printf("Case #%d: Yes\n",k);
        else printf("Case #%d: No\n",k);
    }
    return 0;
}


活动打卡代码 AcWing 78. 左旋转字符串

wyc1996
5天前
class Solution {
public:
    string leftRotateString(string str, int n) {
        return str.substr(n)+str.substr(0,n);
    }
};


活动打卡代码 AcWing 3772. 更新线路

wyc1996
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=200010,M=N;
int h[N],e[M],ne[M],idx;
int n,m;
int dist[N],cnt[N];
int path[N];
int q[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int start)
{
    int hh=0,tt=0;
    memset(dist,0x3f,sizeof dist);
    dist[start]=0;
    q[0]=start;

    while(hh<=tt){
        auto t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+1){
                dist[j]=dist[t]+1;
                cnt[j]=1;
                q[++tt]=j;
            }
            else if(dist[j]==dist[t]+1){
                cnt[j]++;
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

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

    int k;
    cin>>k;
    for(int i=1;i<=k;i++)scanf("%d",&path[i]);

    bfs(path[k]);

    int minc=0,maxc=0;

    for(int i=1;i<k;i++){
        int a=path[i],b=path[i+1];
        if(dist[a]<dist[b]+1)minc++,maxc++;
        else if(cnt[a]>1)maxc++;
    }

    printf("%d %d",minc,maxc);
    return 0;
}


活动打卡代码 AcWing 3771. 选取石子

wyc1996
8天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;

int main()
{
    int n;
    cin>>n;

    unordered_map<int,LL>h;

    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        h[t-i]+=t;
    }

    LL res=0;
    for(auto [s,c]:h){
        res=max(res,c);
    }
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 3770. 最小消耗

wyc1996
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--){
        int n,a,b,c;
        cin>>n>>a>>b>>c;

        string str;
        cin>>str;

        char s=a<=b?'0':'1';

        int flag=abs(a-b)<=c?0:1;

        int res=0;

        for(int i=0;i<str.size();i++){
            if(flag){
                if(str[i]==s)res+=min(a,b);
                else res+=min(a,b)+c;
            }
            else{
                if(str[i]=='0')res+=a;
                else res+=b;
            }
        }

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

    }
    return 0;
}