2020 Multi-University Training Contest 3

wenzhuan

发布于 2022-08-15 12:43:20

2280

发布于 2022-08-15 12:43:20

文章被收录于专栏：你会烧尽还是结冰你会烧尽还是结冰

7.28 勇于乱冲的杭电3

1004-Tokitsukaze and Multiple

题意

给定一个长度为 n 的序列 a ，可以两两间任意合并（合并为两数之和同时数组长度减一）。问最多能合并出多少个 k 的倍数（可以不操作）。

思路

求模 k 的前缀和，每次找前一个相同前缀和的位置。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e6 + 5;
int sum[maxn],pos[maxn];
int solve(){
    int n,a,q,cnt(0); sc(n); sc(q); rep(i,0,q) pos[i]=0;
    int l=0; rep(i,1,n+1){
        sc(a),sum[i]=sum[i-1]+a,sum[i]%=q;
        if(!pos[sum[i]]&&sum[i]){ pos[sum[i]]=i; continue; }
        if(!pos[sum[i]]&&!sum[i]&&!l){
            l=i; cnt++; pos[sum[i]]=i; continue;
        }
        if(pos[sum[i]]<l){ pos[sum[i]]=i; continue; }
        l=i; cnt++; pos[sum[i]]=i;
    } return pf("%d\n",cnt);
}
int main(){
    int _; sc(_); while(_--) solve();
}

1005-Little W and Contest

题意

给定能力为 1 或 2 的 n 个人，从中选择 3 个人组队，需要能力之和大于 5 。一个队需要彼此不熟（也不能有共同的熟人）。输出初始方案数。之后有 n-1 个询问，每次有两个人互相熟识，输出此时组队的所有方案数。

思路

初始状态就是 cnt[1] * C ^ {2} _ {cnt[2]}+C ^ {3} _ {cnt[2]} 。每次询问减去这两个人（u 、v）所在的组所有的组队情况：

u 组能力 2 和 v 组能力 2 的人的组队
u 组能力 1 和 v 组能力 2 的人的组队
u 组能力 2 和 v 组能力 1 的人的组队

想要每次求出也很简单，只需要每个组记录能力为 1 和 2 的人数，每次并查集后将人数合并。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int qpow(int a,int b,int mod){
    int ans=1; while(b){
        if(b&1) ans=1ll*ans*a%mod;
        b>>=1; a=1ll*a*a%mod;
    } return ans;
}
int jc[maxn],inv[maxn];
int C(int s,int x){
    if(s>x) return 0;
    return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
int vis[maxn],peo[2][maxn];
int find(int x){ 
    return vis[x]==x?x:vis[x]=find(vis[x]);
}
int solve(){
    int n,cnt[2]; sc(n); mst(cnt,0); mst(peo,0);
    rep(i,1,n+1) sc(a[i]),a[i]&=1,cnt[a[i]]++,peo[a[i]][i]++,vis[i]=i;
    int sum=1ll*cnt[1]*C(2,cnt[0])%mod+1ll*C(3,cnt[0]); if(sum>=mod) sum-=mod;
    pf("%d\n",sum); rep(i,1,n){
        int u,v; sc(u); sc(v); int c=find(u),d=find(v);
        int tt=1ll*peo[0][c]*peo[0][d]%mod*(n-peo[0][c]-peo[1][c]-peo[0][d]-peo[1][d])%mod;
        // u v 2 2
        tt+=1ll*peo[1][c]*peo[0][d]%mod*(cnt[0]-peo[0][c]-peo[0][d])%mod; if(tt>=mod) tt-=mod;
        tt+=1ll*peo[1][d]*peo[0][c]%mod*(cnt[0]-peo[0][c]-peo[0][d])%mod; if(tt>=mod) tt-=mod;
        // u v 1 2 / 2 1
        sum-=tt; if(sum<0) sum+=mod; pf("%d\n",sum);
        vis[c]=d; rep(j,0,2) peo[j][d]+=peo[j][c];
        // change
    } return 0;
}
int main(){
    jc[0]=inv[0]=1; rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod;
    inv[maxn-1]=qpow(jc[maxn-1],mod-2,mod);
    dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    int _; sc(_); while(_--) solve();
}

1006-X Number

题意

对于 1\leq i\leq 9，定义 i 类型数为数位上 i 出现次数严格多于其他数字。问 l 到 r 中有多少个 d 类型数。

思路

数位 dp 嗯搞。将数位上各数字数量情况传进去，用 mx 记录最高位不为 d 的数位数量。搜到最末时只需计算 d 此时的数量是否大于 mx 。

备注

如果单组开 dp[20][20] 没啥问题，但多组就要清空反而更慢了。直接开 dp[20][10][20] 可以直接用前面的。sort 是为了去重（ map 里可以少存点东西），具体哪一位多少个是没有影响的，只需要记录相对数量。

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
int a[20],cnt[10],d; // 位数 一般题目最大1e18
ll l,r; map<array<int,10>,ll> dp[20][10][20]; // 位数 数位 个数
ll dfs(int pos,int state,array<int,10> pre,int mx,int limit){
    // pos位数 pre之前状态 与dp数组对应 
    // state各种情况包括前导零 具体看题目 limit前一位限制 
    rep(i,0,10) pre[i]=cnt[i]; 
    sort(pre.begin(),pre.end()); // sort去重
    if(pos==-1) return cnt[d]>mx; // 计数，具体看题目
    if(!limit&&dp[pos][d][cnt[d]].count(pre)) return dp[pos][d][cnt[d]][pre];
    int last=limit?a[pos]:9;
    ll ans=0; rep(i,0,last+1){
        if(!state||i) cnt[i]++;
        ans+=dfs(pos-1,state&&!i,pre,i==d?mx:max(mx,cnt[i]),limit&&i==a[pos]);
        if(!state||i) cnt[i]--; // cnt是全局的 到下一位就要减掉
    }
    if(!limit) dp[pos][d][cnt[d]][pre]=ans;
    return ans;
}
ll slove(ll x){
    int pos=0;
    while(x){ a[pos++]=x%10; x/=10; }
    array<int,10> tmp{0};
    return dfs(pos-1,1,tmp,0,1);
}
int solve(){
    scl(l),scl(r),sc(d); mst(cnt,0); 
    ll ans=slove(r)-slove(l-1);
    return pf("%lld\n",ans);
}
int main(){
    int _; sc(_); while(_--) solve();
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

map

sort

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

map

sort

登录后参与评论

0 条评论

热度