预计分数：100+60+60=220
实际分数：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 点成就感。
这道题可能是这次考试中我唯一一道推了推结论的题，
对于一个数n,能获得多少成就感我们不知道，
但是我们知道 1+1 = 2一定是n=2的最优情况
那么n=4的时候的最优情况就是(2*1+1)
推广到一般情况，
对于一个n，对他进行二进制拆分，可以证明这样就是最优解。
那么具体怎么拆分呢？？
打个表就好啦
时间复杂度O(31)
233333
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=;
inline void read(long long int &n)
{
char c=getchar();n=;bool flag=;
while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();n=flag==?-n:n;
}
long long int pow2[]=
{
,
,,,,,
,,,,,
,,,,,
,,,,,
,,,,,
,,,,
,};
int main()
{
//freopen("chocolate.in","r",stdin);
//freopen("chocolate.out","w",stdout);
long long n;
cin>>n;
long long ans=;
for(int i=;i>=;i--)
{
if(n>=(pow2[i]+))
{
n=n-(pow2[i]+);
ans+=pow2[i];
}
}
printf("%lld",ans);
return ;
}
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。
输入输出格式
输入格式：
第一行两个数 n,m。
接下来 n 行，每行 m 个数，如果该数为 0，则表示该位置没有怪兽，否则存在怪兽。
数据保证至少存在一个怪兽。
输入格式(run.out)
一个数表示答案。
输出格式：
输入输出样例
3 4
0 1 1 0
0 0 0 0
1 1 1 0
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.
然后爆搜就好了
nclude<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAXN=;
const int INF=0x7ffff;
inline void read(int &n)
{
char c=getchar();n=;bool flag=;
while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();n=flag==?-n:n;
}
int map[MAXN][MAXN];
int a[MAXN][MAXN];
int xx[]={-,+,,};
int yy[]={,,-,+};
int n,m;
int flag=;
int vis[MAXN][MAXN];
void dfs(int nowx,int nowy,int val)
{
if(nowx==n&&nowy==m) { flag=;return ; }
for(int i=;i<;i++)
{
int wx=nowx+xx[i];
int wy=nowy+yy[i];
if(map[wx][wy]>=val&&a[wx][wy]==&&wx>&&wy>&&wx<=n&&wy<=m&&vis[wx][wy]==)
{
vis[wx][wy]=;
dfs(wx,wy,val);
vis[wx][wy]=;
if(flag==) return ;
}
}
}
bool check(int val)
{
flag=;
vis[][]=;
dfs(,,val) ;
if(flag==) return ;else return ;
}
int main()
{
//freopen("run.in","r",stdin);
//freopen("run.out","w",stdout);
read(n);read(m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
read(a[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
map[i][j]=INF;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(a[i][j])
map[i][j]=INF;
else
for(int k=;k<=n;k++)
for(int l=;l<=m;l++)
if(a[k][l])
map[i][j]=min(map[i][j],abs(k-i)+abs(l-j));
int l=,r=(n*m);
int ans=;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid)) l=mid+,ans=mid;
else r=mid-;
}
printf("%d",ans);
return ;
}
60分暴力
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAXN=;
const int INF=0x7ffff;
inline void read(int &n)
{
char c=getchar();n=;bool flag=;
while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();n=flag==?-n:n;
}
int xx[]={-,+,,};
int yy[]={,,-,+};
int n,m;
int a[MAXN][MAXN];
struct POINT
{
int x,y;
}point[MAXN*MAXN],p;
queue<POINT>q;
int vis[MAXN][MAXN];
int dis[MAXN][MAXN];
bool check(int val)
{
queue<POINT>q;
POINT p;p.x=;p.y=;
q.push(p);
memset(vis,,sizeof(vis));
while(q.size()!=)
{
POINT p=q.front();
if(p.x==n&&p.y==m) return ;
q.pop();
for(int i=;i<;i++)
{
POINT nxt;
nxt.x=p.x+xx[i];
nxt.y=p.y+yy[i];
if(nxt.x>&&nxt.y>&&nxt.x<=n&&nxt.y<=m&&vis[nxt.x][nxt.y]==&&dis[nxt.x][nxt.y]>=val&&dis[nxt.x][nxt.y]!=INF)
{
vis[nxt.x][nxt.y]=;
q.push(nxt);
}
}
}
return ;
}
int main()
{
read(n);read(m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
dis[i][j]=INF;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
read(a[i][j]);
if(a[i][j])
{
dis[i][j]=;
p.x=i,p.y=j,q.push(p);
}
} while(q.size()!=)
{
POINT p=q.front();
q.pop();
for(int i=;i<;i++)
{
POINT nxt;
nxt.x=p.x+xx[i];
nxt.y=p.y+yy[i];
if(vis[nxt.x][nxt.y]==&&nxt.x>&&nxt.y>&&nxt.x<=n&&nxt.y<=m)
{
vis[nxt.x][nxt.y]=;
dis[nxt.x][nxt.y]=min(dis[nxt.x][nxt.y],dis[p.x][p.y]+);
q.push(nxt);
}
}
}
int l=,r=(n*m);
int ans=;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid)) l=mid+,ans=mid;
else r=mid-;
}
printf("%d",ans);
return ;
}
100分AC
T3 2017.9.17仙人掌(cactus)
题目描述
LYK 在冲刺清华集训（THUSC） ！于是它开始研究仙人掌，它想来和你一起分享它最近
研究的结果。
如果在一个无向连通图中任意一条边至多属于一个简单环 （简单环的定义为每个点至多
经过一次） ，且不存在自环，我们称这个图为仙人掌。
LYK 觉得仙人掌还是太简单了，于是它定义了属于自己的仙人掌。
定义一张图为美妙的仙人掌， 当且仅当这张图是一个仙人掌且对于任意两个不同的点 i,j，
存在一条从 i 出发到 j 的路径，且经过的点的个数为|j-i|+1 个。 给定一张 n 个点 m 条边且没有自环的图，LYK 想知道美妙的仙人掌最多有多少条边。
数据保证整张图至少存在一个美妙的仙人掌。
输入输出格式
输入格式：
第一行两个数 n,m 表示这张图的点数和边数。
接下来 m 行，每行两个数 u,v 表示存在一条连接 u,v 的无向边。
输出格式：
一个数表示答案
输入输出样例
4 6
1 2
1 3
1 4
2 3
2 4
3 4
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了(玄学)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
const int MAXN=;
const int INF=0x7ffff;
inline void read(int &n)
{
char c=getchar();n=;bool flag=;
while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();n=flag==?-n:n;
}
struct node
{
int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=;
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
edge[num].nxt=head[x];
head[x]=num++;
}
int n,m;
int map[MAXN][MAXN];
int vis[MAXN];// 每个边是否被访问
int vis2[MAXN];// 每个点是否被访问
int have[MAXN][MAXN];// 是否满足条件
int dfs2(int point ,int num)
{
for(int i=;i<=n;i++)
if(abs(point-i)+==num+)
have[point][i]=;
for(int i=;i<=n;i++)
if(map[point][i]&&vis2[i]==)
{
vis2[i]=;
dfs2(i,num+);
vis2[i]=;
}
}
int nowans;
int out;
int vis3[MAXN];
bool flag3=;
void pd()
{
memset(have,,sizeof(have));
memset(map,,sizeof(map));
memset(vis2,,sizeof(vis2));
memset(vis3,,sizeof(vis3));
flag3=;
for(int i=;i<=m;i++)
{
if(vis[i])
{
map[edge[i].u][edge[i].v]=;
map[edge[i].v][edge[i].u]=;
}
}
int tot=;
for(int i=;i<=m;i++)
if(vis[i]) tot++;
if(tot>n) return ;
for(int i=;i<=n;i++)
{
vis2[i]=;
dfs2(i,);
vis2[i]=;
} for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(have[i][j]==&&(i!=j)) return ;
nowans=;
for(int i=;i<=m;i++)
if(vis[i])
nowans++;
out=max(out,nowans);
}
void dfs(int now)
{
if(now==m+)
{
pd();
return ;
}
vis[now]=;
dfs(now+);
vis[now]=;
dfs(now+);
}
int main()
{
// freopen("cactus.in","r",stdin);
//freopen("cactus.out","w",stdout);
read(n);read(m);
if(n==)
{
printf("");
return ;
}
if(n<=)
{
for(int i=;i<=m;i++)
{
int x,y;read(x);read(y);
add_edge(x,y,);
}
dfs();
printf("%d",out);
}
else
{
printf("%d",rand()%m);
}
return ;
}
40分暴力
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAXN=;
const int INF=0x7ffff;
inline void read(int &n)
{
char c=getchar();n=;bool flag=;
while(c<''||c>'') c=='-'?flag=,c=getchar():c=getchar();
while(c>=''&&c<='') n=n*+c-,c=getchar();n=flag==?-n:n;
}
int n,m;
struct node
{
int bg,ed;
}point[MAXN];
int tot=;
int comp(const node &a ,const node &b)
{
return a.ed<b.ed;
}
int main()
{
read(n);read(m);
for(int i=;i<=m;i++)
{
int x,y;read(x);read(y);
if(x>y) swap(x,y);
if(x!=y-) point[++tot].bg=x,point[tot].ed=y;
}
sort(point,point+tot+,comp);
int cur=;
int ans=;
for(int i=;i<=tot;i++)
{
if(cur<=point[i].bg)
{
cur=point[i].ed;
ans++;
}
}
printf("%d",ans+n-);
return ;
}
100分AC
总结：
现在的我相比以前确实稳重了许多，
不会再傻傻的去开一个10000*10000的数组，
也不会再智障的在freopen里多敲一个空格。
但是，因为种种原因，
我很少能想出正解
是因为先天智商太低？
还是因为拿了暴力分之后就沾沾自喜？
亦或是懒得动笔去自喜分析？
这确实是一个严峻的问题，，
那么我前进的方向也就很明确了：
在拿到暴力分的基础上，拼尽全力想正解！