头像

13230668653


访客:1726

离线:5小时前



13230668653
2个月前

https://www.acwing.com/solution/acwing/content/1393/
这个讲解非常好

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 240. 食物链

13230668653
2个月前

带权并查集,十分巧妙的用当前点,到达根节点的距离,代表食物链中的关系。并且d数组是到达向父节点的距离,经过路径压缩之后,d就逻辑上称为了,达到根节点的距离。
而且还有一个非常神奇的点,就是合并集合,本来以为合并集合因为权值的问题,会变得复杂,没有想到通过食物链中的关系,直接计算出了合并后,一个跟节点到另一个跟节点之间的距离。

#include<cstdio>
#include<iostream>
using namespace std;
const int N = 50010;
int p[N],d[N];
int find(int x){
    if(x!=p[x]){
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main(){
    int n,k,res = 0;
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++) p[i] = i;
    while(k--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int px = find(b),py = find(c);
        if(b>n||c>n)  res++;
        else if(a==1){
            if(px==py&&(d[b]-d[c])%3!=0) res++;
            else if(px!=py){
                p[px] = py;
                d[px] = d[c] - d[b];
            }
        }else{
            if(px==py&&(d[b]-d[c]-1)%3!=0) res++;
            else if(px!=py){
                p[px] = py;
                d[px] = d[c]+1-d[b]; 
            }
        }
    }
    cout<<res<<endl;
}



13230668653
2个月前

YXC的代码是不是麻烦了,二分查找,小于等于x最大的数。这样就不用把查询的坐标也离散化了。加一个哨兵防止,l小于离散化中最小的数导致二分查找不到。

C++ 代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
pair<int,int> a[N],b[N];

int request(pair<int,int> *a,int l,int r,int x){
    while(l<r){
        int mid = (l+r+1)/2;
        if(a[mid].first>x)r = mid - 1;
        else l = mid;
    }
    return a[l].second;
}

int main(){
    int n,m,k;
    cin>>n>>m;
    for(int i = 1;i <= n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+1+n);
    for(int i = 1,j = 0;i<=n;i++){
        if(i==1||a[i].first!=a[i-1].first)
            b[++j] = a[i];
        else b[j].second+=a[i].second;
        k = j;
    }
    b[0].first = -1e9-1;
    for(int i = 1;i <= k;i++) b[i].second+=b[i-1].second;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<request(b,0,k,r) - request(b,0,k,l-1)<<endl;
    }

}


活动打卡代码 AcWing 205. 斐波那契

13230668653
3个月前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

void mul(int f[], int d[][2]) {
    int cpy[2] = { 0 };
    for (int i = 0; i < 2; i++) {
        for (int k = 0; k < 2; k++) {
            cpy[i] = (f[k] * d[k][i] + cpy[i]) % 10000;
        }
    }
    for(int i = 0;i < 2;i++) f[i] = cpy[i];
}

void mulself(int d[][2]) {
    int cpy[2][2] = { 0 };
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                cpy[i][j] = (cpy[i][j] + d[i][k] * d[k][j]) % 10000;
            }
        }
    }
    for(int i = 0;i < 4;i++) d[i/2][i%2] = cpy[i/2][i%2];
}

int main() {
    int k;
    while (scanf("%d", &k)&&k!=-1) {
        int s[2] = { 0,1 };
        int d[2][2] = { {0,1} ,{1,1} };
        if (k == -1) return 0;
        for (; k; k >>= 1) {
            if (k & 1) mul(s, d);
            mulself(d);
            /*for(int i = 0;i < 4;i++) cout<<d[i/2][i%2]<<" ";
            cout<<endl;
            for(int i = 0;i < 2;i++) cout<<s[i]<<" ";
            cout<<endl;*/
        }
        cout << s[0] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 274. 移动服务

13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int L = 210,N = 1010;
int g[L][L],q[N],f[N][L][L];
int l,n;
int main(){
    cin>>l>>n;
    for(int i = 1;i <= l;i++)
        for(int j = 1;j <= l;j++)
            cin>>g[i][j];
    for(int i = 1;i <= n;i++) cin>>q[i];
    q[0] = 3;
    memset(f,0x3f,sizeof f);
    f[0][1][2] = 0;
    for(int i = 0;i < n;i++){
        for(int x = 1;x <= l;x++){
            for(int y = 1;y <= l;y++){
                int z = q[i],v = f[i][x][y],u = q[i+1];
                if(x==y||x==z||y==z) continue;
                f[i+1][x][y] = min(f[i+1][x][y],v+g[z][u]);
                f[i+1][z][y] = min(f[i+1][z][y],v+g[x][u]);
                f[i+1][x][z] = min(f[i+1][x][z],v+g[y][u]);
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for(int x = 1;x <= l;x++)
        for(int y = 1;y <= l;y++){
            int z = q[n];
            if(x==y||x==z||y==z) continue;
            ans = min(f[n][x][y],ans);
        }

    cout<<ans<<endl;
}


活动打卡代码 AcWing 273. 分级

13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2010;
int a[N],b[N],n,k = 1,f[N][N];//k代表目前有k-1个内容

int calc(){
    sort(b+1,b+1+n);
    for(int i = 1;i <= n;i++){
        int maxv = 0x3fffffff;
        for(int j = 1;j <= n;j++){
            maxv = min(maxv,f[i-1][j]);
            f[i][j] = maxv+abs(b[j]-a[i]);
            //cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }
    }
    int ans = 0x3fffffff;
    for(int i = 1;i <= n;i++){
        ans = min(ans,f[n][i]);
    }
    return ans;
}


int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        b[i] = a[i];
    }
    int c = calc();
    reverse(a+1,a+1+n);
    int d = calc();
    cout<<min(c,d)<<endl;
}


活动打卡代码 AcWing 184. 虫食算

13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char str[3][30];
int path[30],q[30],n;//存储每个位置填的数,存储依次枚举的位置
bool st[30];

bool check(){
    for(int i = n-1,t = 0;i>=0;i--){
        int a = path[str[0][i] - 'A'],b = path[str[1][i] - 'A'],c = path[str[2][i] - 'A'];
        if(a!=-1&&b!=-1&&c!=-1){
            if(t==-1){
                if((a+b)%n!=c&&(a+b+1)%n!=c) return false;
                if(i==0&&a+b>=n) return false;
            }else{
                if((a+b+t)%n!=c) return false;
                if(i==0&&a+b>=n) return false;
                t = (a+b+t)/n;
            }
        }
        else t = -1;
    }
    return true;
}


bool dfs(int u){
    if(u==n) return true;
    for(int i = n-1;i >= 0;i--){
        if(st[i]==false){
            path[q[u]] = i;
            st[i] = true;
            if(check()&&dfs(u+1)) return true;
            st[i] = false;
            path[q[u]] = -1;
        }
    }
    return false;
}

int main(){
    cin>>n;
    for(int i = 0;i < 3;i++) cin>>str[i];

    for(int i = n-1,k = 0;i >= 0;i--){
        for(int j = 0;j < 3;j++){
            int a = str[j][i] - 'A';
            if(st[a]==false){
                q[k++] = a;
                st[a] = true;
            }
        }
    }
    memset(st,false,sizeof st);
    memset(path,-1,sizeof path);
    dfs(0);
    for(int i = 0;i < n;i++) cout<<path[i]<<" ";
    cout<<endl;
}



13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3010;
long long  a[N],b[N];
int f[N][N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
    for(int i = 1;i <= n;i++) scanf("%lld",&b[i]);
    a[0] = b[0] = -1e15;
    for(int i = 1;i <= n;i++){
        int v = 0;
        for(int j = 1;j <= n;j++){
            if(a[i]!=b[j]) f[i][j] = f[i-1][j];
            else f[i][j] = v + 1;
            if(b[j]<a[i]) v = max(v,f[i-1][j]);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) ans = max(ans,f[n][i]);
    cout<<ans<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[32][16][12][10][8];
int N[5];
int main(){
    int k;
    while(cin>>k&&k!=0){
        memset(N,0,sizeof(N));
        for(int i = 0;i < k;i++) cin>>N[i];
        memset(f,0,sizeof(f));
        f[0][0][0][0][0] = 1;
        for(int a5 = 0;a5<=N[4];a5++){
            for(int a4 = 0;a4<=N[3];a4++){
                for(int a3 = 0;a3<=N[2];a3++){
                    for(int a2 = 0;a2<=N[1];a2++){
                        for(int a1 = 0;a1<=N[0];a1++){
                            if(a1<N[0]) f[a1+1][a2][a3][a4][a5] += f[a1][a2][a3][a4][a5];
                            if(a2<N[1]&&a2<a1) f[a1][a2+1][a3][a4][a5] += f[a1][a2][a3][a4][a5];
                            if(a3<N[2]&&a3<a2) f[a1][a2][a3+1][a4][a5] += f[a1][a2][a3][a4][a5];
                            if(a4<N[3]&&a4<a3) f[a1][a2][a3][a4+1][a5] += f[a1][a2][a3][a4][a5];
                            if(a5<N[4]&&a5<a4) f[a1][a2][a3][a4][a5+1] += f[a1][a2][a3][a4][a5];
                        }
                    }
                }
            }
        }
    cout<<f[N[0]][N[1]][N[2]][N[3]][N[4]]<<endl;;
    }

}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 183. 靶形数独

13230668653
3个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1<<9;
int logone[N],ones[N],num[9][9],row[9],col[9],cell[3][3],ans = -1;
int sour[10][10];
bool st[10][10];
inline int lowbit(int x){
    return x&(-x);
}
inline int pos(int x,int y){
    return (10 - max(abs(x-4),abs(y-4)));
}

inline int get(int x,int y){
    return row[x]&col[y]&cell[x/3][y/3];
}
void dfs(int cnt,int grate){
    if(cnt==0){
        ans = max(ans,grate);
        return ;
    }
    int minnum = 10,x = 0 ,y = 0,f = 0;
    for(int i = 0;i < 9;i++){
        for(int j = 0;j < 9;j++){
            if(st[i][j]==false){
                int u = ones[row[i]&col[j]&cell[i/3][j/3]];
                //f+=logone[u]*(10 - max(abs(x-4),abs(y-4)));
                if(u<minnum) minnum = u,x = i,y = j;
            }
        }
    }
    //if(f+grate<=grate) return ;
    for(int j = get(x,y);j;j-=lowbit(j)){
        int k = lowbit(j);
        row[x]-=k;
        col[y]-=k;
        cell[x/3][y/3]-=k;
        st[x][y] = true;
        dfs(cnt-1,grate + pos(x,y)*(logone[k]+1));
        st[x][y] = false;
        row[x]+=k;
        col[y]+=k;
        cell[x/3][y/3]+=k;
    }
}

int main(){
    int cnt = 0,grate = 0;
    for(int i = 0;i < 9;i++){
        for(int j = 1<<i;j< 1<<(i+1);j++)
        logone[j] = i;//通过这个数组得到每个数的最高位,最优化剪枝
    }
    for(int i = 0;i < (1<<9);i++)
        for(int j = i;j;j-=lowbit(j))
            ones[i]++;
    for(int i = 0;i < 9;i++) row[i] = col[i] = cell[i/3][i%3] = (1<<9)-1;
    for(int i = 0;i < 9;i++){
        for(int j = 0;j < 9;j++){
            cin>>num[i][j];
            if(num[i][j]!=0){
                st[i][j]=true;
                grate+=num[i][j]*pos(i,j);
                row[i]-=1<<(num[i][j]-1);
                col[j]-=1<<(num[i][j]-1);
                cell[i/3][j/3] -= 1<<(num[i][j]-1);
            }
            else cnt++;
        }
    }
    dfs(cnt,grate);
    cout<<ans<<endl;


}