头像

dukakadujama




离线:1天前



//ne[a] 指的是a点的上一条边的编号 
//idx 为每一条边的编号 
//e[idx] 指的是a点所连接的点,即b点 
//h[a] 中存的就是a点的边的编号,即idx 

// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);


活动打卡代码 AcWing 211. 计算系数

#include<iostream>
//#include<cmath>
using namespace std;

int c[1005][1005];

int power(int x,int y){
    x%=10007;
    int ans=1;
    while(y--) ans=ans*x%10007;
    return ans;
}


int main(){
    int a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;

    /*for(int i=0;i<=k;i++)
    for(int j=0;j<=i;j++)
        if(!j) c[i][j]=1;
        else c[i][j]=(c[i-1][j-1]+c[i-1][j])%10007;*/
        for (int i = 0; i <= k; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) %10007;

    cout<<c[k][n]*power(a,n)%10007*power(b,m)%10007; 
    return 0;
}


活动打卡代码 AcWing 496. 机器翻译

#include<iostream>
#include<queue>
using namespace std;

bool s[1005];
int m,n;
int sum;
int main(){
    cin>>m>>n;
    int dc;
    queue<int>a;
    for(int i=1;i<=n;i++){
        cin>>dc;
        if(s[dc]==false)
        {
            if(a.size()==m){
                int k=a.front();
                s[k]=false;
                a.pop();
            }
            a.push(dc);
            s[dc]=true;
            sum++;
        }
    }
    cout<<sum;
    return 0;
}


活动打卡代码 AcWing 458. 比例简化

#include<iostream>
using namespace std;
double a,b;
int L;
double get(int A,int B){
    double aa=(double)A;
    double bb=(double)B;
    //if(A==99&&B==1) cout<<aa/bb-a/b<<endl;
    return aa/bb-a/b;
}
int main(){
    //64 49 0.0131589 0.00109952
    int a1=0,b1=0;
    double m=100000;
    cin>>a>>b>>L;
    for(int i=1;i<=L;i++)
    {
        int l=1,r=L+1;
        double max=100000;
        while(l!=r){
            int mid=(l+r)/2;
            if(get(mid,i)>=0&&get(mid,i)<max){
               r=mid;
               max=get(mid,i);
            }else {
               l=mid+1; 
            }
            //if(i==1)
            //cout<<l<<" "<<r<<' '<<(l+r)/2<<' '<<i<<' '<<get(mid,i)<<' '<<m<<" "<<endl;
        }
        //cout<<l<<' '<<i<<' '<<max<<' '<<m<<endl;
        if(max<m) a1=l,b1=i,m=max;
    }
    cout<<a1<<' '<<b1<<endl;
}


活动打卡代码 AcWing 1402. 星空之夜

#include<iostream>
using namespace std;
int f[35][35];
int a[35];
int b[35][35];
int ff=0;
int dp(int l,int r){
    if(f[l][r]) return f[l][r];
    for(int k=l;k<=r;k++){
        if(k==l) 
        {
                if(f[l][r]<(f[l][k]+dp(k+1,r)))
            {
                f[l][r]=f[l][k]+dp(k+1,r);
                b[l][r]=k;
            }
        }
        else if(k==r) {
            if(f[l][r]<(dp(l,k-1)+f[k][r])){
                f[l][r]=dp(l,k-1)+f[k][r];
                b[l][r]=k;
            }
        }
        else {
            if(f[l][r]<(f[k][k]+dp(l,k-1)*dp(k+1,r))){
                f[l][r]=f[k][k]+dp(l,k-1)*dp(k+1,r);    
                b[l][r]=k;
            }
        }
    }
    return f[l][r];
}
void pr(int l,int r){
    if(l>r) return ;
    cout<<b[l][r]<<' ';
    pr(l,b[l][r]-1);
    pr(b[l][r]+1,r);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        f[i][i]=a[i];
        b[i][i]=i;
    }
    dp(1,n);
    cout<<f[1][n]<<endl;
    pr(1,n);
    return 0;
}



活动打卡代码 AcWing 312. 乌龟棋

#include<iostream>
using namespace std;

int n,m,s[400],t[5];
int f[45][45][45][45];

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>s[i];
    int x;
    for(int i=1;i<=m;i++) {
        cin>>x;
        t[x]++;
    }

    for(int a=0;a<=t[1];a++)
    for(int b=0;b<=t[2];b++)
    for(int c=0;c<=t[3];c++)
    for(int d=0;d<=t[4];d++)
    {
        f[a][b][c][d]=s[a+2*b+3*c+4*d];
        if(a) f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+s[a+2*b+3*c+4*d]);
        if(b) f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+s[a+2*b+3*c+4*d]);
        if(c) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+s[a+2*b+3*c+4*d]);
        if(d) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+s[a+2*b+3*c+4*d]);
        //cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<f[a][b][c][d]<<endl;
    }

    cout<<f[t[1]][t[2]][t[3]][t[4]];
    return 0;
}


活动打卡代码 AcWing 425. 明明的随机数

#include<iostream>
using namespace std;
int a[1005];
int main(){
    int n,m,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>m;
        if(a[m]==0) sum++;
        a[m]=1;
    }
    cout<<sum<<endl;
    for(int i=1;i<=1000;i++) if(a[i]==1) cout<<i<<' ';
}


活动打卡代码 AcWing 1262. 鱼塘钓鱼

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,t;
long long ans=0;
int a[105],b[105],c[105];

int z[105];

long long getm(int k,int time){
    memset(z,0,sizeof(z));
    long long num=0;
    for(int i=1;i<=time;i++){
        int g=0,j=0;
        for(int i=1;i<=k;i++)
        {
            if(g<a[i]-b[i]*z[i]&&a[i]-b[i]*z[i]>=0){
                g=a[i]-b[i]*z[i],j=i;
            }
        }
        z[j]++;
        num+=g;
    }
    //cout<<num<<endl;
    return num;
}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n-1;i++){ cin>>c[i];c[i]+=c[i-1]; }

    cin>>t;

    for(int i=1;i<=n;i++){
        ans=max(ans,getm(i,t-c[i-1]));
    }
    cout<<ans;

    return 0;
}


活动打卡代码 AcWing 417. 不高兴的津津

#include<iostream>
using namespace std;

int main(){
    int sum=0;
    int max=0,ma=0;
    int x,y;
    for(int i=1;i<=7;i++) {
        cin>>x>>y;
        if(x+y>8) sum=x+y-8;
        else sum=0;
        if(sum>max){
            max=sum;ma=i;
        }
    }
    cout<<ma;
    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

#include<iostream>
#include<algorithm>
using namespace std;

struct aa{
    int x,y;
    int s;
}a[210000];
int f[41000];
int n,m;

bool cmp(aa j,aa k){
    return j.s>k.s;
}

int find(int x){
    while(f[x]!=x) x=f[x];
    return x;
}

int main(){

    cin>>n>>m;

    for(int i=1;i<=m;i++) {
        cin>>a[i].x>>a[i].y>>a[i].s;
    }

    for(int i=1;i<=2*n;i++) f[i]=i; 

    sort(a+1,a+1+m,cmp);

    for(int i=1;i<=m;i++){
        int xx=find(a[i].x);
        int yy=find(a[i].y);
        if(xx==yy) {
            cout<<a[i].s;
            return 0;
        }
        f[xx]=find(a[i].y+n);
        f[yy]=find(a[i].x+n);
    }
    cout<<0;
    return 0; 
}