noip 2011

  • P1003 铺地毯
  • P1311 选择客栈
  • P1312 Mayan游戏
  • P1313 计算系数
  • P1314 聪明的质监员
  • P1315 观光公交

    P1003 铺地毯

    Pascal代码不想放.年代久远
    随便判一下就可以了

    P1311 选择客栈

    一种比较正常的方法。
    统计是统计的:对于每个客栈i,其与前面的同色调的能选的客栈的数量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include<map>
    #include<string>
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,k,p;//n:客栈个数 k:颜色,p:最低消费
    int col[200010];//客栈颜色
    int cost[200010];//咖啡店最低消费
    long long sum;//方案总数
    int f[52];//存每种颜色可以选择的客栈数
    int i,j;//循环控制变量
    int las;//上一个满足 最低消费低于P的 咖啡店 的位置
    int main()
    {
    col[0]=51;
    scanf("%d%d%d",&n,&k,&p);
    for (i=1;i<=n;i++)
    {
    scanf("%d%d",&col[i],&cost[i]);
    if (cost[i]<=p)//等于的情况也可以
    {
    for (j=las+1;j<=i;j++) f[col[j]]++;//在这之间所有可选的客栈数量+1
    las=i;
    }
    sum+=f[col[i]];//统计
    if (i==las) sum--;//去掉两个人住同一间宿舍的情况
    //cout<<f[col[i]]<<endl;
    }
    //cout<<endl;
    //for (i=0;i<=k;i++) cout<<f[i]<<endl;
    cout<<sum;
    return 0;
    }

P1312 Mayan游戏

大牛分站可过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
bool flag;
int n;
int a[7][9];
bool f[7][9];
int ans[6][4];//(1,2) -1左移 +1右移
inline void down()//下落
{
for (int i=1;i<=5;i++)
for (int j=1;j<7;j++)
if (a[i][j]==0)
{
int k=j+1;
int x=1;
while (a[i][k]==0) k++,x++;
while (k<=7)
{
a[i][k-x]=a[i][k];//一次填掉下面的几个0
a[i][k]=0;
k++;
}
}
}
inline void qu()//消去
{
down();
memset(f,0,sizeof(f));
bool f4=false;
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
{
if (a[i][j]==0) continue;
int num=1,k=j+1;//往上
while (k<=7&&a[i][k]==a[i][j]) num++,k++;
if (num>=3)
{
f4=true;
for (k=j;k<=j+num-1;k++) f[i][k]=true;
}

num=1;k=i+1;//往右
while (k<=5&&a[k][j]==a[i][j]) num++,k++;
if (num>=3)
{
f4=true;
for (k=i;k<=i+num-1;k++) f[k][j]=true;
}
}
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
if (f[i][j]) a[i][j]=0;
if (f4)qu();else
return;
}
inline bool pd()
{
for (int i=1;i<=5;i++)
if (a[i][1]!=0) return false;
return true;
}
inline void dfs(int deep)
{
if (deep>n)
{
//sc();
if (pd())//判断是否清空
{
for (int i=1;i<=n;i++)
printf("%d %d %d\n",ans[i][1]-1,ans[i][2]-1,ans[i][3]);
exit(0);
}
return;
}
int bf[7][9];
memcpy(bf,a,sizeof(a));

for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)//右移
{
if (i==5||(a[i-1][j]==0&&i!=1))//最后一列,或者左边为0的,才往左边移
{//因为输出的奇奇怪怪的要求
if (a[i][j]==a[i-1][j]) continue;//一样的就剪枝减掉
int t=a[i][j];//交换
a[i][j]=a[i-1][j];
a[i-1][j]=t;

qu();//下落+消除
ans[deep][1]=i;ans[deep][2]=j;ans[deep][3]=-1;
dfs(deep+1);
memcpy(a,bf,sizeof(bf));//还原
}
if (i==5) continue;//右移
if (a[i][j]==0) break;
if (a[i][j]==a[i+1][j]) continue;
int t=a[i][j];
a[i][j]=a[i+1][j];
a[i+1][j]=t;
qu();
ans[deep][1]=i;ans[deep][2]=j;ans[deep][3]=1;
dfs(deep+1);
memcpy(a,bf,sizeof(bf));
}
}
int main()
{
n=read();
for (int i=1;i<=5;i++)
{
int j=1;
a[i][j]=read();
while (a[i][j]!=0) a[i][++j]=read();
}
dfs(1);
printf("-1");
return 0;
}

P1313 计算系数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<set>  
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
long long h[1010][1010];
long long ksm(long long haha,long long hehe)//快速幂求haha的hehe次方
{
long long a=1;
long long b=haha;
while (hehe!=0)
{
if (hehe%2==1) a=(a*b)%10007;
b=(b*b)%10007;
hehe=hehe/2;
}
return a;
}
int main()
{
int s,a,b,k,n,m,i,j;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
for (i=1;i<=k+1;i++)//杨辉三角初始化
{
h[i][i]=1;//最后一个数赋值为1
h[i][1]=1;//第一个数赋值为1
}
for (i=2;i<=k+1;i++)//递推求杨辉三角
for (j=2;j<=i;j++)
{
h[i][j]=(h[i-1][j]+h[i-1][j-1])%10007;
}
s=h[k+1][m+1];
s=(s*(ksm(a,n)*ksm(b,m)))%10007;
cout<<s;
return 0;
}

P1314 聪明的质监员

开始每太看清楚题,然后看了下标签,于是就写了二分答案(二分w)
然后每次二分之后更新一次答案
然后S要开longlong,注意:二分的范围是0~max(w[i])+1(想一想,为什么)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,m,W,x,y,mid;
int a[200110];
int l[200110];
int r[200110];
int w[200110];//重量
int v[200110];//价值
long long v1[200110];//价值
int s[200110];//数量
long long ans,S,sum,Ans;
int main()
{
n=read();m=read();
scanf("%lld",&S);
ans=23333333333333333;
for (int i=1;i<=n;i++)
{
w[i]=read();
v[i]=read();
y=max(y,w[i]);
}
y++;
for (int i=1;i<=m;i++) l[i]=read(),r[i]=read();
x=1;
while (x<y)
{
memset(v1,0,sizeof(v1));
memset(s,0,sizeof(s));//清空
mid=(x+y)>>1;
sum=0;
for (int i=1;i<=n;i++)
{
if (w[i]>=mid)
{
s[i]=s[i-1]+1;
v1[i]=v1[i-1]+v[i];
} else
{
s[i]=s[i-1];
v1[i]=v1[i-1];
}
}//v1:记w[i]符合条件的v[i]的前缀和
for (int i=1;i<=m;i++)
{
sum+=(long long)(s[r[i]]-s[l[i]-1])*(v1[r[i]]-v1[l[i]-1]);
}//求每一段的贡献
if (sum==S)
{
ans=0;
break;
}//判掉
ans=min(ans,abs(sum-S));//更新答案
if (sum<S) y=mid; else
if (sum>S) x=mid+1;
}
printf("%lld",ans);
return 0;
}

P1315 观光公交

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s^'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=1e3+10;
const int maxm=1e4+10;
int n,m,k,ans;
int dis[maxn];
int t[maxm],a[maxm],b[maxm];
int c[maxm],tim[maxm];//c:出现次数
int last[maxm],Max,bh;
int yx[maxn];
int main()
{
n=read();m=read();k=read();
for (int i=1;i<n;i++) dis[i]=read();
for (int i=1;i<=m;i++)
{
t[i]=read();a[i]=read();b[i]=read();
//for (int j=a[i];j<b[i];j++) c[j]++;
c[b[i]]++;
last[a[i]]=max(last[a[i]],t[i]);
}
for (int i=2;i<=n;i++) c[i]+=c[i-1];//c:某一位置作为终点的人数的前缀和
tim[1]=0;
for (int i=2;i<=n;i++) tim[i]=max(tim[i-1],last[i-1])+dis[i-1];//存到达某个点的时间
for (int i=1;i<=m;i++) ans+=tim[b[i]]-t[i];
while (k--)
{
yx[n]=n;yx[n-1]=n;//yx[i]表示第i段路能影响i+1~yx[i]时刻到达的点
for (int i=n-2;i>=1;i--) if (tim[i+1]>last[i+1]) yx[i]=yx[i+1]; else yx[i]=i+1;
Max=-233;bh=0;
for (int i=1;i<n;i++)//找影响最大的那条边
if (c[yx[i]]-c[i]>Max&&dis[i]>0) {Max=c[yx[i]]-c[i];bh=i;}
dis[bh]--;
ans-=Max;
tim[1]=0;//更新
for (int i=2;i<=n;i++) tim[i]=max(tim[i-1],last[i-1])+dis[i-1];
}
cout<<ans<<endl;
return 0;
}