manbetx官方网站

9,9

十二月 13th, 2018  |  manbet体育登录

预测分数:100+60+60=220

展望分数:100+60+60=220

其实分数:100+60+40=200

实在分数:100+60+40=200

除此之外武力什么都非谋面的我。。。。。

除了武力什么都非会合之自身。。。。。

T1 2017.9.17巧克力棒(chocolate)

巧克力棒(chocolate)
Time Limit:1000ms Memory Limit:64MB
题目叙述
LYK 找到了同到底巧克力棒,可是就根本巧克力棒太充分了,LYK 不能等同口吞食进。
具体地,这穷巧克力棒长为 n,它想将这到底巧克力棒折成 n 段长为 1
的巧克力棒,然后
逐步享用。
她打算每一回用同一完完全全长为 k 的巧克力棒折成稀截长吗 a 和 b 的巧克力棒,此时若
a=b,则
LYK 觉得它们就了平宗很不方便的行,并会师沾 1 点成就感。
LYK 想通晓同样到底长为 n 的巧克力棒能使它们获最好多几点成就感。
输入格式(chocolate.in)
先是实践一个数 n。
出口格式(chocolate.out)
一个屡屡表示答案。
输入样例
7
出口样例
4
数码范围
对于 20%的数据 n<=5。
对于 50%的数据 n<=20。
对于 80%的数据 n<=2000。
对于 100%的数据 n<=1000000000。
样例解释
用 7 掰成 3+4, 将 3 掰成 1+2, 将 4 掰成 2+2 得 1 点成就感,
将余下的富有 2 掰成 1+1
博 3 点成就感。总共 4 点成就感。

霎时道题可能是本次试验中自我唯一同步推了推结论的题,

opebet网址,对一个数n,能获多少成就感大家不知道,

不过我们驾驭 1+1 =
2一定是n=2的不过美好情状

那么n=4的当儿的无限优质境况就是是(2*1+1)

放手到一般意况,

对一个n,对客举办二进制拆分,能够声明这样就是是极优解。

那么具体怎么拆分呢??

起个表达就好啊

时刻复杂度O(31)

233333

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=400001; 
 8 inline void read(long long int &n)
 9 {
10     char c=getchar();n=0;bool flag=0;
11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
13 }
14 long long int pow2[80]=
15             {
16             0,
17             1,3,7,15,31,
18             63,127,255,511,1023,
19             2047,4095,8191,16383,32767,
20             65535,131071,262143,524287,1048575,
21             2097151,4194303,8388607,16777215,33554431,
22             67108863,134217727,268435455,536870911,1073741823
23             ,2147483647};
24 int main()
25 {
26     //freopen("chocolate.in","r",stdin);
27     //freopen("chocolate.out","w",stdout);
28     long long n;
29     cin>>n;
30     long long  ans=0;
31     for(int i=31;i>=1;i--)
32     {
33         if(n>=(pow2[i]+1))
34         {
35             n=n-(pow2[i]+1);
36             ans+=pow2[i];
37         }
38     }
39     printf("%lld",ans);
40     return 0;
41 }

T1 2017.9.17巧克力棒(chocolate)

巧克力棒(chocolate)
Time Limit:1000ms Memory Limit:64MB
问题叙述
LYK 找到了平等绝望巧克力棒,不过这到底巧克力棒太丰盛了,LYK 不能等同口吞食进去。
具体地,这到底巧克力棒长为 n,它想用及时穷巧克力棒折成 n 段长为 1
的巧克力棒,然后
逐步享用。
它们打算每一次将同一根长吗 k 的巧克力棒折成稀段落长为 a 和 b 的巧克力棒,此时若
a=b,则
LYK 觉得她成功了同样起非凡忙碌的行,并会博得 1 点成就感。
LYK 想知道相同完完全全长也 n 的巧克力棒能如它取最好多几触及成就感。
输入格式(chocolate.in)
首先履行一个数 n。
出口格式(chocolate.out)
一个屡屡表示答案。
输入样例
7
出口样例
4
多少范围
对于 20%的数据 n<=5。
对于 50%的数据 n<=20。
对于 80%的数据 n<=2000。
对于 100%的数据 n<=1000000000。
样例解释
用 7 掰成 3+4, 将 3 掰成 1+2, 将 4 掰成 2+2 取 1 点成就感,
将剩余的装有 2 掰成 1+1
拿到 3 点成就感。总共 4 点成就感。

立道题可能是这一次考试受到自己唯一同步推了推结论的书,

对一个数n,能获多少成就感大家无精通,

只是咱解 1+1 =
2一定是n=2的极其出色情形

那n=4的时候的出色优良情形就是是(2*1+1)

放至一般景色,

于一个n,对他展开二进制拆分,能够印证这样即便是太优解。

这具体怎么拆分呢??

从独表明就吓啊

日复杂度O(31)

233333

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=400001; 
 8 inline void read(long long int &n)
 9 {
10     char c=getchar();n=0;bool flag=0;
11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
13 }
14 long long int pow2[80]=
15             {
16             0,
17             1,3,7,15,31,
18             63,127,255,511,1023,
19             2047,4095,8191,16383,32767,
20             65535,131071,262143,524287,1048575,
21             2097151,4194303,8388607,16777215,33554431,
22             67108863,134217727,268435455,536870911,1073741823
23             ,2147483647};
24 int main()
25 {
26     //freopen("chocolate.in","r",stdin);
27     //freopen("chocolate.out","w",stdout);
28     long long n;
29     cin>>n;
30     long long  ans=0;
31     for(int i=31;i>=1;i--)
32     {
33         if(n>=(pow2[i]+1))
34         {
35             n=n-(pow2[i]+1);
36             ans+=pow2[i];
37         }
38     }
39     printf("%lld",ans);
40     return 0;
41 }

T2 2017.9.17LYK 快跑!(run)

T2 2017.9.17LYK 快跑!(run)

题目叙述

LYK 陷进了一个迷宫! 这些迷宫是网格图形状的。 LYK 一先河在(1,1)地方,
出口以(n,m)。

与此同时以此迷宫里暴发不少怪兽,若第 a 行第 b 列有一个怪兽,且这 LYK 处于第
c 行 d 列,此

常之怪兽对它们的威迫程度吗|a-c|+|b-d|。 LYK
想找到同样条路线,使得其会由(1,1)到达(n,m),且在中途对它要挟程度最小之怪兽之

威慑程度尽可能大。

理所当然假诺起源仍旧极端处来充足兽时,无论路径长什么样,胁制程度最小之怪兽始终=0。

问题叙述

LYK 陷进了一个迷宫! 这多少个迷宫是网格图形状的。 LYK 一开端以(1,1)地方,
出口在(n,m)。

又那个迷宫里暴发多怪兽,若第 a 行第 b 列有一个怪兽,且这 LYK 处于第
c 行 d 列,此

时不时是怪兽对其的威迫程度也|a-c|+|b-d|。 LYK
想找到同样长条路子,使得其可以打(1,1)到达(n,m),且当半路对它们劫持程度极其小之怪兽的

威慑程度尽可能充分。

当若是起源依旧极端处起坏兽时,无论路径长什么样,胁迫程度最小之怪兽始终=0。

输入输出格式

输入格式:

 

先是行六个数 n,m。

接通下去 n 行,每行 m 个数,若是该数为
0,则代表该职位没有怪兽,否则有怪兽。

数保证至少是一个怪兽。

输入格式(run.out)

一个累表示答案。

 

出口格式:

 

输入输出格式

输入格式:

 

第一实践四个数 n,m。

紧接下 n 行,每行 m 个数,假诺该数为
0,则意味着该职务并未怪兽,否则是怪兽。

数保证至少有一个怪兽。

输入格式(run.out)

一个再三表示答案。

 

输出格式:

 

输入输出样例

输入样例#1:

3 4
0 1 1 0
0 0 0 0
1 1 1 0

出口样例#1:

1

输入输出样例

输入样例#1:

3 4
0 1 1 0
0 0 0 0
1 1 1 0

输出样例#1:

1

说明

对于 20%的数据 n=1。

对于 40%的数据 n<=2。

对于 60%的数据 n,m<=10。

对于 80%的数据 n,m<=100。

对于 90%的数据 n,m<=1000。

于此外 10%底数码 n,m<=1000 且相当兽数量<=100。

 

一样最先之思路是拿每个点还拆起来飞大搜,

遂n^4的做法就出生了。

下一场就是最先破罐子破摔了,

左右预处理都n^4了,搜索也描绘好搜暴力吧,,,

无脑60分,,

 

正解:

反向考虑,对于一个起怪兽的点(i,j),对客方圆的触及遍历,

如此的先期处理就下降成了N^2.

接下来爆搜就吓了

 

opebet网址 1opebet网址 2

 1 nclude<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int MAXN=1001; 
 8 const int INF=0x7ffff;
 9 inline void read(int &n)
10 {
11     char c=getchar();n=0;bool flag=0;
12     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
14 }
15 int map[MAXN][MAXN];
16 int a[MAXN][MAXN];
17 int xx[5]={-1,+1,0,0};
18 int yy[5]={0,0,-1,+1};
19 int n,m;
20 int flag=0;
21 int vis[MAXN][MAXN];
22 void dfs(int nowx,int nowy,int val)
23 {
24     if(nowx==n&&nowy==m)    { flag=1;return ; }
25     for(int i=0;i<4;i++)
26     {
27         int wx=nowx+xx[i];
28         int wy=nowy+yy[i];
29         if(map[wx][wy]>=val&&a[wx][wy]==0&&wx>0&&wy>0&&wx<=n&&wy<=m&&vis[wx][wy]==0)
30         {
31             vis[wx][wy]=1;
32             dfs(wx,wy,val);
33             vis[wx][wy]=0;
34             if(flag==1)    return ;
35         }
36     }
37 }
38 bool check(int val)
39 {
40     flag=0;
41     vis[1][1]=1;
42     dfs(1,1,val) ;
43     if(flag==1)    return 1;else return 0;    
44 }
45 int main()
46 {
47     //freopen("run.in","r",stdin);
48     //freopen("run.out","w",stdout);
49     read(n);read(m);
50     for(int i=1;i<=n;i++)
51         for(int j=1;j<=m;j++)
52             read(a[i][j]);
53     for(int i=1;i<=n;i++)
54         for(int j=1;j<=m;j++)
55             map[i][j]=INF;
56     for(int i=1;i<=n;i++)
57         for(int j=1;j<=m;j++)
58             if(a[i][j])
59                 map[i][j]=INF;
60             else
61                 for(int k=1;k<=n;k++)
62                     for(int l=1;l<=m;l++)
63                         if(a[k][l])
64                             map[i][j]=min(map[i][j],abs(k-i)+abs(l-j));
65     int l=0,r=(n*m);
66     int ans=0;
67     while(l<=r)
68     {
69         int mid=(l+r)>>1;
70         if(check(mid))    l=mid+1,ans=mid;
71         else r=mid-1;
72     }
73     printf("%d",ans);
74     return 0;
75 }

60分暴力

opebet网址 3opebet网址 4

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=2001; 
 9 const int INF=0x7ffff;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
15 }
16 int xx[5]={-1,+1,0,0};
17 int yy[5]={0,0,-1,+1};
18 int n,m;
19 int a[MAXN][MAXN];
20 struct POINT
21 {
22     int x,y;
23 }point[MAXN*MAXN],p;
24 queue<POINT>q;
25 int vis[MAXN][MAXN];
26 int dis[MAXN][MAXN];
27 bool check(int val)
28 {
29     queue<POINT>q;
30     POINT p;p.x=1;p.y=1;
31     q.push(p);
32     memset(vis,0,sizeof(vis));
33     while(q.size()!=0)
34     {
35         POINT p=q.front();
36         if(p.x==n&&p.y==m)    return 1;
37         q.pop();
38         for(int i=0;i<4;i++)
39         {
40             POINT nxt;
41             nxt.x=p.x+xx[i];
42             nxt.y=p.y+yy[i];
43             if(nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m&&vis[nxt.x][nxt.y]==0&&dis[nxt.x][nxt.y]>=val&&dis[nxt.x][nxt.y]!=INF)
44             {
45                 vis[nxt.x][nxt.y]=1;
46                 q.push(nxt);
47             }
48         }
49     }
50     return 0;
51 }
52 int main()
53 {
54     read(n);read(m);
55     for(int i=1;i<=n;i++)
56         for(int j=1;j<=m;j++)
57             dis[i][j]=INF;
58     for(int i=1;i<=n;i++)
59         for(int j=1;j<=m;j++)
60         {
61             read(a[i][j]);
62             if(a[i][j])    
63             {
64                 dis[i][j]=0;
65                 p.x=i,p.y=j,q.push(p);
66             }
67         }
68     
69     while(q.size()!=0)
70     {
71         POINT p=q.front();
72         q.pop();
73         for(int i=0;i<4;i++)
74         {
75             POINT nxt;
76             nxt.x=p.x+xx[i];
77             nxt.y=p.y+yy[i];
78             if(vis[nxt.x][nxt.y]==0&&nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m)
79             {
80                 vis[nxt.x][nxt.y]=1;
81                 dis[nxt.x][nxt.y]=min(dis[nxt.x][nxt.y],dis[p.x][p.y]+1);
82                 q.push(nxt);
83             }
84         }
85     }
86     int l=0,r=(n*m);
87     int ans=0;
88     while(l<=r)
89     {
90         int mid=(l+r)>>1;
91         if(check(mid))    l=mid+1,ans=mid;
92         else r=mid-1;
93     }
94     printf("%d",ans);
95     return 0;
96 }

100分AC

 

说明

对于 20%的数据 n=1。

对于 40%的数据 n<=2。

对于 60%的数据 n,m<=10。

对于 80%的数据 n,m<=100。

对于 90%的数据 n,m<=1000。

对于其余 10%之多少 n,m<=1000 且卓殊兽数量<=100。

 

一样起先之笔触是管每个点还拆起来飞大搜,

于是乎n^4的做法即便诞生了。

然后便起来破罐子破摔了,

左右预处理都n^4了,搜索也勾勒死搜暴力吧,,,

无脑60分,,

 

正解:

反向考虑,对于一个出怪兽的触发(i,j),对客方圆的点遍历,

这么的预处理就降成了N^2.

下一场爆搜就吓了

 

opebet网址 5opebet网址 6

 1 nclude<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int MAXN=1001; 
 8 const int INF=0x7ffff;
 9 inline void read(int &n)
10 {
11     char c=getchar();n=0;bool flag=0;
12     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
14 }
15 int map[MAXN][MAXN];
16 int a[MAXN][MAXN];
17 int xx[5]={-1,+1,0,0};
18 int yy[5]={0,0,-1,+1};
19 int n,m;
20 int flag=0;
21 int vis[MAXN][MAXN];
22 void dfs(int nowx,int nowy,int val)
23 {
24     if(nowx==n&&nowy==m)    { flag=1;return ; }
25     for(int i=0;i<4;i++)
26     {
27         int wx=nowx+xx[i];
28         int wy=nowy+yy[i];
29         if(map[wx][wy]>=val&&a[wx][wy]==0&&wx>0&&wy>0&&wx<=n&&wy<=m&&vis[wx][wy]==0)
30         {
31             vis[wx][wy]=1;
32             dfs(wx,wy,val);
33             vis[wx][wy]=0;
34             if(flag==1)    return ;
35         }
36     }
37 }
38 bool check(int val)
39 {
40     flag=0;
41     vis[1][1]=1;
42     dfs(1,1,val) ;
43     if(flag==1)    return 1;else return 0;    
44 }
45 int main()
46 {
47     //freopen("run.in","r",stdin);
48     //freopen("run.out","w",stdout);
49     read(n);read(m);
50     for(int i=1;i<=n;i++)
51         for(int j=1;j<=m;j++)
52             read(a[i][j]);
53     for(int i=1;i<=n;i++)
54         for(int j=1;j<=m;j++)
55             map[i][j]=INF;
56     for(int i=1;i<=n;i++)
57         for(int j=1;j<=m;j++)
58             if(a[i][j])
59                 map[i][j]=INF;
60             else
61                 for(int k=1;k<=n;k++)
62                     for(int l=1;l<=m;l++)
63                         if(a[k][l])
64                             map[i][j]=min(map[i][j],abs(k-i)+abs(l-j));
65     int l=0,r=(n*m);
66     int ans=0;
67     while(l<=r)
68     {
69         int mid=(l+r)>>1;
70         if(check(mid))    l=mid+1,ans=mid;
71         else r=mid-1;
72     }
73     printf("%d",ans);
74     return 0;
75 }

60分暴力

opebet网址 7opebet网址 8

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=2001; 
 9 const int INF=0x7ffff;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
15 }
16 int xx[5]={-1,+1,0,0};
17 int yy[5]={0,0,-1,+1};
18 int n,m;
19 int a[MAXN][MAXN];
20 struct POINT
21 {
22     int x,y;
23 }point[MAXN*MAXN],p;
24 queue<POINT>q;
25 int vis[MAXN][MAXN];
26 int dis[MAXN][MAXN];
27 bool check(int val)
28 {
29     queue<POINT>q;
30     POINT p;p.x=1;p.y=1;
31     q.push(p);
32     memset(vis,0,sizeof(vis));
33     while(q.size()!=0)
34     {
35         POINT p=q.front();
36         if(p.x==n&&p.y==m)    return 1;
37         q.pop();
38         for(int i=0;i<4;i++)
39         {
40             POINT nxt;
41             nxt.x=p.x+xx[i];
42             nxt.y=p.y+yy[i];
43             if(nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m&&vis[nxt.x][nxt.y]==0&&dis[nxt.x][nxt.y]>=val&&dis[nxt.x][nxt.y]!=INF)
44             {
45                 vis[nxt.x][nxt.y]=1;
46                 q.push(nxt);
47             }
48         }
49     }
50     return 0;
51 }
52 int main()
53 {
54     read(n);read(m);
55     for(int i=1;i<=n;i++)
56         for(int j=1;j<=m;j++)
57             dis[i][j]=INF;
58     for(int i=1;i<=n;i++)
59         for(int j=1;j<=m;j++)
60         {
61             read(a[i][j]);
62             if(a[i][j])    
63             {
64                 dis[i][j]=0;
65                 p.x=i,p.y=j,q.push(p);
66             }
67         }
68     
69     while(q.size()!=0)
70     {
71         POINT p=q.front();
72         q.pop();
73         for(int i=0;i<4;i++)
74         {
75             POINT nxt;
76             nxt.x=p.x+xx[i];
77             nxt.y=p.y+yy[i];
78             if(vis[nxt.x][nxt.y]==0&&nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m)
79             {
80                 vis[nxt.x][nxt.y]=1;
81                 dis[nxt.x][nxt.y]=min(dis[nxt.x][nxt.y],dis[p.x][p.y]+1);
82                 q.push(nxt);
83             }
84         }
85     }
86     int l=0,r=(n*m);
87     int ans=0;
88     while(l<=r)
89     {
90         int mid=(l+r)>>1;
91         if(check(mid))    l=mid+1,ans=mid;
92         else r=mid-1;
93     }
94     printf("%d",ans);
95     return 0;
96 }

100分AC

 

T3 2017.9.17仙人掌(cactus)

T3 2017.9.17仙人掌(cactus)

问题叙述

LYK 于拼搏武大集训(THUSC)
!于是她开始探究仙人掌,它想和您一头享用其近来

研之结果。

假如以一个无向连通图中随意一条边至多属于一个简短环
(简单环之概念也每个点交多

经同次等) ,且未存自环,我们遂是图为神明掌。

LYK 觉得神仙掌仍旧绝简单了,于是它定义了属自己之菩萨掌。

概念一摆图为优良之神仙掌,
当且只当就张图是一个神仙掌且对于自由两单例外的点 i,j,

存在同样长从 i 出发到 j 的路径,且经的触及的个数为|j-i|+1 个。 给得一摆放 n
个点 m 条边且没有自环的图,LYK 想知道完美的仙人掌最多生略条边。

数据保证整治张图至少有一个上佳之神明掌。

题材叙述

LYK 以努力南开集训(THUSC)
!于是她起研商仙人掌,它想跟而共同分享她如今

商讨之结果。

假诺当一个任往连通图中随机一久边至多属于一个简单环
(简单环之概念也每个点及多

透过同破) ,且非设有自环,我们遂这么些图为神明掌。

LYK 觉得神仙掌仍旧太简单了,于是它定义了属自己之神明掌。

概念一张图也特出之仙掌,
当且仅当就张图是一个神仙掌且对于随意两独不同的点 i,j,

存同样漫长由 i 出发到 j 的门径,且通过的点的个数为|j-i|+1 只。 给一定一布置 n
个点 m 条边且没有自环的希冀,LYK 想精通好的神灵掌最多出微微条边。

数量保证整治张图至少存在一个妙的神仙掌。

输入输出格式

输入格式:

 

率先推行三只数 n,m 表示这张图的罗列和边数。

对接下 m 行,每行两独数 u,v 表示有一样条连接 u,v 的无向边。

 

出口格式:

 

一个再三表示答案

 

输入输出格式

输入格式:

 

第一实践两个数 n,m 代表即张图的罗列和边数。

紧接下 m 行,每行两单数 u,v 表示是同样长连接 u,v 的无向边。

 

输出格式:

 

一个频繁表示答案

 

输入输出样例

输入样例#1:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

出口样例#1:

4
样例解释
选择边 1-2,1-3,2-3,3-4,能组成美妙的仙人掌,且不存在其它美妙仙人掌有超过 4 条
边。

输入输出样例

输入样例#1:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例#1:

4
样例解释
选择边 1-2,1-3,2-3,3-4,能组成美妙的仙人掌,且不存在其它美妙仙人掌有超过 4 条
边。

说明

对于 20%的数据 n<=3。

对于 40%的数据 n<=5。

对于 60%的数据 n<=8。

对于 80%的数据 n<=1000。

对于 100%的数据 n<=100000 且 m<=min(200000,n*(n-1)/2)。

 

 

读题都念的自我同一脸蒙蔽

遂直接为着n<=8的场馆去矣

平昔暴力生成有的觊觎,

下一场暴力判断可行不可行。

当然以为会得60分,结果只可以了40分。。。

正解:

照某位玄学的至极佬说。

i和i+1一定假设选(贪心)

又必然如若挑选满n个点(贪心)

下一场跑一边线段覆盖就得A了(玄学)

opebet网址 9opebet网址 10

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 #include<iostream>
  7 using namespace std;
  8 const int MAXN=101; 
  9 const int INF=0x7ffff;
 10 inline void read(int &n)
 11 {
 12     char c=getchar();n=0;bool flag=0;
 13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
 14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
 15 }
 16 struct node
 17 {
 18     int u,v,w,nxt;
 19 }edge[MAXN];
 20 int head[MAXN];
 21 int num=1;
 22 inline void add_edge(int x,int y,int z)
 23 {
 24     edge[num].u=x;
 25     edge[num].v=y;
 26     edge[num].w=z;
 27     edge[num].nxt=head[x];
 28     head[x]=num++;
 29 }
 30 int n,m;
 31 int map[MAXN][MAXN];
 32 int vis[MAXN];// 每个边是否被访问 
 33 int vis2[MAXN];// 每个点是否被访问 
 34 int have[MAXN][MAXN];// 是否满足条件 
 35 int dfs2(int point ,int num)
 36 {
 37     for(int i=1;i<=n;i++)
 38         if(abs(point-i)+1==num+1)
 39             have[point][i]=1;
 40     for(int i=1;i<=n;i++)
 41         if(map[point][i]&&vis2[i]==0)
 42         {
 43             vis2[i]=1;
 44             dfs2(i,num+1);
 45             vis2[i]=0;
 46         }
 47 }
 48 int nowans;
 49 int out;
 50 int vis3[MAXN];
 51 bool flag3=0;
 52 void pd()
 53 {
 54     memset(have,0,sizeof(have));
 55     memset(map,0,sizeof(map));
 56     memset(vis2,0,sizeof(vis2));
 57     memset(vis3,0,sizeof(vis3));
 58     flag3=0;
 59     for(int i=1;i<=m;i++)
 60     {
 61         if(vis[i])
 62         {
 63             map[edge[i].u][edge[i].v]=1;
 64             map[edge[i].v][edge[i].u]=1;
 65         }
 66     }
 67     int tot=0;
 68     for(int i=1;i<=m;i++)
 69         if(vis[i])    tot++;
 70     if(tot>n)    return ;
 71     for(int i=1;i<=n;i++)
 72     {
 73         vis2[i]=1;
 74         dfs2(i,1);
 75         vis2[i]=0;
 76     }
 77         
 78     for(int i=1;i<=n;i++)
 79         for(int j=1;j<=n;j++)
 80             if(have[i][j]==0&&(i!=j))    return ;
 81     nowans=0;
 82     for(int i=1;i<=m;i++)
 83         if(vis[i])
 84             nowans++;
 85     out=max(out,nowans);
 86 }
 87 void dfs(int now)
 88 {
 89     if(now==m+1)
 90     {
 91         pd();
 92         return ;
 93     }
 94     vis[now]=1;
 95     dfs(now+1);
 96     vis[now]=0;
 97     dfs(now+1);
 98 }
 99 int main()
100 {
101 //    freopen("cactus.in","r",stdin);
102     //freopen("cactus.out","w",stdout);
103     read(n);read(m);
104     if(n==1)
105     {
106         printf("0");
107         return 0;
108     }
109     if(n<=8)
110     {
111         for(int i=1;i<=m;i++)
112         {
113             int x,y;read(x);read(y);
114             add_edge(x,y,1);
115         }
116         dfs(1);
117         printf("%d",out);    
118     }
119     else
120     {
121         printf("%d",rand()%m);
122     }
123     return 0;
124 }

40分暴力

opebet网址 11opebet网址 12

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=100001; 
 9 const int INF=0x7ffff;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
15 }
16 int n,m;
17 struct node
18 {
19     int bg,ed;
20 }point[MAXN];
21 int tot=0;
22 int comp(const node &a ,const node &b)
23 {
24     return a.ed<b.ed;
25 }
26 int main()
27 {
28     read(n);read(m);
29     for(int i=1;i<=m;i++)
30     {
31         int x,y;read(x);read(y);
32         if(x>y)    swap(x,y);
33         if(x!=y-1)    point[++tot].bg=x,point[tot].ed=y;
34     }
35     sort(point,point+tot+1,comp);
36     int cur=0;
37     int ans=0;
38     for(int i=1;i<=tot;i++)
39     {
40         if(cur<=point[i].bg)
41         {
42             cur=point[i].ed;
43             ans++;
44         }
45     }
46     printf("%d",ans+n-1);
47     return 0;
48 }

100分AC

 

总结:

今的自身比较此前确实稳重了广大,

不会晤更傻傻的夺开一个10000*10000的数组,

也不会见再次智障的在freopen里多敲一个空格。

但,因为各个原因,

自我那多少个少会想发正解

凡为先天智商太没有?

抑或以将了强力分后就抖?

也可能懒得动笔去自喜分析?

立马确是一个严峻的问题,,

那么我发展的趋向为固然分外彰着了:

以将到暴力分的功底及,拼尽全力想正解!

 

说明

对于 20%的数据 n<=3。

对于 40%的数据 n<=5。

对于 60%的数据 n<=8。

对于 80%的数据 n<=1000。

对于 100%的数据 n<=100000 且 m<=min(200000,n*(n-1)/2)。

 

 

读题都念的我同一得体蒙蔽

于是直接向着n<=8的情景去矣

直暴力生成有的希冀,

接下来暴力判断可行不可行。

当然觉得会得60分,结果只可以了40分。。。

正解:

遵照某位玄学的生佬说。

i和i+1一定要摘(贪心)

还要肯定要选拔满n个点(贪心)

下一场跑一边线段覆盖就可以A了(玄学)

opebet网址 13opebet网址 14

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 #include<iostream>
  7 using namespace std;
  8 const int MAXN=101; 
  9 const int INF=0x7ffff;
 10 inline void read(int &n)
 11 {
 12     char c=getchar();n=0;bool flag=0;
 13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
 14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
 15 }
 16 struct node
 17 {
 18     int u,v,w,nxt;
 19 }edge[MAXN];
 20 int head[MAXN];
 21 int num=1;
 22 inline void add_edge(int x,int y,int z)
 23 {
 24     edge[num].u=x;
 25     edge[num].v=y;
 26     edge[num].w=z;
 27     edge[num].nxt=head[x];
 28     head[x]=num++;
 29 }
 30 int n,m;
 31 int map[MAXN][MAXN];
 32 int vis[MAXN];// 每个边是否被访问 
 33 int vis2[MAXN];// 每个点是否被访问 
 34 int have[MAXN][MAXN];// 是否满足条件 
 35 int dfs2(int point ,int num)
 36 {
 37     for(int i=1;i<=n;i++)
 38         if(abs(point-i)+1==num+1)
 39             have[point][i]=1;
 40     for(int i=1;i<=n;i++)
 41         if(map[point][i]&&vis2[i]==0)
 42         {
 43             vis2[i]=1;
 44             dfs2(i,num+1);
 45             vis2[i]=0;
 46         }
 47 }
 48 int nowans;
 49 int out;
 50 int vis3[MAXN];
 51 bool flag3=0;
 52 void pd()
 53 {
 54     memset(have,0,sizeof(have));
 55     memset(map,0,sizeof(map));
 56     memset(vis2,0,sizeof(vis2));
 57     memset(vis3,0,sizeof(vis3));
 58     flag3=0;
 59     for(int i=1;i<=m;i++)
 60     {
 61         if(vis[i])
 62         {
 63             map[edge[i].u][edge[i].v]=1;
 64             map[edge[i].v][edge[i].u]=1;
 65         }
 66     }
 67     int tot=0;
 68     for(int i=1;i<=m;i++)
 69         if(vis[i])    tot++;
 70     if(tot>n)    return ;
 71     for(int i=1;i<=n;i++)
 72     {
 73         vis2[i]=1;
 74         dfs2(i,1);
 75         vis2[i]=0;
 76     }
 77         
 78     for(int i=1;i<=n;i++)
 79         for(int j=1;j<=n;j++)
 80             if(have[i][j]==0&&(i!=j))    return ;
 81     nowans=0;
 82     for(int i=1;i<=m;i++)
 83         if(vis[i])
 84             nowans++;
 85     out=max(out,nowans);
 86 }
 87 void dfs(int now)
 88 {
 89     if(now==m+1)
 90     {
 91         pd();
 92         return ;
 93     }
 94     vis[now]=1;
 95     dfs(now+1);
 96     vis[now]=0;
 97     dfs(now+1);
 98 }
 99 int main()
100 {
101 //    freopen("cactus.in","r",stdin);
102     //freopen("cactus.out","w",stdout);
103     read(n);read(m);
104     if(n==1)
105     {
106         printf("0");
107         return 0;
108     }
109     if(n<=8)
110     {
111         for(int i=1;i<=m;i++)
112         {
113             int x,y;read(x);read(y);
114             add_edge(x,y,1);
115         }
116         dfs(1);
117         printf("%d",out);    
118     }
119     else
120     {
121         printf("%d",rand()%m);
122     }
123     return 0;
124 }

40分暴力

opebet网址 15opebet网址 16

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=100001; 
 9 const int INF=0x7ffff;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;
15 }
16 int n,m;
17 struct node
18 {
19     int bg,ed;
20 }point[MAXN];
21 int tot=0;
22 int comp(const node &a ,const node &b)
23 {
24     return a.ed<b.ed;
25 }
26 int main()
27 {
28     read(n);read(m);
29     for(int i=1;i<=m;i++)
30     {
31         int x,y;read(x);read(y);
32         if(x>y)    swap(x,y);
33         if(x!=y-1)    point[++tot].bg=x,point[tot].ed=y;
34     }
35     sort(point,point+tot+1,comp);
36     int cur=0;
37     int ans=0;
38     for(int i=1;i<=tot;i++)
39     {
40         if(cur<=point[i].bg)
41         {
42             cur=point[i].ed;
43             ans++;
44         }
45     }
46     printf("%d",ans+n-1);
47     return 0;
48 }

100分AC

 

总结:

近来的本身比以前确实稳重了无数,

无会面重新傻傻的失开一个10000*10000的数组,

否不汇合另行智障的于freopen里多敲一个空格。

只是,因为各个原因,

自我杀少会想发正解

举凡盖先天智商太没有?

抑或因将了强力分后就抖?

也可能懒得动笔去自喜分析?

就确是一个严苛的问题,,

那么我提升的方向为便异常醒目了:

于拿到暴力分的根底及,拼尽全力想正解!

 

相关文章

Your Comments

近期评论

    功能


    网站地图xml地图