在9012年1月22日观【NOIP 2017】
总结:两句话
不会高级算法就搜呗
使劲搜,使劲剪
暴力整起嘛,搜索来起嘛
进入正题
听说是一道
数学竞赛原题我可要感谢您啊CCF,在学信奥的同时也可以学数竞现在我来说说要是在考场不会推公式该怎么解这道题
可以类比NOIP 2018 D1T2
这不是NOIP2017吗你类比NOIP2018干啥暴力打表
可以随机搞两个数,去找规律
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int n,m;
int a[maxn];
void init()
{
freopen("NOIP2017 D1T1.in","r",stdin);
}
void work()
{
memset(a,0,sizeof(a));
a[n]=1;a[m]=1;
for(int i=1;i<=1000;i++)
{
if(a[i])//i可以被表示
{
for(int j=1;j<=i;j++)
{
if(a[j])//在i之前的某个j也可以被表示
a[i+j]=1;//那么i+j也可以被表示
}
}
}
for(int i=n*m;i=2*n*m;i++)//见注释Ⅰ
{
printf("%d ",a[i]);
}
}
void readdata()
{
// scanf("%d%d",&n,&m);
srand(190123);//随机化种子,只是今天的日期
n=rand()%100;m=rand()%100;//可以试小一点便于观察
printf("n=%d m=%d\n\n",n,m);
}
int main()
{
// init();
readdata();
work();
return 0;
}
注释Ⅰ:为什么是nm?试出来的啊!慢慢试,
反正考场上有时间。最后可以发现在nm之后都可以被表示了,但还是太大了?于是我们慢慢的逼近;经过多次找规律可以发现答案正是n*m-n-m!(虽然有可能是错的)但是在考场上总比不交代码好吧。何况数学上有一种方法叫【归纳法】
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int n,m;
int a[maxn];
void init()
{
freopen("NOIP2017 D1T1.in","r",stdin);
}
void work()
{
memset(a,0,sizeof(a));
a[n]=1;a[m]=1;
for(int i=1;i<=1000;i++)
{
if(a[i])//i可以被表示
{
for(int j=1;j<=i;j++)
{
if(a[j])//在i之前的某个j也可以被表示
a[i+j]=1;//那么i+j也可以被表示
}
}
}
for(int i=1;i<=n*m;i++)
{
if(a[n*m-i]=='0')
{
printf("当前的i为%d;数字为%d",i,n*m-i);
break;
}
}
}
void readdata()
{
// scanf("%d%d",&n,&m);
srand(190123);//随机化种子,只是今天的日期
n=rand()%10;m=rand()%10;
printf("n=%d m=%d\n\n",n,m);
}
int main()
{
// init();
readdata();
work();
return 0;
}
NOIP 2017 D2T1
暴力得分 100
思路?
染色标记搜索
从下往上搜索(也可以从上往下)//具体见注释
坑?!
这道题坑之多,一锅炖不下1.坐标有可能不是整数------>【不用快读】
2.ans要用long long 存【正所谓十年竞赛一场空,没开long long见祖宗】
3.开方sqrt()有精度误差------>【既然开放不行,那就平方呗】
4.{YES vs Yes} {.vs }------>【一定要看清楚是Yes/Yes./No/No./YES/YES./NO/NO.】
/* NAME:EPSILON
LANG:C++
TEXT:NOIP 2017 D2T1
TIME:8:35
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int flag,T;
long long n,h,r,used[maxn];
struct EDGE
{
double x,y,z;
}edge[maxn];
bool pd(EDGE a,EDGE b)
{
long long d=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
if(d<=4*r*r) return true;//既然开方不好,那我就平方三!
else return false;
}
void dfs(int x)
{
if(flag==1)return ;//剪枝
if(edge[x].z+r>=h)//最上面的都已经打通了
{
flag=1;
return ;
}
for(int i=1;i<=n;i++)
{
if(used[i])continue;
if(pd(edge[x],edge[i])) //判断两个洞是否相连
{
used[i]=1;//这只是染色,不用回溯
dfs(i);//找下一个
}
}
}
void readdata()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
scanf("%d%d%d",&n,&h,&r);
flag=0;//注意清0
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&edge[i].x,&edge[i].y,&edge[i].z);//double型要用lf
}
for(int i=1;i<=n;i++)
if(edge[i].z<=r)//找到最下面的那个空心球
{
used[i]=1;
dfs(i);//当然是愉快的暴力啦
}
if(flag)printf("Yes\n");//注意大小写和有无标点
else printf("No\n");
}
}
void init()
{
freopen("NOIP 2017 D2T1.in","r",stdin);
}
int main()
{
//init();
readdata();
return 0;
}
/**************************************************************
Problem: 1326
User: mzg1811
Language: C++
Result: 正确
Time:40 ms
Memory:1748 kb
****************************************************************/
T1还算 比较 简单吧
还有一种并查集的做法;以后再更吧
接下来放大招了!非战斗人员请迅速撤离
NOIP 2017 D2T1
神奇剪枝暴力得分100.
正所谓天天剪,周周剪,月月剪
剪枝真的是一个很玄学的工具
来看看怎么玄学
/* NAME:EPSILON
LANG:C++
TEXT:NOIP 2017 D2T2
TIME:9:16
*/
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f;
const int maxn=15;
int used[maxn],mapp[maxn][maxn],deep[maxn];
int f[maxn][maxn][maxn];
int ans=inf;
int tot;
int n,m;
int read()
{
char ch=getchar();int x=0,f=1;
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool check()
{
for(int i=1;i<=n;i++)
{
if(!used[i])return false;
}
return true;
}
void init()
{
freopen("NOIP 2017 D2T2.in","r",stdin);
}
void dfs(int sum,int num)
{
if(num>n+1)return;
if(sum>=ans)return;
if(check())
{
ans=min(ans,sum);
return ;
}
////////////////////////神奇剪枝开始////////////////////////////
for(int u=1;u<=n;u++)//找当前节点是由那个节点扩展来的
{
if(!used[u])continue;//必须使用过 ——>就是上一个节点
for(int v=1;v<=n;v++)//z找当前节点的下一个节点
{
if(v==u)continue;
if(mapp[u][v]==inf)continue;//两个点之间无边
if(used[v])continue;//不能使用过 ——>就是下一个节点
if(f[v][deep[u]+1][num+1]<=sum+(deep[u]+1)*mapp[u][v])continue;//神奇剪枝 见注释Ⅰ
used[v]=1;
deep[v]=deep[u]+1;//维护深度信息
f[v][deep[v]][num+1]=sum+deep[v]*mapp[u][v];//神奇剪枝 见注释Ⅱ
dfs(sum+deep[v]*mapp[u][v],num+1);
used[v]=0;
}
}
}
void readdata()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)mapp[i][j]=inf;
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
mapp[v][u]=mapp[u][v]=min(mapp[u][v],w);//找两个点的最小边
}
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
memset(deep,0,sizeof(deep));
memset(f,inf,sizeof(f));
used[i]=1;
dfs(0,1);//dfs(当前的值,现在完成了几个点)
}
printf("%d",ans);
}
int main()
{
// init();
readdata();
// work();
return 0;
}
注释Ⅰ:
if(f[v][deep[u]+1][num+1]<=sum+(deep[u]+1)*mapp[u][v])continue;
f[u][deep][num]表示当前的节点,深度,已经遍历了几个点对应的sum值,所以f值一定是原来某时算过得值。如果下一个节点的f值比下一个节点所需的sum值小的话,那么就不用更新了。
因为这时也没有更新的必要了。
注释Ⅱ:
f[v][deep[v]][num+1]=sum+deep[v]*mapp[u][v];
更新f
但是!!!
为什么这样还没有A呢?我也不知道 现在正在排差,应该是存图的问题 玄学剪枝没问题
玄学剪枝95
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;
struct node{
int nxt,v,w;
} edge[maxn*10];
int n,m;
int size,head[maxn],used[maxn],ans = 2e9,tot;
int deep[maxn];
int f[20][20][20];
int read()
{
char ch=getchar();int x=0,f=1;
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool check()
{
for (int i = 1;i <= n;i++)
if(!used[i])return 0;
return 1;
}
void dfs(int sum,int num)
{
if(sum>=ans) return ;
if(check())
{
ans=min(ans,sum);
return ;
}
for (int u=1;u<=n;u++)
{
if(!used[u]) continue;
for (int i=head[u];~i;i=edge[i].nxt)
{
int v=edge[i].v;
if(used[v]) continue;
if(f[v][deep[u]+1][num+1]<=sum+(deep[u]+1)*edge[i].w)continue;
used[v]=1;
deep[v]=deep[u]+1;
f[v][deep[v]][num+1]=sum+deep[v]*edge[i].w;
dfs(sum+(deep[v])*edge[i].w,num+1);
used[v]=0;
}
}
}
void add(int u,int v,int w)
{
edge[size].v=v;
edge[size].w=w;
edge[size].nxt=head[u];
head[u]=size++;
}
int main()
{
memset(head,-1,sizeof(head));
n=read(),m=read();
for (int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w);
add(v,u,w);
}
for (int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
memset(deep,0,sizeof(deep));
memset(f,maxn,sizeof(f));
used[i]=1;
dfs(0,1);
}
printf("%d",ans);
return 0;
}