NOIp2018集训test-9-17(pm)-白红宇

NOIp2018集训test-9-17(pm)

阅读量：5094 次

发布时间：2019-06-13

本文共 3439 字，大约阅读时间需要 11 分钟。

T1记忆(memory)

我大概是只记忆只有七秒的金鱼吧。看了下以前的代码发现真的很简单，但是考场上只打了个暴力，虽然骗了88pt。就是枚举选的是哪个串，然后vis[i]表示选了i这些位能不能猜出它，然后dp选到i这个状态的概率。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=21,M=1048577; 7 using namespace std; 8 typedef long long LL; 9 typedef double db;10 int n,len,vis[M],cnt[M];11 char S[55][21];12 db p[M],ans;13 14 template
       
        void read(T &x) {15     char ch=getchar(); T f=1; x=0;16     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();17     if(ch=='-') f=-1,ch=getchar();18     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;19 }20 21 #define ANS22 int main() {23 #ifdef ANS24     freopen("memory.in","r",stdin);25     freopen("memory.out","w",stdout);26 #endif27     read(n);28     For(i,1,n) scanf("%s",S[i]);29     len=strlen(S[1]);30     int up=(1<

View Code

正解如注释。看到n有50就不想用二进制表示n的情况，真是太蠢了。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int M=1048577; 7 using namespace std; 8 typedef long long LL; 9 typedef double db;10 int n,len,tot[M],cnt[M];11 LL no[M];12 char s[55][21];13 db f[M],ans;14 15 template
       
        void read(T &x) {16     char ch=getchar(); T f=1; x=0;17     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();18     if(ch=='-') f=-1,ch=getchar();19     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;20 }21 22 #define ANS23 int main() {24 #ifdef ANS25     freopen("memory.in","r",stdin);26     freopen("memory.out","w",stdout);27 #endif28     read(n);29     For(i,1,n) scanf("%s",s[i]);30     len=strlen(s[1]);31     int up=(1<

View Code

T2神经元(neuron)

prufer序列的水题，f[i][j]表示放了i个数进序列序列长度为j的方案数，k的答案就是序列长度为k-2的方案乘上看有多少个叶子，在剩下的点里选那么多个叶子的方案。

1 //Achen 2 #include
      
        3 #define For(i,a,b) for(int i=(a);i<=(b);i++) 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 5 #define Formylove return 0 6 const int N=107,p=1e9+7; 7 using namespace std; 8 typedef long long LL; 9 typedef double db;10 int n,d[N];11 LL f[N][N],C[N][N];12 13 template
       
        void read(T &x) {14     char ch=getchar(); T f=1; x=0;15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();16     if(ch=='-') f=-1,ch=getchar();17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;18 }19 20 LL mo(LL x) { return x>=p?x-p:x; }21 22 #define ANS23 int main() {24 #ifdef ANS25     freopen("neuron.in","r",stdin);26     freopen("neuron.out","w",stdout);27 #endif28     read(n);29     For(i,1,n) read(d[i]);30     For(i,0,n) C[i][0]=1;31     For(i,1,n) For(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;32     f[0][0]=1;33     For(x,1,n) {34         Rep(i,x,0) Rep(j,n-2,0) if(f[i][j]) {35             For(l,1,min(n-2-j,d[x]-1)) 36                 f[i+1][j+l]=mo(f[i+1][j+l]+f[i][j]*C[j+l][l]%p);37         }38     }39     For(i,1,n) {40         if(i==1) printf("%d ",n);41         else if(i==2) {42             if(i!=n) printf("%lld ",C[n][2]);43             else printf("%lld\n",C[n][2]);44         }45         else {46             LL rs=0;47             For(j,1,i) rs=mo(rs+f[j][i-2]*C[n-j][i-j]%p);48             if(i!=n) printf("%lld ",rs);49             else printf("%lld\n",rs);50         }51     }52     Formylove;53 }

View Code

T3子串(substring)

sam上维护lct的题，没看，noip后要是没退役再来写吧。

转载于:https://www.cnblogs.com/Achenchen/p/9683123.html

你可能感兴趣的文章