cf

codeforces366 语文题

Posted by Cww97 on 2016-07-18

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51942191
http://codeforces.com/contest/366

A题,
(看题目看了半小时)
要去女票家,女票家有4个门,每个门有2个守卫,每个守卫可以用巧克力或者果汁去贿赂,我们肯定选一个比较便宜的,我们需要选择一个门走,,,
注意要把钱花光,把钱花光,把钱花光T_T,坑死了

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[11][11];

int main(){
int n;
while (scanf("%d",&n)==1&&n){
for (int i=1;i<=4;i++)
for (int j=1;j<=4;j++)scanf("%d",&a[i][j]);
bool ok=0;
for (int i=1;i<=4;i++){
int x = min(a[i][1],a[i][2]);
int y = min(a[i][3],a[i][4]);
if (x+y<=n){
ok=1;
printf("%d %d %d\n",i,x,n-x);
break;
}
}
if (!ok)puts("-1");
}
return 0;
}

B题
给个数列,然后隔k个取数字,起点任意(保证n整除k)
枚举起点咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<iostream>
using namespace std;
const int N=100707;
int a[N];

int main(){
int n,k;
while (scanf("%d%d",&n,&k)==2){
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
int Min=999999999,ans=0;
for (int i=1;i<=k;i++){
int sum=0;
for (int j=i;j<=n;j+=k)sum+=a[j];
if (sum<Min){Min=sum;ans=i;}
}
printf("%d\n",ans);
}
return 0;
}

C题
很多个水果,每个水果有啊a[i],b[i]要求这里写图片描述求sum(a[i])最大的结果
把式子变一下,c[i]=a[i]-k*b[i]为重量,a[i]为价值
做背包,因为c[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<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 10007;
const int INF=0x3f3f3f3f;
int a[N],b[N],c[N],f[N],g[N];

int main(){
//freopen("fuck.in","r",stdin);
int n,k;
while (scanf("%d%d",&n,&k)==2){
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i=1;i<=n;i++)scanf("%d",&b[i]);
for (int i=1;i<=n;i++)c[i] =a[i]-k*b[i];
for (int i=1;i<N;i++)f[i]=-INF;
for (int i=1;i<N;i++)g[i]=-INF;
f[0]=g[0]=0;
for (int i=1;i<=n;i++){
if (c[i]<0){
for (int j=N-1;j>=-c[i];j--)
f[j]=max(f[j],f[j+c[i]]+a[i]);
}else{
for (int j=N-1;j>= c[i];j--)
g[j]=max(g[j],g[j-c[i]]+a[i]);
}
}
int ans=-1;
for (int i=0;i<N;i++)ans=max(ans,f[i]+g[i]);
if (ans==0) ans = -1;
printf("%d\n",ans);
}
return 0;
}

D题
图上每条边有一个区间[l,r],要求找一条从1到n的路径,要求路径上的边有公共区间,求公共区间最长的。。。
r降序,l升序,排序穷举,i确定区间左边界,j枚举右边界,然后联通则出ans,并查集啊

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
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5007;
struct Edge{
int a,b,l,r;
Edge(){a=b=l=r=0;}
Edge(int x,int y,int z,int w){a=x;b=y;l=z;r=w;}
bool operator < (const Edge a)const{
return r==a.r?l<a.l:r>a.r;
}
}edges[N];
int f[N];
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}

int main(){
//freopen("fuck.in","r",stdin);
int n,m,x,y,z,w;
while (scanf("%d%d",&n,&m)==2){
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&z,&w);
edges[i] = Edge(x,y,z,w);
}
sort(edges+1,edges+m+1);
int ans=0;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++)f[j]=j;
for (int j=1;j<=m;j++){
if (edges[j].l>edges[i].l)continue;
if (edges[j].r<edges[i].l)break;
if (F(edges[j].a)!=F(edges[j].b)){
f[f[edges[j].a]]=f[edges[j].b];
}
if (F(1)==F(n)){
ans = max(ans,edges[j].r-edges[i].l+1);
break;
}
}
}
if (ans)printf("%d\n",ans);
else puts("Nice work, Dima!");
}
return 0;
}

E题
magic guitar ,没见过这么反人类的吉他
最远曼哈顿距离,看看武森的笔记吧
http://www.cppblog.com/sonicmisora/archive/2009/09/14/96143.aspx
一开始把题目看错了,以为要谈整首曲子然后问sum(复杂度)最大,
以为又是什么变态的dp题,妈的只问其中任意一步啊

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
//http://www.cppblog.com/sonicmisora/archive/2009/09/14/96143.aspx
#include<cstdio>//cww97 2016/7/18-1:02
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=~0x3f3f3f3f;
int a[11][5];

int main(){
//freopen("fuck.in","r",stdin);
int n,m,k,s,x;
while (scanf("%d%d%d%d",&n,&m,&k,&s)==4){
memset(a,INF,sizeof(a));
for (int i=0;i<n;i++)
for(int j=0;j<m;j++){
scanf("%d",&x);
a[x][0]=max(a[x][0], i+j);
a[x][1]=max(a[x][1], i-j);
a[x][2]=max(a[x][2],-i+j);
a[x][3]=max(a[x][3],-i-j);
}
int ans=0,pre,now;
scanf("%d",&pre);
for (int i=1;i<s;i++){
scanf("%d",&now);
for (int j=0;j<4;j++)
ans=max(ans,a[pre][j]+a[now][3-j]);
pre = now;
}
printf("%d\n",ans);
}
return 0;
}
这里写图片描述
这里写图片描述