2015全国互测 1
计算
给定n,m
对于[1,n]不包含m作为其子串的数k
求\(\sum_k e^{k/n}\)
kmp预处理后数位dp。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 using namespace std; char s[25]; int la,lb,n,a[25],b[25]; int ch[25][10],p[25]; double f[25][25][2],bin[25]; void pre() { bin[0]=1;for(int i=1;i<=la;i++)bin[i]=bin[i-1]*10; for(int i=1;i<=la;i++) n=n*10+a[i]; p[1]=0; for(int i=0;i<=lb;i++) { if(i!=lb)ch[i][b[i+1]]=i+1; if(i)p[i+1]=ch[p[i]][b[i+1]]; for(int j=0;j<=9;j++) if(!ch[i][j])ch[i][j]=ch[p[i]][j]; } } void dp() { f[0][0][0]=1; bool flag=(lb==1&&b[1]==0); for(int i=0;i<la;i++) { if(flag&&i)f[i][0][1]++; for(int j=0;j<lb;j++) { for(int k=0;k<=9;k++) f[i+1][ch[j][k]][1]+=f[i][j][1]*exp(bin[la-i-1]*k/n); f[i+1][ch[j][a[i+1]]][0]+=f[i][j][0]*exp(bin[la-i-1]*a[i+1]/n); for(int k=0;k<a[i+1];k++) f[i+1][ch[j][k]][1]+=f[i][j][0]*exp(bin[la-i-1]*k/n); } } double ans=0; if(flag)ans++; for(int i=0;i<lb;i++) ans+=f[la][i][0]+f[la][i][1]; printf("%.3lf",ans-1); } int main() { scanf("%s",s+1); la=strlen(s+1); for(int i=1;i<=la;i++)a[i]=s[i]-'0'; scanf("%s",s+1); lb=strlen(s+1); for(int i=1;i<=lb;i++)b[i]=s[i]-'0'; pre(); dp(); return 0; } |
移动
小x有n张卡片和n个卡槽，现在第i张卡片在ai卡槽中。小x每次可以把一个在a位置的卡片移动到b位置，消耗的代价为min(|a−b|,n−|a−b|)，每张卡片可以被移动多次。小x想使得每个卡槽有且仅有一张卡片，请你告诉他最少需要的代价是多少。
环形分金币参加白书
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[1000005],C[1000005]; ll ans; int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); a[x]++; } for(int i=2;i<=n;i++) C[i]=C[i-1]+a[i]-1; sort(C+1,C+n+1); ll ans=0; int mid=C[n/2+1]; for(int i=1;i<=n;i++) ans+=abs(C[i]-mid); printf("%lld\n",ans); return 0; } |
分离
小x喜欢分数字，所以他现在想要把1到n的所有整数分为两个集合A和B，使得对于任意一个集合里的三个不同数字x,y,z，有xy≠z。问你有多少不同的方案。两个方案不同当且仅当A集合不同或B集合不同。由于答案可能很大，小x要求你将答案对M取模后输出。
证明n>=96答案是0
所以打个表。。
爆搜代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,ans; int mark[1005]; bool check() { for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++) if(mark[i]==mark[j]&&mark[j]==mark[k]) if(i*j==k)return 0; return 1; } void dfs(int x) { if(x==n+1) { ans+=check(); if(ans==m)ans=0; return; } mark[x]=0; dfs(x+1); mark[x]=1; dfs(x+1); } int main() { T=read(); while(T--) { n=read();m=read(); if(n>=20)puts("0"); else { ans=0; dfs(1); printf("%d\n",ans); } } return 0; } |
Subscribe
计数器 9787073
OI 课件=>
OI 课件=>