专栏首页数据结构与算法Day5上午解题报告

Day5上午解题报告

预计分数:100+40+30=170

实际假分数:0+0+0=0 CE*3

实际真分数:60+50+0=110

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

T1

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

一眼秒C(n,k)

组合数,

不过数组少开了1.。。翻车了呜呜呜~~~~(>_<)~~~~

 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;
11 inline LL read()
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);
45     n=read();k=read();
46 //    for(LL i=1;i<=n;i++)
47 //        a[i]=read();
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

没想到正解

正解其实很简单

先求最大生成树

在建最大生成树的时候记录下选择k次的最大限重

每次二分查找

考场上为了求稳光敲了暴力

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1e6+10;
 7 inline int read()
 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 {
59     n=read();m=read();q=read();
60     for(int i=1;i<=n;i++)    fa[i]=i;
61     for(int i=1;i<=m;i++)
62     {
63         int x=read(),y=read(),z=read();
64         add_edge(x,y,z);
65     }
66     Kruskal();
67     for(int i=1;i<=q;i++)
68     {
69         int p=read();
70         int pos=lower_bound(happen+1,happen+cnt+1,p)-happen;
71         printf("%d\n",pos);
72     }
73     return 0;
74 }

T3

写了30分的暴力,但是被卡T了。

 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;
12 inline int read()
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);
45     n=read(),q=read();
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));
57         int qr=read(),ans=0;
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\)

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

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

    attack
  • 1250 Fibonacci数列

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

    attack
  • 暑假(补)-4

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

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

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

    武培轩
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

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

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

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

    用户7727433
  • 「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++实现)

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

    用户2038589
  • 1250 Fibonacci数列

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

    attack

扫码关注云+社区

领取腾讯云代金券