首页 > 代码库 > BestCoder Round #93 ABC
BestCoder Round #93 ABC
A:
题目大意：
将数组划分成最少的段,每段的数两两不同。
题解：直接用一个map记录一个数是否出现过,贪心的每次取最多个数就好。
B：
题目大意：
给出一个0-9组成的字符串,问能否删掉K个数字,使得最后形成的数没有前导零且能被3整除。
题解：
最后会留下N-K个数,枚举第一个数的位置,然后问题就可以转化为判断同余方程0*x+1*y+2*z = v (mod 3) 是否有解。 其中(x+y+z=K-1 && x<=a && y<=b && z<=c)
设:
x = i (mod 3)
y = j (mod 3)
z = k (mod 3)
在[0,2]范围里枚举i,j,k
然后可行的条件是：
1. i<=a , j <=b , k <=c
2. 0*i+1*j+2*k = v (mod 3)
3. i+j+k <= K-1
4. 3*( (a-i)/3+(b-j)/3+(c-k)/3 )+ i+ j + k >= K-1
代码：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <cmath>
7 #include <map>
8 using namespace std;
9
10 #define X first
11 #define Y second
12 #define N 100010
13 #define M 500010
14
15 typedef long long ll;
16 const int INF=1ll<<30;
17
18 char s[N];
19 int dp[N][3],suf[N][3];
20
21 bool Check(int a,int b,int c,int r,int n)
22 {
23 for (int i=0;i<3 && i<=a;i++)
24 {
25 for (int j=0;j<3 && j<=b;j++)
26 {
27 for (int k=0;k<3 && k<=c;k++)
28 {
29 if (i+j+k>n) continue;
30 if ((j+k*2)%3!=r) continue;
31 if ((n-i-j-k)%3) continue;
32 int t=(a-i)/3+(b-j)/3+(c-k)/3;
33 if (3*t>=n-i-j-k) return true;
34 }
35 }
36 }
37 return false;
38 }
39
40 int main()
41 {
42 //freopen("in.in","r",stdin);
43 //freopen("out.out","w",stdout);
44
45 int T,n,K; scanf("%d",&T);
46 while (T--)
47 {
48 scanf("%d%d",&n,&K);
49 scanf("%s",s+1);
50 K=n-K;
51 if (K==1)
52 {
53 bool flag=false;
54 for (int i=1;i<=n;i++) if ((s[i]-‘0‘)%3==0) flag=true;
55 puts(flag? "yes":"no");
56 continue;
57 }
58 suf[n+1][0]=suf[n+1][1]=suf[n+1][2]=0;
59 for (int i=n;i>=1;i--)
60 {
61 suf[i][0]=suf[i+1][0];
62 suf[i][1]=suf[i+1][1];
63 suf[i][2]=suf[i+1][2];
64 suf[i][(s[i]-‘0‘)%3]++;
65 }
66 bool flag=false;
67 for (int i=1;i<=n;i++)
68 {
69 if (s[i]==‘0‘) continue;
70 int a=suf[i+1][0],b=suf[i+1][1],c=suf[i+1][2];
71
72 int r=(s[i]-‘0‘)%3,need=r==0? 0:3-r;
73 if (Check(a,b,c,need,K-1)) flag=true;
74 }
75 puts(flag? "yes":"no");
76 }
77
78 return 0;
79 }
C：
由26个小写字母组成长度为n的字符串, 定义一次变化后 字母i会变成a[i], 问一个随机的字符串 变换成自身的期望次数。
题解：
首先求出置换环, 因为总共才26个字母,置换环不同的大小最多有6种(1+2+3+4+5+6<26 1+2+3+4+5+6+7>26)。
设字母i变换fi次变成自身,fi就是它所在置换环大小。
一个串变成自身所需的次数就是串内所有字母的fi的最小公倍数。
所以可以枚举串内有哪些fi, 最多$2^6$ 种情况。
对于当前枚举的特定的fi集合S, 可以用容斥原理来计算总的次数, 即枚举哪些fi没被用上, 用二项式定理容易证明 两次枚举的复杂度一共是$3^6$
具体实现看代码：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <cmath>
7 #include <queue>
8 using namespace std;
9
10 #define X first
11 #define Y second
12 #define N 100010
13 #define M 11
14
15 typedef long long ll;
16 const int Mod=1000000007;
17 const int INF=1<<30;
18
19 char s[26];
20 int cnt[27],a[10],b[10];
21 int pw[27];
22 bool vis[26];
23
24 int Lcm(int x,int y)
25 {
26 int lcm=x*y,tmp;
27 while (y)
28 {
29 tmp=x%y;
30 x=y,y=tmp;
31 }
32
33 return lcm/x;
34 }
35
36 int Power(int x,int P)
37 {
38 if (pw[x]) return pw[x];
39 int res=1,xx=x;
40 for (;P;P>>=1)
41 {
42 if (P&1) res=1ll*res*x%Mod;
43 x=1ll*x*x%Mod;
44 }
45 return pw[xx]=res;
46 }
47
48 int Solve(int len,int n)
49 {
50 //for (int i=0;i<n;i++) cout<<i<<" "<<a[i]<<" "<<b[i]<<endl;
51 int lim=1<<n,val,cnt,m,t,res=0;
52 for (int mask1=1;mask1<lim;mask1++)
53 {
54 val=1; t=0;
55 for (int i=0;i<n;i++) if (mask1&(1<<i)) val=Lcm(val,a[i]),t+=b[i];
56 cnt=Power(t,len);
57 for (int mask2=(mask1-1)&mask1;mask2;mask2=(mask2-1)&mask1)
58 {
59 int op=1; m=t;
60 for (int j=0;j<n;j++) if (mask2&(1<<j)) op=-op,m-=b[j];
61 cnt+=op*Power(m,len); cnt%=Mod;
62 }
63
64 res+=1ll*cnt*val%Mod; res%=Mod;
65 }
66 return res<0? res+Mod:res;
67 }
68
69 int main()
70 {
71 //freopen("in.in","r",stdin);
72 //freopen("out.out","w",stdout);
73
74 int T,len; scanf("%d",&T);
75 while (T--)
76 {
77 scanf("%d%s",&len,s);
78 memset(vis,0,sizeof(vis));
79 memset(cnt,0,sizeof(cnt));
80 memset(pw,0,sizeof(pw));
81 for (int i=0;i<26;i++)
82 {
83 if (!vis[i])
84 {
85 int c=0,x=i;
86 do
87 {
88 c++;
89 x=s[x]-‘a‘;
90 vis[x]=true;
91 }while (x!=i);
92 cnt[c]+=c;
93 }
94 }
95 int n=0;
96 for (int i=1;i<=26;i++) if (cnt[i]) a[n]=i,b[n++]=cnt[i];
97 printf("%d\n",Solve(len,n));
98 }
99 return 0;
100 }
BestCoder Round #93 ABC
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。