7.28 勇于乱冲的杭电3
1004-Tokitsukaze and Multiple
题意
给定一个长度为 n 的序列 a ，可以两两间任意合并（合并为两数之和同时数组长度减一）。问最多能合并出多少个 k 的倍数（可以不操作）。
思路
求模 k 的前缀和，每次找前一个相同前缀和的位置。
代码
代码语言：javascript复制#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("%dn",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 的人数，每次并查集后将人数合并。
代码
代码语言：javascript复制#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("%dn",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("%dn",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
题意
对于 1leq ileq 9，定义 i 类型数为数位上 i 出现次数严格多于其他数字。问 l 到 r 中有多少个 d 类型数。
思路
数位 dp 嗯搞。将数位上各数字数量情况传进去，用 mx 记录最高位不为 d 的数位数量。搜到最末时只需计算 d 此时的数量是否大于 mx 。
备注
如果单组开 dp[20][20] 没啥问题，但多组就要清空反而更慢了。直接开 dp[20][10][20] 可以直接用前面的。sort 是为了去重（ map 里可以少存点东西），具体哪一位多少个是没有影响的，只需要记录相对数量。
代码
代码语言：javascript复制#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; 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("%lldn",ans);
}
int main(){
int _; sc(_); while(_--) solve();
}
