# 老师没把我的程序放的文件夹里面，于是。。。。。

## T1

https://www.luogu.org/problem/show?pid=T15678

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define LL long long
6 using namespace std;
7 const LL MAXN=2*1e6;
8 const LL INF=0x7ffff;
9 const LL mod=1e9+7;
10 const LL limit=2*1e6+10;
12 {
13     char c=getchar();LL flag=1,x=0;
14     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
15     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
16 }
17 LL n,k;
18 LL a[MAXN];
19 LL js[MAXN];
20 LL x,y;
21 LL exgcd(LL a,LL b,LL &x,LL &y)
22 {
23     if(b==0)
24     {
25         x=1,y=0;return a;
26     }
27     LL r=exgcd(b,a%b,x,y)%mod;
28     LL tmp=x%mod;x=y%mod;y=tmp-(a/b)*y%mod;
29     return r%mod;
30 }
31 LL C(LL n,LL k)
32 {
33     LL r=exgcd((js[n-k]%mod*js[k]%mod)%mod,mod,x,y);
34     while(x<0)
35         x+=mod;
36     LL yy1=js[n]%mod;
37     LL xx1=x%mod;
38     LL rt=((LL)yy1*xx1)%mod;
39     return rt;
40 }
41 int main()
42 {
43 //12    freopen("cube.in","r",stdin);
44 //    freopen("cube.out","w",stdout);
46 //    for(LL i=1;i<=n;i++)
48     js[0]=1;
49     for(LL i=1;i<=limit;i++)    js[i]=((LL)js[i-1]%mod*i%mod)%mod;
50     LL ans=C(n,k)%mod;
51     printf("%lld",ans%mod);
52     return 0;
53 }
54
55 /*
56 3 2
57 1 1 0
58 //3
59
60 4 2
61 0 0 0 0 //6
62
63 5 3
64 1 0 1 0 1//10
65 //
66
67 */```

## T2

``` 1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<algorithm>
5 using namespace std;
6 const int MAXN=1e6+10;
8 {
9     char c=getchar();int flag=1,x=0;
10     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
11     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*flag;
12 }
13 int n,m,q;
14 int fa[MAXN];
15 struct node
16 {
17     int u,v,w;
18 }edge[MAXN];
19 int num=1;
20 inline void add_edge(int x,int y,int z)
21 {
22     edge[num].u=x;
23     edge[num].v=y;
24     edge[num].w=z;num++;
25 }
26 int comp(const node &a,const node &b)
27 {
28     return a.w>b.w;
29 }
30 int find(int x)
31 {
32     if(fa[x]==x)    return fa[x];
33     else return fa[x]=find(fa[x]);
34 }
35 inline void unionn(int a,int b)
36 {
37     fa[find(a)]=find(b);
38 }
39 int happen[MAXN];
40 int cnt=0;
41 inline void Kruskal()
42 {
43     sort(edge+1,edge+num,comp);
44     int tot=0;
45     for(int i=1;i<=num-1;i++)
46     {
47         if(find(edge[i].u)!=find(edge[i].v))
48         {
49             unionn(edge[i].u,edge[i].v);
50             happen[++cnt]=edge[i].w;
51             tot++;
52             if(tot==n-1)    break;
53         }
54     }
55     reverse(happen+1,happen+cnt+1);
56 }
57 int main()
58 {
60     for(int i=1;i<=n;i++)    fa[i]=i;
61     for(int i=1;i<=m;i++)
62     {
65     }
66     Kruskal();
67     for(int i=1;i<=q;i++)
68     {
70         int pos=lower_bound(happen+1,happen+cnt+1,p)-happen;
71         printf("%d\n",pos);
72     }
73     return 0;
74 }```

## T3

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define LL long long
6 using namespace std;
7 const int MAXN=1e4+10;
8 const int INF=0x7ffff;
9 const int mod1=10260817;
10 const int mod2=100007;
11 const int mod =1e9+7;
13 {
14     char c=getchar();int flag=1,x=0;
15     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
16     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;
17 }
18 int n,q;
19 char word[MAXN][51];
20 int len[MAXN];
21 int sum[MAXN];//长度>=i的单词有多少个
22 int mxlen=0;
23 int hash[MAXN*200];
24 bool pd(int now,int nowlen,int will,int need)
25 {
26     if(need-nowlen>len[will]) return 1;
27     unsigned int seed=27;
28     unsigned LL h=0;
29     for(int i=1;i<=nowlen;i++)
30         h=(h+( (seed*word[now][i])%mod2))%mod1,seed=seed*seed;
31     for(int i=len[will]-(need-nowlen)+1;i<=len[will];i++)
32         h=(h+( (seed*word[will][i])%mod2))%mod1,seed=seed*seed;
33     h=h%mod1;
34     if(hash[h]==0)
35     {
36         hash[h]=1;
37         return 0;
38     }
39     return 1;
40 }
41 int main()
42 {
43 //    freopen("word.in","r",stdin);
44 //    freopen("word.out","w",stdout);
46     for(int i=1;i<=n;i++)
47     {
48         scanf("%s",word[i]+1);
49         len[i]=strlen(word[i]+1);
50         mxlen=max(len[i],mxlen);
51         for(int j=len[i];j>=1;j--)
52         sum[j]++;
53     }
54     for(int i=1;i<=q;i++)
55     {
56         memset(hash,0,sizeof(hash));
58         for(int j=1;j<=n;j++)//枚举每个单词
59             for(int k=1;k<=min(len[j],qr-1);k++)//这个单词的长度
60                 for(int l=1;l<=n;l++)// 枚举其他的单词
61                     if(pd(j,k,l,qr)==0)
62                     {
63                     /*    for(int o=1;o<=k;o++)    cout<<word[j][o];
64                         for(int o=len[l]-(qr-k)+1;o<=len[l];o++)    cout<<word[l][o];
65                         cout<<endl;*/
66                         ans=(ans+1)%mod;
67                     }
68         printf("%d\n",ans%mod);
69     }
70     return 0;
71 }
72
73 /*
74 2 2
75 cool
76 at
77 6
78 3
79
80 //7 \n 5
81 */```

## 总结

T2没想到正解，，好失败啊。。。。

T3被卡成零分。。

GG

0 条评论

• ### TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

有一个 \(n\) 个点的树，每个点有点权（点权可能为负） ，求包含点\(1\)的最 大权连通子图（的权值和） 。 \(n \leqslant 2500\)

• ### T4701 【卜卜】树状数组模板

题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

• ### 1250 Fibonacci数列

时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义：f0=...

• ### 暑假（补）-4

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 动态规划算法的基本思想与分治法类似，也是将待求解的问题...

• ### 剑指Offer-构建乘积数组

package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

• ### PTA 7-1 畅通工程之局部最小花费问题（35 分）

7-1 畅通工程之局部最小花费问题（35 分） 某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城...

• ### DFS+记忆化搜索 -- 简单练习

题意：你要去滑雪，你想在整个场地上找到一条最长的路好让你能够滑的尽兴！那么你要找出这条路

• ### 「CodeForces - 598B」Queries on a String

字符串s（1 ≤ |s| ≤ 10 000），有m（1 ≤ m ≤ 300）次操作，每次给l,r,k，代表将r位置插入l位置前，执行k（1 ≤ k ≤ 1 00...

• ### 数码管问题（c++实现）

描述：液晶数码管用七笔阿拉数字表示的十个数字，把横和竖的一 个短划都称为一笔，即７有３笔，８有７笔等。对于十个数字一种排列，要做到  两相邻数字都可以由...

• ### 1250 Fibonacci数列

时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义：f0=...