2017.7.21夏令营清北学堂解题报告

预计分数:

60+30+0=90=划水

实际分数:

90+30+20=140=rank5=雷蛇鼠标

一句话总结:今天该买彩票!

T1:

题目描述

从前有一个?行?列的网格。

现在有?种颜色,第?种颜色可以涂??格,保证

Σ︀ ?? = ? * ?。

需要你对这个网格图进行着色,你必须按照从上到下,每一行内从左到右

的顺序进行着色,并且在用完一种颜色前你不能换颜色(当然颜色的使用顺序

是随意的)。

每个相邻的相同色块可以获得1分,问在给定的规则下进行着色所能获得的

最高分是多少。

多组数据。

输入输出格式

输入格式:
从文件diyiti.in中读入数据。

第一行一个整数?表示数据组数。

对于每组数据,第一行三个整数?, ?, ?表示网格的大小和颜色的数量。

之后一行?个数,第?个数表示第?种颜色可以涂的格数。

输出格式:
将答案输出到diyiti.out。

对于每组数据一个数???,表示能获得的最高分。

输入输出样例

输入样例#1:
2
3 3 4
1 2 2 4
4 2 4
1 2 2 3
输出样例#1:
5
4
说明

【样例解释】

第一组数据

1 2 2 3 3 4 4 4 4 第二组数据

1 4 4 4 2 2 3 3 对于30%的数据,1 ≤ ?, ? ≤ 10, 1 ≤ ? ≤ 2

对于60%的数据,1 ≤ ?, ? ≤ 1000, 1 ≤ ? ≤ 3

对于100%的数据,1 ≤ ?, ? ≤ 100000, 1 ≤ ? ≤ 4, ?? ≥ 1, ? ≤ 10

3

感觉这题好鬼畜,从来没有见过这种类型的题,一开始噼里啪啦的敲了90+行的暴力,

不出所料只能过30%的数据,没办法,只能留着对拍了。。。。

后来发现了一个公式:

当p%m==0的时候的方案数是:((m-1)+(p/m-1)*(m*2-1));

然后特判一下每种情况搞一搞就好了,

预计能过60%的数据,

但是最后居然得了90分,,

而且另外的十分不知道怎么丢的,,,,=.=

暴力:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=100001;
  8 const int maxn=0x7ffff;
  9 void read(int &n)
 10 {
 11     char c='+';int x=0;bool flag=0;
 12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 13     while(c>='0'&&c<='9')
 14     x=(x<<1)+(x<<3)+c-48,c=getchar();
 15     flag==1?n=-x:n=x;
 16 }
 17 int T;
 18 int n,m,colornum;
 19 int color[MAXN];
 20 int map[MAXN][6];
 21 int ans=0;
 22 int xx[5]={-1,+1,0,0};
 23 int yy[5]={0,0,-1,+1};
 24 int vis[MAXN];
 25 void dfs(int used,int bh,int coloruse,int x,int y)
 26 //  使用了的颜色   当前点的编号  当前已使用 
 27 {
 28     if(used==colornum&&coloruse==color[bh])
 29     {
 30         int now=0;
 31         for(int i=1;i<=n;i++)
 32             for(int j=1;j<=m;j++)
 33                 for(int k=0;k<4;k++)
 34                 {
 35                     int wx=i+xx[k];
 36                     int wy=j+yy[k];
 37                     if(wx>=1&&wx<=n&wy>=1&&wy<=m)
 38                         if(map[i][j]==map[wx][wy])
 39                             now++;
 40                 }
 41                     
 42         ans=max(ans,now/2);
 43         return ;
 44     }
 45     int wx,wy;
 46     if(y==m)    {    wy=1;wx=x+1;}
 47     else    {    wy=y+1;    wx=x;    }
 48     if(coloruse==color[bh])
 49     {
 50         vis[bh]=1;
 51         for(int i=1;i<=colornum;i++)
 52         {
 53             if(!vis[i])
 54             {
 55             //    vis[i]=1;
 56                 map[wx][wy]=i;
 57                 dfs(used+1,i,1,wx,wy);
 58                 map[wx][wy]=0;
 59             //    vis[i]=0;
 60             }
 61         }
 62         vis[bh]=0;
 63     }
 64     else
 65     {
 66         map[wx][wy]=bh;
 67         dfs(used,bh,coloruse+1,wx,wy);
 68         map[wx][wy]=0;
 69     }
 70         
 71 }
 72 int main()
 73 {
 74 //    freopen("diyiti.in","r",stdin);
 75 //    freopen("diyiti.out","w",stdout);
 76     //
 77     read(T);
 78     while(T--)
 79     {
 80         memset(vis,0,sizeof(vis));
 81         memset(map,0,sizeof(map));
 82         memset(color,0,sizeof(color));
 83         ans=0;
 84         read(n);read(m);read(colornum);
 85         if(n>=0)
 86         {
 87             for(int i=1;i<=colornum;i++)
 88                 read(color[i]);
 89             for(int i=1;i<=colornum;i++)
 90             {
 91             //    vis[color[i]]=1;
 92                 map[1][1]=i;
 93                 dfs(1,i,1,1,1);
 94                 map[1][1]=0;
 95                 //vis[color[i]]=0;
 96             }
 97             printf("%d\n",ans);    
 98         }
 99         else
100         {
101             int p;
102             if(colornum==n*m) 
103             {
104                 for(int i=1;i<=colornum;i++)
105                     read(p);
106                 printf("0\n");
107                 continue;
108             }
109             if(m==1) 
110             {
111                 for(int i=1;i<=colornum;i++) 
112                 {
113                     read(p);
114                     ans+=p-1;//上下两个相邻 
115                 }
116             } 
117             else if(m==2) 
118             {
119                 for(int i=1;i<=colornum;i++) 
120                 {
121                     read(p);
122                     if(p==1) 
123                         continue;// 没有相邻 
124                     else 
125                         ans+=((m-1)+(p/m-1)*(m*2-1))+p%m;
126                 }
127             } 
128             else if(m==3) 
129             {
130                 for(int i=1;i<=colornum;i++) 
131                 {
132                     read(p);
133                     if(p==1) 
134                         continue;
135                     if(p<m) 
136                         if(p%2)
137                             ans+=p-1;// 左右相邻 
138                         else
139                             ans+=p-2;
140                     else 
141                     {
142                         ans+=((m-1)+(p/m-1)*(m*2-1));
143                         int remain=p%3;
144                         if(remain!=0)
145                             ans+=(remain*2-1);
146                     }
147                 }
148             } 
149             else if(m==4) 
150             {
151                 for(int i=1;i<=colornum;i++) 
152                 {
153                     read(p);
154                     if(p==1) 
155                         continue;
156                     if(p<m) 
157                         ans+=p-1;
158                     else 
159                     {
160                         ans+=((m-1)+(p/m-1)*(m*2-1));
161                         int remain=p%4;
162                         if(remain!=0)
163                             ans+=(remain*2-1);
164                     }
165                 }
166             }
167             printf("%d\n",ans);
168         }
169     }
170     return 0;
171 }
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T,n,m,S,a[100010],p[5],ans;
 4 int main(){
 5     freopen("diyiti3.in","r",stdin);
 6     freopen("diyiti3.out","w",stdout);
 7     scanf("%d",&T);
 8     while(T--){
 9         memset(p,0,sizeof(p));
10         ans=0;
11         scanf("%d%d%d",&n,&m,&S);
12         for(int i=1;i<=S;i++){
13             scanf("%d",&a[i]);
14             p[a[i]%m]++;
15             if(a[i]>=m)ans+=(a[i]/m*(2*m-1)-m+a[i]%m+max(0,a[i]%m-1));
16             else ans+=a[i]-1;
17         }
18         if(m==3){
19             if(p[2]>p[1])ans-=(p[2]-p[1])/3;
20         }else if(m==4){
21             if(p[3]>p[1])ans-=(p[3]-p[1])/2;
22         }
23         printf("%d\n",ans);
24     }
25 }

T2:

题目描述

在纸上有一个长为?的数列,第?项值为??。

现在小A想要在这些数之间添加加号或乘号。问对于不同的2?−1种方案,

所有答案的和是多少?

由于数据范围较大,所以输出对1000000007取模的结果。

输入输出格式

输入格式:
从文件dierti.in中读入数据。

输入第一行一个整数?表示数列的长度。

之后一行?个整数,第?个整数表示数列的第?项??。

输出格式:
输出到文件dierti.out中。

?行,第?行表示第?个询问的答案对1000000007取模的结果。

输入输出样例

输入样例#1:
3
1 2 4
输出样例#1:
30
说明

对于30%的数据,1 ≤ ? ≤ 10, 1 ≤ ?? ≤ 10

对于另外30%的数据,1 ≤ ? ≤ 1000, ?? = 1

4 对于90%的数据,1 ≤ ? ≤ 1000, 1 ≤ ?? ≤ 105

对于100%的数据,1 ≤ ? ≤ 100000, 1 ≤ ?? ≤ 109

第一眼:DP,十分不可做。。

第二眼:30%的暴力好像可以搞一搞

第三眼:其余30%的数据好像可以用组合数搞一搞

第三眼:最后40%不要了,开始搞吧,

于是噼里啪啦敲完第一题的鬼畜代码(就是实现个加减法我连队列都用上了,,,,)

然后开始搞其余30%,其实这时候剩下的时间已经不多了,于是想也没想就直接暴力就组合数。

暴力敲的应该是对的,但是因为求组合数牵扯到除法而且这道题还要取mod,当时想到需要求逆元了然而这时候也就还剩十几分钟所以果断放弃

后来有大佬说全是一的情况只要把所有数的平方全加起来再加个什么东西就可以,,,,,

正解:动规,用f[i]表示第i轮的所有情况的和,然后就不会了,,,,

暴力:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=100001;
 8 const int maxn=0x7ffff;
 9 const int mod=1000000007;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     x=(x<<1)+(x<<3)+c-48,c=getchar();
16     flag==1?n=-x:n=x;
17 }
18 int n;
19 int a[MAXN];
20 int flag=0;
21 int ans;
22 int how[MAXN];
23 int num=1;
24 int tot=0;
25 void calc()
26 {
27     queue<int>q;
28     for(int i=1;i<=num;i++)
29     {
30         if(how[i]==2)
31         {
32             int now=1;
33             while(how[i]==2)
34             {
35                 now=(now*a[i])%mod;
36                 i++;
37             }
38             now=(now*a[i])%mod;
39             q.push(now);
40         }
41         else
42             q.push(a[i]);
43     }
44     while(q.size()!=0)
45     {
46         ans=(ans+q.front())%mod;
47         q.pop();
48     }
49 }
50 void dfs(int pos)
51 {
52     if(pos==n-1)
53     {    
54         tot++;
55         calc();
56         return ;
57     }
58     
59     for(int i=1;i<=2;i++)
60     {
61         how[num++]=i;
62         dfs(pos+1);
63         how[--num]=0;
64     }
65 }
66 int jc(int num)
67 {
68     if(num==0)
69         return 1;
70     else 
71         return (num*(jc(num-1)))%mod;
72 }
73 int main()
74 {
75     freopen("dierti.in","r",stdin);
76     freopen("dierti.out","w",stdout);
77     read(n);
78     for(int i=1;i<=n;i++)
79     {    read(a[i]);    if(a[i]==1)        flag++;    }
80     if(flag==n)
81     {
82         int p=jc(n-1)%mod; 
83         for(int i=1;i<=n-1;i++)// 放多少个* 
84         {
85             int hh=(p/(jc(i)*jc(n-i-1)))%mod;
86             ans=ans+((n-i)*hh)%mod;
87         }
88         printf("%d",(ans+n)%mod);
89     }
90     else
91     {
92         dfs(0);
93         printf("%d",ans%mod);    
94     }
95     return 0;
96 }
 1 #include<bits/stdc++.h>
 2 #define mod 1000000007 
 3 #define N 100010
 4 using namespace std;
 5 int T,n,i,a[N],g[N],f[N],sum,sum1;
 6 int powmod(int x,int y){
 7     int ans=1;
 8     for(;y;y>>=1,x=1ll*x*x%mod)
 9         if(y&1)ans=1ll*ans*x%mod;
10     return ans;
11 }
12 int main(){
13     scanf("%d",&n);
14     sum=0;sum1=g[0]=1;
15     for(i=1;i<=n;i++){
16         scanf("%d",&a[i]);
17         g[i]=1ll*g[i-1]*a[i]%mod;
18         f[i]=(sum+1ll*g[i]*sum1)%mod;
19         sum=(sum+f[i])%mod;
20         sum1=(sum1+1ll*powmod(2,(i-1))*powmod(g[i],mod-2))%mod;
21     }
22     printf("%d\n",f[n]);
23 }

T3

题目描述

有一个? * ?的网格图,其中每个格子都有一个数。

设??为第?行的最小值,??为第?列的最大值,我们称一个网格是好的,当

且仅当满足

max(?1, ...,??) = min(??, ...,??)

现在问最少改变多少个数可以使得这个网格是好的。

输入输出格式

输入格式:
从文件disanti.in中读入数据。

第一行一个整数?。

之后?行,每行?个数,描述这个矩阵。

输出格式:
输出到文件disanti.out中。

一个数???,表示最少需要改变的数的个数。

输入输出样例

暂无测试点
说明

对于30%的数据,1 ≤ ?, ?? ≤ 10

对于另外30%的数据,1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 3

对于90%的数据,1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 105

对于100%的数据,1 ≤ ? ≤ 1000, 1 ≤ ?? ≤ 10

这题,,是我有史以来骗的最完美的、

说一下我的思路:

当n>100时,cout<<rand();

else cout<<2;

然后,就得了20分。

为什么是2不是3呢?

我们想,对于一个n<=10的矩阵,

改一次会不会太少了?

所以

改两次!

正解:我们假设一个i是要找的答案。

那么这个i就要满足&……¥*……(&(*#@!&#(*@……¥(*&#%2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=1001;
 8 const int maxn=0x7ffff;
 9 void read(int &n)
10 {
11     char c='+';int x=0;bool flag=0;
12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')
14     x=(x<<1)+(x<<3)+c-48,c=getchar();
15     flag==1?n=-x:n=x;
16 }
17 int map[MAXN][MAXN];
18 int main()
19 {
20     freopen("disanti.in","r",stdin);
21     freopen("disanti.out","w",stdout);
22     int n;
23     read(n);
24     for(int i=1;i<=n;i++)
25         for(int j=1;j<=n;j++)
26             read(map[i][j]);
27     if(n<=10)
28     printf("2");
29     else if(n<=100&&n<=1000)
30     printf("20");
31     else
32     printf("200");
33     return 0;
34 }
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,i,x,A[1100],B[1100],C[1100000],ans,j,k,SS[1100000],TT[1100000];
 4 pair<int,int>a[1100000];
 5 int main(){
 6     scanf("%d",&n);
 7     m=n*n;
 8     ans=n*2-1;
 9     for(i=0;i<m;i++)
10         scanf("%d",&a[i].first),a[i].second=i;
11     sort(a,a+m);
12     for(i=0;i<m;i=j){
13         TT[i]=TT[i-1];
14         for(j=i;a[j].first==a[i].first&&j<m;j++){
15             x=a[j].second;
16             B[x%n]++;
17             TT[i]=max(TT[i],B[x%n]);
18         }
19         for(k=i;k<j;k++)TT[k]=TT[i];
20     }
21     memset(A,0,sizeof(A));
22     for(i=m-1;i>=0;i=j){
23         SS[i]=SS[i+1];
24         for(j=i;a[j].first==a[i].first&&j>=0;j--){
25             x=a[j].second;
26             A[x/n]++;
27             SS[i]=max(SS[i],A[x/n]);
28         }
29         for(k=i;k>j;k--)SS[k]=SS[i];
30     }
31     for(i=0;i<m;i++)
32         if(n-SS[i]+n-TT[i]<ans)ans=n-SS[i]+n-TT[i];
33     printf("%d\n",ans);
34 }

总结:

还算考的不错,但这次考试能得rank5,运气成分真的是非常的大。

T1有七八个人A掉,

T2有一个人A掉 ,五六个90分,

说明自己的提升空间还很大。

加油!

2017 noip 创造奇迹!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

3136
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

942
来自专栏聊聊技术

原 初学算法-快速排序与线性时间选择(De

3886
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

3575
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

3416
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

1112
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

3194
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

2188
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

41313
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

2075

扫码关注云+社区

领取腾讯云代金券