2022/7/27

282B - Painting Eggs

ai+gi会等于1000，并且要求最后A和G的价值之差不超过500，其实我们可以发现，假设现在该要分配第i个鸡蛋，A和G价值只差是x，我们发现无论x是多少，ai和gi是多少，我们总可以让分配完后的A和G之差还是小于等于500，只需要这个式子就可以

if(abs(sum+a[i])<abs(sum-b[i])) sum+=a[i],s+="A";

        else sum-=b[i],s+="G";

也就是根据差来贪心

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,a[1000006],b[1000006];
string s="";
int main(){
    ll sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        if(abs(sum+a[i])<abs(sum-b[i])) sum+=a[i],s+="A";
        else sum-=b[i],s+="G";
        //cout<<sum<<" "<<i<<endl;
    }
    cout<<s<<endl;
    system("pause");
    return 0;
} 

1342C - Yet Another Counting Problem

这两个题花了快一下午了，，，

假设b永远是较大的，打表一下就可以看出，a和b的公倍数一直到公倍数+b-1，这些数是都不符合条件的，所以目的就是找出这些不符合条件的就可以了，假设p为最小公倍数，x=l/p,y=r/p,那么x+1和y-1都是完整的在l，r内的，所以先把这些减去，然后再去考虑x，y这俩边缘情况就可以了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll t,a,b,q;
ll lcm(ll x,ll y){
    return x*y/__gcd(x,y);
}
int main(){
    cin>>t;
    ll cnt=0;
    //cout<<lcm(2,6)<<" "<<lcm(2,7)<<" "<<lcm(4,22)<<endl;
    while(t--){
        cin>>a>>b>>q;
        if(a>b) swap(a,b);
        while(q--){
            cnt++;
            ll l,r;
            scanf("%lld%lld",&l,&r);
            
            l=max(l,b);
            //if(cnt==48405) cout<<l<<","<<r<<","<<a<<","<<b<<endl;
            if(b%a==0||l>r){printf("0\n");continue;}
            ll ans=r-l+1;
            ll x,y,z,p=lcm(a,b);
            x=l/p;y=r/p;
            ans-=max(y-x-1,0LL)*b;
            ans-=max(min(x*p+b-1,r)-l+1,0LL);
            //cout<<ans<<" "<<x<<" "<<y<<endl;
            if(y>x) ans-=max(min(r,y*p+b-1)-y*p+1,0LL);
            printf("%lld\n",ans);
        }
    }
    system("pause");
    return 0;
} 

J-Serval and Essay_"蔚来杯"2022牛客暑期多校训练营1 启发式合并

如果x能够推y，那么x一定比y要推的多，那从y开始也就没什么意义了，可以直接将y合到x上，当所有从x开始的边能够推出z的话，z也可以合到x上，按照这个思路遍历每一个没有入度的点，看看谁的siz最大就可以，用启发式合并就不会超时

题解 | J. Serval and Essay_牛客博客 (nowcoder.net) 

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll t,n,s[200005],siz[200005];
set<ll>to[200005],from[200005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
void uni(ll x,ll y){
    x=findd(x); y=findd(y);
    if(x==y) return;
    if(to[x].size()<to[y].size()) swap(x,y);
    s[y]=x;
    siz[x]+=siz[y];
    vector<pair<ll,ll> >v;
    for(auto i:to[y]){
        to[x].insert(i);
        from[i].erase(y);
        from[i].insert(x);
        if(from[i].size()==1) v.push_back({i,x});
    }
    for(auto [x,y]:v) uni(y,x);
}
int main(){
    cin>>t;
    ll ca=0;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) s[i]=i,siz[i]=1;
        for(int i=1;i<=n;i++){
            ll k;cin>>k;
            for(int j=1;j<=k;j++){
                ll a;cin>>a;
                to[a].insert(i);
                from[i].insert(a);
            }
        }
        for(int i=1;i<=n;i++) 
            if(from[i].size()==1) uni(*from[i].begin(),i);
        ll ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,siz[i]);
        printf("Case #%lld: %lld\n",++ca,ans);
        for(int i=1;i<=n;i++) to[i].clear(),from[i].clear();
        
    }
    system("pause");
    return 0;
} 

L-Link with Level Editor I_"蔚来杯" dp

f[i]表示上一个世界i可以最大从第几个世界的1开始，g[i]是表示这个世界的，不能之用一个数组，比如下面这个代码

【题解】"蔚来杯"2022牛客暑期多校训练营2_ICPC/CCPC/NOIP/NOI刷题训练题单_牛客竞赛OJ (nowcoder.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=10007;
ll n,m,dp[2005];
int main(){
    cin>>n>>m;
    ll ans=n+1;
    for(int i=1;i<=n;i++){
        ll l;cin>>l;dp[1]=i;
        for(int j=1;j<=l;j++){
            ll u,v;
            cin>>u>>v;
            dp[v]=max(dp[v],dp[u]);//u应该是上一个世界的，如果在这个世界u被更新过的话就会产生错误答案了
        }
        if(dp[m]) ans=min(ans,i-dp[m]+1);
    }
    printf("%lld\n",ans>n?-1:ans);
    system("pause");
    return 0;
} 

下面这个是正确代码

#include <bits/stdc++.h>
using namespace std;
const int M = 2010;
int n, m, f[M], g[M];
int main() {
    scanf("%d%d", &n, &m);
    int ans = n + 1;
    for (int i = 1; i <= n; i++) {
        f[1] = i;
        int l, u, v;
        scanf("%d", &l);
        while (l--) {
            scanf("%d%d", &u, &v);
            g[v] = max(g[v], f[u]);
        }
        if (g[m]) ans = min(ans, i - g[m] + 1);
        for (int j = 1; j <= m; j++) f[j] = g[j];
    }
    printf("%d\n", ans > n ? -1 : ans);
    return 0;
}

 K-Link with Bracket Sequence I_"蔚来杯" dp

dp[i][j][k]表示在b串前i个中，a串的前j个是b串的子序列，并且左括号和右括号差为k的个数，那么答案就是dp[m][n][0],分别考虑加左括号和右括号时所需要写的方程，但是j从0开始这一点还不是很清楚，现在的理解是其作用是把边界条件补充完全 

【题解】"蔚来杯"2022牛客暑期多校训练营2_ICPC/CCPC/NOIP/NOI刷题训练题单_牛客竞赛OJ (nowcoder.com)

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const int mod=1e9+7;
int n,m,t,dp[205][205][205];
char s[205];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%s", &n, &m, s+1);
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=0;j<=min(i,n);j++)
            for(int k=0;k<=i;k++){
                if(k>0){
                    if(s[j]=='(') dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k-1])%mod;
                    else dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1])%mod;
                }
                if(s[j]==')') dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k+1])%mod;
                else dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k+1])%mod;
            }
            printf("%d\n",dp[m][n][0]);
    }
    system("pause");
    return 0;
}