NOIP2014-9-6模拟赛

工资

(money/money.in/money.out)

时限1000ms 内存256MB

聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）

聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）

输入

第一行 2个数 n,m

接下来n行，每行一个数，代表Vi.

输出

最小的最大钱数。

样例输入

7 5

100

400

300

100

500

101

400

样例输出

500

样例说明

100 400//300 100//500//101//400//

“//”表示老大要去拿钱。

数据范围

20% 1<=n<=20

另 20% 1<=n<=50,Vi的和不超过1000

100% 1<=n<=100,000,m<=n,Vi<=10,000

第二题藏妹子之处（excel）

问题描述：

今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：

（1）任意两个单元格都不在同一行。

（2）任意两个单元格都不在同一列。

选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少。

答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。

输入格式：

一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。

对于30%的数据, 3 ≤ R, C ≤ 70。

输出格式:

一个整数，表示不同的选择方案数量模1000000007后的结果。

输入输出样例：

输入样例	3 3 1 20000	3 3 4 7	4 6 9 12	7 5 13 18	4000 4000 4000 14000
输出样例	6	0	264	1212	859690013

Problem 3 银河之星(galaxy.cpp/c/pas)

T1:

二分贪心

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define MAXN 100005
 6 #define ll long long
 7 using namespace std;
 8 int a[MAXN];
 9 int n,m;
10 int read(){
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if('-'==ch)f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 int check(int w){
17     int cnt=1,s=0;
18     for(int i=1;i<=n;i++){
19         if(s+a[i]>w){
20             cnt++;
21             if(cnt>m){
22                 return 0;
23             }
24             s=a[i];
25         }
26         else{
27             s+=a[i];
28         }
29     }
30     return 1;
31 }
32 int main()
33 {
34     int L=0,R=0;
35     n=read();m=read();
36     for(int i=1;i<=n;i++){
37         a[i]=read();
38         R+=a[i];
39         L=max(L,a[i]);
40     }
41     while(R-L>1){
42         int mid=((ll)R+(ll)L)/2;
43         if(check(mid)){
44             R=mid;
45         }
46         else{
47             L=mid+1;
48         }
49     }
50     if(check(L)){
51         printf("%d
",L);
52     }
53     else{
54         printf("%d
",R);
55     }
56     return 0;
57 }

Code1

T2:

数学分析,发现代价就是三个点组成的矩形的边长，枚举之后分两种情况：

1，两个点在矩形的对角线顶点，第三点到处逛~
左上-右下对角线 (x-1)*(y-1)
左下-右上对角线 (x-1)*(y-1)
2，一个点在矩形的一个顶点，其余两个点分别在其余的两条边
(x-1)(y-1)
然后矩形有4个顶点，所以是4*(x-1)(y-1)
可以证明，至少有一个点在矩形的顶点处
所以根据加法原理，有6*(x-1)(y-1)种情况，
然后矩形可以在局域里面到处跑，总共可以跑(n-x+1)*(m-y+1)处
乘起来即可

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define MOD 1000000007
 6 #define ll long long
 7 using namespace std;
 8 ll n,m,s,t;
 9 ll ans;
10 int main()
11 {
12 //    freopen("data.in","r",stdin);
13     scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
14     n--;m--;
15     if(s%2==1) s++;
16     if(t%2==1) t--;
17     if(t>(n+m)*2){
18         t=(n+m)*2;
19     }
20     for(ll i=s;i<=t;i+=2){
21         ll d=i/2;
22         for(ll j=max(1LL,d-m);j<=min(n,d-1);j++){
23             ans=(ans+(6*(j-1)*(d-j-1))%MOD*(n-j+1)%MOD*(m-(d-j)+1)%MOD)%MOD;
24         }
25     }
26     printf("%lld
",ans);
27     return 0;
28 }

Code2

T3:

一开始以点的位置为状态，用hash加搜索，结果好慢好慢啊，T了8个点

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #define MAXN 105
  7 #define MOD 1000003
  8 #define P 17
  9 #define pii pair<int,int>
 10 using namespace std;
 11 int gx[8]={0,0,1,1,1,-1,-1,-1};
 12 int gy[8]={1,-1,1,0,-1,1,0,-1};
 13 int k,n,m,x0,y0;
 14 bool b[MOD];
 15 struct Node{
 16     int s;
 17     pii p[11];
 18 };
 19 queue<Node> q;
 20 int hash(Node t){
 21     int ret=0;
 22     for(int i=0;i<k;i++){
 23         if(t.s&(1<<i)){
 24             ret=(ret+t.p[i].first*MAXN+t.p[i].second)%MOD;
 25         }
 26         ret=ret*P%MOD;
 27     }
 28     return ret;
 29 }
 30 int Abs(int x){
 31     return (x>0)?x:-x;
 32 }
 33 int bfs(){
 34     while(!q.empty()){
 35         int s=q.front().s;
 36         pii p[11];
 37         memcpy(p,q.front().p,sizeof(p));
 38         q.pop();
 39         int L=0,cnt;
 40         for(int i=0;i<k;i++){
 41             if(s&(1<<i)){
 42                 L++;
 43                 cnt=i;
 44             }
 45         }
 46         if(1==L){
 47             if(Abs(p[cnt].first-x0)%3==0&&Abs(p[cnt].second-y0)%3==0){
 48                 return 1;
 49             }
 50             continue;
 51         }
 52         int a[MAXN][MAXN]={0};
 53         for(int i=0;i<k;i++){
 54             if(s&(1<<i)){
 55                 a[p[i].first][p[i].second]=i+1;
 56             }
 57         }
 58         for(int i=0;i<k;i++){
 59             if(s&(1<<i)){
 60                 for(int d=0;d<8;d++){
 61                     int dx=p[i].first,dy=p[i].second;
 62                     for(int j=1;j<=3;j++){
 63                         dx+=gx[d];
 64                         dy+=gy[d];
 65                     }
 66                     if(1<=dx&&dx<=n&&1<=dy&&dy<=m&&!a[dx][dy]){
 67                         Node t;
 68                         t.s=s;
 69                         memcpy(t.p,p,sizeof(t.p));
 70                         t.p[i]=make_pair(dx,dy);
 71                         int h=hash(t);
 72                         if(!b[h]){
 73                             b[h]=1;
 74                             q.push(t);
 75                         }
 76                     }
 77                 }
 78             }
 79         }
 80         for(int i=0;i<k;i++){
 81             if(s&(1<<i)){
 82                 for(int d=0;d<8;d++){
 83                     int dx=p[i].first,dy=p[i].second;
 84                     dx+=gx[d];
 85                     dy+=gy[d];
 86                     if(a[dx][dy]){
 87                         int v=a[dx][dy]-1;
 88                         dx+=gx[d];
 89                         dy+=gy[d];
 90                         if(1<=dx&&dx<=n&&1<=dy&&dy<=m&&!a[dx][dy]){
 91                             Node t;
 92                             t.s=s^(1<<v);
 93                             memcpy(t.p,p,sizeof(t.p));
 94                             t.p[i]=make_pair(dx,dy);
 95                             int h=hash(t);
 96                             if(!b[h]){
 97                                 b[h]=1;
 98                                 q.push(t);
 99                             }
100                         }
101                     }
102                 }
103             }
104         }
105     }
106     return 0;
107 }
108 void solve(){
109     memset(b,0,sizeof(b));
110     while(!q.empty()) q.pop();
111     Node t;
112     t.s=(1<<k)-1;
113     for(int i=0;i<k;i++){
114         scanf("%d%d",&t.p[i].first,&t.p[i].second);
115     }
116     b[hash(t)]=1;
117     q.push(t);
118     if(bfs()){
119         printf("Yes
");
120     }
121     else{
122         printf("No
");
123     }
124 }
125 int main()
126 {
127 //    freopen("data.in","r",stdin);
128     while(~scanf("%d%d%d%d%d",&k,&n,&m,&x0,&y0)){
129         solve();
130     }
131     return 0;
132 }

Code3-1

后来发现，应当抓住问题的性质，即能否到达，而不是最短距离之类
由于坐标相差3的倍数的点可以互相移动到达，不妨认为就是一个点了，然后只会存在9种点
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
这样移动三步的情况就解决了
然后移动两步比如0+4=8 3+4=5
注意需要考虑这种情况
1 X X
X X X
X X 1
一般来说0+8=4
但是这种情况下地图只有这么小，你的0跑到8底下就超出范围了
所以不能直接计算，需要枚举处理合法的情况
然后问题迎刃而解了

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<map>
 6 #define MAXN 102
 7 #define P 11
 8 #define ll long long
 9 using namespace std;
10 map<ll,bool> mp;
11 int gx[]={0,0,-1,-1,-1,1,1,1};
12 int gy[]={-1,1,-1,0,1,-1,0,1};
13 int K,n,m,ed;
14 int G[10][10];
15 ll hash(int a[9]){
16     ll ret=0;
17     for(int i=0;i<9;i++){
18         ret=ret*P+a[i];
19     }
20     return ret;
21 }
22 int place(int x,int y){
23     return ((x-1)%3)*3+(y-1)%3;
24 }
25 void init(){
26     memset(G,-1,sizeof(G));
27     for(int i=1;i<=n;i++){
28         for(int j=1;j<=m;j++){
29             for(int k=0;k<8;k++){
30                 int x1=i+gx[k],y1=j+gy[k];
31                 int x2=x1+gx[k],y2=y1+gy[k];
32                 if(1<=x2&&x2<=n&&1<=y2&&y2<=m){
33                     int t1=place(i,j);
34                     int t2=place(x1,y1);
35                     int t3=place(x2,y2);
36                     G[place(i,j)][place(x1,y1)]=place(x2,y2);
37                 }
38             }            
39         }
40     }
41 }
42 int dfs(ll x){
43     if(x==ed){
44         return 1;
45     }
46     int b[9]={0};
47     for(int i=8;i>=0;i--){
48         b[i]=x%11;
49         x/=11;
50     }
51     for(int i=0;i<9;i++){
52         for(int j=0;j<9;j++){
53             if(b[i]&&b[j]&&G[i][j]!=-1){
54                 int d[9]={0};
55                 memcpy(d,b,sizeof(d));
56                 d[i]--;
57                 d[j]--;
58                 d[G[i][j]]++;
59                 ll h=hash(d);
60                 if(!mp[h]){
61                     mp[h]=1;
62                     if(dfs(h))
63                         return 1;
64                 }
65             }
66         }
67     }
68     return 0;
69 }
70 int main()
71 {
72 //    freopen("data.in","r",stdin);
73     int x,y;
74     while(~scanf("%d%d%d%d%d",&K,&n,&m,&x,&y)){
75         mp.clear();
76         init();
77         int b[9]={0};
78         b[place(x,y)]++;
79         ed=hash(b);
80         b[place(x,y)]--;
81         for(int i=1;i<=K;i++){
82             scanf("%d%d",&x,&y);
83             b[place(x,y)]++;
84         }
85         ll h=hash(b);
86         mp[h]=1;
87         if(dfs(h)){
88             printf("Yes
");
89         }
90         else{
91             printf("No
");
92         }
93     }
94     return 0;
95 }

Code3-2

这是一道搜索的好题，提醒我们铭记问题的性质决定求解的方法

NOIP2014-9-6模拟赛

工资

第二题 藏妹子之处（excel）

Problem 3 银河之星(galaxy.cpp/c/pas)

第二题藏妹子之处（excel）