2022 Niuke winter vacation 3

Catch up with 4 It was finally completed before

Zhinai

B

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e3+10;
int a[maxn];
typedef long long ll;
ll res[maxn];


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//     for(int i=1;i<=n;i++) a[i+n]=a[i]/2;
//     n+=n;
    sort(a+1,a+n+1);
    res[0]=1;
    for(int i=1;i<=n;i++)
    {
        int t=a[i];
        for(int j=m;j>=1;j--)
            {
            if(j>=t/2)res[j]=(res[j]+res[j-t/2])%mod;
            if(j>=t)
            (res[j]+=res[j-t])%=mod;
            }
    }
    for(int i=1;i<=m;i++)printf("%lld ",res[i]);
}

C

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
const int mod=1e9+7;
typedef long long ll;
ll dp[maxn];
int res[maxn];
ll st[maxn],cnt;
ll n;
int main()
{
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d",&dp[i]);dp[0]=1;
    for(int i=1;i<=m;i++)
    {
        if(!dp[i])continue;
        int t=i*2;
        // if(t*2<=m)t=t*2;
        // else res[cnt++]=t;
        res[cnt++]=t;
        ll temp=dp[i];
        st[cnt-1]=dp[i]%mod;
        n+=dp[i];
        // n%=mod;
        while(temp--)
        for(int j=1;j<=m;j++)
        {
            if(j>=t)dp[j]=(dp[j]-dp[j-t]%mod+mod)%mod;
            if(j>=t/2) dp[j]=(dp[j]-dp[j-t/2]%mod+mod)%mod;
            // dp[j]%=mod;
        }
        // dp[i]=0;
    }
    cout<<n<<endl;
    for(int i=0;i<cnt;i++)
        while(st[i])
        printf("%d ",res[i]),st[i]--;
        // cout<<endl;
        // for(int i=1;i<cnt;i++)cout<<st[i]<<" ";
}

F

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,mod=1e9+7;
int p[maxn];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
typedef long long ll;
ll pw[maxn];
int cnt[maxn][10];
int n,m;
ll qmi(ll a,ll k)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}
int inv9;
ll ans;
ll get(int i)
{
    ll res=0;
    for(int k=9,j=i;k>=0;k--)
    {
        j+=cnt[i][k];
        res=(res+1ll*k*(pw[cnt[i][k]]-1)%mod*inv9%mod*pw[n-j+1])%mod;
    }
    return res;
}
void merge(int u)
{
    int a=find(u),b=find(u+1);
    if(a==b)return ;
    ans=(ans-get(a)-get(b))%mod;
    ans+=mod;ans%=mod;
    p[b]=a;
    for(int i=0;i<=9;i++)cnt[a][i]+=cnt[b][i];
    ans=(ans+get(a))%mod;
}
char s[maxn];
int main()
{
    int k;
    ll x;
    inv9=qmi(9,mod-2);
    scanf("%d%d%d",&n,&m,&k);
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*10%mod;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)p[i]=i,cnt[i][s[i]-'0']++,ans=(ans*10+s[i]-'0')%mod;
    vector<int>col(n+1);
    vector<set<int>> T(m+1);
    for(int i=1;i<=n;i++)scanf("%d",&col[i]),T[col[i]].insert(i);
    for(int i=1;i<n;i++)
        if(col[i]==col[i+1])merge(i);
    printf("%lld\n",ans);
    while(k--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==b)
        {
            printf("%lld\n",ans);continue;
        }
        if(T[a].size()>T[b].size())swap(T[a],T[b]);
        for(auto t:T[a])
        {
            if(T[b].count(t-1))merge(t-1);
            if(T[b].count(t+1))merge(t);
            T[b].insert(t);
        }
        T[a].clear();
        printf("%lld\n",ans);
    }
}

H

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
struct Node
{
    int p;int s[2];
}tr[maxn],a[maxn];


void rot(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;  // k=0 Express x yes y The left son ;k=1 Express x yes y Right son of 
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
//     pushup(y), pushup(x);
}
vector<int> ans;
int n;
int root_a,root_b;
int input(Node *t)
{
    int x,y;
    bool st[maxn];
    memset(st,false,sizeof(st));
    for(int i=1;i<=n;i++)
    {
       scanf("%d %d",&x,&y);
        st[x]=true;
        st[y]=true;
        t[i].s[0]=x,t[i].s[1]=y;
        if(x)t[x].p=i;
        if(y)t[y].p=i;
    }
    for(int i=1;i<=n;i++)if(!st[i])return i;
    return -1;
}
bool vis[maxn];
void splay(int root)
{
    while (!vis[tr[root].p])
    {
        ans.push_back(root);
        rot(root);
    }
    return ;
}
void dfs(int root)
{
    splay(root);
    vis[root] = true;
    if (a[root].s[0])dfs(a[root].s[0]);
    if (a[root].s[1])dfs(a[root].s[1]);
    return ;
}
int main()
{
    vis[0]=true;
    scanf("%d",&n);
    root_a=input(a);
    root_b=input(tr);
    dfs(root_a);
    printf("%d\n", ans.size());
    for (auto i : ans)printf("%d\n", i);
}

J

#include<bits/stdc++.h>
using namespace std;
int p,l,r,L,R;
int get(int x,int y)
{
    return max(0,min(y,r)-max(x,l)+1);
}
int f(int u)
{
    if(u<0) return -u/p*get(-p+1,0)+get(u%p,0);
    return u/p*get(0,p-1)+get(0,u%p);
}
int main()
{
    cin>>p>>l>>r>>L>>R;
    p=abs(p);
    if(L<=0&&R>=0)cout<<f(R)+f(L)-f(0);
    else if(L>0&&R>0)cout<<f(R)-f(L-1);
    else if(L<=0&&R<=0)cout<<f(L)-f(R+1);
    
}

K

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p,l1,r1,L,R;
const int maxn=1e9;
ll f(int l,int r)
{
    return max(0,min(r,R)-max(l,L)+1);
}
ll calc(int a,int d,int base,int len)
{
    if(d==0)return a>=l1&&a<=r1?f(base,base+len)+f(-base-len,-base):0;
    int s=a>r1?(a-r1+d-1)/d:0;
    int t=a>=l1?(a-l1)/d:-1;t=min(t,len-1);
    return f(base+s,base+t)+f(-base-t,-base-s);
}
int main()
{
   cin>>p>>l1>>r1>>L>>R;
    if(p<0)p=-p,r1=-r1,l1=-l1,swap(l1,r1);
    ll res=0;
    l1=max(0,l1);
    for(int l=1,r;l<=p;l=r+1)
    {
        r=p/(p/l);
        res+=calc(p%l,p/l,l,r-l+1);
    }
    res+=calc(p,0,p+1,maxn);
    cout<<res<<endl;
}