loli的测试-2018.12.9

模拟赛-2018.12.9

　　这是NOIP之后第一次模拟赛...但是考的比较悲惨。

　　非常喜欢写考试总结,不知道为什么...

　　T1:https://www.luogu.org/problemnew/show/P4147

　　暴力加剪枝，跑的非常快。正解是悬线法，应该会更快一些。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <algorithm>
 5 # define R register int
 6 
 7 using namespace std;
 8 
 9 const int maxn=1003;
10 int n,m,ans;
11 int a[maxn][maxn],u[maxn][maxn];
12 char c[5];
13 
14 int main()
15 {
16     scanf("%d%d",&n,&m);
17     for (R i=1;i<=n;++i)
18         for (R j=1;j<=m;++j)
19         {
20             scanf("%s",c+1);
21             if(c[1]=='R') a[i][j]=0;
22             else a[i][j]=1;    
23             if(a[i][j])
24                 u[i][j]=u[i-1][j]+1; 
25         }
26     for (R i=1;i<=n;++i)
27         for (R j=1;j<=m;++j)
28         {
29             int s=u[i][j];
30             for (R k=j;k>=1;--k)
31             {
32                 s=min(s,u[i][k]);
33                 if(s==0) break;
34                 if(s*j<=ans) break;
35                 ans=max(ans,(j-k+1)*s);
36             }
37         }
38     printf("%d",ans*3);
39     return 0;
40 }

　　T2:https://www.lydsy.com/JudgeOnline/problem.php?id=2351

　　矩阵哈希，但是被卡常了，其实本机跑的还挺快的，但是一用Cena测就变慢很多，不知道为什么。后来将所有的哈希值存下来排序，再利用单调性离线做就过了。

　　因为不想写双哈希，所以想了一种比较奇妙的哈希方法，只要出题人没想到可以这样做就不会被卡了。首先对于每一行进行哈希，然后再对哈希值进行哈希，这里的精髓是变换角度的时候换一个base，几乎不可能被卡。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <algorithm>
 5 # define R register int
 6 # define ULL int
 7 
 8 using namespace std;
 9 
10 const int maxn=1002;
11 const int base1=233;
12 const int base2=97;
13 int q,m,n,at,a,b,f[maxn][maxn],st,cnt;
14 ULL hash1[maxn][maxn],hash2[maxn][maxn],po1[maxn],po2[maxn],Hash[101],s[maxn*maxn];
15 char c[maxn];
16 struct ask
17 {
18     int id,ans;
19     ULL v;
20 }A[maxn];
21 ULL get_hash (int i,int l,int r) { return hash1[i][r]-hash1[i][l]*po1[r-l]; }
22 bool cmp (ask a,ask b) { return a.v<b.v; }
23 bool cmp1 (ask a,ask b) { return a.id<b.id; }
24 
25 int main()
26 {
27     scanf("%d%d%d%d",&m,&n,&a,&b);
28     po1[0]=1;
29     for (R i=1;i<=n;++i)
30         po1[i]=po1[i-1]*base1;
31     po2[0]=1;
32     for (R i=1;i<=n;++i)
33         po2[i]=po2[i-1]*base2;
34     for (R i=1;i<=m;++i)
35     {
36         scanf("%s",c+1);
37         for (R j=1;j<=n;++j)
38         {
39             if(c[j]=='0') f[i][j]=2;
40             else f[i][j]=3; 
41             hash1[i][j]=hash1[i][j-1]*base1+f[i][j];
42         }
43     }
44     for (R i=1;i<=m;++i)
45         for (R j=b;j<=n;++j)
46             hash2[i][j]=hash2[i-1][j]*base2+get_hash(i,j-b,j);
47     for (R i=a;i<=m;++i)
48         for (R j=b;j<=n;++j)
49             s[++st]=hash2[i][j]-hash2[i-a][j]*po2[a];
50     sort(s+1,s+1+st);
51     scanf("%d",&q);
52     while(q--)
53     {
54         memset(Hash,0,sizeof(Hash));
55         for (R i=1;i<=a;++i)
56         {
57             scanf("%s",c+1);
58             for (R j=1;j<=b;++j)
59                 if(c[j]=='0') f[i][j]=2;
60                 else f[i][j]=3;
61         }
62         for (R i=1;i<=a;++i)
63             for (R j=1;j<=b;++j)
64                 Hash[i]=Hash[i]*base1+f[i][j];
65         for (R i=1;i<=a;++i)
66             Hash[i]=Hash[i-1]*base2+Hash[i];
67         A[++at].id=++cnt;
68         A[at].v=Hash[a];
69     }
70     int p=1;
71     sort(A+1,A+1+at,cmp);
72     for (R i=1;i<=at;++i)
73     {
74         while(p<=st&&s[p]<A[i].v) p++;
75         if(s[p]==A[i].v) A[i].ans=1;
76     }
77     sort(A+1,A+1+at,cmp1);
78     for (R i=1;i<=at;++i)
79         printf("%d
",A[i].ans);
80     return 0;
81 }

　　T3:https://www.lydsy.com/JudgeOnline/problem.php?id=1398

　　题意概述：最小表示法板子题；

　　...可惜我不会.考场上手推了一个不知道复杂度多少的算法,但是跑的非常快,只是读错了输出要求丢了十分,下次要认真读题.

　　说一下我自己编的做法:

　　首先将字符串复制一份拼在后面:abac->abacabac.

　　从之前的半段找到最小的字母作为开头,会发现有两个:

　　那么把这两个点都加入队列里面，下一轮接着比较，发现第一个更优，此时当前最优解只有一个了,就是最终答案.

　　但是这样做对于随机数据的确很快,对于构造的数据就变得很慢了,举个例子:aaaaa;

　　但是这个算法并没有就此而至,要巧妙的应用最优解的性质,比如说这样,当前两个解都扫描到了相同的长度，但还没有分出高下.

　　显然后面那个"可能的最优解"没有必要再保留了,因为绿色段最好也就是和蓝色段一样好(否则它就是最优解了),所以前者将来可能制造的最优解不会比后者劣,加上这个优化后跑的飞快,也许均摊证一下复杂度会变得非常科学?如果有人会证明或者Hack请私信我,谢谢~

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <algorithm>
 5 # define R register int
 6 
 7 using namespace std;
 8 
 9 const int maxn=2000006;
10 char s[maxn],t[maxn],ds[maxn];
11 int len,f,vis[maxn];
12 int q1[maxn],q2[maxn];
13 
14 void min_dic ()
15 {
16     memset(vis,0,sizeof(vis));
17     int minn=1000,beg=1;
18     int t1=0,t2=0;
19     for (R i=1;i<=len;++i)
20         minn=min(minn,(int)s[i]);
21     for (R i=1;i<=len;++i)
22         ds[i]=ds[i+len]=s[i];
23     for (R i=1;i<=len;++i)
24         if(ds[i]==minn) q1[++t1]=i;
25     for (R i=1;i<len;++i)
26     {
27         t2=0;
28         for (R j=1;j<=t1;++j)
29             if(q1[j]!=0&&vis[ q1[j] ]==0) q2[++t2]=q1[j];            
30         if(t2==1)
31         {
32             beg=q2[1];
33             break;
34         }
35         t1=0;
36         minn=1000;
37         for (R j=1;j<=t2;++j)
38             minn=min(minn,(int)ds[ q2[j]+i ]);
39         for (R j=1;j<=t2;++j)
40             if(ds[ q2[j]+i ]==minn) vis[ q2[j]+i ]=true;
41             else q2[j]=0;
42         t1=t2;
43         for (R j=1;j<=t1;++j)
44             q1[j]=q2[j];
45     }
46     for (R i=1;i<=len;++i)
47         s[i]=ds[i-1+beg];
48 }
49 
50 int main()
51 {
52     scanf("%s",s+1);
53     len=strlen(s+1);
54     min_dic();
55     for (R i=1;i<=len;++i)
56         t[i]=s[i];
57     memset(s,0,sizeof(s));
58     scanf("%s",s+1);
59     min_dic();
60     int f=0;
61     for (R i=1;i<=len;++i)
62         if(t[i]!=s[i]) f=1;
63     if(f) printf("No
");
64     else printf("Yes
"),printf("%s",s+1);
65     return 0;
66 }

　　T4:https://www.luogu.org/problemnew/show/P2860

　　题意概述:边双板子题;

　　一个小结论:缩完边双后的新图如果有$n$个叶子,那么需要再加$f(n)$条边才能变成一个大边双.

　　$$f(n)=egin {Bmatrix}0,n=1\ frac{n+1}{2},othersend{Bmatrix}$$

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <algorithm>
 5 # define R register int
 6 
 7 using namespace std;
 8 
 9 const int maxn=5002;
10 const int maxm=20004;
11 int k,n,m,h=1,firs[maxn],x,y,sta[maxn],Tp,ans,id[maxn],low[maxn],cnt,d[maxn],bp,color[maxn];
12 struct edge
13 {
14     int too,nex;
15 }g[maxm];
16 
17 void add (int x,int y)
18 {
19     g[++h].nex=firs[x];
20     g[h].too=y;
21     firs[x]=h;
22 }
23 
24 void dfs (int x,int las)
25 {
26     id[x]=low[x]=++cnt;
27     sta[++Tp]=x;
28     int j;
29     for (R i=firs[x];i;i=g[i].nex)
30     {
31         if(i==(las^1)) continue;
32         j=g[i].too;
33         if(!id[j]) dfs(j,i);
34         low[x]=min(low[x],low[j]);
35     }
36     if(id[x]==low[x])
37     {
38         color[x]=++bp;
39         while(sta[Tp]!=x)
40         {
41             color[ sta[Tp] ]=bp;
42             Tp--;
43         }
44         Tp--;
45     }
46 }
47 
48 int main()
49 {
50     scanf("%d%d",&n,&m);
51     for (R i=1;i<=m;++i)
52     {
53         scanf("%d%d",&x,&y);
54         add(x,y);
55         add(y,x);
56     }
57     for (R i=1;i<=n;++i)
58         if(!id[i]) dfs(i,-1);
59     for (R i=1;i<=n;++i)
60         for (R j=firs[i];j;j=g[j].nex)
61         {
62             k=g[j].too;
63             if(color[i]!=color[k]) d[ color[k] ]++,d[ color[i] ]++;
64         }
65     for (R i=1;i<=bp;++i)
66         if(d[i]==2) ans++;
67     if(ans==1) printf("0");
68     else printf("%d",(ans+1)/2);
69     return 0;
70 }

　　T5:https://www.luogu.org/problemnew/show/P4819

　　题意概述:有$n$个人,$m$对认识关系(单向),其中有一个人是杀手,如果问普通人,那他就会告诉你他认识的人中有没有杀手,否则就会被杀,每个人是杀手的概率相同,求最优策略下不被杀的概率.

　　显然要先缩点,然后入度为零的问一问,就没了...吗?

　　考试时这么写,挂成了25分.这道题还需要用到一点人类智慧.

　　举个例子:5 0这组数据,被杀的概率用我的做法做是1,但其实是0.8,因为如果问了四个人都不是杀手,第五个人就不用问了,推广一下,如果有一个入度为0的联通分量的大小为一,且连出去的边指向的点入度不为一,这个点就是一个可有可无的点,不过即使有很多这样的点也只能删一个,注意一下.

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # include <vector>
  5 # include <algorithm>
  6 # define R register int
  7 
  8 using namespace std;
  9 
 10 const int maxn=100005;
 11 const int maxm=300005;
 12 int k,ans,h,x,y,n,m,siz[maxn],firs[maxn],id[maxn],low[maxn],color[maxn],bp,cnt,r[maxn],sta[maxn],Tp,vis[maxn];
 13 struct edge
 14 {
 15     int too,nex;
 16 }g[maxm];
 17 struct edg
 18 {
 19     int x,y;
 20 }ed[maxm];
 21 vector <int> v[maxn];
 22 
 23 void add (int x,int y)
 24 {
 25     g[++h].too=y;
 26     g[h].nex=firs[x];
 27     firs[x]=h;
 28 }
 29 
 30 void dfs (int x)
 31 {
 32     id[x]=low[x]=++cnt;
 33     vis[x]=true;
 34     sta[++Tp]=x;
 35     int j;
 36     for (R i=firs[x];i;i=g[i].nex)
 37     {
 38         j=g[i].too;
 39         if(!id[j])
 40         {
 41             dfs(j);
 42             low[x]=min(low[x],low[j]);
 43         }
 44         else
 45         {
 46             if(vis[j]) low[x]=min(low[x],low[j]);
 47         }
 48     }
 49     if(id[x]==low[x])
 50     {
 51         color[x]=++bp;
 52         vis[x]=false;
 53         siz[bp]++;
 54         while(sta[Tp]!=x)
 55         {
 56             color[ sta[Tp] ]=bp;
 57             vis[ sta[Tp] ]=false;
 58             Tp--;
 59             siz[bp]++;
 60         }
 61         Tp--;
 62     }
 63 }
 64 
 65 bool check (int x)
 66 {
 67     if(siz[x]>1) return false;
 68     int sz=v[x].size();
 69     for (R i=0;i<sz;++i)
 70         if(r[ v[x][i] ]==1) return false;
 71     return true;
 72 }
 73 
 74 bool cmp (edg a,edg b)
 75 {
 76     if(a.x==b.x) return a.y<b.y;
 77     return a.x<b.x;
 78 }
 79 
 80 int main()
 81 {
 82     scanf("%d%d",&n,&m);
 83     for (R i=1;i<=m;++i)
 84         scanf("%d%d",&ed[i].x,&ed[i].y);
 85     sort(ed+1,ed+1+m,cmp);
 86     for (R i=1;i<=m;++i)
 87         if(ed[i].x!=ed[i-1].x||ed[i].y!=ed[i-1].y) add(ed[i].x,ed[i].y);
 88     for (R i=1;i<=n;++i)
 89         if(!id[i]) dfs(i);
 90     for (R i=1;i<=n;++i)
 91         for (R j=firs[i];j;j=g[j].nex)
 92         {
 93             k=g[j].too;
 94             if(color[i]!=color[k]) r[ color[k] ]++,v[ color[i] ].push_back(color[k]);
 95         }
 96     for (R i=1;i<=bp;++i)
 97         if(r[i]==0) ans++;
 98     for (R i=1;i<=bp;++i)
 99         if((r[i]==0)&&check(i))
100         {
101             ans--;
102             break;
103         }
104     ans=n-ans;
105     printf("%.6lf",(double)ans/n);
106     return 0;
107 }

　　今天又是被烜神仙吊着锤的一天呢,自闭了,还是要提高知识水平呀.

---shzr